Método de dos fases para el problema de ruteo de mensajeros en motocicleta con ventanas de tiempo
DOI:
https://doi.org/10.18041/entramado.2018v14n1.27106Palabras clave:
Problema de ruteo de mensajeros en motocicleta, servicio de mensajería, ventanas de tiempo, distribución de correspondencia, programación lineal entera mixtaResumen
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.
Descargas
Referencias
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
2. 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.
3. 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.
4. 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.
5. 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
6. 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
7. 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
8. 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
9. 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.
10. 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
11. FLOUDAS, C.A. y PARDALOS, P.M. Encyclopedia of optimization. 2nd Edition. New York: Springer New York LLC. 2009.
12. 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
13. 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-2
14. 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
15. 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
16. 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
17. 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
18. 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.
19. KHOUADJIA, M.R., SARASOLA, B., ALBA, E., JOURDAN, L. y TALBI, 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
20. 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.004
21. 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
22. 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
23. 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
24. 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
25. 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
26. 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
27. 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
28. 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
29. 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
30. 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
31. REPOUSSIS, Panagiotis; TARANTILIS, Christos D. y IOANNOU, George. Arc-guided 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
32. 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
33. TAHA, H. Investigación de operaciones. 7ma edición. México: Pearson Educación. 2004.
34. 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
35. 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/IJSIMM15(4)CO19
36. 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
37. 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
38. 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.
Publicado
Número
Sección
Licencia
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
