A Comparative Study of the PSO and GA for the m-MDPDPTW

  • Essia Ben Alaia ENIT
  • Imen Harbaoui ENIT
  • Pierre Borne EC-Lille
  • Hanen Bouchriha ENIT

Abstract

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

[1] 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.

[2] 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.

[3] 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.

[4] 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.

[5] 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.

[6] 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

[7] 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

[8] 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.

[9] 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

[10] 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

[11] 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

[12] 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

[13] 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.

[14] 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.

[15] 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.

[16] 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.

[17] 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.

[18] 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

[19] 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

[20] 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

[21] 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
2018-02-12
How to Cite
BEN ALAIA, Essia et al. A Comparative Study of the PSO and GA for the m-MDPDPTW. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 13, n. 1, p. 8-23, feb. 2018. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/2970>. Date accessed: 13 july 2020. doi: https://doi.org/10.15837/ijccc.2018.1.2970.

Keywords

Particle Swarm Optimization (PSO), Genetic Algorithm (GA), Vehicle Routing Problem (VRP), Pick-up and Delivery Problem with Time Windows (PDPTW), m-MDPDPTW, optimization