A PSO based algorithm with an efficient optimal split procedure for the multiperiod vehicle routing problem with profit
- PDF / 1,372,513 Bytes
- 36 Pages / 439.37 x 666.142 pts Page_size
- 119 Downloads / 211 Views
A PSO based algorithm with an efficient optimal split procedure for the multiperiod vehicle routing problem with profit Racha El-Hajj1 · Rym Nesrine Guibadj2
· Aziz Moukrim3 · Mehdi Serairi3
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The multiperiod vehicle routing problem with profit (mVRPP) is a selective vehicle routing problem where the planning horizon of each vehicle is divided into several periods. The aim of solving mVRPP is to design service itineraries so that the total amount of collected profit is maximized and the travel time limit of each period is respected. This problem arises in many real life applications, as the one encountered in cash-in-transit industry. In this paper, we present a metaheuristic approach based on the particle swarm optimization algorithm (PSO) to solve the mVRPP. Our approach incorporates an efficient optimal split procedure and dedicated local search operators proposed to guarantee high search intensification. Experiments conducted on an mVRPP benchmark show that our algorithm outperforms the state of the art metaheuristic approaches in terms of performance and robustness. Our PSO algorithm determines all the already known optimal solutions within a negligible computational time and finds 88 strict improvements among the 177 instances of the benchmark. Keywords Multiperiod vehicle routing problem with profit · Metaheuristic · Particle swarm optimization · Optimal split · Local search
B
Rym Nesrine Guibadj [email protected] Racha El-Hajj [email protected] Aziz Moukrim [email protected] Mehdi Serairi [email protected]
1
Faculté de génie, Université Libanaise, Campus Hadath, Beirut, Lebanon
2
Laboratoire d’Informatique Signal et Image de la Côte d’Opale, Université du Littoral Côte d’Opale, 62228 Calais, France
3
Université de Technologie de Compiègne, CNRS Heudiasyc UMR 7253, CS 60 319, Sorbonne Universités, 60 203 Compiègne Cedex, France
123
Annals of Operations Research
1 Introduction The vehicle routing problem (VRP) represents a wide concern in the real life applications (Koyuncu and Yavuz 2019). Several variants of VRP were proposed in the literature and many solution methods were developed to separately respond to each of these applications (Dantzig and Ramser 1959). By limiting the maximum traveling time allowed for a vehicle, the selectivity was introduced and the well-known orienteering problem (OP) was proposed for the case of one vehicle and was later generalized to consider a fleet of vehicles in the team orienteering problem (TOP) (Butt and Cavalier 1994). In TOP, a positive profit is assigned to each customer and the objective is to select the set of customers to serve in order to maximize the total collected profit without exceeding traveling time limit of each vehicle. Several restrictions were added to TOP to respond to new needs, as vehicle with limited capacity (Ben-Said et al. 2019; Chena et al. 2018) and time window for each customer (Labadie et al. 2012). Although, the single-p
Data Loading...
