A selective adaptive large neighborhood search heuristic for the profitable tour problem with simultaneous pickup and delivery services
| Autor: | Rachid Ouafi, Hayet Chentli, Wahiba Ramdane Cherif-Khettaf |
|---|---|
| Přispěvatelé: | OPTImisation Methods for Integrated SysTems (OPTIMIST), Department of Networks, Systems and Services (LORIA - NSS), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
metaheuristics 021103 operations research Heuristic (computer science) Computer science 0211 other engineering and technologies 02 engineering and technology [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Management Science and Operations Research Solver profitable tour problem Computer Science Applications Theoretical Computer Science Operator (computer programming) Local optimum Simulated annealing Vehicle routing problem 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing adaptive large neighborhood search Routing (electronic design automation) reverse logistic Metaheuristic Vehicle routing problem with pickup and delivery |
| Zdroj: | RAIRO-Operations Research RAIRO-Operations Research, EDP Sciences, 2018, 52 (4-5), pp.1295-1328. ⟨10.1051/ro/2018024⟩ RAIRO-Operations Research, 2018, 52 (4-5), pp.1295-1328. ⟨10.1051/ro/2018024⟩ |
| ISSN: | 0399-0559 1290-3868 |
| DOI: | 10.1051/ro/2018024⟩ |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|