1. bookVolume 22 (2021): Issue 3 (June 2021)
Journal Details
License
Format
Journal
First Published
20 Mar 2000
Publication timeframe
4 times per year
Languages
English
access type Open Access

Genetic Algorithm for the Pick-up and Delivery Problem with Time Window by Multi-Compartment Vehicles

Published Online: 22 Jun 2021
Page range: 343 - 352
Journal Details
License
Format
Journal
First Published
20 Mar 2000
Publication timeframe
4 times per year
Languages
English
Abstract

In this article we focus on multi-compartment vehicles that have to pick-up goods from suppliers and deliver them to various 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. 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 his customer. Our work consists firstly of mathematically modelling the problem described and secondly of solving it using methods due to its complexity. In this case we use the genetic algorithm to solve the pick-up and delivery problem of goods with a time window provided by multi-compartment vehicles. Our model allows to find a minimum distance and a minimum cost in the tour carried out by a reasonable number of vehicles.

Keywords

1. El Fallahi, A., Prins, C. et Wolfler Calvo, R. (2008) A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem, Computers & Operations Research, 35(5):1725-1741. Search in Google Scholar

2. AlChami, et al. (2018) An advanced GRASP-HGA combination to solve a multi-period Pickup and Delivery Problem, Expert Systems with Applications, 105, March 2018. Search in Google Scholar

3. Godart, A. (2019) Hybrid metaheuristic for the Pickup and Delivery Problem designed for passengers and goods transportation, IFAC-PapersOnLine, 52(13): 2584-2589, January 2019. Search in Google Scholar

4. Joseph, Cadet David. (2013) Optimisation des flux: application aux problèmes de distribution en nutrition animale, 2013TROY003, 18 décembre 2013. Search in Google Scholar

5. Goldberg, D. E. (1989) Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Professional, 1 edition, 1989. ISBN 0201157675. Search in Google Scholar

6. Kaabi, Hadhrami and Jabeur, Khaled (2015) International Conference on Informatics in Control, Automation and Robotics (ICINCO), Institute of Electrical and Electronics Engineers, pp. 21-23, July 2015. Search in Google Scholar

7. Li, H., Lim, A. (2001) A metaheuristic for the pickup and delivery problem with time windows. In: IEEE International Conference on Tools with Artificial Intelligence, 13, 160–167. Search in Google Scholar

8. Li, H., Lim, A., Rodrigues, B. (2002) Solving the pickup and delivery problem with time windows using squeaky wheel” optimization with local search. SMU Business Conference Paper Series. Search in Google Scholar

9. Alinaghian, Mahdi, et al. (2018) A Hybrid Algorithm Composed Of Adaptive Large Neighbourhood Search and Variable Neighbourhood Search PDPTW, Elsevier, 76, 85-99, April 2018. Search in Google Scholar

10. Harbaoui Dridi, Imen. (2011) Optimisation heuristique pour la résolution du m-PDPTW statique et dynamique, Int. J. of Computers, Communications & Control, ISSN 1841-9836, E-ISSN 1841-9844, Vol. VI, 246-257. Search in Google Scholar

11. Holland, J. H. (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor. Search in Google Scholar

12. Holland, J. H. (1992) Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Bradford Books. MIT Press. ISBN 9780262581110. Search in Google Scholar

13. Latif, Mehdi. (2018) Conception d’une métaheuristique pour la résolution du Pickup and Delivery Problem with Time Windows, pp. 7-8, 4 juin 2018. Search in Google Scholar

14. Ostermeier, M. (2018) Loading constraints for a multi-compartment vehicle routing problem, OR Spectrum, 40, 997–1027. Search in Google Scholar

15. Sol, M., Savelsbergh, M. (1994) A branch-and-price algorithm for the pickup and delivery problem with time windows. Memorandum COSOR 94-22, Dept. of Mathematics and Computing Science, Eindoven University of Technology, Eindoven, Netherlands. Search in Google Scholar

16. Kammarti, R. (2007) Approches Evolutionnistes Pour La Resolution Du 1-Pdptw Statique Et Dynamique, https://tel.archives-ouvertes.fr/tel-00143782, 25 mai 2007. Search in Google Scholar

17. Curtois, T. et al. (2018) Large neighborhood search with adaptive guided ejection search for the pickup and delivery problem with time windows, EURO Journal on Transportation and Logistics, 7, 151–192. Search in Google Scholar

18. Bukchin, Y., Sarin, Subhash C. (2006) Discrete and dynamic versus continuous and static loading policy for a multi-compartment vehicle, European Journal of Operational Research, 174(2), 1329-1337. Search in Google Scholar

19. Peng, Zh. et al. (2018) A Particle Swarm Optimization for Selective Pickup and Delivery Problem, Conference Paper, November 2018. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo