A Comparative Study of the PSO and GA for the m-MDPDPTW
Keywords:
Particle Swarm Optimization (PSO), Genetic Algorithm (GA), Vehicle Routing Problem (VRP), Pick-up and Delivery Problem with Time Windows (PDPTW), m-MDPDPTW, optimizationAbstract
The m-MDPDPTW is the multi-vehicles, multi-depots pick-up and delivery problem with time windows. It is an optimization vehicles routing problem which must meet requests for transport between suppliers and customers for the purpose of satisfying precedence, capacity and time constraints. This problem is a very important class of operational research, which is part of the category of NP-hard problems. Its resolution therefore requires the use of evolutionary algorithms such as Genetic Algorithms (GA) or Particle Swarm Optimization (PSO). We present, in this sense, a comparative study between two approaches based respectively on the GA and the PSO for the optimization of m-MDPDPTW. We propose, in this paper, a literature review of the Vehicle Routing Problem (VRP) and the Pick-up and Delivery Problem with Time Windows (PDPTW), present our approaches, whose objective is to give a satisfying solution to the m-MDPDPTW minimizing the total distance travelled. The performance of both approaches is evaluated using various sets instances from [10] PDPTW benchmark data problems. From our study, in the case of m-MDPDPTW problem, the proposed GA reached to better results compared with the PSO algorithm and can be considered the most appropriate model to solve our m-MDPDPTW problem.References
Ben Alaia, E.; Harbaoui, D.I.; Bouchriha, H.; Borne, P. (2015); Genetic Algorithm for Multi- Criteria Optimization of Multi-Depots Pickup and Delivery Problem with Time Windows and multi vehicles, Acta Polytechnica Hungarica, 12(8), 155-174, 2015.
Ben Alaia, E.; Harbaoui, D.I.; Bouchriha, H.; Borne, P. (2015); Insertion of new depot locations for the optimization of multi-vehicles Multi-Depots Pickup and Delivery Problems using Genetic Algorithm, IEEE International Conference on Industrial Engineering and Systems Management, Seville, Spain, 695-701, 2015.
Ben Alaia, E.; Harbaoui, D.I.; Bouchriha, H.; Borne, P. (2015); Genetic Algorithm with Pareto Front selection for Multi-Criteria Optimization of Multi-Depots and multi- vehicle Pickup and Delivery Problems with Time Windows, IEEE International Conference on Sciences and Techniques of Automatic control and computer engineering, 21-23 December, Hammamet, Tunisie, 488-493, 2014.
Fatma, P.G.; Fulya, A.; Ismail, K. (2012); A Hybrid Particle Swarm Optimization for Vehicle Routing Problem with Simultaneous Pickup and Delivery, Computers and Industrial Engineering, 1-6, 2012.
Harbaoui, D.I., Ben Alaia, E.; Borne, P. (2015); Heuristic Approach for The Optimization of The Dynamic Multi-Vehicle Pickup and Delivery Problem with Time Windows, IEEE International Conference on Industrial Engineering and Systems Management, 21-23 October, Seville, Spain, 488-493, 2015.
Harbaoui, D.I.; Kammarti, R., Ksouri, M.; Borne, P. (2011); Multi-objective optimization for the mpdptw : Aggregation methode with use of genetic algorithm and lower bounds, International Journal of Computers Communications & Control, 6(2), 246-257, 2011. https://doi.org/10.15837/ijccc.2011.2.2172
Lau, H.C.W.; Chan, T.M.; Tsui, W.T.; Pang, W.K. (2010); Application of genetic algorithms to solve the multidepot vehicle routing problem, IEEE Transactions on Automation Science and Engineering, 7(2), 383-392, 2010. https://doi.org/10.1109/TASE.2009.2019265
Lei, W.; Fanhua, M. (2008); An Improved PSO for the Multi-Depot Vehicle Routing Problem with Time Windows, Pacific-Asia Workshop on Computational Intelligence and Industrial Application, 852-856, 2008.
Liu, R.; Xi, X.; Augusto, V.; Rodriguez, C. (2013); Heuristic algorithms fora vehicle routing problem with simultaneous delivery and pickup andtime windows in home health care, European Journal of Operational Research, 230(3), 475-486, 2013. https://doi.org/10.1016/j.ejor.2013.04.044
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, 2001. https://doi.org/10.1109/ICTAI.2001.974461
Marinakis, Y.; Iordanidou, G.R.; Marinaki, M (2013); Particle Swarm Optimization for the Vehicle Routing Problem with Stochastic Demands, Applied Soft Computing, 13 (4), 1693-1704, 2013. https://doi.org/10.1016/j.asoc.2013.01.007
Marinakis, Y.; Marinaki, M. (2010); Ahybrid genetic - particle swarm optimization algorithm for the vehicle routing problem, Expert Systems with Applications, 37(2), 1446-1455, 2010. https://doi.org/10.1016/j.eswa.2009.06.085
Nagata, Y.; Kobayashi, S. (2011); A memetic algorithm for the pickup and delivery problem with time windows using selective route exchange crossover, In: Schaefer R., Cotta C., Kolodziej J., Rudolph G. (eds), Parallel Problem Solving from Nature, PPSN XI. PPSN 2010. Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 6238, 536-545, 2011.
Ombuki, B. B.; Hansharin, F. (2009); Using genetic algorithms for multi depot vehicle routing, Studies in Computational Intelligence, 161, 77-99, Springer Berlin Heidelberg, 2009.
Pop, P.C.; Pop Sitar, C.; Zelina, I.; Lupse, V., Chira, C. (2011); Heuristic Algorithms for Solving the Generalized Vehicle Routing Problem, International Journal of Computers Communications & Control, 2011(1), 158-165, 2011.
Shuilong, Z.; Jin, L.; Xueqian, L. (2013); A Hybrid Particle Swarm Optimization Algorithm for Multi-Objective Pickup and Delivery Problem with Time Windows, Journal of Computers, 8(10),2583-2589, 2013.
Sombuntham, P., Kachitvichayanukul, V. (2010); A Particle Swarm Optimization Algorithm for Multi-depot Vehicle Routing problem with Pickup and Delivery Requests, The International MultiConference of Engineers and Computer Scientists, 1-6, 2010.
Vidal, T.; Crainic, T.G.; Gendreau, M., Prins, C. (2014); Implicit depot assignments and rotations in vehicle routing heuristics, European Journal of Operational Research, 237(1), 15-28, 2014. https://doi.org/10.1016/j.ejor.2013.12.044
Vidal, T.; Crainic, T G.; Gendreau, M.; Prins, C. (2013); Heuristics for multiattribute vehicle routing problems : a survey and synthesis, European Journal of Operational Research, 231(1), 1-21, 2013. https://doi.org/10.1016/j.ejor.2013.02.053
Vidal, T.; Crainic, T.G.; Gendreau, M.; Lahrichi, N.; Rei, W. (2012); A hybrid genetic algorithm for multi-depot and periodic vehicle routing problems, Operations Research, 60(3), 611-624, 2012. https://doi.org/10.1287/opre.1120.1048
Yousefikhoshbakht, M.; Didehvar, F.; Rahmati, F. (2014); An Efficient Solution for the VRP by Using a Hybrid Elite Ant System, International Journal of Computers Communications & Control, 9(3), 340-347, 2014. https://doi.org/10.15837/ijccc.2014.3.161
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
