Optimización de Rutas de Vehículos.
Orígenes y variantes
1. Los orígenes, el Travelling Salesman Problem (TSP)
El problema del vendedor ambulante, problema del agente viajero o problema del viajante (TSP por sus siglas en inglés: Travelling Salesman Problem), responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta[1] posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen?
El problema fue formulado por primera vez en 1930 y es uno de los problemas de optimización más estudiados. Es usado como prueba para muchos métodos de optimización. Aunque el problema es computacionalmente complejo, se conoce gran cantidad de heurísticas y métodos exactos, así que es posible resolver planteamientos concretos del problema desde cien hasta miles de ciudades.
Una posible simplificación es el ‘TSP simétrico’, en el cual la distancia entre un par de ciudades es la misma en ambas direcciones, formando un grafo técnicamente denominado “no dirigido”. Este problema reduce a la mitad el número de soluciones posibles. En el ‘TSP asimétrico’, pueden no existir caminos en ambas direcciones o las distancias pueden ser diferentes, formando un “grafo dirigido”. Los accidentes de tráfico, las calles de un solo sentido y las tarifas aéreas para ciudades con diferentes costos de ida y vuelta son ejemplos de cómo esta simetría puede tener sentido.
En el problema original (asimétrico) se presentan N! rutas posibles (factorial de N), aunque se puede simplificar ya que dada una ruta nos podría dar igual el punto de partida y esto reduciría el número de rutas a examinar en un factor N, quedando (N-1)! Si además, no importase la dirección en que se desplaza el viajante, el número de rutas a examinar se reduce nuevamente en un factor 2. Por lo tanto, habría que considerar, evaluar o comparar un total (N-1)! / 2 rutas posibles. En la práctica, para un problema del viajante con 5 ciudades habría (5-1)!/2 = 12 rutas diferentes y no necesitamos un ordenador para encontrar la mejor ruta, pero apenas aumentamos el número de ciudades las posibilidades crece exponencialmente:
- Para 10 ciudades hay (10-1)!/2=181.440 rutas diferentes
- Para 30 ciudades hay más de 4·1030 rutas posibles. Un ordenador que calcule un millón de rutas por segundo necesitaría 1017 años para resolverlo. Dicho de otra forma, si se hubiera comenzado a calcular al comienzo de la creación del universo (hace unos 13.400 millones de años) todavía no se habría terminado.
Puede comprobarse que por cada ciudad nueva que incorporemos, el número de rutas se multiplica por el factor N y crece exponencialmente[2].
2. El VRP clásico, el capacitado
El problema optimización de rutas de vehículos capacitado (CVRP, por sus siglas en inglés) es un problema, podría decir, una variante del TSP pretende dar respuesta a problemas que no encajan con el TSP por la aparición de nuevas restricciones (la capacidad): ¿Cuál es el conjunto óptimo de rutas para una flota de vehículos que debe satisfacer las demandas de un conjunto dado de clientes teniendo en cuenta la capacidad de los vehículos?
La primera definición aparece en un artículo de George Dantzig y John Ramser en 1959, en donde plantean una aproximación algorítmica y fue aplicado para entregas de gasolina. El problema, requiere la entrega de cierto producto, almacenado en un único local o almacén, a los clientes los cuales poseen cierta demanda. El objetivo fundamental era minimizar el coste total de las rutas trazadas. En 1964, Clarke y Wright mejoraron la aproximación de Dantzig y Ramser utilizando una aproximación ‘greedy‘ conocido como algoritmo de ahorros.
3. Variantes VRP
A continuación, se describirán brevemente las principales variantes del problema clásico visto en las secciones anteriores. Esta lista no es exhaustiva, sino que define particularidades, funcionalidades o restricciones nuevas que la diferencias de las otras y que surgen de manera natural para satisfacer las necesidades reales de los operadores logísticos. No obstante, en la vida real, vuestro problema de optimización de rutas puede que incluya todas o casi todas estas restricciones o variantes que veremos a continuación.
3.1. VRP with Time Windows (VRPTW)
El VRP con ventanas de tiempo es el mismo problema que el VRP con la restricción adicional de que en el VRPTW se asocia una ventana de tiempo a cada cliente en el que el cliente tiene que ser suministrado. El objetivo ha sido tradicionalmente reducir al mínimo la flota de vehículos y la suma del tiempo de viaje y el tiempo de espera necesarios para abastecer a todos los clientes en las horas requeridas, pero existen otros enfoques en el que se permiten incumplir ventanas de tiempo (a costa de mejorar en el criterio de optimización principal).
3.2. VRP with Backhauls (VRPB)
El Problema de Rutas de Vehículos con Retroceso (VRPB) es un VRP en el que los clientes pueden exigir o devolver algunos productos básicos. Así en el VRPPB es necesario tener en cuenta que las mercancías que los clientes devuelven al vehículo de entrega deben caber en él. La suposición crítica es que todas las entregas deben hacerse en cada ruta antes de que se pueda hacer cualquier recogida. Esto se debe al hecho de que los vehículos se cargan por la parte trasera, y la reorganización de las cargas en las vías de los puntos de entrega no se considera económica ni factible. Las cantidades para entregar y a recoger son fijas y se conocen de antemano. La VRPB es similar al VRP with Pick-Up and Delivery con la restricción de que, en el caso del VRPB, todas las entregas de cada ruta deben completarse antes de realizar las recogidas.
El objetivo o criterio de optimización ha sido tradicionalmente la minimización de la distancia total recorrida pero se podría enfocar con cualquier otro tratado en el curso.
3.3. VRP with Pickup and Delivery (VRPPD)
El problema de rutas de vehículos con recogidas y entregas (VRPPD, por sus siglas en inglés) es un VRP en el que se contempla la posibilidad de que los clientes devuelvan algunos productos. Así, en el VRPPD es necesario tener en cuenta que las mercancías que los clientes devuelven al vehículo de entrega deben caber en él. Esta restricción dificulta el problema de la planificación y puede dar lugar a una mala utilización de las capacidades de los vehículos, al aumento de las distancias de viaje o a la necesidad de más vehículos.
Por lo tanto, suele considerarse que hay situaciones restringidas en las que todas las demandas de entrega parten del depósito y todas las demandas de recogida se llevan de vuelta al depósito, de modo que no hay intercambios de mercancías entre los clientes. Otra alternativa es relajar la restricción de que todos los clientes tienen que ser visitados exactamente una vez. Otra simplificación habitual es considerar que cada vehículo debe entregar todas las mercancías antes de recogerlas.
El objetivo ha sido tradicionalmente el reducir al mínimo la flota de vehículos y la suma del tiempo de viaje, con la restricción de que el vehículo debe tener suficiente capacidad para transportar las mercancías que se van a entregar y las que se recogen en los clientes para devolverlas al depósito.
3.4. Periodic VRP (PVRP)
En los VRP clásicos, típicamente el período de planificación es de un solo día. En el caso del Problema de la Ruta del Vehículo Periódico (PVRP), la VRP clásica se generaliza extendiendo el período de planificación a M días. El objetivo es por tanto minimizar la flota de vehículos y la suma del tiempo de viaje necesario para abastecer a todos los clientes de los M días.
Una solución es factible si se satisfacen todas las limitaciones del VRP. Además, un vehículo no puede volver al depósito el mismo día que sale. Durante el período del día M, cada cliente debe ser visitado al menos una vez.
En la siguiente figura simulamos que cada color de ruta se realiza un día diferente.
3.5. Multi-Depot VRP (MDVRP)
Surgen cuando una empresa tiene varios depósitos desde los que puede atender a sus clientes. Si los clientes están agrupados en torno a los depósitos, entonces el problema de distribución debe modelarse como un conjunto de problemas VRP independientes. Sin embargo, si los clientes y los depósitos están entremezclados, entonces se debe resolver un problema de distribución de vehículos en varios depósitos (MDVRP).
Un MDVRP requiere la asignación de clientes a los depósitos. Una flota de vehículos se basa en cada depósito. Cada vehículo se origina en un depósito, atiende a los clientes asignados a ese depósito y regresa al mismo depósito. El objetivo del problema es atender a todos los clientes y al mismo tiempo reducir al mínimo el número de vehículos y la distancia de viaje.
3.6. Split Delivery VRP (SDVRP)
En el problema de la ruta de vehículos de reparto dividida (SDVRP, por sus siglas en inglés), se permite que más de un vehículo atienda a un cliente, de modo que la demanda de un cliente puede dividirse entre varios vehículos en diferentes rutas.
3.7. VRP with Satellite Facilities (VRPSF)
Un aspecto importante del problema de rutas de vehículos (VRP) que se ha pasado por alto en gran medida es el uso de instalaciones de satélites para reponer los vehículos durante una ruta. Cuando es posible, el reabastecimiento por satélite permite a los conductores seguir haciendo entregas hasta el final de su turno sin tener que volver necesariamente al depósito central. Esta situación se plantea principalmente en la distribución de combustibles y de ciertos artículos de venta al por menor.
3.8. Site Dependent VRP (SDVRP)
En el problema de rutas de vehículos con dependencia del emplazamiento (SDVRP), se utiliza una flota heterogénea de vehículos para atender a un conjunto de clientes, pero existen dependencias de compatibilidad entre los emplazamientos de los clientes y los tipos de vehículos. El objetivo es seleccionar cuidadosamente un tipo de vehículo permitido para cada cliente.
3.9. Stochastic VRP (SVRP)
El problema de las rutas de los vehículos es estocástico cuando las demandas en los lugares de entrega (recogida) individuales se comportan como variables aleatorias, y las rutas deben definirse antes de que se conozcan los valores de estas variables aleatorias.
3.10. Dynamic VRP (DVRP)
El problema de rutas dinámico (DVRP) es una de las variantes importantes del VRP. Su objetivo consiste en diseñar el conjunto óptimo de rutas para una flota de vehículos con el fin de atender a un determinado conjunto de clientes mientras llegan nuevos pedidos de clientes durante la realización de la jornada laboral prevista más temprano.
3.11. Capacitated Arc Routing Problem (CARP)
El problema de rutas por arco capacitado (CARP) es un conocido problema combinatorio que requiere la identificación de la distancia total mínima recorrida por un conjunto de vehículos para dar servicio a un determinado conjunto de caminos sujetos a las limitaciones de capacidad del vehículo. Es un enfoque adecuado cuando en una misma calle se deben visitar varios puntos (para entregar correo, por ejemplo).
Referencias
- Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
- Golden, B. L., & Wong, R. T. (1981). Capacitated arc routing problems.Networks, 11(3), 305-315.
- Pullen, H. G. M., & Webb, M. H. J. (1967). A computer application to a transport scheduling problem.The computer journal, 10(1), 10-13.
- Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing.Networks, 11(2), 109-124.
- Dumas, Y., Desrosiers, J., & Soumis, F. (1991). The pickup and delivery problem with time windows.European journal of operational research, 54(1), 7-22.
- Beltrami, E. J., & Bodin, L. D. (1974). Networks and vehicle routing for municipal waste collection.Networks, 4(1), 65-94.
- Ball, M. O., Golden, B. L., Assad, A. A., & Bodin, L. D. (1983). Planning for truck fleet size in the presence of a common‐carrier option.Decision Sciences, 14(1), 103-120.
- Dror, M., & Trudeau, P. (1989). Savings by split delivery routing.Transportation Science, 23(2), 141-145.
- Dror, M., & Ball, M. (1987). Inventory/routing: Reduction from an annual to a short‐period problem.Naval Research Logistics (NRL), 34(6), 891-905.
- Nag, B. L. (1988). Golden, and AA Assad. Vehicle Routing with Site Dependencies. Vehicle Routing: Methods and Studies, BL Golden and AA Assad, Eds.
- Gendreau, M., Laporte, G., & Séguin, R. (1995). An exact algorithm for the vehicle routing problem with stochastic demands and customers.Transportation science, 29(2), 143-155.
- Psaraftis, H. N. (1980). A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem.Transportation Science, 14(2), 130-154.
[1] Criterio de optimización original (distancia total recorrida) pero se puede se resolver el TSP con cualquier de los criterios visto en el curso.
[2] Por ello el problema pertenece a la clase de problemas NP-completos.
Últimos artículos
Acerca del autor
Alfredo García
Catedrático en la Universidad Pablo de Olavide (UPO) y Doctor en Matemáticas por la Universidad de Sevilla. Senior Optimization Consultant en oga.
Apasionado de la Matemática, como ciencia fundamental, pero sobre todo de la Matemática Aplicada. Lo que más le motiva es la resolución de problemas reales y es por ello que, tras más de 20 años de experiencia, ha trabajado en Matemáticas Puras, Investigación Operativa, Optimización Multiobjetivo, Computación Evolutiva y finalmente en Machine Learning y Business Analytics.
