Implementación de una nueva matheuristica para resolver el problema de ruteo de vehículos con entregas y recogidas simultáneos - VRPSPD


Autores/as

  • Pedro Pablo Ballesteros Silva Universidad Tecnológica de Pereira https://orcid.org/0000-0003-0777-7376
  • Diana Paola Ballesteros Riveros Servicio Nacional de Aprendizaje - SENA

DOI:

https://doi.org/10.22517/23447214.23791

Palabras clave:

Genetic algorithm is Chu – Beasley, heuristics, optimization, pick-up and delivery, vehicles routing.

Resumen

El objetivo de este artículo es presentar una nueva metodología para resolver el Problema de Encaminamiento de Vehículos Homogéneos con Recogidas y Entregas Simultáneas (VRPSPD). La metodología integra una matemática que utiliza el algoritmo genético Chu-Beasley y la programación lineal entera mixta, basada en el procedimiento Branch-and-Bound. La mejor configuración obtenida a partir del algoritmo genético se mejora mediante el uso de métodos heurísticos constructivos en la determinación de subproblemas, que contribuyen a la creación de la población inicial necesaria en la etapa de mejora local. El objetivo es determinar rutas de coste mínimo que satisfagan las demandas de recogida y entrega de un grupo de clientes dispersos geográficamente, teniendo en cuenta las restricciones del sistema y el número de vehículos necesarios. La metodología se implementa en C++ y se utiliza un software solver CPLEX para encontrar la solución. Los resultados de instancias de prueba en literatura especializada demuestran la eficiencia de este nuevo modelo híbrido, mostrando buenos resultados en tiempos de computación cortos. Este artículo está basado en la tesis doctoral en ingeniería del autor y presenta temas similares discutidos en congresos internacionales, lo que puede explicar las similitudes en las referencias bibliográficas consultadas.

Descargas

Los datos de descargas todavía no están disponibles.

Biografía del autor/a

Pedro Pablo Ballesteros Silva, Universidad Tecnológica de Pereira

Industrial Engineer, Production Engineering Specialist of the Francisco José de Caldas District University of Bogotá; Master in Operations Research and Statistics, PhD. in Engineering from the Technological University of Pereira.

Diana Paola Ballesteros Riveros, Servicio Nacional de Aprendizaje - SENA

D.P. Ballesteros Riveros. I am a professional with a global vision and research mentality. During 8 years of experience as Industrial Engineering, University Professor and Master in Economic and Financial Administration, I have demonstrated my ability to generate and implement initiatives to solve problems in public and private organizations, with a firm commitment to sustainable development, and a high sense of ownership and responsibility.

Citas

H. Min. "The multiple vehicle routing problem with simultaneous delivery and pick up points". Transportation Research. Vol. 23. No. 5, pp. 377-386, 1989. DOI: https://doi.org/10.1016/0191-2607(89)90085-X

P. Belrea and H. Yoshizaki. "Heuristic methods for the fleet size and mix vehicle routing problem with time windows and split deliveries". European Journal of Operational Research-ELSEVIER. Part B 40. pp. 589-601, 2013, DOI: https://doi.org/10.1016/j.cie.2012.11.007

Y. Dumas, J. Desrosiers and F. Soumis. "The pickup and delivery problem with time windows". European Journal of Operational Research-ELSEVIER.Vol.54,pp.7-22, 1991. DOI: https://doi.org/10.1016/0377-2217(91)90319-Q

A. Fabri and P. Recht. "On dynamic pickup and delivery vehicle routing with several time windows and waiting times". European Journal of Operational Research-ELSEVIER. Part B 40. pp. 335-350, 2006. DOI: https://doi.org/10.1016/j.trb.2005.04.002

J. Fan. "The vehicle routing problem with simultaneous pickup and delivery based on customer satisfaction". European Journal of Operational Research-ELSEVIER, pp. 5284- 5289, 2011,DOI: https://doi.org/10.1016/j.proeng.2011.08.979

I. Gribkovskaiaa, G. Laporte and A. Shyshou, "The single vehicle routing problem with deliveries and selective pickups". European Journal of Operational Research-ELSEVIER. Part B 40. pp. 2908-2924, 2008. DOI: https://doi.org/10.1016/j.cor.2007.01.007

I. Karaoglan, F. Altiparmak, I. Kara, I., & Dengiz, B. "A branch and cut algorithm for the location routing problem with simultaneous pickup and delivery". European Journal of Operational Research-ELSEVIER. pp. 318-332, 2011. DOI: https://doi.org/10.1016/j.ejor.2011.01.003

F. Hennig, B. Nygreena, K. C. Furmanb, and J. Song, "Alternative approach¬es to the crude oil tanker routing and scheduling problem with split pickup and split delivery", European Journal of Operational Research - ELSEVIER, vol. 243, pp.41-51, 2015. DOI: https://doi.org/10.1016/j.ejor.2014.11.023

M. Nowak, O. Ergun and C. White III Chelsea. "An empirical study on the benefit of split loads with the pickup and delivery problem". European Journal of Operational Research-ELSEVIER. Part B 40, pp. 734-740, 2009. DOI: https://doi.org/10.1016/j.ejor.2008.09.041

