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.

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.

DOI : 10.1051/ro/2018024
Classification : 90B06, 90C11, 90C27, 90-08
Mots-clés : Vehicle routing problem with pickup and delivery, profitable tour problem, reverse logistic, adaptive large neighborhood search, metaheuristics
Chentli, Hayet 1 ; Ouafi, Rachid 1 ; Cherif-Khettaf, Wahiba Ramdane 1

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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ro/2018024/

[1] C. Archetti, D. Feillet, A. Hertz and M.G. Speranza, The capacitated team orienteering and profitable tour problems. J. Oper. Res. Soc. 60 (2009) 831–842. | DOI | Zbl

[2] R. Bent and P. Van Hentenryck, A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows. Comput. Oper. Res. 33 (2006) 875–893. | DOI | Zbl

[3] B. Çatay, A new saving-based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery. Expert Syst. Appl. 37 (2010) 6809–6817. | DOI

[4] V. Černỳ, Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J. Optim. Theory Appl. 45 (1985) 41–51. | DOI | MR | Zbl

[5] N. Christofides, A. Mingozzi and P. Toth, The vehicle routing problem, in Combinatorial Optimization, edited by N. Christofides, A. Mingozzi, P. Toth and C. Sandi. Wiley, Chichester (1979) 315–338. | MR | Zbl

[6] M. Dell’Amico, G. Righini and M. Salani, A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Transp. Sci. 40 (2006) 235–247. | DOI

[7] M. Gansterer, M. Küçüktepe and R.F. Hartl, The multi-vehicle profitable pickup and delivery problem. OR Spectr. 39 (2017) 303–319. | DOI | MR | Zbl

[8] V. Ghilas, E. Demir and T. Van Woensel, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows and scheduled lines. Comput. Oper. Res. 72 (2016) 12–30. | DOI | MR | Zbl

[9] I. Gribkovskaia, G. Laporte and A. Shyshou, The single vehicle routing problem with deliveries and selective pickups. Comput. Oper. Res. 35 (2008) 2908–2924. | DOI | MR | Zbl

[10] G. Gutiérrez-Jarpa, G. Desaulniers, G. Laporte and V. Marianov, A branch-and-price algorithm for the vehicle routing problem with deliveries, selective pickups and time windows. Eur. J. Oper. Res. 206 (2010) 341–349. | DOI | Zbl

[11] M. Hifi and L. Wu, A hybrid metaheuristic for the vehicle routing problem with time windows, in 2014 International Conference on Control, Decision and Information Technologies (CoDIT). IEEE (2014) 188–194. | DOI

[12] S.C. Ho and W. Szeto, Grasp with path relinking for the selective pickup and delivery problem. Expert Syst. Appl. 51 (2016) 14–25. | DOI

[13] M.K. Jepsen, B. Petersen, S. Spoorendonk and D. Pisinger, A branch-and-cut algorithm for the capacitated profitable tour problem. Discret. Optim. 14 (2014) 78–96. | DOI | MR | Zbl

[14] C.B. Kalayci and C. Kaya, An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery. Expert Syst. Appl. 66 (2016) 163–175. | DOI

[15] S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by simulated annealing. Science 220 (1983) 671–680. | DOI | MR | Zbl

[16] J.B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7 (1956) 48–50. | DOI | MR | Zbl

[17] Y. Li, H. Chen and C. Prins, Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests. Eur. J. Oper. Res. 252 (2016) 27–38. | DOI | MR | Zbl

[18] D. Männel and A. Bortfeldt, A hybrid algorithm for the vehicle routing problem with pickup and delivery and three-dimensional loading constraints. Eur. J. Oper. Res. 254 (2016) 840–858. | DOI | MR | Zbl

[19] H. Min, The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transp. Res. Part A: General 23 (1989) 377–386. | DOI

[20] F.A.T. Montané and R.D. Galvao, A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Comput. Oper. Res. 33 (2006) 595–619. | DOI | MR | Zbl

[21] D. Mu, C. Wang, F. Zhao and J.W. Sutherland, Solving vehicle routing problem with simultaneous pickup and delivery using parallel simulated annealing algorithm. Int. J. Shipp. Transp. Logist. 8 (2016) 81–106. | DOI

[22] D. Pisinger and S. Ropke, A general heuristic for vehicle routing problems. Comput. Oper. Res. 34 (2007) 2403–2435. | DOI | MR | Zbl

[23] X. Qiu, S. Feuerriegel and D. Neumann, Making the most of fleets: a profit-maximizing multi-vehicle pickup and delivery selection problem. Eur. J. Oper. Res. 259 (2017) 155–168. | DOI | MR | Zbl

[24] S. Ropke and D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp. Sci. 40 (2006) 455–472. | DOI

[25] S. Ropke and D. Pisinger, A unified heuristic for a large class of vehicle routing problems with backhauls. Eur. J. Oper. Res. 171 (2006) 750–775. | DOI | MR | Zbl

[26] S. Salhi and G. Nagy, A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. J. Oper. Res. Soc. 35 (1999) 1034–1042. | DOI | Zbl

[27] M.M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35 (1987) 254–265. | DOI | MR | Zbl

[28] A. Subramanian, L.M.D.A. Drummond, C. Bentes, L.S. Ochi and R. Farias, A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Comput. Oper. Res. 37 (2010) 1899–1911. | DOI | Zbl

[29] C.-K. Ting and X.-L. Liao, The selective pickup and delivery problem: formulation and a memetic algorithm. Int. J. Prod. Econom. 141 (2013) 199–211. | DOI

[30] VRPLIB, Available at: http://or.dei.unibo.it/library/vrplib-vehicle-routing-problem-library

[31] E.E. Zachariadis and C.T. Kiranoudis, A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries. Expert Syst. Appl. 38 (2011) 2717–2726. | DOI

[32] E.E. Zachariadis, C.D. Tarantilis and C.T. Kiranoudis, A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service. Expert Syst. Appl. 36 (2009) 1070–1081. | DOI

[33] E.E. Zachariadis, C.D. Tarantilis and C.T. Kiranoudis, An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries. Eur. J. Oper. Res. 202 (2010) 401–411. | DOI | Zbl

Cité par Sources :