A Comparative Study of the PSO and GA for the m-MDPDPTW
AbstractThe 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  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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International 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.