S. N. Parragh, K. F. Doerner, R. F. Hartl. "A survey on pickup and delivery problems" Part II: Transportation between pickup and delivery locations. Institut fur Betriebswirtschaftslehre, Universitat Wien Brunnerstr. 72, 1210 Wien, Austria, 2008. DOI: https://doi.org/10.1007/s11301-008-0036-4

H. Wang and Y. Chen. "A coevolutionary algorithm for the flexible delivery and pickup problem with time windows". European Journal of Operational Research-ELSEVIER. International Journal of Production Economics. pp. 4-13, 2013. DOI: https://doi.org/10.1016/j.ijpe.2012.04.011

E. Zachariadis, C. D. Tarantilis, and C.T. Kiranoudisb, "The vehicle rout¬ing problem with simultaneous pickups and deliveries and two-dimensional loading constraints", European Journal of Operational Research - ELSEVIER, vol. 251, pp. 369-386, 2016. DOI: https://doi.org/10.1016/j.ejor.2015.11.018

A. Subramanian, E. Uchoa, A. Alves Pessoa, and L. Satoru Ochi, "Branch and cut with lazy separation for the vehicle routing problem with simultane¬ous pickup and delivery". European Journal of Operational Research-ELSEVI¬ER, vol. 39, Issue 5, pp. 338-341, 2011. DOI: https://doi.org/10.1016/j.orl.2011.06.012

Y. Li, H. Chen, and C. Prins, "Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved re¬quests", European Journal of Operational Research - ELSEVIER, vol. 252, pp. 27-38, 2016.

DOI: https://doi.org/10.1016/j.ejor.2015.12.032

M. Dell 'Amico, G. Righini, and M. Salani. "A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection". Transportation Science, 40(2), pp. 235-247, 2006, DOI: https://doi.org/10.1287/trsc.1050.0118

T. Gschwind, "A comparison of column generation approaches to the syn¬chronized pickup and delivery problem", European Journal of Operational Research - ELSEVIER, vol. 247, pp. 60-71, 2015. DOI: https://doi.org/10.1016/j.ejor.2015.06.017

M. Gendreaua, J. Nossackb, and E. Pesch, "Mathematical formulations for a 1- full truckload pickup and delivery problem". European Journal of Opera¬tional Research - ELSEVIER, vol. 242, pp. 1008-1016, 2015. DOI: https://doi.org/10.1016/j.ejor.2014.10.053

O. Polata, C. B. Kalaycia, O. Kulaka, and H. Otto, "A perturbation based variable neighborhood search heuristic for solving the vehicle routing prob¬lem with simultaneous pickup and delivery with time limit", European Jour¬nal of Operational Research - ELSEVIER, vol. 242, pp. 369-382, 2015. DOI: https://doi.org/10.1016/j.ejor.2014.10.010

M. Cherkesly, G. Desaulniers, S. Irnich, and G. Laporte, "Branch price and cut algorithms for the pickup and delivery problem with time windows and multiple stacks", European Journal of Operational Research - ELSEVIER, vol. 250, pp. 782-793, 2016. DOI: https://doi.org/10.1016/j.ejor.2015.10.046

E. Zachariadis, C. D. Tarantilis, and C.T. Kiranoudisb, "The vehicle rout-ing problem with simultaneous pickups and deliveries and two-dimensional loading constraints", European Journal of Operational Research - ELSEVIER, vol. 251, pp. 369-386, 2016. DOI: https://doi.org/10.1016/j.ejor.2015.11.018

H. Hernández, I. Rodríguez, and J. J. Salazar, "A hybrid heuristic approach for the multi-commodity pickup and delivery traveling salesman problem", European Journal of Operational Research - ELSEVIER, vol. 251, pp. 44-52, 2016. DOI:

https://doi.org/10.1016/j.ejor.2015.10.053

Y. Li, H. Chen, and C. Prins, "Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved re¬quests", European Journal of Operational Research - ELSEVIER, vol. 252, pp. 27-38, 2016. DOI:

https://doi.org/10.1016/j.ejor.2015.12.032

A. Subramanian. (2012) "Heuristics exact and hybrid approaches for vehicle routing problems". Universidade Federal Fluminense. Tesis Doctoral. Niteroi. pp. 13, 17, 19. DOI: https://doi.org/10.1016/j.cor.2013.01.013

J. Dethloff. "Vehicle routing problem and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up" [Journal]. - Springer Berlin: Operation Research Spectrum, vol. 23, pp.79 -96, 2001, DOI: https://doi.org/10.1007/PL00013346

E. Zachariadis, C. Tarantilis and C. Kiranoudis. "A hybrid methaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick - up service" [Journal]. - [s.l.]: Expert System with Aplications, Vol. 36, Issue 2, part 1, pp. 1070 -1081, 2009. DOI: https://doi.org/10.1016/j.eswa.2007.11.005

N. Bianchessi and G. Righini. "Heuristic algorithms for the vehicle routing problem with simultaneous pickup and delivery" [Journal] // Computer and Operation Research Elsevier, vol.36 (12), pp.3215-3223, 2007, DOI: https://doi.org/10.1016/j.cor.2005.03.014

