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

Essia Ben Alaia, Imen Harbaoui, Pierre Borne, Hanen Bouchriha

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.

Keywords


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

Full Text:

PDF

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




DOI: https://doi.org/10.15837/ijccc.2018.1.2970



Copyright (c) 2018 Imen Harbaoui Harbaoui, Essia Ben Alaia Ben Alaia, Pierre Borne Borne, Hanen Bouchriha Bouchriha

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

CC-BY-NC  License for Website User

Articles published in IJCCC user license are protected by copyright.

Users can access, download, copy, translate the IJCCC articles for non-commercial purposes provided that users, but cannot redistribute, display or adapt:

  • Cite the article using an appropriate bibliographic citation: author(s), article title, journal, volume, issue, page numbers, year of publication, DOI, and the link to the definitive published version on IJCCC website;
  • Maintain the integrity of the IJCCC article;
  • Retain the copyright notices and links to these terms and conditions so it is clear to other users what can and what cannot be done with the  article;
  • Ensure that, for any content in the IJCCC article that is identified as belonging to a third party, any re-use complies with the copyright policies of that third party;
  • Any translations must prominently display the statement: "This is an unofficial translation of an article that appeared in IJCCC. Agora University  has not endorsed this translation."

This is a non commercial license where the use of published articles for commercial purposes is forbiden. 

Commercial purposes include: 

  • Copying or downloading IJCCC articles, or linking to such postings, for further redistribution, sale or licensing, for a fee;
  • Copying, downloading or posting by a site or service that incorporates advertising with such content;
  • The inclusion or incorporation of article content in other works or services (other than normal quotations with an appropriate citation) that is then available for sale or licensing, for a fee;
  • Use of IJCCC articles or article content (other than normal quotations with appropriate citation) by for-profit organizations for promotional purposes, whether for a fee or otherwise;
  • Use for the purposes of monetary reward by means of sale, resale, license, loan, transfer or other form of commercial exploitation;

    The licensor cannot revoke these freedoms as long as you follow the license terms.

[End of CC-BY-NC  License for Website User]


INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL (IJCCC), With Emphasis on the Integration of Three Technologies (C & C & C),  ISSN 1841-9836.

IJCCC was founded in 2006,  at Agora University, by  Ioan DZITAC (Editor-in-Chief),  Florin Gheorghe FILIP (Editor-in-Chief), and  Misu-Jan MANOLESCU (Managing Editor).

Ethics: This journal is a member of, and subscribes to the principles of, the Committee on Publication Ethics (COPE).

Ioan  DZITAC (Editor-in-Chief) at COPE European Seminar, Bruxelles, 2015:

IJCCC is covered/indexed/abstracted in Science Citation Index Expanded (since vol.1(S),  2006); JCR2016: IF=1.374. .

IJCCC is indexed in Scopus from 2008 (SNIP2016 = 0.701, SJR2016 =0.319):

Nomination by Elsevier for Journal Excellence Award Romania 2015 (SNIP2014 = 1.029): Elsevier/ Scopus

IJCCC was nominated by Elsevier for Journal Excellence Award - "Scopus Awards Romania 2015" (SNIP2014 = 1.029).

IJCCC is in Top 3 of 157 Romanian journals indexed by Scopus (in all fields) and No.1 in Computer Science field by Elsevier/ Scopus.