Implementation of a new matheuristic to solve the vehicle routing problem with simultaneous deliveries and pick-ups – VRPSPD


Authors

  • 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

Keywords:

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

Abstract

The objective of this article is to present a new methodology for solving the Homogeneous Vehicle Routing Problem with Simultaneous Pickups and Deliveries (VRPSPD). The methodology integrates a matheuristic using the Chu-Beasley genetic algorithm and mixed integer linear programming, based on the Branch-and-Bound procedure. The best configuration obtained from the genetic algorithm is improved through the use of constructive heuristic methods in determining sub-problems, which contribute to the creation of the initial population necessary in the stage of local improvement. The goal is to determine minimum-cost routes that satisfy the pick-up and delivery demands of a group of geographically dispersed customers, while considering the restrictions of the system and the number of vehicles required. The methodology is implemented in C++ and a solver CPLEX software is used to find the solution. Results from test instances in specialized literature demonstrate the efficiency of this new hybrid model, showing good results in short computation times. This article is based on the author's doctoral thesis in engineering and presents similar topics discussed in international congresses, which may explain the similarities in the consulted bibliographical references.

Downloads

Download data is not yet available.

Author Biographies

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.

References

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

Downloads

Published

2022-06-30

How to Cite

Ballesteros Silva, P. P. ., & Ballesteros Riveros, D. P. . (2022). Implementation of a new matheuristic to solve the vehicle routing problem with simultaneous deliveries and pick-ups – VRPSPD. Scientia Et Technica, 27(2), 97–108. https://doi.org/10.22517/23447214.23791

Issue

Vol. 27 No. 2 (2022): Abril- Junio

Section

Industrial

License

Copyright (c) 2021 Scientia et Technica

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Copyrights

The journal is free open access. The papers are published under the Creative Commons Attribution / Attribution-NonCommercial-NoDerivatives 4.0 International - CC BY-NC-ND 4.0 license. For this reason, the author or authors of a manuscript accepted for publication will yield all the economic rights to the Universidad Tecnológica of Pereira free of charge, taking into account the following:

In the event that the submitted manuscript is accepted for publication, the authors must grant permission to the journal, in unlimited time, to reproduce, to edit, distribute, exhibit and publish anywhere, either by means printed, electronic, databases, repositories, optical discs, Internet or any other required medium. In all cases, the journal preserves the obligation to respect, the moral rights of the authors, contained in article 30 of Law 23 of 1982 of the Government Colombian.

The transferors using ASSIGNMENT OF PATRIMONIAL RIGHTS letter declare that all the material that is part of the article is entirely free of copyright.  Therefore, the authors are responsible for any litigation or related claim to intellectual property rights. They exonerate of all responsibility to the Universidad Tecnológica of Pereira (publishing entity) and the Scientia et Technica journal. Likewise, the authors accept that the work presented will be distributed in free open access, safeguarding copyright under the Creative Commons Attribution / Recognition-NonCommercial-NoDerivatives 4.0 International - https://creativecommons.org/licenses/by-nc-nd/4.0/deed.es license.