In this article, we focus on multi-compartment vehicles from different depots that have to collect goods from suppliers and deliver them to different customers. Usually these goods cannot be transported by single-compartment vehicles due to the fact that some products are harmful to others: incompatibility between products. Also, it should be noted that often the problems with a single depot include delays due to inter-municipal traffic jams, long distances and traffic accidents. It is necessary to create several depots closer and closer to the customers and suppliers in order to produce a quality service. It is therefore a question of satisfying a set of customers while respecting the constraints linked to the capacity of each vehicle compartment, each type of product and ensuring that each supplier is visited before its customer. Our work consists firstly in mathematical modeling the problem described and secondly in solving it. We use the genetic algorithm to solve the problem of pickup and delivery goods with a time window provided by multi-compartment vehicles distributed in several depots. Our model allows to find a minimum distance and a minimum cost in the tour carried out by a reasonable number of vehicles.

genetic algorithm, multi-compartment vehicles, PDPTW, multi-depots.

Received: November 26, 2020; Accepted: January 6, 2021; Published: January 22, 2021

How to cite this article: Berté Ousmane, Diaby Moustapha and Coulibaly Adama, Multi-compartment vehicles for multi-depots pickup and delivery problems with time windows, Far East Journal of Applied Mathematics 109(1) (2021), 49-66. DOI: 10.17654/AM109010049

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References

[1] Abdellah El Fallahi, Christian Prins and Roberto Wolfler Calvo, A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem, Computers & Operations Research 35(5) (2008), 1725-1741.
[2] Z. Al Chami, H. Manier, M.-A. Manier and E. Chebib, An advanced GRASP-HGA combination to solve a multi-period pickup and delivery problem, Expert Systems with Applications 105 (2018). DOI: 10.1016/j.eswa.2018.03.040.
[3] Alexis Godart, Hybrid metaheuristic for the pickup and delivery problem designed for passengers and goods transportation, IFAC-Papers Online 52(13) (2019), 2584-2589.
[4] Cadet David Joseph, Optimisation des flux: application aux problèmes de distribution en nutrition animale, 2013TROY003, 18 December 2013.
[5] David E Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Professional, 1 ed., 1989.
[6] E. Ben Alaia, I. Harbaoui, P. Borne and H. Bouchriha, A comparative study of the PSO and GA for the m-MDPDPTW, International Journal of Computers Communications and Control 13(1) (2018), 8-23.
[7] Essia Ben Alaia, I. Harbaoui Dridi, H. Bouchriha and P. Borne, Optimization of the multi-depot and multi-vehicle pickup and delivery problem with time windows using genetic algorithm, 2013 International Conference: Control, Decision and Information Technologies (CoDIT), 2013.
[8] Essia Ben Alaia, I. Harbaoui Dridi, H. Bouchriha and P. Borne, Insertion of new depot locations for the optimization of multi-vehicles multi-depots pickup and delivery problems using genetic algorithm, International Conference on Industrial Engineering and Systems Management (IESM), 2015.
[9] Hadhrami Kaabi and Khaled Jabeur, International Conference on Informatics in Control, Automation and Robotics (ICINCO), Institute of Electrical and Electronics Engineers, July 2015, pp. 21-23.
[10] H. Li and A. Lim, A metaheuristic for the pickup and delivery problem with time windows, IEEE International Conference on Tools with Artificial Intelligence, Vol. 13, 2001, pp. 160-167.
[11] H. Li, A. Lim and B. Rodrigues, Solving the pickup and delivery problem with time windows using squeaky wheel optimization with local search, SMU Business Conference Paper Series, 2002.
[12] Mahdi Alinaghian et al., A hybrid algorithm composed of adaptive large neighborhood search and variable neighborhood search PDPTW, Elsevier 76 (2018), 85-99.
[13] Imen Harbaoui Dridi, Optimisation heuristique pour la résolution du m-PDPTW statique et dynamique, International Journal of Computers Communications and Control VI (2011), 246-257.
[14] J. H. Holland, Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor, 1975.
[15] J. H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, Bradford Books, MIT Press, 1992.
[16] Latif Mehdi, Conception d’une métaheuristique pour la résolution du pickup and delivery problem with time windows, Université de Nantes, 2018, pp. 7-8.
[17] Manuel Ostermeier, Loading constraints for a multi-compartment vehicle routing problem, OR Spectrum 40 (2018), 997-1027.
[18] M. Sol and M. Savelsbergh, A branch-and-price algorithm for the pickup and delivery problem with time windows, Memorandum COSOR 94-22, Department of Mathematics and Computing Science, Eindoven University of Technology, Eindoven, The Netherlands, 1994.
[19] Ryan Kammarti, Approches Evolutionnistes Pour La Resolution Du 1-Pdptw Statique Et Dynamique, 2007. https://tel.archives-ouvertes.fr/tel-00143782.
[20] Timothy Curtois, Dario Landa-Silva, Yi Qu and Wasakorn Laesanklang, Large neighborhood search with adaptive guided ejection search for the pickup and delivery problem with time windows, EURO Journal on Transportation and Logistics 7 (2018), 151-192.
[21] Yossi Bukchin and Subhash C. Sarin, Discrete and dynamic versus continuous and static loading policy for a multi-compartment vehicle, European J. Oper. Res. 174(2) (2006), 1329-1337.
[22] Zhihao Peng, Zaher Chami, Hervé Manier and Marie-Ange Manier, A particle swarm optimization for selective pickup and delivery problem, Conference Paper, November 2018.