Juan Daniel Acevedo
Paola Andrea solano
XXXXXXXX
XXXXXX@[Link]
Problema de ruteo de vehículos
1
Origen: el problema de ruteo de vehículos data del año de 1959 el cual fue introducido por Dantzing y Ramser,
quienes describieron una aplicación real de la entrega de gasolina a las estaciones de servicio y propusieron una
formulación matemática. Cinco años mas tarde Clarke y Wright propusieron el primer algoritmo que resulto eficiente
para resolverlo.
Elementos que componen el problema: Los componentes generales establecidos para un estudio del problema de
ruteo son los: clientes, los vehículos, los depósitos, las restricciones, objetivos, tipo de red, Las restricciones y objetivos
se establecen con relación a la situación del objeto de estudio
Herramientas de solución al problema:
• CVRP – VRP capacitado: la cual establece que el vehículo no puede transportar mas de su capacidad de carga le
permita, se clasifica en dos ACVRP y SCVRP, la flota de vehículos es homogénea y deben estar centralizadas en un
solo deposito.
1.1
• PVRP – VRP con múltiples depósitos: los almacenes de despachos son superiores a uno, se establece la premisa de que los
clientes y los depósitos se encuentran mezclados, de lo contrario puede ser solucionado como problemas VRP
independientes (Lau, Chan, Tsui, & Pang, 2010) & (Salhi, Imran, & Wassan, 2014).
• PVRP – VRP periodico: un conjunto de clientes debe ser visitado una o mas veces durante un periodo de tiempo establecido
el objetivo principal, es minimizar la flota de vehiculos requerida y el tiempo total recorrido( Cacchiani, Hemmelmayr, &
Tricoire, 2014).
• SDVRP – VRP con entrega divida: la cantidad de vehículos que se encarga de la distribución a un cliente es
superior a uno, siempre que el total de costo se reduzca, debido a que la demanda de un cliente supera la
capacidad de un vehículo, por lo que el abastecimiento debe ser realizado por mas de uno de estos (Bolduc,
Laporte, Renaud, & Boctor, 2010).
1.2
• DCVRP – VRP con restricción de capacidad y distancia: la capacidad de los vehículos es limitada y la longitud de los arcos
que se realizan en una ruta, es decir las distancias. En consecuencia, la suma de las longitudes de los arcos, no debe ser
superior a una distancia máxima establecida (Tlili, Faiz, & Krichen, 2014).
• MFVRP – VRP con flota mixta: La flota de vehículos es
homogénea, presentando variaciones en la capacidad y
en los costos relacionados al transporte de la
mercancía, tales como el combustible, programación y
ejecución de mantenimientos (Subramanian, Vaz
Penna, Uchoa, & Satoru Ochi, 2012).
1.3
Ventajas:
• Bajos costos asociados a los vehículos
• Mayor acceso para la distribución de los productos
• Menores costos de infraestructura
• Incremento de la seguridad.
Aplicabilidad:
Diseño de rutas: es la búsqueda estratégica y esta se compone de dos partes, la primera es denominada construcción y
utiliza métodos de optimización con el objetivo de acercar el proceso hasta una buena solución inicial. La segunda parte
llamada mejoramiento emplea un método de búsqueda inteligente con características de memoria para mejorar los
resultados logrados en la primera parte.
Heurística de inserción mas próxima: construye un tour por la repetida selección de los arcos mas cortos y los adhiere a
un tour con tal que no cree un ciclo con menos bordes, o aumentos del grado de cualquier nodo a mas de dos. (Wren,
1971; Wren y Holliday, 1972; Gillett y Miller, 1974),
Búsqueda tabú: es una técnica que trata de evitar que las soluciones caigan en mejores locales, para esto se utilizan
estructuras de memoria de corto y largo plazo acompañadas de criterios de aspiración. El objetivo es continuar el
descubrimiento de soluciones de alta calidad.
1.4
Problema del agente viajero
Origen: la primera solución reportada para resolver el problema del agente viajero fue en 1954, cuando George Dantzig,
Ray Fulkerson , y Selmer Jonhson publicaron la descripción de un método de solución del PAV para resolver una instancia
de 49 cuidades asignándoles un costo por visitar ciudades contiguas, para esta solución se propusieron dos condiciones:
regresar a la misma ciudad de la cual partió y no repetir cuidades con el objetivo de encontrar un camino con el menor
costo posible.
Caracterización: es un problema considerado difícil de resolver, el cual no podemos garantizar que se encontrara la mejor
solución en un tiempo razonable, para dar solución se emplean diferentes métodos, entre los cuales. Los principales se
denominan heurísticas cuyo objetivo es generar soluciones de buena calidad en tiempos cortos.
Elementos del problema
• Tiempo de recorrido entre cuidades: horas, minutos, días y semanas
• Distancia de recorrido entre cuidades: metros, kilómetros, millas.
• Costo de traslado: dinero, desgaste de piezas.
1.5
Variables de cada problema:
• Circuitos electrónicos, control de semáforos, previsión de transito terrestre, entrega de productos, estaciones de trabajo,
edificación.
Herramientas de solución al problema:
• Enumeración de todas las soluciones factibles, calcular los costos asociados.
• Métodos exactos tratan de acelerar la búsqueda y llegar a una conclusión optima
• Heurísticas son métodos que obtienen buenas soluciones en tiempos muy cortos.
Estrategias para dar solución
• Algoritmos genéticos: una solución es cada gen es una cuidad y cuyo orden dependerá del orden en que sean visitados
• Redes neuronales: simula conexiones entre los nodos y cara recorrido para asi mismo no repetir mismas ciudades
• Colonia de hormigas: se considera el punto de inicio como el punto final para asi no pasar dos veces por la misma ciudad
• Combinación de propuestas: las técnicas de inteligencia artificial se pueden combinar para crear metaheurísticas,
conformando diferentes soluciones como, algoritmos genéticos, PSP con ACO, PSP con redes neuronales.
1.6
Aplicabilidad:
• Reparto de productos: mejorar una ruta de entrega para seguir la mas corta.
• Transporte: mejora el recorrido de caminos buscando la menor longitud.
• Robótica: resolver problemas de fabricación para minimizar el numero de desplazamientos de un circuito.
• Turismo y agencias de viajes: las compañías dedicadas a este giro utilizan un software que realizan todo el trabajo.
• Horarios de transportes laborales.
• Inspecciones a sitios remotos: ordenar los lugares que deberá visitar un inspector en el menor tiempo.
Simulación:
•Planificación estratégica de la producción
•Optimización de redes de distribución
•Programación y mezcla de crudo
•Modelado y optimización de procesos
•Planificación de la utilización de plantas de generación eléctrica
•Gestión estratégica de bosques
•Optimización de aprovisionamientos
•Gestión de riesgo financiero
1.7
Problema de ruteo vehicular
Permite establecer las rutas que debe seguir una flota de carros, con el propósito de optimizar las variables asociadas al
transporte de mercancías, tales como son costos, distancias, nivel de satisfacción al cliente, es por ello que a partir de
1959, ha sido uno de los principales objetivos de estudio de grandes organizaciones.
Se ha establecido que el costo de transporte asociado representa el 20% del valor total de los bienes brindados. (Bernal
García, Hontoria Hernández, & Aleksovski, 2013).
Elementos que componen el problema:
1. Supuestos: la demanda es determinística, la demanda puede no estar dividida, los vehículos son similares, los
vehículos están en un solo deposito central.
2. Entradas: conjunto de vértices, conjunto de arcos, demanda de cada cliente, costo de viaje, conjunto de clientes,
demanda total, capacidad de cada vehículo.
1.8
Técnicas de solución al problema:
• Técnicas exactas: los algoritmos son aquellos que producen soluciones optimas, estas no son muy adecuadas en
aplicaciones que requieran soluciones rápidas debido a la naturaleza NP del dicho problema.
• Técnicas heurísticas: realizan una exploración relativamente limitada en el espacio de búsqueda y comúnmente
producen soluciones de buena calidad dentro de tiempos razonables estas están divididas en tres tipos.
1. heurísticas constructivas
2. heurísticas de dos fases
3. técnicas metaheurísticas
• Métodos de búsqueda local: parte de que hay una solución inicial realizable y a esta se le aplican una serie de
cambios a la solución y que dichos cambios mejoren el objetivo del problema de estudio, entre los principales
métodos de búsqueda se encuentran; búsqueda local simple, búsqueda local múltiple, reconocido simulado,
búsqueda de vecindario variable.
Planteamiento del problema:
Fase 1: creación de clusters de afectación para cada uno de los vehículos, dependiendo de su capacidad.
Fase 2: se da solución a cada clusters establecido en la etapa anterior implementando AGCB adaptado a un problema de
optimización del agente viajero simétrico.
1.9
Recomendaciones: incluir estrategias de búsqueda local para realizar movimientos intra-ruta e inter-ruta, implementar
clusters aleatorios para explorar aun mejor el espacio de soluciones del problema.
Aplicabilidad del PVRP:
En el PVRP un conjunto de clientes tiene que ser visitado en un tiempo determinado una o mas veces, diferentes clientes por
lo general necesitan varias visitas.
• Aplicabilidad del VRP clásico: se aplica a la red de distribución local ya que los mensajeros inician su recorrido en la sede,
después de recibir la asignación de la zona, los vehículos utilizados para esta labor son motos, bicicletas e inclusive a pie
dependiendo de la zona y si es de lato riesgo.
• Aplicabilidad de VRPPD: Los vehículos tienen dos conjuntos de actividades uno de mercancías que entregan a los clientes,
otro de bienes recogidos en las instalaciones del cliente. Los transportistas así como entregan recogen por las mismas
zonas.
• Aplicabilidad de OVRP: los vehículos no están obligados a regresar al punto de partida, en un porcentaje muy
considerable la empresa realiza la distribución local de documentos en vehículos de bajo desempeño y bajo costo.
• Aplicabilidad CVRP: se tiene en cuenta la capacidad del vehículo que realiza el recorrido, la empresa cuenta con una flota
compuesta por unos camiones con ciertas especificaciones para su respectiva recolección.
2.0
Ventajas:
• Mejora la capacidad de reacción, ya que cuenta con mayor tiempo para planear otro tipo de detalles.
• Se produce un ahorro considérale de tiempos debido a que el sistema automatiza el proceso de generar rutas.
• Se minimizan los errores de planificación, debido a que el sistema considera una serie de variables que una persona
puede pasar por alto.
• El sistema considera los trayectos mas adecuados, lo cual reducirá el costo de combustible.
• Permite llevar el control sobre la entrega de mercancías y evita perdidas de cargamento.
Limitaciones:
• Combinaciones de variables estocásticas
• Las entregas son periódicas o no
• Los clientes tiene que ser visitados dentro de una franja horaria
• Los puntos de suministro son sencillos o múltiples
• Los vehículos atienden a varios clientes.
2.1
Problema de ruteo de vehículos con ventanas de tiempo
Es una extensión del modelo básico de ruteo el VRPTW es un problema que consiste en diseñar un conjunto posible de
rutas para una flota de vehículos de igual capacidad que salen y llegan a un deposito, de modo que visiten todos los
destinos una vez con el costo mínimo satisfaciendo restricciones horarias y de capacidad.
Las ventanas de tiempo del problema pueden ser flexibles o suaves, para el ruteo con ventanas de tiempo suaves permiten
violar las restricciones de inicio de servicio dentro de las ventanas de los clientes.
La función de costo varia según el alcance del modelo que se proponga ya sea que optimice el tiempo de viaje total, la
cantidad de vehículos usados de la flota la suma de los costos de transporte.
Procedimiento:
• Calcular los ahorros de todos los clientes
• Organizar una lista de ahorros de manera descendente
• Se asigna la ruta
• Se organizan los clientes de la ruta mas lejana a las mas cercana
2.2
Formulación de problema: consiste en realizar el enrutamiento de una flota de vehículos que tienen una capacidad
restringida medida de peso y volumen hacia un numero definido de puntos de demanda los clientes estos se caracterizan
por tener un intervalo de tiempo o ventana de tiempo la cual no podrá ser violada no podrá llegar después de lo acordado,
cada cliente tiene cierta cantidad de productos, de ciertas características peso y volumen que deben ser recogidos por un
único vehículo.
En cuanto a estos vehículos todos parten desde una bodega y deben regresar a esta en un intervalo de tiempo dado,
además que no se puede exceder la capacidad de carga que cada uno posee, la idea es dar cobertura a los clientes
cumpliéndose todo lo mencionado anteriormente utilizando el menor numero de vehículos y empleando la menor
distancia recorrida posible.
Modelo de programación lineal entera: a continuación veremos algunas variables para el caso de estudio.
• Conjunto de clientes
• Conjunto de depósitos
• Conjunto de vértices
• Capacidad de carga de vehículo
• Hora de cierre de depósitos
• Demanda de cliente
• Costo fijo
2.3
Problema: se ha evidenciado un incremento del uso del software de optimización basado en cálculos matemáticos
todo esto para un manejo adecuado de la provisión de bienes y servicios en todos los procesos.
La distribución de bienes y servicios entre los depósitos y los centros de distribución a usuarios o consumidor final es
la actividad que se modela en los problemas de ruteo de vehículos.
El VRPTW aparece como investigación al problema de los modelos de distribución, incluye la dimensión temporal,
como la espacial la cual permite una detallada descripción de la actividad logística de distribución.
Características: consiste en diseñar un conjunto posible de rutas para una flota de vehículos de igual capacidad que
salen y llegan a un lugar desterminado, de modo que visiten todos los destinos una vez como mínimo satisfaciendo
horarios y capacidad.
Los clientes estas dispersos geográficamente y cada uno tiene asociado un intervalo de tiempo en el que permiten el
servicio de recogida o despachos.
Función objetivo: expresa el costo total, se pretende optimizar el tiempo total de recorrido entre los clientes el costo
de la función objetivo es el tiempo de viaje asignado a cada ruta.
2.4
Restricciones:
• Limitan el numero de rutas por cada vehículo y caracterizan el flujo que debe seguir la flota.
• Asegura que a cada cliente solo llegue un vehículo y el mismo salga de el esto permite que no se formen ciclos
• Indica que la suma de las demandas de los clientes de una ruta no debe exceder la capacidad del vehículo
Instancias : son usadas con frecuencia para comparar resultados propios con algunos otros, estos grupos difieren
entre si al respecto al ancho de sus ventanas de tiempo, medido como la diferencia entre el fin y el inicio de la ventana.
La ubicación geográfica de los clientes según sus coordenadas y la densidad de ventana.
2.5
Problema de ruteo vehicular con restricción de capacidad y distancia
Posible solución a este problema:
• capacidad de carga: tienen capacidad de carga limitada dado esto las rutas solo serán viables si es cada vehículo soporta
la carga a ser distribuida a lo largo de su ruta.
• Flota heterogénea: pueden tener distintas características de distinto tamaño, terminar en distintos lugares o tener
distintos horarios.
• Rutas abiertas: fijar un punto de fin de ruta por cada vehículo.
• Zonas geográficas: permite asignar un vehículo a una o varias zonas o también varios vehículos en unas sola zona.
• Ventanas de tiempo: solo pueden ser visitados en determinadas ventanas de tiempo por lo cual esto será capaz de
organizar rutas antes de dar dicha información.
Fortalezas: vehículos propios, distribución de productos de conjunto.
Debilidades: la programación de las rutas se realiza con base a la experiencia de los conductores, falta de coordinación
entre los jefes de despachos, falta de comunicación con los clientes en cuanto a recepción.
Oportunidades: mejorar la comunicación con los clientes, utilizar el servicio de entrega y mensajería para la distribución.
Amenazas: la velocidad promedio en la mañana es de 24 km/h y en la tarde 25 km/h.
2.6
Problema de ruteo estético: es considerado el problema central de la distribución de bienes y servicios limita su
implementación practica en problemas reales de distribución entre los cuales están.
• Los vehículos atienden desde una sola bodega.
• Los vehículos solo reparten o recolectan, pero no ambos a la vez.
• Los clientes son atendidos por un solo vehículo.
• No se consideran ventanas de tiempo.
• Los tiempos de viaje son constantes.
Problema de ruteo de vehículos con tiempos de viaje dependientes del tiempo: en varias ciudades los altos niveles de
trafico pueden ocasionar retrasos y cambios inesperados para ello se busca soluciones de transporte a diferentes tipos
de vehículos para que cada uno salga a diferentes horas para que no se crucen en el camino. Ya que los viajes cambian
continuamente en función del tiempo.
2.7
Métodos propuestos:
• Función objetivo: distancia y tiempos de viaje
• Ventanas de tiempo: lo que importa realmente es si los trabajos incluyeron o no restricciones de ventanas de tiempo
para la atención de clientes.
• Demandas: ver si las rutas son fijas o pueden tener variaciones a lo largo del periodo de planificación.
• Desvíos: ver si los vehículos pueden ser desviados de sus destinos hacia un nuevo cliente o por una nueva ruta.
Estrategias de operación
Estrategia VC: ruteo según plan de rutas obtenido considerando velocidades contantes en la red.
Estrategia VV-4: ruteo según plan de rutas considerado que las variaciones de velocidad ocurren cada 10 minutos.
2.8
Ventajas:
• Rapidez y puntualidad de entrega
• Fiabilidad en las fechas estipuladas
• Seguridad e higiene del transporte
• Información y control de transporte.
Elementos principales:
• Red de transporte
• Flota de vehículos
• Clientes y proveedores
• Deposito central
• Rutas de solución
• Sistemas de información geográfica.
Restricciones:
• Cada vehículo tiene capacidad limitada
• Los clientes pueden ser atendidos por varios vehículos
• Las entregas se deben realizar en determinados días.
(Toth & Vigo, 2002)
2.9
Ruteo de vehículos con múltiples depósitos: se caracteriza por tener mas de un deposito para entender a los clientes,
cuando estos están agrupados alrededor de los depósitos, el problema de distribución puede modelarse como un
sistema de ruteo de vehículos independiente. Si los clientes y los depósitos están mezclados el problema Debra ser
resuelto como un sistema de vehículos con múltiples depósitos. (Tansini, Urquhart, & Viera, 2001).
Desarrollo metodológico:
• Coordenadas de ubicación geográfica de depósitos y clientes
• Capacidades de los depósitos
• Capacidad de los vehículos
• Demandas de los clientes
• Número de clientes y depósitos.
3.0
• CONCLUSIONES
• El problema del Agente Viajero (TSP) es un problema cuya solución puede ser en diferentes puntos a visitar con
un costo considerado en el enlace entre dichos puntos costo: recursos empleados como distancia, tiempo,
monto económico, etc. en determinado momento, se pueden emplear para dar lugar a nuevas soluciones; de las
técnicas empleadas la más común es el uso de redes neuronales dada su similitud, donde cada neurona es un
nodo a visitar y las relaciones entre neuronas es el vector que representa el costo.
• Las utilizaciones de heurísticas constructivas para generar soluciones básicas factibles de inicio se muestran
como una ventaja tanto computacional como en resultados, ya que se garantiza tener individuos de buena
calidad desde el inicio del algoritmo.
• Todo lo mencionado anteriormente en el documento esta planteado de diferentes formas por varios autores
pero para que estos nodos funciones correctamente deben estar correlacionados unos con otros para asi
encontrar la mejor solución al problema planteado.
3.1
Bibliografía
Bolduc, M.-C., Laporte, G., Renaud, J., & Boctor, F. (2010). A tabu search heuristic for the split delivery vehicle routing
problem with production and demand calendars. European Journal of Operational Research, 122-130.
Tlili, T., Faiz, S., & Krichen, S. (2014). A Hybrid Metaheuristic for the Distanceconstrained Capacitated Vehicle Routing
Problem. Procedia - Social and Behavioral Sciences, 779 - 783.
Subramanian, A., Vaz Penna, P., Uchoa, E., & Satoru Ochi, L. (2012). A hybrid algorithm for the Heterogeneous Fleet
Vehicle Routing Problem. European Journal of Operational Research, 285-295.
Archetti, C., Savelsbergh, M. and Speranza, M., An optimization-based heuristic for the split delivery vehicle routing
problem. Transportation Science, 42 (1), pp. 22-31. 2008. DOI: 10.1287/trsc.1070.0204
Wren, A. y Holliday, A. Programación informática de vehículos desde uno o más depósitos hasta varios puntos de
entrega. Investigación operativa trimestral 23 (1972) 333-44.
3.2
Applegate, D., Bixby,R., Chvatal V., Cook,W. “On the solution of the Traveling Salesman Problem”.
DocumentaMathematica-Extra Volume ICM III. 1998. 645-656.
Bernal García, J., Hontoria Hernández, E., & Aleksovski, D. (2013). El problema del enrutamiento de vehículos.
Cartagena, Colombia: Universidad Politécnica de Cartagena.
. C. Prins. “A simple and effective evolutionary algorithm for the vehicle routing problem”. Computers & Operations
Research, volume 31, issue 12, pages 1985-2002. 2004.
Berbeglia, G., Cordeau, J. F., Gribkovskaia, I., & Laporte,G. (2007). Static pickup and delivery problems: a
classification scheme and survey. Journal of the Spanish Society of Statistics and Operations Research, 15, 1-31.
Afshar-Nadjafi, B., y A. Afshar-Nadjafi, A Constructive Heuristic for Time-Dependent Multi-Depot Vehicle Routing
Problem with Time-Windows and heterogeneous fleet, doi: 10.1016/[Link].2014.04.007, Journal of King Saud
University - Engineering Sciences, 29(1), 29-34, (2017)
Adriana Lozada, Ricardo Cadena, Solucion del problema de ruteo de vehículos con ventanas de tiempo mediante
métodos heurísticos, universidad industrial de snatander facultad de ingeniería, 2012
3.3
Archetti. C, y Speranza, M. (2006). An Overview on the Split Delivery Vehicle Routing Problem. Operations Research
Proceeding, Volume 2006, 123-127.
Toth, P., & Vigo, D. (2002). Vehicle Routing Problem. Philadelphia, USA: Society for Industrial and Applied Mathematics
Tansini, L., Urquhart, M., & Viera, O. (2001). Comparing Assignment Algorithms for the Multi-Depot VRP. Montevideo,
Uruguay: Dpto. Investigación Operativa, Instituto de Computación, Facultad de Ingeniería, UDELAR.
Lau, H., Chan, T., Tsui, W., & Pang, W. (2010). Application of genetic algorithms to solve the multidepot vehicle routing
problem. Automation Science and Engineering, 383-392.
Cacchiani, V., Hemmelmayr, V., & Tricoire, F. (2014). A set-covering based heuristic algorithm for the periodic vehicle
routing problem. Discrete Applied Mathematics, 53-64.
