Hallar el camino de mínimo peso total entre dos nodos de un grafo ponderado — en las variantes single-source single-destination, single-source all-destinations o all-pairs. Problema fundacional grafo-OR; algoritmos clásicos: Dijkstra, Bellman-Ford, Floyd-Warshall. El algoritmo de OR más invocado en la industria moderna.
En pocas palabras
¿Te suena?
- Somos un operador doméstico de routing de paquetería — para 5.000-50.000 paquetes/día necesitamos rutas de menor tiempo desde el depósito central a direcciones de clientes; necesitamos optimización multi-criterio sobre tiempo, distancia y combustible.
- Operamos un servicio urbano en campo con 10-50 vehículos (fontanería, electricidad, reparación de electrodomésticos, HVAC); calculamos tiempos cliente-a-cliente y queremos un motor de cálculo consciente del tráfico.
- Somos un centro municipal de gestión de tráfico; queremos un puente entre datos de congestión en tiempo real y la red cartográfica estática para ofrecer camino más corto consciente del tráfico para servicios de emergencia (ambulancia, bomberos, policía).
- Somos planificadores de red troncal de telecomunicaciones; calculamos el camino de menor latencia de reenvío de paquetes entre dos conmutadores (o dos POPs); protocolos como OSPF (Open Shortest Path First) ejecutan este cálculo por debajo.
- Somos planificadores de cadena de suministro; en una red fábrica-puerto-almacén-cliente necesitamos el coste de flujo más barato entre cada par de nodos (all-pairs shortest path) — entre opciones de transporte multimodal.
- Operamos una autopista o una empresa de transporte; para routing de largo recorrido aplicamos un camino más corto de tres criterios (combustible + peaje + horas de conducción); el grafo estático no basta, buscamos camino más corto dependiente del tiempo.
- Nuestro equipo de software empezó con una implementación directa de Dijkstra, pero las consultas en tiempo real sobre grafos grandes (1M+ nodos, red vial nacional) son demasiado lentas — evaluamos soluciones basadas en preprocesamiento (contraction hierarchies).
Por qué importa
Cómo se resuelve
Profundidad técnica
Cómo se resuelve
Profundidad técnicaEn una frase: Dado nodos (intersecciones) + aristas ponderadas (distancia/tiempo), usa Dijkstra cuando las aristas son no negativas (en cada paso elige el vecino más cercano y actualiza distancias de vecinos), Bellman-Ford cuando puede haber aristas negativas, Floyd-Warshall cuando se necesita una matriz de distancias todos-pares — cada uno garantiza el óptimo.
Este problema se estudia en la literatura de Investigación de Operaciones (disciplina que usa matemáticas e informática para resolver decisiones de negocio) como Shortest Path Problem (SPP — problema del camino más corto) — el problema grafo-OR fundacional, con 60+ años de madurez. Tres variantes principales: single-source single-destination (un punto a punto), single-source all-destinations (de una fuente a todos los destinos), all-pairs (cada par). Los algoritmos clásicos fundacionales datan de finales de los años 50 y 60: Dijkstra para grafos con aristas no negativas, Bellman-Ford para grafos con aristas negativas, Floyd-Warshall para todos-pares; las modernas contraction hierarchies basadas en preprocesamiento alcanzan tiempo de consulta sub-milisegundo en redes viarias a escala nacional. Tres etapas:
1. Modelado. Datos de entrada: (a) estructura del grafo — conjunto de nodos V (intersecciones, ubicaciones, conmutadores), conjunto de aristas E (carreteras, conexiones), pesos w(u,v) (distancia, tiempo, coste, latencia), dirigido (calle de un sentido) o no dirigido (doble sentido), pesos no negativos o posiblemente negativos, con o sin ciclos negativos, (b) tipo de consulta — punto a punto único (origen s, destino t), single-source all-destinations (origen s, destino V), all-pairs (cada par i,j), (c) dinamismo — pesos estáticos, dependientes del tiempo (tráfico variable por hora del día) o con actualizaciones en tiempo real (cortes por accidentes, meteorología), (d) multi-criterio — mono-objetivo (solo tiempo) o multi-objetivo (tiempo + distancia + combustible + peaje); multi-objetivo con caminos Pareto-óptimos o suma ponderada, (e) restricciones — prohibiciones por tipo de vía (camión no puede entrar en ciertas vías, ambulancia exenta), ventanas horarias (horario laboral), capacidad (carga a transportar). Variables de decisión: secuencia de aristas en el grafo (s → … → t), variable “en el camino o no” por arista. Objetivo: mínima suma de pesos.
2. Decisión guiada por solver. La elección del algoritmo depende del grafo y del tipo de consulta:
(a) Dijkstra — aristas no negativas, single-source. Goloso (greedy — en cada paso elegir la mejor opción local): en cada paso, extraer el nodo no visitado de menor distancia tentativa de una cola de prioridad y actualizar las distancias de sus vecinos. Binary heap O((V+E)logV), Fibonacci heap O(E + V logV). En la práctica: single-source single-destination / single-source all-destinations, grafos estáticos pequeños-medios (1K-100K nodos).
(b) Bellman-Ford — soporta aristas negativas. Relajación (revisión de cada arista para “¿hay un camino más corto ahora?”) sobre todas las aristas V-1 veces. Complejidad O(VE). Detección de ciclo negativo: si en la iteración V aún ocurre una actualización, existe un ciclo negativo y el camino más corto es indefinido. Uso: grafos con aristas negativas (arbitraje financiero, flujo inverso de red), protocolos de enrutamiento distance-vector.
(c) Floyd-Warshall — all-pairs, grafo pequeño. Programación dinámica: O(V³) tiempo, O(V²) memoria. En la práctica: V ≤ 1.000 nodos, cuando se necesita all-pairs. Soporta aristas negativas (sin ciclos).
(d) A — punto a punto guiado por heurística.* Variante dirigida al objetivo de Dijkstra; una heurística h(v) (p. ej. distancia euclídea / gran círculo) guía las prioridades de los nodos. Hart, Nilsson y Raphael (1968). En la práctica: single-source single-destination en redes viales geográficas, búsqueda de caminos en mapas de juego. Más rápido en promedio que Dijkstra; si la heurística es admisible (h ≤ distancia real), el óptimo está garantizado.
(e) Búsqueda bidireccional. Ejecutar Dijkstra/A* hacia adelante desde el origen y hacia atrás desde el destino; parar cuando las dos búsquedas se encuentran. Típicamente 2-4x más rápido que Dijkstra unidireccional.
(f) Contraction Hierarchies (Geisberger et al. 2008) — moderno basado en preprocesamiento para redes viales nacionales. El grafo se preprocesa una vez (los nodos se ‘contraen’ en orden jerárquico, añadiendo atajos); cada consulta posterior se responde en sub-milisegundo. Enfoque estándar de campo para navegación en tiempo real en redes viales nacionales (10M+ aristas). ALT (A*, Landmarks, Triangle inequality), Transit Node Routing y Hub Labels son otros métodos modernos basados en preprocesamiento.
(g) Camino más corto dependiente del tiempo — consciente del tráfico. Los pesos de las aristas son funciones del tiempo w(u,v,t); el tiempo de viaje depende de la hora de salida t. Dijkstra estático se generaliza; si la propiedad FIFO se cumple (salida posterior — no llegada anterior), el problema es polinómico. En la práctica: un motor de routing alimentado por datos de predicción de tráfico.
(h) Camino más corto estocástico. Pesos de aristas como variables aleatorias (p. ej. distribución de tráfico); camino más corto en valor esperado o ajustado al riesgo (CVaR); Polychronopoulos-Tsitsiklis (1996).
3. Integración en campo. Salida en tres capas: (a) operativa — visualización de la ruta dirección a dirección en la app móvil del conductor / ruta de reparto / app del técnico de campo, integrada con navegación, (b) planificación — la matriz de camino más corto se invoca como subrutina bajo la optimización VRP/TSP en software diario de planificación de rutas, (c) estratégica / analítica — análisis de red de cadena de suministro, informes de cuellos de botella de red de telecomunicaciones, matriz all-pairs de distancia / tiempo para soporte a la decisión. Integración upstream: ERP (direcciones de pedido), TMS (sistema de gestión de transporte), servicio de mapas (geocoding + datos de red vial), servicio de datos de tráfico (predicción en tiempo real), datos GPS de seguimiento de flota. Comité operativo trimestral: volumen de consultas de camino más corto, tiempo medio de consulta, desviación de predicción de tráfico (real vs. plan), tasa de cambio de ruta (disparadores de recálculo).
Alternativas
Manual + servicio de mapas + experiencia del conductor
GratisServicio de mapas en capa gratuita, coste de desarrollo cero
Para quién: Operación pequeña (1-10 vehículos/día), 10-50 paradas/vehículo, rutas estáticas conocidas
- + Cero inversión de software
- + Conocimiento de campo del conductor cuenta
- + Respuesta telefónica al tráfico en tiempo real
- − Sin garantía de óptimo, ruta intuitiva infla la distancia 15-30%
- − Sin cómputo multi-criterio (tiempo + combustible + peaje)
- − Sin captura de datos — el rendimiento no se mide
- − Más allá de 10 vehículos se supera la capacidad del planificador
API de servicio de mapas + integración interna
cloudPrecio por consulta; €0,003-0,01/consulta, a 50K paquetes/día son €2K-7K/mes
Para quién: Operación mediana (50-500 vehículos, 50K-500K paradas/día), consultas conscientes del tráfico
- + Datos de tráfico maduros integrados
- + Geocoding de direcciones integrado
- + API fácil de consumir, tiempo de desarrollo corto
- − Coste por consulta caro a alto volumen
- − Algoritmo es caja negra, control limitado
- − Lock-in con el proveedor (contrato del servicio de mapas)
- − No escala para consultas all-pairs / matriz grande
Motor open-source de red vial + servidores propios
Código abiertoLicencia gratis; desarrollo interno + servidores 6-12 semanas o €80K-250K consultoría + €15K-50K/año infraestructura
Para quién: Operación con equipo técnico, alto volumen de consultas (1M+/día), restricciones especializadas (prohibiciones de tipo de vía para camiones)
- + Sin coste de licencia, sin tarifa por consulta
- + Elección del algoritmo bajo control propio (Dijkstra, A*, contraction hierarchies)
- + Restricciones especializadas (acceso de camiones, exención de ambulancia) embebibles
- + Soberanía del dato dentro de la empresa
- + 30+ tesis TR (YÖK) como implementaciones de referencia
- − Datos de red vial (calidad OpenStreetMap) requieren actualizaciones periódicas
- − Datos de tráfico requieren un proveedor aparte
- − Especialista OR interno + equipo de infraestructura imprescindible
- − De prototipo académico a producción: 3-6 meses
Plataforma internacional de routing / TMS
Empresarial€300K-2M licencia + €100K-500K/año mantenimiento
Para quién: Gran operación (500+ vehículos, multi-sitio, 1M+ paradas/día), integración TMS completa
- + Módulo maduro de camino más corto + VRP integrado
- + Multi-criterio (tiempo + coste + combustible + peaje) estándar
- + Variantes dependiente del tiempo + estocástica soportadas
- + Servicio de tráfico en el paquete
- − Licencia alta + larga (12-24 meses) puesta en marcha
- − La calibración local de red vial alarga el proyecto
- − Algoritmo caja negra — control limitado de parámetros de preprocesamiento
- − Alto riesgo de lock-in con un único proveedor
Recomendación
Pregunta en la reunión
- ¿Qué enfoque usa el algoritmo de camino más corto — Dijkstra (binary heap, Fibonacci heap), A*, búsqueda bidireccional, contraction hierarchies, ALT? ¿Cuál es el tiempo medio de consulta sobre red vial nacional (10M+ aristas)?
- ¿Soporta aristas negativas (Bellman-Ford)? ¿Hay detección de ciclos negativos? ¿En qué escenarios (arbitraje financiero, flujo inverso) se recurre a Bellman-Ford?
- ¿Soporta camino más corto dependiente del tiempo (consciente del tráfico)? ¿De qué fuente vienen los datos de tráfico, con qué frecuencia (5-min, 15-min, horaria)? ¿Está garantizada la propiedad FIFO?
- ¿De dónde vienen los datos de red vial (OpenStreetMap, servicio comercial de mapas, inventario nacional de carreteras)? ¿Cuál es el ciclo de actualización? ¿Cómo se modelan los tipos de vía (autopista, carretera dividida, urbana, acceso pesado) como restricciones?
- ¿Soporta all-pairs shortest path (Floyd-Warshall, Johnson), hasta qué tamaño (cuántos nodos)? ¿Cómo se genera la matriz all-pairs para análisis de red de cadena de suministro?
- ¿Soporta optimización multi-criterio (tiempo + distancia + combustible + peaje) — suma ponderada o caminos Pareto-óptimos? ¿Puede el usuario ajustar parámetros multi-objetivo?
- En un piloto con datos operativos reales (8-12 semanas), ¿qué informe de ahorro puede presentarse frente a la ruta manual / del sistema actual — combustible, tiempo de entrega, horas de conductor, tasa de cambio de ruta?
- Si termina el contrato, ¿en qué formato estándar (GeoJSON, GraphML, CSV) podemos exportar los datos de red vial, datos de calibración de tráfico, historial de consultas y archivo de rutas?
Detalles técnicos
Nota del editor
En lenguaje llano este problema se llama “ruta más corta”, “cálculo de ruta” o “navegación”. En la literatura académica el nombre canónico es Shortest Path Problem (SPP), el problema grafo-OR fundacional. Edsger Dijkstra (1959), en un artículo de dos páginas en Numerische Mathematik, definió un algoritmo polinómico para grafos con aristas no negativas — este artículo está entre los más citados en informática. Richard Bellman (1958), en Quarterly of Applied Mathematics, introdujo Bellman-Ford con soporte para aristas negativas. Robert Floyd (1962), en Communications of the ACM algoritmo 97 (un artículo de un párrafo), desarrolló all-pairs Floyd-Warshall. Ahuja, Magnanti y Orlin (1993) Network Flows es el libro de texto canónico. Los enfoques modernos basados en preprocesamiento (Geisberger et al. 2008 — contraction hierarchies) entregan consultas sub-milisegundo en redes viales nacionales.
Diferencia con #068 (TSP): TSP es el problema de tour de todos los nodos — visitar cada uno de N nodos exactamente una vez y volver al inicio, NP-difícil, problema fundacional de optimización combinatoria. Shortest path es punto a punto único o single-source all-destinations — polinómico (Dijkstra O((V+E)logV), Bellman-Ford O(VE), Floyd-Warshall O(V³)). La brecha de complejidad es grande: para un grafo de 1.000 nodos Dijkstra termina en milisegundos, TSP corre horas-días. TSP llama al shortest path como subrutina: la matriz de distancias por pares se calcula con shortest path, luego TSP resuelve el problema del tour sobre ella.
Diferencia con #069 (CVRP): CVRP es routing de flota con capacidad — múltiples vehículos, con restricción de capacidad, clientes atendidos colectivamente. CVRP llama al shortest path como subrutina: distancias cliente-a-cliente y depósito-a-cliente se calculan con shortest path, luego CVRP resuelve el problema de asignación + secuencia. En esta pila shortest path desempeña el rol de “rellena la matriz de pesos del grafo” y CVRP el de “asignación + secuenciación”.
Diferencia con #002 (VRPTW): VRPTW es routing de flota con ventanas temporales — múltiples vehículos, restricciones de capacidad + ventana horaria. VRPTW también llama al shortest path como subrutina. Si se embebe shortest path dependiente del tiempo dentro de VRPTW, el resultado es routing de flota consciente del tráfico.
Punto más omitido en el campo: detección de aristas o ciclos negativos. El practicante usa Dijkstra en todos los casos; pero si hay un coste negativo (p. ej. descuento en una conexión, retorno de capital, reembolso por flujo inverso, una arista logarítmica negativa en un ciclo de arbitraje de divisas) Dijkstra no es óptimo — devuelve un resultado silenciosamente erróneo. Se necesita Bellman-Ford. Si hay un ciclo negativo, el camino más corto es indefinido (el ciclo puede recorrerse indefinidamente, reduciendo la suma en cada vuelta). En muchos escenarios de arbitraje financiero / flujo de red / flujo inverso este bug es silencioso. Bellman-Ford detecta un ciclo negativo si en la iteración V todavía hay actualización.
Segundo punto omitido: elección de la complejidad algorítmica. El practicante dice “Dijkstra funciona en todas partes”; pero en una red vial nacional (10M+ aristas) una sola consulta clásica de Dijkstra tarda segundos — inaceptable para navegación en tiempo real. Los enfoques modernos basados en preprocesamiento (contraction hierarchies — Geisberger et al. 2008, Transit Node Routing, Hub Labels) entregan tiempos de consulta sub-milisegundo; el preprocesamiento es de coste único (horas-días) pero cada consulta posterior es rápida. Tercer punto omitido: supuesto de grafo estático. El tráfico cambia en tiempo real; el camino más corto sobre grafo estático señala “óptimo para las 14:00” pero se cae en la hora punta de las 17:00. El camino más corto dependiente del tiempo (peso de arista como función del tiempo) o el recálculo rolling-horizon es imprescindible.
Camino paso a paso para pymes
Etapa 1 — Mide primero, planifica después. Al menos 6 meses de datos de consultas / rutas: volumen diario (cuántas consultas A-B, cuántas all-pairs), tiempo medio de consulta, desviación de predicción de tráfico (tiempo planificado vs. real), tasa de cambio de ruta (disparadores de recálculo). Inventario de red vial: fuente (servicio de mapas, OpenStreetMap, inventario propio), calidad (cobertura, frescura, tipo de peso — distancia / tiempo / coste), tipo de vía (autopista, dividida, urbana, acceso pesado). Fuente de datos de tráfico: ninguna / dentro del paquete del servicio de mapas / proveedor separado / datos GPS de flota propia.
Etapa 2 — Construye la matriz de algoritmos. Perfil de consultas: ¿mayoritariamente punto a punto único, single-source all-destinations, análisis all-pairs? ¿Escenarios de aristas / ciclos negativos (arbitraje financiero, flujo inverso)? Tamaño del grafo: 1K, 10K, 100K, 1M, 10M+ nodos? Requisito de tiempo de consulta: ¿sub-milisegundo (navegación en tiempo real), segundos (planificación), minutos (análisis estratégico)? Elige el algoritmo de esta matriz: Dijkstra (pequeño-medio, no negativo), Bellman-Ford (aristas negativas), Floyd-Warshall (all-pairs pequeño), A* (red vial geográfica), contraction hierarchies (nacional en tiempo real).
Etapa 3 — Piloto. 8-12 semanas. Ejecuta el nuevo motor de camino más corto sobre un subconjunto de la operación (p. ej. la región más cargada o el segmento de cliente con más consultas); la decisión sigue en planificador / conductor, el motor recomienda. Criterio de éxito por escrito de antemano: en la región piloto combustible -10% mínimo, tiempo de entrega -15% mínimo, el tiempo de consulta cumple el requisito de tiempo real.
Etapa 4 — Despliegue. 6-12 meses para extender a la operación completa + integración con servicio de tráfico + recálculo rolling-horizon. Comité operativo trimestral: volumen de consultas, tiempo medio de consulta, desviación de predicción de tráfico, tasa de cambio de ruta, informe de cuellos de botella de red (análisis all-pairs).
Riesgos — qué puede salir mal
Desviación de predicción de tráfico (riesgo del grafo estático). El camino más corto sobre un grafo estático no refleja las condiciones reales de tráfico; el riesgo más crítico. En horas punta la ruta “óptima” calculada tarda más en la realidad. Solución: camino más corto dependiente del tiempo (peso como función del tiempo) + servicio de datos de tráfico (refresco 5-15 minutos) + recálculo rolling-horizon (cada 15-30 minutos o por evento — accidente, corte).
Retraso de actualizaciones en tiempo real. Si los datos de corte de vía, accidente o evento de tráfico llegan tarde al motor, este recomienda una vía cerrada sin saberlo — el conductor va, vuelve, doble coste. Solución: recálculo guiado por eventos, notificaciones de evento de tráfico en tiempo real en la app del conductor, sugerencia de ruta alternativa.
Cierre / prohibición de vía desconocida. Si los datos (estáticos) de red vial no se refrescan periódicamente, obras nuevas, cierres estacionales y prohibiciones a vehículos pesados quedan ignorados; el motor produce rutas no factibles. Solución: ciclo de actualización de red vial 3-6 meses, retroalimentación de campo del conductor (un informe de “vía cerrada” en la app), capa de red vial específica para camiones en routing de carga pesada.
Lock-in de software de routing / servicio de mapas único. Sin cláusula contractual de “exportación anual en formato estándar (GeoJSON, GraphML, CSV) de datos de red vial, datos de calibración de tráfico, historial de consultas y archivo de rutas”, salir del sistema significa perder años de datos operativos y memoria de calibración. El contrato debe cubrir explícitamente la soberanía de datos de red vial, la exportación de parámetros de calibración de tráfico y la salida en formato estándar para la API de consulta.
Método de solución — visión técnica
| Enfoque | Tamaño típico | Tiempo de resolución | ¿Aristas negativas? |
|---|---|---|---|
| Dijkstra ingenuo (O(V²)) | Pequeño, V ≤ 1.000 | milisegundos | No |
| Dijkstra binary heap (O((V+E)logV)) | Medio, V ≤ 100K | ms-segundos | No |
| Dijkstra Fibonacci heap (O(E + VlogV)) | Medio-grande, V ≤ 1M | segundos | No |
| Bellman-Ford (O(VE)) | Pequeño-medio, aristas negativas | segundos-minutos | Sí, detecta ciclo negativo |
| Floyd-Warshall (O(V³)) | All-pairs pequeño, V ≤ 1.000 | segundos-minutos | Sí (sin ciclo) |
| Johnson (O(V² logV + VE)) | All-pairs medio, disperso | minutos | Sí |
| A* (guiado por heurística) | Red vial geográfica, punto a punto | ms-segundos | No |
| Dijkstra/A* bidireccional | Punto a punto, grafo grande | ms-segundos | No |
| Contraction Hierarchies | Red vial nacional | sub-milisegundo (preprocesado horas) | No |
| Dijkstra dependiente del tiempo | Red vial consciente del tráfico | ms-segundos | No |
Elección de la función objetivo:
- Objetivo 1 — Mínimo tiempo total: Enfocado en velocidad; típico para navegación, emergencias, reparto de paquetería.
- Objetivo 2 — Mínima distancia total: Enfocado en combustible + desgaste; típico en largo recorrido.
- Objetivo 3 — Mínimo coste total: Suma ponderada de combustible + peaje + horas de conducción.
- Objetivo 4 — Multi-criterio (Pareto-óptimo): Compensación entre tiempo + coste + combustible; el decisor elige en la frontera Pareto.
Multi-objetivo: suma ponderada (más común) o jerárquico (primero tiempo, luego coste, luego combustible) o caminos Pareto-óptimos (soporte avanzado a la decisión).
Variantes del camino más corto — elige por campo:
- Dijkstra clásico (1959): Aristas no negativas, single-source, fundacional.
- Bellman-Ford (1958): Capaz con aristas negativas, detecta ciclos negativos, enrutamiento distance-vector.
- Floyd-Warshall (1962): All-pairs, grafo pequeño, programación dinámica.
- A (Hart-Nilsson-Raphael 1968):* Punto a punto guiado por heurística, redes viales geográficas.
- Contraction Hierarchies: Red vial nacional, basado en preprocesamiento, tiempo real.
- Camino más corto dependiente del tiempo: Consciente del tráfico, peso como función del tiempo.
- Camino más corto estocástico (Polychronopoulos-Tsitsiklis 1996): Pesos inciertos, ajustado al riesgo.
- Camino más corto con restricciones de recurso (RCSP): Restricciones adicionales (combustible, ventanas); aparece como subproblema de pricing en VRP por column generation.
Fuentes académicas
Listadas en la frontmatter de la página bajo sources.
Fuentes
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271. Artículo fundacional de dos páginas; uno de los más citados en informática.
- Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90. Referencia fundacional de Bellman-Ford para grafos con aristas negativas.
- Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6), 345. Fuente canónica de un párrafo del Floyd-Warshall all-pairs.
- Ahuja, R. K., Magnanti, T. L. y Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall. Libro de texto canónico de flujos de red y camino más corto.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C. (2009). Introduction to Algorithms (3.ª ed.). MIT Press. Referencia docente para Dijkstra / Bellman-Ford / Floyd-Warshall.
- Geisberger, R., Sanders, P., Schultes, D. y Delling, D. (2008). Contraction hierarchies: Faster and simpler hierarchical routing in road networks. Experimental Algorithms (WEA 2008), LNCS 5038, 319-333. Algoritmo moderno basado en preprocesamiento para redes viales nacionales.
- Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. Artículo fundacional del algoritmo A*.
- YÖK Thesis Center — palabras clave: ’en kısa yol’ o ‘Dijkstra’ o ‘graf algoritması’ — 30+ tesis de la academia TR. tez.yok.gov.tr
Glosario
- Shortest Path Problem
- Problema fundacional grafo-OR de hallar el camino de mínimo peso total entre dos nodos en un grafo ponderado (single-source single-destination, single-source all-destinations o all-pairs); algoritmos polinómicos Dijkstra (1959), Bellman-Ford (1958), Floyd-Warshall (1962).
- Dijkstra Algorithm
- Algoritmo polinómico de Edsger Dijkstra (1959) para caminos más cortos single-source en grafos con pesos no negativos; goloso — extrae el nodo no visitado con menor distancia tentativa de una cola de prioridad y relaja sus vecinos; O((V+E) log V) con binary heap.
- MIP
- Modelo de optimización donde parte de las variables de decisión deben ser números enteros (p. ej. número de camiones o de turnos).
- VRP
- La decisión de qué vehículos, partiendo de uno o varios almacenes, visitan a qué clientes y en qué orden.
Problemas relacionados
¿Dónde Abro el Nuevo Almacén?
Un distribuidor, un operador de comercio electrónico o un fabricante pyme prevé abrir 1–5 nuevos almacenes, sucursales o centros de distribución en los próximos 2–5 años. La decisión: en qué ciudad o región, cuántas instalaciones, de qué tamaño y qué almacenes existentes transfieren qué volumen de pedido o cliente a la nueva instalación. Una mala localización implica 5–10 años de alto coste de transporte, entregas tardías y pérdida de clientes; una buena localización supone 300.000–1,5 M EUR de ahorro anual en el mismo periodo. Cuando la decisión se toma por intuición (por ejemplo 'al lado de la fábrica, los empleados viven cerca') rara vez se acierta — porque coste de transporte, alquiler, impuestos, mano de obra y tiempo de servicio son restricciones que deben equilibrarse a la vez.
¿Qué cabe en un camión o contenedor, y en qué orden se carga?
Dado un camión, contenedor o vehículo de carga de dimensiones fijas, ¿qué disposición de cajas (o pallets) con tamaños, pesos y reglas de apilado distintos da la mayor tasa de utilización? El nombre matemático de esta pregunta es Three-Dimensional Bin Packing Problem (3D-BPP) o Container Loading Problem (CLP). Métodos que resuelven al mismo tiempo volumen, límites de peso, reglas de apilado, distribución del peso (balance) y orden de entrega (multi-drop) se estudian desde los 1990. Incluso un 5% de mejora en utilización aumenta entregas por vehículo de forma material para una pyme.
¿Qué Furgoneta a Qué Cliente, a Qué Hora?
Una flota local de reparto de 5–30 furgonetas planifica sus rutas diarias. Cada cliente tiene una ventana horaria (una tienda recibe entre 09:00 y 12:00; un restaurante solo antes de las 14:00). La decisión: a qué furgoneta asignar cada cliente, en qué orden visitarlos, de modo que todas las ventanas se cumplan, las horas de combustible y conductor sean mínimas, y ninguna furgoneta supere su capacidad. Un repartidor puede planificar a mano 30–50 paradas; por encima, la calidad cae — kilómetros vacíos, entregas tardías, segundas rutas y horas extra del conductor.