In this paper, a new multiobjective discrete particle swarm algorithm is presented for the Capacitated vehicle routing problem. The binary algorithm integrates particle displacement based on local attractors, a crowding distance as elitism policy and genetic operators. The proposed approach is first implemented on a set of well-known benchmarks for single-objective capacitated vehicle routing problems and compared to results underlined in the literature. The obtained results demonstrate its ability to achieve the main optimization solution and sometimes prove its efficiency from other given techniques. Then, the approach is applied to an academical example for the multiobjective Urban Bus Routing Problem with Route Balancing.
Keywords: Particle swarm optimization, multiobjective optimization, vehicle routing problems, Urban bus routing problems, simultaneous pick-up and delivery
@article{RO_2021__55_5_2599_0,
author = {Halassi Bacar, Abdoul-Hafar and Rawhoudine, Said Charriffaini},
title = {An attractors-based particle swarm optimization for multiobjective capacitated vehicle routing problem},
journal = {RAIRO. Operations Research},
pages = {2599--2614},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {5},
doi = {10.1051/ro/2021119},
mrnumber = {4316573},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021119/}
}
TY - JOUR AU - Halassi Bacar, Abdoul-Hafar AU - Rawhoudine, Said Charriffaini TI - An attractors-based particle swarm optimization for multiobjective capacitated vehicle routing problem JO - RAIRO. Operations Research PY - 2021 SP - 2599 EP - 2614 VL - 55 IS - 5 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021119/ DO - 10.1051/ro/2021119 LA - en ID - RO_2021__55_5_2599_0 ER -
%0 Journal Article %A Halassi Bacar, Abdoul-Hafar %A Rawhoudine, Said Charriffaini %T An attractors-based particle swarm optimization for multiobjective capacitated vehicle routing problem %J RAIRO. Operations Research %D 2021 %P 2599-2614 %V 55 %N 5 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021119/ %R 10.1051/ro/2021119 %G en %F RO_2021__55_5_2599_0
Halassi Bacar, Abdoul-Hafar; Rawhoudine, Said Charriffaini. An attractors-based particle swarm optimization for multiobjective capacitated vehicle routing problem. RAIRO. Operations Research, Tome 55 (2021) no. 5, pp. 2599-2614. doi: 10.1051/ro/2021119
[1] and , A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Comput. Oper. Res. 36 (2009) 1693–1702. | Zbl | DOI
[2] and , On Ant Colony Algorithms for Multiobjective Optimization, chap.5 in: Ant Colony Optimization – Methods and Applications, edited by . InTech (2011) 53–74.
[3] and , Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Comput. Oper. Res. 34 (2007) 578–94. | Zbl | DOI
[4] , and , Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. J. Zhejiang Univ. Sci. A 7 (2006) 607–614. | Zbl | DOI
[5] , , , , and , A novel set-based particle swarm optimization method for discrete optimization problems. IEEE Trans. Evol. Comput. 14 (2010) 278–300. | DOI
[6] , Discrete particle swarm optimization, illustrated by the traveling salesman problem. In: New Optimization Techniques in Engineering. Vol. 141 of Studies in Fuzziness and Soft Computing. Springer-Verlag, Berlin-Heidelberg (2004) 219–239. | Zbl | DOI
[7] and , MOPSO: a proposal for multiple objective particle swarm optimization. In: Vol. 2 of Congress on Evolutionary Computation. CEC’02 (2002) 1051–1056.
[8] and , The truck dispatching problem. Manage. Sci. 6 (1959) 80–91. | MR | Zbl | DOI
[9] and , Variable neighborhood search for a dynamic rich vehicle routing problem with time windows. Comput. Ind. Eng. 85 (2015) 120–131. | DOI
[10] , , and , A fast elitist nondominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In: Parallel Problem Solving from Nature VI Conference (2000) 849–858. | DOI
[11] , and , A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Transp. Sci. 40 (2006) 235–247. | DOI
[12] , Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR Spectr. 23 (2001) 79–96. | MR | Zbl | DOI
[13] and , The urban bus routing problem in the Tunisian case by the hybrid artificial ant colony algorithm. Swarm Evol. Comput. 2 (2012) 15–24. | DOI
[14] and , Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm. Appl. Soft Comput. 10 (2010) 1096–1107. | DOI
[15] , An attractor-based multiobjective particle swarm optimization. Int. J. Appl. Comput. Math. 3 (2017) 1019–1036. | MR | DOI
[16] , and , An empirical study on similarity-based mating for evolutionary multiobjective combinatorial optimization. Eur. J. Oper. Res. 188 (2008) 57–75. | Zbl | DOI
[17] , and , Multi-objective vehicle routing problems. Eur. J. Oper. Res. 189 (2008) 296–309. | MR | Zbl | DOI
[18] and , Particle swarm optimization. In: Proceedings of the Fourth IEEE International Conference on Neural Networks, Perth, Australia (1995). | DOI
[19] and , A discrete binary version of the particle swarm algorithm. In: Vol. 5 of 1997 IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation (1997) 4104–4108. | DOI
[20] and , Approximating the nondominated front using the Pareto archived evolution strategy. Evol. Comput. 8 (2000) 149–172. | DOI
[21] , , and , A new strategy for finding good local guides in MOPSO. In 2014 IEEE Congress on Evolutionary Computation (CEC) (2014) 1990–1997. | DOI
[22] , A non-dominated sorting particle swarm optimizer for multiobjective optimization. In: Genetic and Evolutionary Computation-GECCO 2003. Vol. 2723 ofLecture Notes in Computer Science. Springer-Verlag, Berlin-Heidelberg (2003) 37–48. | Zbl | DOI
[23] , , and , An improved MOPSO with a crowding distance based external archive maintenance strategy, edited by , and (eds)ICSI. Springer (2012) 74–82.
[24] , and , A hybrid particle swarm optimization algorithm for the vehicle routing problem. Eng. App. Artif. Intell. 23 (2010) 463–472. | DOI
[25] and , A particle swarm optimization algorithm for open vehicle routing problem. Expert Syst. App. 38 (2011) 11547–11551. | DOI
[26] and , Evaluation of the multiobjective ant colony algorithm performances on biobjective quadratic assignment problems. Appl. Math. Modell. 37 (2013) 7822–7838. | MR | DOI
[27] and , An effective use of crowding distance in multiobjective particle swarm optimization. In: Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation, GECCO’05. ACM (2005) 257–264. | DOI
[28] , and , A novel particle swarm optimization algorithm for multi-objective combinatorial optimization problem. Int. J. Appl. Metaheuristic Comput. (IJAMC) 2 (2012) 41–57. | DOI
[29] , , , , and , A metaheuristic for the school bus routing problem with bus stop selection. Eur. J. Oper. Res. 229 (2013) 518–528. | DOI
[30] , Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35 (1987) 254–265. | MR | Zbl | DOI
[31] , and , A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. Comput. Optim. App. 34 (2006) 115–151. | MR | Zbl | DOI
[32] and , A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Comput. Oper. Res. 33 (2006) 595–619. | MR | Zbl | DOI
[33] and , A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries. Comput. Ind. Eng. 62 (2012) 755–761. | DOI
[34] , , and , Particle swarm optimization: hybridization perspectives and experimental illustrations. Appl. Math. Comput. 217 (2011) 5208–5226. | Zbl
[35] and , editors. The Vehicle Routing Problem (Monographs on Discrete Mathematics and Applications). SIAM (2001). | Zbl | MR
[36] , , and , A novel probability binary particle swarm optimization algorithm and its application. J. Softw. 3 (2008) 28–35. | DOI
[37] , , and , A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup-delivery and time windows. Comput. Ind. Eng. 8 (2015) 111–122. | DOI
[38] , Integer Programming. John Wiley & Sons (1998). | MR | Zbl
[39] , , and , Multiobjective vehicle routing problem with route balance based on genetic algorithm. Discrete Dyn. Nat. Soc. 2013 (2013) 1–9. | DOI
[40] , and , SPEA2: improving the strength pareto evolutionary algorithm, edited by , , , and . In: EUROGEN 2001. Evolutionary Methods for Design, Optimization and Control With Applications to Industrial Problems (2000).
Cité par Sources :
