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

IAENG Internaitonal journal of computer science

Pierre Borne¹  Essia Ben Alaia²  Imen Harbaoui²  Hanen Bouchriha² 

[1] EC-Lille;ENIT

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

DOI  :  10.15837/ijccc.2018.1.2970

学科分类：计算机科学（综合）

来源: International Association of Engineers

【 摘 要 】

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.

【 授权许可】

CC BY