Se presenta un método para la solución del problema de ruteo de mensajeros en motocicleta con ventanas de tiempo. En este se identifican dos fases: en la primera, se conforman grupos de clientes, cada grupo es asignado a una ruta y cada ruta es atendida por un vehículo; en la segunda, por medio de un modelo de programación lineal entera mixta, se hace un ruteo para cada una de las agrupaciones respetando las ventanas de tiempo estrictas de algunos clientes. Para validar el método, se utilizó como caso de estudio el área de mensajería de un centro de servicios compartidos de Cali, Colombia. Los resultados muestran que, al probar diferentes métodos de agrupación (fase 1), no se influye de forma significativa en el tiempo total de permanencia del vehículo en la ruta; en cambio, una reagrupación de los clientes después del ruteo (fase 2), mejora considerablemente la duración total de la ruta, aunque en algunos casos, aumenta la distancia recorrida por el vehículo.
ABSTRACT
In this work, a method to solve a motorcycle messenger routing problem with time windows is presented. This has two phases: in the first one, clusters of clients are formed, each group is assigned to a route and each route is served by a vehicle; in the second phase, through a mixed integer linear programming model the routing for each cluster is made while respecting hard time windows of some clients. To validate the method, the mail delivery section of a shared service center in Cali - Colombia is used as case study The results show that, when testing different clustering methods (phase l) these do not significantly influence the vehicle's duration on the road; On the other hand, regrouping the clients after routing (phase 2) can considerably improve the total duration of the route, although in some cases, increasing the distance traveled by the vehicle.
RESUMO
Neste trabalho se apresenta um método para a solução do problema de roteiro de mensageiros de motocicleta com janelas de tempo. Nele identificam-se duas fases: na primeira, conformam-se grupos de clientes, cada grupo é atribuído a uma rota e cada uma delas é servida por um veículo; na segunda, por meio de um modelo de programação linear todo misto, faz-se um roteiro para cada uma das agrupações respeitando as janelas de tempo estritas de alguns clientes. Para validar o método, usou-se como caso de estudo a área de mensageria de um centro de serviços compartilhados na cidade de Cali, na Colômbia. Os resultados mostram que ao testar diferentes métodos de agrupamento (fase l), não influem de maneira significativa no tempo total de permanência do veículo na rota; por outro lado, um reagrupamento dos clientes após do roteiro (fase 2), melhora consideravelmente a duração total do percurso, porém em alguns casos, aumenta a distância percorrida pelo veículo.
PALABRAS CLAVE:Problema de ruteo de mensajeros en motocicletaservicio de mensajeríaventanas de tiempodistribución de correspondenciaprogramación lineal entera mixtaKEYWO RDS:Motorcycle messenger routing problemmail servicetime windowspostal deliverymixed integer linear programmingPALAVRAS-CHAVE:Problema de roteiro de mensageiros de motocicletaserviço de mensageriajanelas de tempodistribuição de correioprogramação inteira misturadaIntroducción
La mensajería es un servicio importante para las organizaciones y la sociedad en general. Sin embargo, el auge de los servicios de correspondencia electrónica ha provocado el declive a las unidades de negocio orientadas al correo postal (Coelho et al., 2016). Las empresas especializadas compiten principalmente con los proveedores de mensajería exprés, razón por la cual se ven obligados a reducir costos operativos y tiempos de atención a los clientes (Cetiner, Sepil y Sural, 2010). Para alcanzar estos objetivos se han implementado sistemas automatizados y software que permiten una ventaja competitiva para consolidarse en el largo plazo dentro del sector servicios de mensajería postal (Coelho et al., 2016).
Los trabajos acerca del ruteo de vehículos para problemas de mensajería y envío de pequeños paquetes, están orientados a mejorar principalmente dos indicadores: el tiempo de llegada, orientado al servicio; y los costos de operación, orientando a la eficiencia.
Entre los enfoques para la reducción del tiempo de llegada del paquete a los clientes se incluyen: El mejoramiento de los tiempos de respuesta y ventanas de tiempo (Larsen, Madsen y Solomon, 2004), atención a clientes con horarios restringidos y tiempos de atención aleatorios (Sungur et al.; 2010 citado por Coelho et al., 2016), modificación de rutas de forma dinámica para atender nuevos clientes durante el recorrido (Khouadjia, Sarasola, Alba, Jourdan y Talbi, 2012).
El costo de operación ha sido abordado desde la reducción de la distancia recorrida para vehículos de capacidades diferentes (Ji y Chen, 2007; Winkenbach, Kleindorfer y Spinler, 2016), la optimización del uso de vehículos y personal (Hollis, Forbesc Douglas, 2006), la eliminación y fusión de rutas para reducir tiempos de recorrido (Pignac-Robitaille et al. 2014 citado por Coelho et al., 2016), y la consolidación de centros de distribución para el mejoramiento en eficiencia relacionada con el tamaño de la flota (Cetiner et al., 2010; Matis, 2008).
El panorama actual del mercado ha obligado a las empresas de mensajería a concentrarse en los dos indicadores mencionados anteriormente: Costo de operación y reducción de tiempo de recorrido. La búsqueda de mayor eficiencia ha provocado la transformación de las flotas, lo que las ha hecho mucho más flexibles, de bajo costo y de respuesta más rápida. Mejorar el servició implica mayor flexibilidad y respuesta rápida, lo que condicionó ajustar la flota a las necesidades actuales y también el conjunto de técnicas de gestión para estas.
Así pues, la mensajería motorizada se ajusta a las ideas de flexibilidad, bajo costo y respuesta rápida. Lo que requiere un esfuerzo importante en la planeación, el control y la comunicación. Uno de los sub-problemas más relevantes de esta actividad, y que más incide en la eficiencia del servicio, es la definición de rutas para los mensajeros. Este problema pertenece a una categoría mayor conocida como VRP, por sus siglas en inglés (Vehicle Routing Problem).
El VRP es reconocido por su complejidad, ya que tiene diferentes variantes. Para el caso de la mensajería, la variante del VRP corresponde a la llamada: Ruteo de vehículos con ventanas de tiempo (VRPTW). Entendemos al servicio de mensajería como un servicio en el cual vehículos, en este caso de estudio: motocicletas, deben llegar a los clientes dentro de unos intervalos de tiempo establecido previamente dentro del proceso de planeación. El VRPTW es un problema de optimización combinatoria clasificado como NP-Hard. El VRPTW considera a las motocicletas como idénticas, con una capacidad limitada y utilizada para atender un cierto número de clientes situados en una región de cobertura.
Durante el desarrollo del servicio, las motocicletas parten de una central de entregas y al finalizar su respectiva ruta deben volver a esta. La distancia entre clientes, los tiempos de recorrido, las demandas y el número de motocicletas disponible son predeterminados en procesos iniciales de planeación. El VRPTW debe resolver la distancia o el tiempo de recorrido total de las motocicletas al mínimo, pero a diferencia del clásico problema de ruteo con capacidades (CVRP), se deben respetar los horarios de atención de los clientes y el depósito. (Alzaqebah, Abdullah y Jawar-neh, 2016; Pecin, Contardo, Desaulniers y Uchoa, 2017; Wu, Dong, Li y Li, 2016; Zhang, Cai, Ye, Si y Nguyen, 2017).
El VRPTW se usa en otras múltiples empresas, tanto del sector industrial como de servicios, como por ejemplo: recolección de residuos, distribución de correo postal y paquetería (Abbatecola, Fanti, Mangini y Ukovich, 2016; Coelho, Renaud y Laporte, 2016; Irnich, Lagana, Schlebusch y Vo-caturo, 2015), servicios de atención médica domiciliara (Haddadene, Labadie y Prodhon, 2016), distribución de bienes y servicios para una misma organización (Pu et al., 2017), ruteo de buses escolares (Irnich et al., 2015), distribución de combustibles, gas, alimentos perecederos y refrigerados bajo venta minorista (Coelho et al., 2016), entre otros.
En ese sentido, y bajo esta perspectiva, el presente trabajo propone una metodología de dos fases para dar una solución al problema de ruteo de mensajeros que consideran ventanas de tiempo. El problema se considera cerrado ya que las motocicletas deben regresar al centro de despacho una vez se termine la ruta.
Este trabajo está organizado de la siguiente manera: en el primer capítulo se realiza una revisión de los principales métodos utilizados para la solución de VRPTW; en el segundo capítulo, se explican las dos fases del método propuesto para la solución de este tipo de problemas; en el tercer capítulo, se presenta el caso de estudio del servicio de mensajería de una empresa de servicios compartidos; en el cuarto capítulo, se muestran gráficamente los resultados obtenidos al aplicar el método de dos fases con diferentes técnicas de agrupación (fase 1) con el mismo modelo de ruteo (fase 2); en el quinto capítulo, se hace una análisis de los resultados obtenidos, se reconocen algunas limitaciones del método, y se proponen agrupaciones alternativas que mejoran los resultados de aquellas creadas con la fase 1; para finalizar, se hacen conclusiones acerca de todo lo anterior.
1. Revisión de métodos de solución
Los enfoques de solución para el VRPTW se pueden clasificar en 3 categorías generales:
Métodos exactos: con este enfoque se garantiza una solución óptima para todas las instancias del problema (Baldacci, Toth y Vigo, 2010; Fisher, 1994; Floudas, Pardalos y York, 2009); sin embargo, dado que el VRPTW es un problema de optimización combinatoria, no es viable desde el punto de vista computable utilizar métodos exactos para solucionar problemas relativamente grandes, por ejemplo, un caso de 100 o más clientes de VRP (Baldacci, Christofides y Mingozzi, 2008; Fukasawa et al., 2006). Es decir, el número de clientes puede ser menor para el VRPTW. Debido a que en la práctica es muy común encontrar problemas de cientos y de hasta miles de clientes, es más común el uso de heurísticas y metaheurísticas, ya que ofrecen soluciones relativamente cercanas al óptimo en un tiempo considerablemente menor (Laporte, 2009).
Las heurísticas: son métodos adaptados al problema que se quiere resolver (Funke, Grünert y Irnich, 2005), por lo tanto, pueden haber muchas heurísticas para cada variación del VRPTW, como por ejemplo: el algoritmo de los ahorros (Anbuudayasankar, Ganesh, Koh y Ducq, 2012; Yu, Yang y Yao, 2011), heurística del barrido (Repoussis, Tarantilis y loannou, 2009), y heurísticas de dos fases (Prescott-Gagnon, Desaulniers y Rousseau, 2009).
Las metaheurísticas: no están adaptadas a cada problema de ruteo en particular, sino que, son un marco de solución para problemas de optimización combinatorios, el cual puede ejecutar varios métodos de búsqueda para encontrar una solución en un tiempo de computación razonable, algunas de ellas son: búsqueda local (Miranda y Conceicao, 2016), búsqueda tabú (Schneider, 2015; Zhang et al., 2017), búsqueda en vecindario variable (Kytöjoki, Nuortio, Bräysy y Gendreau, 2007), algoritmo genético (Koç, Bekta§, Jabali y Laporte, 2015), algoritmo de colonia de hormigas (Ding, Hu, Sun y Wang, 2012), y colonia artificial de abejas (Alzaqebah et al., 2016; Zhang et al., 2017).
En este trabajo se propone un método híbrido de dos fases: la primera, usa una técnica de agrupación que asigna los clientes a una determinada ruta, y la segunda, por medio de un modelo de programación lineal entera mixta, establece la secuencia de dichas rutas. A este enfoque de solución se le denomina «agrupar primero, rutear después», en la literatura se pueden encontrar varios trabajos que utilizan esta metodología, como lo de (Abbatecola et al., 2016; Hedar y Bakr, 2014; Matis, 2008;Yang y Bard, 2017), aunque, principalmente orientada a la solución de CVRP y m-TSP (Multiple Traveling Salesman Problem).
2. Diseño metodológico2.1. Definición de indicadores
El indicador de desempeño por excelencia de un ruteo es la distancia recorrida (Laporte, 2009; Taha, 2004). Sin embargo, debido a la presencia de ventanas de tiempo, un recorrido óptimo no necesariamente reduce el tiempo de permanencia en la ruta, pues el vehículo a pesar de haber recorrido la mínima distancia posible podría tener tiempo de inactividad al esperar ser atendido por determinado cliente. Si bien, reducir la distancia recorrida es importante para medir el desempeño de un ruteo, en este caso no puede ser el único indicador.
En este orden de ideas, en este trabajo se consideran los siguientes indicadores:
Tiempo de recorrido: tiempo que los vehículos utilizan para desplazarse entre clientes.
Tiempo de inactividad: cuando hay ventanas de tiempo en una ruta, es el tiempo que debe esperar un vehículo para que sea atendido por determinado cliente.
Tiempo variable: es el tiempo dependiente del ruteo, es decir, la suma del tiempo de recorrido y el tiempo de inactividad.
Tiempo de servicio: tiempo de atención para cada cliente, se asume constante y no depende del ruteo.
Tiempo de permanencia en la ruta: es la suma del tiempo variable y el tiempo de servicio. En otras palabras, cuanto demora el vehículo desde que sale hasta que llega nuevamente al depósito.
2.2. Descripción del método
Según la literatura, al enfoque utilizado por el siguiente método se le denomina como «asignación y ruteo». Este consta de dos fases: en la primera, se agrupan los clientes que serán atendidos por un mismo vehículo, para este fin, se comparan 3 técnicas de agrupación: la heurística de los ahorros de Clerk y Wright (El-Sherbeny, 2010), la heurística del barrido de Gillett y Miller (El-Sherbeny, 2010), y la p-mediana (Kusiak, 1987). En la segunda fase, una vez hechas las agrupaciones, se determina cuál es la ruta que debe seguir dicho vehículo de tal forma que se minimice su tiempo de permanencia en la ruta, en este caso se utiliza un modelo de programación lineal entera mixta para resolver VRPTW (Cordeau et. al., 1999 citado por Olivera, 2004).
Cada una de las tres técnicas de agrupación se implementa por separado, y a cada conjunto de grupos el modelo de la segunda fase (sección 2.3) determinará el orden de visita de los clientes y horario de partida de los vehículos del depósito.
2.3. Formulación del modelo
A continuación, se formula matemáticamente el modelo y se hace una breve descripción de cada una de las expresiones del mismo.
Conjuntos
N= Nodos
Índices
i,j,k= Nodos
c= Nodo salida del depósito
f= Nodo llegada al depósito
Parámetros
tij= Tiempo de recorrido entre el nodo i y el nodo j
Si= Tiempo de atencion o espera en el nodo i
ei= Horarío de apertura del nodo i
li= Horario de cierre del nodo i
M= Número entero muy grande
Variables
1: Al vehículo se le asigna el recorrido entre los
xij= clientes iyj
0:Cualquier otro caso
yi= Hora de arribo del vehículo al cliente i
Función objetivo
Minimizar Z=yf-yc
La función objetivo minimiza el tiempo de permanencia en la ruta, lo cual implica, disminuir la diferencia entre la hora de llegada y la hora de salida del vehículo al depósito.
Restricciones
(l) El vehículo debe salir del depósito hacia algún nodo j.
(2) Cada cliente debe ser visitado por un vehículo.
(3) Restricción de balance: si un vehículo visita a un cliente k desde un nodo i, ese mismo vehículo debe abandonar el nodo k hacia otro nodo j.
(4) Restricción para la asignación de los horarios de llegada a cada nodo y de eliminación subtours «circuito entre un grupo de clientes que no incluyen ni al depósito ni a los demás clientes» (Paredes y Obreque, 2009): La diferencia entre las horas de arribo a un cliente i y el cliente j sucesor en la ruta debe ser mayor o igual al tiempo de servicio del cliente i mas el tiempo de recorrido desde el cliente i al cliente j.
(5) Restricción de ventanas de tiempo: la hora de llegada de un vehículo a un cliente debe ser después de la hora de apertura pero, debe llegar con el tiempo suficiente para ser atendido sin que el cliente cierre.
(6) Definición de la variable binaria para asignación de los recorridos entre las sedes ij.
(7) Definición de la variable para la asignación de la hora de llegada a la sede i como un número real mayor o igual a cero.
3. Caso de estudio
Con el objetivo de validar el enfoque de solución propuesto, se realiza la asignación y el ruteo para el área de mensajería de una empresa de servicios compartidos. Desde esta área, se centraliza y se distribuye la correspondencia entre las distintas sedes del grupo y otros interesados externos con el objetivo de generar ahorros para todo el consorcio en general.
El área de mensajería cuenta con 10 vehículos que se usan principalmente en 2 tareas: 1) mensajería entre sedes, que se realiza todos los días hacia las otras empresas del consorcio con unos horarios y sedes preestablecidas. 2) Mensajería externa: son los envíos desde cualquiera de las empresas del grupo, que se consolidan en el departamento de mensajería, hacia destinarios diferentes a las sedes que se recorren rutinariamente. Siempre se prioriza la mensajería entre sedes. Cuando los 10 mensajeros no dan abasto, se opta por subcontratar parte de la mensajería externa con una empresa especializada en este servicio.
Por esta razón, es importante reducir el tiempo que se emplea en las tareas de mensajería entre sedes, para que de esta forma, los mensajeros de planta puedan cubrir una mayor parte de la demanda de mensajería externa, reduciendo los costos de tercerizar parte de esta unidad de negocio.
Se dispone de un solo depósito desde el cual los mensajeros inician el recorrido y deben volver una vez han recorrido toda su ruta. Se deben atender 35 sedes de las cuales 7 tienen ventanas de tiempo (Tabla 1).
Horario de apertura y cierre de las sedes con ventanas de tiempo.
Sede
Horario de apertura
Parámetro horario de apertura
Horario de cierre
Parámetro horario de cierre
1
8:00
30
8:40
70
3
8:00
30
8:20
50
10
10:00
150
12:00
270
11
8:00
30
8:10
40
23
9:00
90
9:20
110
28
8:10
40
8:30
60
34
10:00
150
10:10
160
Fuente: Los autores.
Se utiliza el mínimo de vehículos suficiente para satisfacer la demanda. Cada vehículo tiene una capacidad de 25 kg, la suma de la demanda de todas las sedes es 119,2 kg, por lo tanto, se usan 5 vehículos.
Los mensajeros tienen 300 minutos para entregar todos los envíos entre las 7:30 y las l2:30, por lo tanto, los parámetros de horario de apertura y horario de cierre deben escribirse como un número entre 0 (7:30) y 300 (12:30). El parámetro horario de cierre debe ser mayor que el horario de apertura. La diferencia entre ambos horarios debe ser mayor o igual al tiempo de servicio para esa sede (Anexo 1).
En la Tabla 1 se mencionan a todas aquellas sedes que tienen un horario de apertura o cierre diferente a la duración del turno de la mañana de los mensajeros.
4. Resultados
En esta sección se presentan los resultados obtenidos al correr el modelo de ruteo para cada conjunto de clientes generado con cada uno de los 3 métodos de agrupación. El modelo matemático se transcribió en el lenguaje de optimización AMPL, y para la ejecución del código se utilizó SCIP® de la página NEOS SOLVERS.
4.1. Heurística de los ahorros
La Tabla 2 muestra la secuencia de las rutas representadas por la Figura 1, los destinos en esta tabla subrayados y en negrita son aquellos clientes que tienen ventanas de tiempo. Con esta distribución de rutas, el tiempo empleado por los mensajeros para realizar las diligencias entre sedes sería de 6551 minutos.
Secuencia de las rutas con el algoritmo de los ahorros.
Fuente: Los autores.
Diagrama esquemático de las rutas con la heurística de los ahorros.
Fuente: Los autores.
4.2. Heurística del barrido
Utilizando la heurística del barrido se agruparon nuevamente las sedes. Los resultados que arrojó el modelo para esta agrupación se muestran en la Figura 2. En este caso, el tiempo de permanencia en la ruta es de 659,5 minutos. (Ver Tabla 3).
Consolidado de rutas con la heurística del barrido.
Fuente: Los autores.
Secuencia de rutas con la heurística del barrido.
Fuente: Los autores.
4.3. Modelo de p-mediana con restricciones de capacidad
En la Tabla 4 se muestran los resultados con p-mediana, para este caso el tiempo de permanencia en la ruta es de 637,8 minutos. Los resultados de esta agrupación se evidencian en la Figura 3.
Consolidado de rutas con modelo de p-mediana.
Fuente: Los Autores.
5. Discusión de los resultados
Claramente, estas técnicas de agrupación clásicas no están diseñadas para resolver problemas de ruteo con ventanas de tiempo (VRPTW), sino problemas de ruteo de vehículos con capacidad limitada (CVRP). A pesar de todo, el método tiene un gran desempeño para todas aquellas rutas que tienen una sola ventana tiempo, porque en muchas ocasiones, el resultado sería igual al de la solución de un CVRP para estas rutas en específico.
Sin embargo, cuando la ruta tiene dos o más sedes con horarios restringidos pero distantes entre sí (distantes en tiempo), y el tiempo de servicio y recorrido para los demás clientes no permiten cubrir la diferencia entre el cierre de la primera sede con la apertura de la última sede (Ruta 1 con método de los ahorros), se presentan tiempos de inactividad (Ruta 3).
En esta sección se analiza el impacto de las técnicas de agrupación en el ruteo, y se proponen alternativas para reducir significativamente los tiempos de inactividad.
5.1. Comparación entre técnicas de agrupación
Las diferentes técnicas de agrupación tienen incidencia, aunque no significativa, en el desempeño del modelo de ruteo. La mayor diferencia se da entre el modelo p-mediana y la heurística del barrido: 21,7 minutos (12 %); seguida por la diferencia entre la heurística del barrido y p-mediana: 17,3 minutos (9,5 %); y finalmente, un margen de 4,4 minutos (2,2 %) entre las heurísticas de los ahorros y barrido. La comparación se hace aún más pequeña si se tiene que todas las sedes se combinan para un gran total de 457 minutos de tiempo de servicio, dando como resultado un 3,4 % de diferencia entre barrido y p-mediana, un 2,7 % entre ahorros y p-mediana, y un 0,7 % entre ahorros y barrido.
Comparación de diferentes métodos de agrupación.
Fuente: Los autores.
Un aspecto llamativo de las 3 soluciones, concentran todo el tiempo de inactividad en la ruta 3. La causa de este problema es que las formas de agrupación hacen énfasis en la distancia (tiempo de recorrido) que hay entre los clientes, más no en sus ventanas de tiempo. La ruta 3 tiene la particularidad de poseer dos o tres clientes (según el método de agrupación) con ventanas de tiempo, cuyos intervalos entre ellas son mayores que la suma del tiempo de recorrido y de servicio de los clientes sin ventanas de tiempo visitados durante dichos intervalos.
5.2. Reducción de tiempos de inactividad
Se muestran nuevas agrupaciones que reducen los tiempos de inactividad. Para este fin, las tres distribuciones conformadas anteriormente se tomarán como ejemplo.
5.2.1. Agregar más clientes a la ruta con tiempo de inactividad
Si la capacidad de los vehículos lo permite, es conveniente agregar clientes cercanos que pertenezcan a una ruta a aquella que presenta tiempo de inactividad. En la distribución que se hizo mediante el algoritmo de los ahorros (Figura 1) fue posible agregar los clientes 7 y 8 a la ruta 3.
De esta forma, se redujo el tiempo total que se requiere para hacer la ruta 4, a la cual pertenecían los clientes 7 y 8, y se elimina casi por completo el tiempo de inactividad de la ruta 3 (Figura 4).
Consolidado de rutas con algoritmo de los ahorros (modificado).
Fuente: Los autores.
Para los otros métodos de agrupación se excedía el límite de capacidad de los mensajeros al agregar clientes cercanos de otras rutas a la ruta 3. A continuación, se proponen más alternativas.
Como se expresó con anterioridad, para reducir el tiempo de inactividad en la ruta 3, a ésta se le agregaron los clientes 7 y 8, que antes pertenecían a la ruta 4, estas sedes no tienen ventanas de tiempo, y su demanda no viola el límite de capacidad de los auxiliares de mensajería. Con esta modificación, la solución del modelo ha mejorado en 27,2 minutos respecto de la elaborada originalmente con el algoritmo de los ahorros (Tabla 6). A pesar de que el tiempo de recorrido aumentó en 11,9 minutos, el tiempo de inactividad de la ruta 3 disminuyó 39,1 minutos.
Secuencia de ruta con el algoritmo de los ahorros (modificado).
Fuente: Los autores.
5.2.2. Asignar un vehículo adicional a la zona de un cliente con ventana de tiempo
Para eliminar el tiempo de inactividad de la ruta 3 de la distribución cuyos clientes fueron agrupados con la heurística del barrido (Figura 2). Se dividió en dos regiones el área ocupada por los clientes de esta ruta. Los clientes 30 y 34 quedaron agrupados para que sean atendidos por un sexto mensajero. Los clientes 24, 26, 28 y 29 aun serían parte de la ruta 3 (Figura 5).
Adición de un vehículo a la ruta 3 de la heurística del barrido.
Fuente: Los autores.
Con la nueva agrupación fue posible eliminar el tiempo de inactividad de 35,2 minutos, y mejorar el tiempo de recorrido de la distribución en 8,6 minutos para un ahorro total de 43,8 minutos.
Cabe observar, que el tiempo de recorrido de la ruta 3 es ineficiente. Al modelo de ruteo le es indiferente si en los 90 minutos entre el cierre de la sede 28 y la apertura de la sede 34 (Tabla 1) el mensajero: 1) espera más tiempo frente a la puerta a que el último cliente del recorrido le atienda, o 2) gasta ese tiempo recorriendo las sedes en cualquier orden. (Tabla 7).
Comparación entre ruta 3 original y la nueva para la heurística del barrido.
Fuente: Los autores.
5.2.3. Agrupar nuevamente los clientes con un vehículo adicional
En este caso, se tiene en consideración a todos los clientes y se realiza una nueva agrupación utilizando los mismos criterios del ruteo previo. En el siguiente ejemplo, se muestra el ruteo realizado con los clientes agrupados con el modelo de p-mediana (Figura 6) pero, en vez de 5 para 6 vehículos, y agregando una restricción que impida que los clientes 34 y 28 (cuyas ventanas de tiempo están separadas por más de 90 minutos) queden agrupados en una misma ruta.
La Tabla 4 muestra a tres clientes con ventanas tiempo asignados a la ruta 3, sin embargo, al realizar nuevamente las agrupaciones con el modelo de p-mediana con 6 vehículos, al menos una ruta debía quedar con dos de estos clientes. En este caso, al existir la restricción anteriormente mencionada, la ruta 3 siguió conservando, en la nueva agrupación, las sedes 28 y 23, resultando en un pequeño tiempo de inactividad de 0,9 minutos. A pesar de que se redujo el tiempo de inactividad del sistema en 19 minutos, el recorrido se hizo más ineficiente, resultando en un ahorro de tan solo 7,2 minutos (Tabla 8).
Secuencia de las rutas con p-mediana (modificado).
Fuente: Los autores.
Consolidado de rutas con modelo de p-mediana (modificado). Fuente: Los autores.
5.3. Comparación entre todas las agrupaciones después de eliminar tiempos de inactividad
La eliminación de los tiempos de inactividad tiene un gran impacto en el resultado del modelo, incluso mayor que el método de agrupación mismo (Figura 6). Si bien, con este i ejercicio no se puede decidir qué método de agrupación es mejor, si se pueden destacar algunas características deseables en las agrupaciones que mejoran sustancialmente el tiempo variable:
Un mayor aprovechamiento de la capacidad de los vehículos implica un mayor tiempo variable cuando las rutas tienen más de una ventana de tiempo: en las agrupaciones de la sección de resultados se asignó una capacidad combinada de 125 kg (5 mensajeros) para 119,2 kg de demanda (95,36 % de la capacidad). Si bien, en un CVRP es deseable utilizar una menor cantidad de vehículos porque se mejora el tiempo de recorrido (o «distancia recorrida» que es un indicador más utilizado), en el VRPTW esto no necesariamente es así, porque se hace más difícil la eliminación de los tiempos de inactividad al asignar sedes a otra ruta (sección 4.2.1.), y en caso de poder hacerse, es inevitable desmejorar el tiempo de recorrido (método de los ahorros modificado).
Más vehículos pueden reducir el tiempo de inactividad: puede ser preferible que un mensajero disponible (o el mismo) atienda a un cliente con una ventana de tiempo muy distante, a esperar el horario de apertura de dicho cliente (sección 4.2.2.).
Más vehículos pueden reducir el tiempo de recorrido: ventanas de tiempo muy distantes pueden ocasionar recorridos ineficientes como en la ruta 3 del método de los ahorros y del método del barrido (sección 3.1 y 3.2). (Ver Figura 7)
Comparación del tiempo variable para cada técnica de agrupación antes y después de la eliminación del tiempo de inactividad.
Fuente: Los autores.
6. Conclusiones
De los resultados presentados y de su discusión se puede obtener las siguientes conclusiones:
El método propuesto de agrupación y ruteo es efectivo al solucionar problemas para vehículos con capacidad limitada y clientes con ventanas de tiempo, más allá de que las técnicas utilizadas en la fase de agrupación no tengan en cuenta los horarios de apertura y cierre de los clientes, la fase de ruteo arroja un buen diseño de rutas para cada uno de los 3 métodos de asignación utilizados.
Las técnicas de agrupación son fáciles e intuitivas de aprender, y el software para correr el modelo de optimización es gratuito y accesible al público, por lo que esta propuesta se puede implementar (ya se hizo en el área de mensajería del caso de estudio) para resolver problemas de ruteo de vehículos con ventanas de tiempo de pequeña y mediana escala (menos de 100 clientes).
Una gran diferencia entre los horarios de cierre y apertura en dos o más clientes de una misma ruta, además de generar tiempo de inactividad en el vehículo que la atiende, puede causar que el modelo de ruteo (fase 2) programe una secuencia ineficiente, inflando artificialmente el tiempo de recorrido de dicho vehículo, aunque, el tiempo de permanencia en la ruta (función de desempeño a minimizar en la fase 2) permanezca igual. En otras palabras, para el modelo de ruteo la distancia recorrida del mensajero podría llegarle a ser indiferente en tanto de que el tiempo de permanencia en la ruta ya ha sido optimizado.
Es necesaria una holgura en la capacidad promedio utilizada en los vehículos para tener la posibilidad de eliminar los tiempos de inactividad que las dos fases no tienen en cuenta; de esta forma, se pueden implementar estrategias como: intercambiar clientes entre rutas adyacentes, agregar más vehículos que atiendan específicamente a aquellos clientes que tienen un horario de apertura tardío con relación al cierre de otro nodo con horario restringido en la misma ruta, entre otras. Estas estrategias generan un gran impacto en el tiempo variable del problema (gráfico 7) sin importar que en algunos casos esto implique un leve aumento del tiempo de recorrido.
Las técnicas para disminuir el tiempo de inactividad (sección 4.2) se pueden interpretar como una nueva forma de agrupar los clientes, sólo que, a diferencia de la fase 1, si tiene en cuenta los tiempos de inactividad. Por lo tanto, una manera de mejorar el método actual podría ser crear una tercera fase que identifique secuencialmente aquellos clientes que ocasionan tiempo de inactividad y genere nuevas agrupaciones que lo minimicen, pero, sin incrementar el tiempo de permanencia en la ruta de todo el problema.
Referencias bibliográficas1. ABBATECOLA, L., FANTI, M.P., MANGINI, A.M. y UKOVICH, W. A Decision Support Approach for Postal Delivery and Waste Collection Services. In: IEEE Transactions On Automation Science And Engineering. 2016. vol.13, no. 4, pp. 1458-1470. ISSN 1545-5955. DOI 10.1109/TASE.2016.2570121.ABBATECOLAL.FANTIM.P.MANGINIA.M.UKOVICHWA Decision Support Approach for Postal Delivery and Waste Collection ServicesIEEE Transactions On Automation Science And Engineering2016134145814701545-595510.1109/TASE.2016.25701212. ALZAQEBAH, M., ABDULLAH, S. y JAWARNEH, S. Modified artificial bee colony for the vehicle routing problems with time windows. In: SpringerPlus. 2016. vol. 5. ISSN 2193-1801. DOI 10.1186/s40064-016-2940-8.ALZAQEBAHM.ABDULLAHS.JAWARNEHSModified artificial bee colony for the vehicle routing problems with time windowsSpringerPlus201652193-180110.1186/s40064-016-2940-83. ANBUUDAYASANKAR, S., GANESH, K., KOH, S. y DUCQ, Y. Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls. In: Expert Syst. Appl. 2012. vol. 39, pp. 2296-2305.ANBUUDAYASANKARS.GANESHK.KOHS.DUCQYModified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhaulsExpert Syst. Appl201239229623054. BALDACCI, R., CHRISTOFIDES, N. y MINGOZZI, A. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. In: Mathematical Programming. 2008. vol. 115, no. 2, pp. 351-385. ISSN 00255610. DOI 10.1007/s10107-007-0178-5.BALDACCIR.CHRISTOFIDESN.MINGOZZIAAn exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cutsMathematical Programming2008115235138510.1007/s10107-007-0178-55. BALDACCI, R., TOTH, P. y VIGO, D. Exact algorithms for routing problems under vehicle capacity constraints. In: Annals of Operation Research. 2010. vol. 1, no. 175, pp. 213-245. https://doi.org/10.1007/s10479-009-0650-0.BALDACCIR.TOTHP.VIGODExact algorithms for routing problems under vehicle capacity constraintsAnnals of Operation Research20101175213245https://doi.org/10.1007/s10479-009-0650-06. CETINER, S., SEPIL, C. y SURAL, H. Hubbing and routing in postal delivery systems. In: Annals Of Operations Research. 2010. vol. 181, no. 1, pp. 109-124. ISSN 0254-5330. https://doi.org/10.1007/s10479-010-0705-2.CETINERS.SEPILC.SURALHHubbing and routing in postal delivery systemsAnnals Of Operations Research20101811109124https://doi.org/10.1007/s10479-010-0705-27. COELHO, L.C., RENAUD, J. y LAPORTE, G. Road-based goods transportation: a survey of real-world logistics applications from 2000 to 2015. In: INFOR. 2016. vol. 54, no. 2, pp. 79-96. ISSN 0315-5986. https://doi.org/10.1080/03155986.2016.1167357.COELHOL.C.RENAUDJ.LAPORTEGRoad-based goods transportation: a survey of real-world logistics applications from 2000 to 2015INFOR20165427996https://doi.org/10.1080/03155986.2016.11673578. DING, Q., HU, X., SUN, L. y WANG, Y. An improved ant colony optimization and its application to vehicle routing problem with time windows. In: Neurocomputing. 2012. vol. 98, pp. 101-107. https://doi.org/10.1016/j.neucom.2011.09.040.DINGQ.HUX.SUNL.WANGYAn improved ant colony optimization and its application to vehicle routing problem with time windowsNeurocomputing201298101107https://doi.org/10.1016/j.neucom.2011.09.0409. EL-SHERBENY, N.A. Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods. Journal of King Saud University - Science [en línea]. 2010. vol. 22, no. 3, pp. 123-131. http://dx.doi.org/10.1016/j.jksus.2010.03.002. ISSN 10183647. DOI 10.1016/j.jksus.2010.03.002.EL-SHERBENYN.AVehicle routing with time windows: An overview of exact, heuristic and metaheuristic methodsJournal of King Saud University - Science2010223123131http://dx.doi.org/10.1016/j.jksus.2010.03.00210.1016/j.jksus.2010.03.00210. FISHER, M.L. Optimal solution of vehicle routing problems using minimum K-trees. In: Operations Research. 1994. vol. 42, pp. 626-642. ISSN 0030-364X. Disponible en https://www.jstor.org/stable/171617?seq=1#page_scan_tab_contents.FISHERM.LOptimal solution of vehicle routing problems using minimum K-treesOperations Research199442626642https://www.jstor.org/stable/171617?seq=1#page_scan_tab_contents11. FLOUDAS, C.A. y PARDALOS, P.M. Encyclopedia of optimization. 2nd Edition. New York: Springer New York LLC. 2009.FLOUDASC.A.PARDALOSP.MEncyclopedia of optimization2New YorkSpringer New York LLC200912. FUKASAWA, R., LONGO, H., LYSGAARD, J., DE ARAGAO, M.P., REIS, M., UCHOA, E. y WERNECK, R.F. Robust branch-and-cut-and-price for the capacitated vehicle routing problem. In: Mathematical Programming. 2006. vol. 106, no. 3, pp. 491-511. ISSN 00255610. https://doi.org/10.1007/s10107-005-0644-x.FUKASAWAR.LONGOH.LYSGAARDJ.DE ARAGAOM.P.REISM.UCHOAE.WERNECKR.FRobust branch-and-cut-and-price for the capacitated vehicle routing problemMathematical Programming20061063491511https://doi.org/10.1007/s10107-005-0644-x13. FUNKE, B., GRÜNERT, T. y IRNICH, S. Local search for vehicle routing and scheduling problems: review and conceptual integration. in: Journal of heuristics. 2005. vol. 11, no. 4 SRC-GoogleScholar FG-0, pp. 267-306. https://doi.org/10.1007/s10732-005-1997-2FUNKEB.GRÜNERTT.IRNICHSLocal search for vehicle routing and scheduling problems: review and conceptual integrationJournal of heuristics2005114SRC-GoogleScholar FG-0267306https://doi.org/10.1007/s10732-005-1997-214. HADDADENE, S.R.A., LABADIE, N. y PRODHON, C. A. GRASP x ILS for the vehicle routing problem with time windows, synchronization and precedence constraints. In: Expert Systems With Applications. 2016. vol. 66, pp. 274-294. ISSN 0957-4174. https://doi.org/10.1016/j.eswa.2016.09.002.HADDADENES.R.A.LABADIEN.PRODHONC. AGRASP x ILS for the vehicle routing problem with time windows, synchronization and precedence constraintsExpert Systems With Applications2016662742940957-4174https://doi.org/10.1016/j.eswa.2016.09.00215. HEDAR, A.R. y BAKR, M. Three Strategies Tabu Search for Vehicle Routing Problem with Time Windows. In: Computer Science and Information Technology. 2014. vol. 2, no. 2, pp. 108-119. http://www.hrpub.org/journals/article_info.php?aid=1141.HEDARA.R.BAKRMThree Strategies Tabu Search for Vehicle Routing Problem with Time WindowsComputer Science and Information Technology201422108119http://www.hrpub.org/journals/article_info.php?aid=114116. HOLLIS, B.L., FORBES, M.A. y DOUGLAS, B.E. Vehicle routing and crew scheduling for metropolitan mail distribution at Australia Post. In: European Journal Of Operational Research. 2006. vol. 173, no. 1, pp. 133-150. ISSN 0377-2217. https://doi.org/10.1016/j.ejor.2005.01.005.HOLLISB.L.FORBESM.A.DOUGLASB.EVehicle routing and crew scheduling for metropolitan mail distribution at Australia PostEuropean Journal Of Operational Research20061731133150https://doi.org/10.1016/j.ejor.2005.01.00517. IRNICH, Stefan, LAGANA, Demetrio, SCHLEBUSCH, Claudia y VOCATURO, Francesca. Two-phase branch-and-cut for the mixed capacitated general routing problem. In: European Journal Of Operational Research. 2015. vol. 243, no. 1, pp. 17-29. ISSN 0377-2217. https://doi.org/10.1016/j.ejor.2014.11.005.IRNICHStefanLAGANADemetrioSCHLEBUSCHClaudiaVOCATUROFrancescaTwo-phase branch-and-cut for the mixed capacitated general routing problemEuropean Journal Of Operational Research201524311729https://doi.org/10.1016/j.ejor.2014.11.00518. JI, P. y CHEN, K. The vehicle routing problem: The case of the Hong Kong postal service. In: Transportation Planning And Technology. 2007. vol. 30, no. 2-3, pp. 167-182. ISSN 0308-1060. https://doi.org/10.1080/03081060701390841.JIP.CHENKThe case of the Hong Kong postal serviceTransportation Planning And Technology2007302-3167182https://doi.org/10.1080/0308106070139084119. KHOUADJIA, M.R., SARASOLA, B., ALBA, E., JOURDAN, L. y TAL-BI, E.-G. A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests. Applied Soft Computing. 2012. vol. 12, no. 4, pp. 1426-1439. ISSN 1568-4946. https://doi.org/10.1080/03081060701390841.KHOUADJIAM.R.SARASOLAB.ALBAE.JOURDANL.TAL-BIE.-GA comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requestsApplied Soft Computing201212414261439https://doi.org/10.1080/0308106070139084120. KOÇ, Ç.; BEKTAÇ, T.; JABALI, O. y LAPORTE, G. A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows. In: Computers Operations Research. 2015. vol. 64, pp. 11-27 https://doi.org/10.1016/j.cor.2015.05.004KOÇÇ.BEKTAÇT.JABALIO.LAPORTEGA hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windowsComputers Operations Research2015641127https://doi.org/10.1016/j.cor.2015.05.00421. KUSIAK, Andrew. The generalized group technology concept. International In: Journal of Production Research. 1987. vol. 25, no. 4, pp. 561-569. https://doi.org/10.1080/00207548708919861.KUSIAKAndrewThe generalized group technology concept. InternationalJournal of Production Research1987254561569https://doi.org/10.1080/0020754870891986122. KYTÖJOKI, Jari; NUORTIO, Teemu; BRÄYSY, Olli y GENDREAU, Michel. An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. In: Computers & Operations Research. 2007. vol. 54, pp. 811-819. https://doi.org/10.1016/j.cor.2005.10.010.KYTÖJOKIJariNUORTIOTeemuBRÄYSYOlliGENDREAUMichelAn efficient variable neighborhood search heuristic for very large scale vehicle routing problemsComputers & Operations Research200754811819https://doi.org/10.1016/j.cor.2005.10.01023. LAPORTE, Gilbert. Fifty Years of Vehicle Routing. In: Transportation Science. 2009. vol. 43, no. 4, pp. 408-416. https://doi.org/10.1287/trsc.1090.0301.LAPORTEGilbertFifty Years of Vehicle RoutingTransportation Science2009434408416https://doi.org/10.1287/trsc.1090.030124. LARSEN, Allan; MADSEN, Oli B.G. y SOLOMON, Marius M. The A priori dynamic traveling salesman problem with time windows. In: Transportation Science. 2004. vol. 38, no. 4, pp. 459-472. ISSN 0041-1655. https://doi.org/10.1287/trsc.1030.0070.LARSENAllanMADSENOli B.G.SOLOMONMarius MThe A priori dynamic traveling salesman problem with time windowsTransportation Science2004384459472https://doi.org/10.1287/trsc.1030.007025. MATIS, Peter. Decision support system for solving the Street Routing Problem. In: Transport. 2008. vol. 23, no. 3, pp. 230-235. ISSN 1648-4142. https://doi.org/10.3846/1648-4142.2008.23.230-235.MATISPeterDecision support system for solving the Street Routing ProblemTransport2008233230235https://doi.org/10.3846/1648-4142.2008.23.230-23526. MIRANDA, Douglas Moura y CONCEIÇÃO, Samuel Vieira. The vehicle routing problem with hard time windows and stochastic travel and service time. In: Expert Systems with Applications. 2016. vol. 64, pp. 104-116. ISSN 0957-4174. https://doi.org/10.1016/j.eswa.2016.07.022.MIRANDADouglas MouraCONCEIÇÃOSamuel VieiraThe vehicle routing problem with hard time windows and stochastic travel and service timeExpert Systems with Applications201664104116https://doi.org/10.1016/j.eswa.2016.07.02227. OLIVERA, Alfredo. Heurísticas para problemas de ruteo de vehículos. Montevideo Uruguay Universidad de la República. 2004. https://www.fing.edu.uy/inco/pedeciba/bibliote/reptec/TR0408.pdf.OLIVERAAlfredoHeurísticas para problemas de ruteo de vehículos2004https://www.fing.edu.uy/inco/pedeciba/bibliote/reptec/TR0408.pdf28. PECIN, Diego; CONTARDO, Claudia; DESAULNIERS, Guy y UCHOA, Eduardo. New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows. In: Informs Journal On Computing. 2017. vol. 29, no. 3, pp. 489-502. ISSN 1091-9856. https://doi.org/10.1287/ijoc.2016.0744.ECINDiegoCONTARDOClaudiaDESAULNIERSGuyUCHOAEduardoNew Enhancements for the Exact Solution of the Vehicle Routing Problem with Time WindowsInforms Journal On Computing2017293489502https://doi.org/10.1287/ijoc.2016.074429. PRESCOTT-GAGNON, Eric; DESAULNIERS, Guy y ROUSSEAU, Louis-Martin. A branch-and-price-based large neighborhood search algorithm for the vehicle routing problem with time windows. In: Networks. 2009. vol. 54, pp. 190-204. https://doi.org/10.1002/net.20332.PRESCOTT-GAGNONEricDESAULNIERSGuyROUSSEAULouis-MartinA branch-and-price-based large neighborhood search algorithm for the vehicle routing problem with time windowsNetworks200954190204https://doi.org/10.1002/net.2033230. PU, Enlai; WANG, Fei; YANG, Zongliang; WANG, Jun; LI, Zhiming y HUANG, Xin. Hybrid Differential Evolution Optimization for the Vehicle Routing Problem with Time Windows and Driver-Specific Times. In: Wireless Personal Communications. 2017. vol. 95, no. 3, pp. 2345-2357. ISSN 0929-6212. https://doi.org/10.1007/s11277-017-4107-5.PUEnlaiWANGFeiYANGZongliangWANGJunLIZhimingHUANGXinHybrid Differential Evolution Optimization for the Vehicle Routing Problem with Time Windows and Driver-Specific TimesWireless Personal Communications201795323452357https://doi.org/10.1007/s11277-017-4107-531. REPOUSSIS, Panagiotis; TARANTILIS, Christos D. y IOANNOU, George. Arcguided evolutionary algorithm for the vehicle routing problem with time windows. In: IEEE Trans. Evol. Comput. 2009. vol. 13, pp. 624-647. ISSN 1063-6560. https://doi.org/10.1109/TEVC.2008.2011740.REPOUSSISPanagiotisTARANTILISChristos D.IOANNOUGeorgeArcguided evolutionary algorithm for the vehicle routing problem with time windowsIEEE Trans. Evol. Comput200913624647https://doi.org/10.1109/TEVC.2008.201174032. SCHNEIDER, M. The vehicle-routing problem with time windows and driver-specific times. In: European Journal of Operational Research. 2015. vol. 250 no. 1, pp. 101-119. https://doi.org/10.1016/j.ejor.2015.09.015.SCHNEIDERMThe vehicle-routing problem with time windows and driver-specific timesEuropean Journal of Operational Research20152501101119https://doi.org/10.1016/j.ejor.2015.09.01533. TAHA, H. Investigación de operaciones. 7ma edición. México: Pearson Educación. 2004.TAHAHInvestigación de operaciones7MéxicoPearson Educación200434. WINKENBACH, Matthias; KLEINDORFER, Paul R. y SPINLER, Stefan. Enabling Urban Logistics Services at La Poste through Multi-Echelon Location-Routing. In: Transportation Science. 2016. vol. 50, no. 2, SI, pp. 520-540. ISSN 0041-1655. https://doi.org/10.1287/trsc.2015.0624.WINKENBACHMatthiasKLEINDORFERPaul R.SPINLERStefanEnabling Urban Logistics Services at La Poste through Multi-Echelon Location-RoutingTransportation Science2016502SI520540https://doi.org/10.1287/trsc.2015.062435. WU, D.Q., DONG, M., LI, H.Y. y LI, F. Vehicle Routing Problem With Time Windows Using Multi-Objective Co-Evolutionary Approach. In: International Journal of Simulation Modelling. 2016. vol. 15, no. 4, pp. 742-753. ISSN 1726-4529. https://doi.org/10.2507/1JS1MM15(4)CO19.WUD.Q.DONGM.LIH.Y.LIFVehicle Routing Problem With Time Windows Using Multi-Objective Co-Evolutionary ApproachInternational Journal of Simulation Modelling2016154742753https://doi.org/10.2507/1JS1MM15(4)CO1936. YANG, Y. y BARD, J.F. Internal mail transport at processing & distribution centers. In: IISE Transactions. 2017. vol. 49, no. 3, pp. 285-303. ISSN 2472-5854. https://doi.org/10.1080/0740817X.2016.1217104.YANGY.BARDJ.FInternal mail transport at processing & distribution centersIISE Transactions2017493285303https://doi.org/10.1080/0740817X.2016.121710437. YU, B., YANG, Z. y YAO, B. A hybrid algorithm for vehicle routing problem with time windows. In: Expert Syst Appl. 2011. vol. 48, pp. 435-441. https://doi.org/10.1016/j.eswa.2010.06.082.YUB.YANGZ.YAOBA hybrid algorithm for vehicle routing problem with time windowsExpert Syst Appl201148435441https://doi.org/10.1016/j.eswa.2010.06.08238. ZHANG, D., CAI, S., YE, F., SI, Y.-W. y NGUYEN, T.T. A hybrid algorithm for a vehicle routing problem with realistic constraints. In: Information Sciences. 2017. vol. 394, pp. 167-182. ISSN 0020-0255. https://doi.org/10.1016/j.ins.2017.02.028.ZHANGD.CAIS.YEF.SIY.-W.NGUYENT.TA hybrid algorithm for a vehicle routing problem with realistic constraintsInformation Sciences2017394167182https://doi.org/10.1016/j.ins.2017.02.028
http://dx.doi.org/10.18041/entramado.2018v14n1.27120 Este es un artículo Open Access bajo la licencia BY-NC-SA (https://creativecommons.org/licenses/by-nc-sa/4.0/) Publicado por Universidad Libre - Cali, Colombia.
ARBOLEDA-CASTILLO, John Jairo; HEREDIA-GIRALDO, Alan David; OREJUELA-CABRERA, Juan Pablo. Método de dos fases para e problema de ruteo de mensajeros en motocicleta con ventanas de tiempo. En: Entramado. Enero - Junio, 2018. vol. 14, no. 1, p. 268-281
Los autores declaran no tener ningún conflicto de intereses.
Parámetros de coordenadas, demanda y tiempo de servicio.