Voir la notice de l'article provenant de la source Numdam
The Vehicle Routing Problem with Simultaneous Pickups and Deliveries (VRPSPD) is a variant of the Vehicle Routing Problem. In this variant, an unlimited fleet of capacitated vehicles is used to satisfy both pickup and delivery demands of each customer simultaneously. In many practical situations, such a fleet is costly. The present study extends the VRPSPD by assuming a fixed number of vehicles when the constraint of visiting all customers is relaxed. More specifically, profits are assigned to the customers with the goal of maximizing the difference between collected profits and routing costs. This variant is named Profitable Tour Problem with Simultaneous Pickup and Delivery services (PTPSPD). We present a mathematical model run with the CPLEX solver. We also present an extension of the Adaptive Large Neighborhood Search heuristic (ALNS) called selective ALNS (sALNS). sALNS uses a new operator selection that executes two phases alternately: the random and the score-dependent phases. An appropriate update of scores is employed. Furthermore, sALNS explores missed regions of the search space by evaluating solutions after the destruction step. Finally, we give tuned insertion and removal operators that handle the constraints of the PTPSPD, as well as a new update of temperature, that helps avoiding local optima, in the Simulated Annealing embedded in sALNS. sALNS is evaluated on 117 new instances with 50–199 customers. A comparison is made between the components of sALNS, the classical ALNS and a recent ALNS heuristic from the literature. sALNS is also evaluated on some VRPSPD instances from the literature. The computational results show that our heuristic provides good quality solutions in reasonable computing time.
Chentli, Hayet 1 ; Ouafi, Rachid 1 ; Cherif-Khettaf, Wahiba Ramdane 1
@article{RO_2018__52_4-5_1295_0,
author = {Chentli, Hayet and Ouafi, Rachid and Cherif-Khettaf, Wahiba Ramdane},
title = {A selective adaptive large neighborhood search heuristic for the profitable tour problem with simultaneous pickup and delivery services},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {1295--1328},
publisher = {EDP-Sciences},
volume = {52},
number = {4-5},
year = {2018},
doi = {10.1051/ro/2018024},
zbl = {1411.90044},
mrnumber = {3884162},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2018024/}
}
TY - JOUR AU - Chentli, Hayet AU - Ouafi, Rachid AU - Cherif-Khettaf, Wahiba Ramdane TI - A selective adaptive large neighborhood search heuristic for the profitable tour problem with simultaneous pickup and delivery services JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2018 SP - 1295 EP - 1328 VL - 52 IS - 4-5 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2018024/ DO - 10.1051/ro/2018024 LA - en ID - RO_2018__52_4-5_1295_0 ER -
%0 Journal Article %A Chentli, Hayet %A Ouafi, Rachid %A Cherif-Khettaf, Wahiba Ramdane %T A selective adaptive large neighborhood search heuristic for the profitable tour problem with simultaneous pickup and delivery services %J RAIRO - Operations Research - Recherche Opérationnelle %D 2018 %P 1295-1328 %V 52 %N 4-5 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2018024/ %R 10.1051/ro/2018024 %G en %F RO_2018__52_4-5_1295_0
Chentli, Hayet; Ouafi, Rachid; Cherif-Khettaf, Wahiba Ramdane. A selective adaptive large neighborhood search heuristic for the profitable tour problem with simultaneous pickup and delivery services. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 4-5, pp. 1295-1328. doi: 10.1051/ro/2018024
Cité par Sources :