E. Cao and M. Lai. "An improved differential evolution algorithm for the vehicle routing problem with simultaneous pickups and deliveries and time windows". European Journal of Operational Research-ELSEVIER. Engineering Applications of Artificial Intelligence, pp. 188-195, 2009, DOI: https://doi.org/10.1016/j.engappai.2009.09.001

M. Dell'Amico, G. Righini, and M. Salani. "A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection". Transportation Science, 40(2), pp. 235-247, 2006, DOI:https://doi.org/10.1287/trsc.1050.0118

A. Subramanian, L. Satoru, E. Uchoa. "New Lower Bounds for the Vehicle Routing Problem with Simultaneous Pickup and Delivery". 9th International Symposium, SEA Ischia Island, Napoles, Italy, may 20/22, pp. 276-287, 2010. DOI: https://doi.org/10.1007/978-3-642-13193-6_24

L. Gouveia. "A result on projection for the vehicle routing problem". European Journal of Operational Research, pp. 610-624, 1995. DOI: https://doi.org/10.1016/0377-2217(94)00025-8

R. Gallego, E. Toro y A. Escobar, "Técnicas Heurísticas y Metaheurísticas", Colección de trabajos de Investigación Editorial UTP, pp.158-162, 2015. ISBN: 978-958-722-207-4

S. Salhi and G. A. Nagy. "A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling" [Journal]. - [s.l.]: Journal of the Operational Research Society, Vol. 50, no. 10, pp. 1034 - 1042, 1999. DOI: https://doi.org/10.1057/palgrave.jors.2600808

F.A.T Montané and R.D Galvao. "A tabu search algorithm for vehicle routing problem with simultaneous pickup and delivery services". European Journal of Operational Research, 33, 3 // Computers and Operation Research Elsevier, pp. 595 -619, 2006. DOI: https://doi.org/10.1016/j.cor.2004.07.009

A. Subramanian, L. M. A. Drummond, C. Bentes, L. S. Ochi, and R. Farias. "A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery". Computers & Operations Research, Vol. 37, Issue 11, pp. 1899-1911, 2010. DOI: https://doi.org/10.1016/j.cor.2009.10.011

Y. Gajpal and P. Abad. "An ant colony system (acs) for vehicle routing problem with simultaneous delivery and pickup". Computers & Operations Research, vol. 36 (12), pp. 3215-3223, 2009, DOI: https://doi.org/10.1016/j.cor.2009.02.017

Descargas

Publicado

2022-06-30

Cómo citar

Ballesteros Silva, P. P. ., & Ballesteros Riveros, D. P. . (2022). Implementación de una nueva matheuristica para resolver el problema de ruteo de vehículos con entregas y recogidas simultáneos - VRPSPD. Scientia Et Technica, 27(2), 97–108. https://doi.org/10.22517/23447214.23791

Número

Vol. 27 Núm. 2 (2022): Abril- Junio

Sección

Industrial

Licencia

Derechos de autor 2021 Scientia et technica

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.

Derechos de autor y licencias

La revista es de acceso abierto gratuito y sus artículos se publican bajo la licencia Creative Commons Atribución/Reconocimiento-No Comercial-Compartir bajo los mismos términos 4.0 Internacional — CC BY-NC-SA 4.0.

Los autores de un artículo aceptado para publicación cederán la totalidad de los derechos patrimoniales a la Universidad Tecnológica de Pereira de manera gratuita, teniendo en cuenta lo siguiente:  En caso de que el trabajo presentado sea aprobado para su publicación, los autores deben autorizar de manera ilimitada en el tiempo, a la revista para que pueda reproducirlo, editarlo, distribuirlo, exhibirlo y comunicarlo en cualquier lugar, ya sea por medios impresos,  electrónicos, bases de datos, repositorios, discos ópticos, Internet o cualquier otro medio  requerido.

Los cedentes mediante contrato CESIÓN DE DERECHOS PATRIMONIALES declaran que todo el material que forma parte del artículo está totalmente libre de derechos de autor de terceros y, por lo tanto, se hacen responsables de cualquier litigio o reclamación relacionada o reclamación relacionada con derechos de propiedad intelectual, exonerando de toda responsabilidad a la Universidad Tecnológica de Pereira (entidad editora) y a su revista Scientia et Technica. De igual forma, los autores aceptan que el trabajo que se presenta sea distribuido en acceso abierto gratuito, resguardando los derechos de autor bajo la licencia Creative Commons Atribución/Reconocimiento-No Comercial- Compartir bajo los mismos términos 4.0 Internacional — CC BY-NC-SA 4.0. 

 https://creativecommons.org/licenses/by-nc-sa/4.0/

A los autores, la revista Scientia et Technica tiene la obligación de respetarle los derechos morales (artículo 30 de la Ley 23 de 1982 del Gobierno Colombiano) que se les debe reconocen a estos la paternidad de la obra, el derecho a la integridad y el derecho de divulgación.  Estos no se pueden ceder ni renunciar.