Abstract
The stochastic multi-depot vehicle routing problem with pickup and delivery (S-MDVRPPD) is a new problem presentend in this work. The deterministic variation of S-MDVRPPD constitutes a generalization of the Traveling Salesman. In the S-MDVRPPD the pickups and delivery points are present in a route with some probability. A route for each depot must be satisfy the following restrictions: (1) each cycle starts and ends at the corresponding vehicle’s depot; (2) each node is visited exactly once by one vehicle; (3) each pair of pickup and delivery points must belong to the same cycle; and (4) each pickup point in a cycle appears before its delivery pair. The objective is to find a solution with the minimum expected cost. We use a closed-form expression to compute the expected cost of an a priori route under general probabilistic assumptions. A linear integer programming model is presented for the deterministic version of S-MDVRPPD. To solve the S-MDVRPPD we propose a Variable Neighborhood Search (VNS) and Iterated local search (ILS) that use the Variable Neighborhood Descent (VND) as local search procedure. We compare the performance of the proposed algorithms with a Tabu Search algorithm (TS). We evaluate the performance of these heuristics on a data set adapted from TSPLIB instances. The results show that the VNS proposed is efficient and effective to solve S-MDVRPPD.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Addinsoft: Data Analysis and Statistical Solution for Microsoft Excel, Paris, France (2017)
Assaf, M., Ndiaye, M.: Multi travelling salesman problem formulation. In: 2017 4th International Conference on Industrial Engineering and Applications (ICIEA). IEEE (2017). https://doi.org/10.1109/iea.2017.7939224
Bektas, T.: The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34(3), 209–219 (2006). https://doi.org/10.1016/j.omega.2004.10.004
Bertsimas, D.J.: A vehicle routing problem with stochastic demand. Oper. Res. 40(3), 574–585 (1992). https://doi.org/10.1287/opre.40.3.574
Carrabs, F., Cordeau, J.-F., Laporte, G.: Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading. INFORMS J. Comput. 19(4), 618–632 (2007). https://doi.org/10.1287/ijoc.1060.0202
Crevier, B., Cordeau, J.-F., Laporte, G.: The multi-depot vehicle routing problem with inter-depot routes. Europ. J. Oper. Res. 176(2), 756–773 (2007). https://doi.org/10.1016/j.ejor.2005.08.015
Dridi, I.H., et al.: Optimisation of the multi-depots pick-up and delivery problems with time windows and multi-vehicles using PSO algorithm. Int. J. Prod. Res. 1–14 (2019). https://doi.org/10.1080/00207543.2019.1650975
Dunn, O.J.: Multiple comparisons among means. J. Amer. Stat. Ass. 56(293), 52–64 (1961)
Erera, A.L., Savelsbergh, M., Uyar, E.: Fixed routes with backup vehicles for stochastic vehicle routing problems with time constraints. Networks 54(4), 270–283 (2009). https://doi.org/10.1002/net.20338
Friedman, M.: The use of ranks to avoid the assumption of normality implicit in the analysis of variance. J. Amer. Stat. Ass. 32(200), 675–701 (1937)
Gendreau, M., Laporte, G., Séguin, R.: A Tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Oper. Res. 44(3), 469–477 (1996). https://doi.org/10.1287/opre.44.3.469
Goodson, J.C.: A priori policy evaluation and cyclic-order-based simulated annealing for the multi-compartment vehicle routing problem with stochastic demands. Europ. J. Oper. Res. 241(2), 361–369 (2015). https://doi.org/10.1016/j.ejor.2014.09.031
Hansen, P., Mladenovic, N.: Variable neighborhood search. In: Search Methodologies, pp. 211–238. Springer US (2005). https://doi.org/10.1007/0-387-28356-0_8
Hansen, P., et al.: Variable neighborhood search: basics and variants. EURO J. Comput. Optim. 5(3), 423–454 (2016). https://doi.org/10.1007/s13675-016-0075-x
Kachitvichyanukul, V., Sombuntham, P., Kunnapapdeelert, S.: Two solution representations for solving multi-depot vehicle routing problem with multiple pickup and delivery requests via PSO. Comput. & Ind. Eng. 89, 125–136 (2015). https://doi.org/10.1016/j.cie.2015.04.011
Kara, I., Bektas, T.: Integer linear programming formulations of multiple salesman problems and its variations. Europ. J. Oper. Res. 174(3), 1449–1458 (2006). https://doi.org/10.1016/j.ejor.2005.03.008
Kuo, Y., Wang, C.-C.: A variable neighborhood search for the multi-depot vehicle routing problem with loading cost. Expert Syst. Appl. 39(8), 6949–6954 (2012). https://doi.org/10.1016/j.eswa.2012.01.024
Laporte, G., Musmanno, R., Vocaturo, F.: An adaptive large neighbourhood search heuristic for the capacitated arc-routing problem with stochastic demands. Trans. Sci. 44(1), 125–135 (2010). https://doi.org/10.1287/trsc.1090.0290
Lourenço, H.R., Martin, O., St ützle, T.: Iterated local search. In: Handbook of Metaheuristics, pp. 321–353 (2003)
Mendoza, J.E., Villegas, J.G.: A multi-space sampling heuristic for the vehicle routing problem with stochastic demands. Optim. Lett. 7(7), 1503–1516 (2012). https://doi.org/10.1007/s11590-012-0555-8
Mladenovic, N., Hansen, P.: Variable neighborhood search. Comput. & Oper. Res. 24(11), 1097–1100 (1997). https://doi.org/10.1016/s0305-0548(97)00031-2
Nemenyi, P.: Distribution-free multiple comparisons. Biometrics 18(2), 263 (1962). International Biometric Soc 1441 I ST, NW, Suite 700, Washington, DC 20005-2210
Oyola, J., Arntzen, H., Woodruff, D.L.: The stochastic vehicle routing problem, a literature review, Part II: solution methods. EURO J. Trans. Log. 6(4), 349–388 (2016). https://doi.org/10.1007/s13676-016-0099-7
Pereira, V.N.G., et al. (2018) The Steiner multi cycle problem with applications to a collaborative truckload problem. In: 17th International Symposium on Experimental Algorithms (SEA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018). https://doi.org/10.4230/LIPICS.SEA.2018.26
Polacek, M., et al.: A variable neighborhood search for the multi depot vehicle routing problem with time windows. J. Heuristics 10(6), 613–627 (2004). https://doi.org/10.1007/s10732-005-5432-5
Pongchairerks, P.: Forward VNS, reverse VNS, and multi-VNS algorithms for job-shop scheduling problem. Modell. Simul. Eng. 2016, 1–15 (2016). https://doi.org/10.1155/2016/5071654
Psaraftis, H.N., Wen, M., Kontovas, C.A.: Dynamic vehicle routing problems: three decades and counting. Networks 67(1), 3–31 (2015). https://doi.org/10.1002/net.21628
Rios, B.H.O., et al.: Stochastic multi-depot vehicle routing problem with pickup and delivery: an ILS approach. In: Proceedings of the 2020 Federated Conference on Computer Science and Information Systems. IEEE (2020). https://doi.org/10.15439/2020f127
Rios, B.H.O., Goldbarg, E.F.G., Goldbarg, M.C.: A hybrid metaheuristic for the traveling car renter salesman problem. In: 2017 Brazilian Conference on Intelligent Systems (BRACIS). IEEE (2017). https://doi.org/10.1109/bracis.2017.20
Rios, B.H.O., Goldbarg, E.F.G., Quesquen, G.Y.O.: A hybrid metaheuristic using a corrected formulation for the Traveling Car Renter Salesman Problem. In: 2017 IEEE Congress on Evolutionary Computation (CEC). IEEE (2017). https://doi.org/10.1109/cec.2017.7969584
Stodola, P.: Hybrid ant colony optimization algorithm applied to the multi-depot vehicle routing problem. Natural Comput. 19(2), 463–475 (2020). https://doi.org/10.1007/s11047-020-09783-6
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Cite this chapter
Rios, B.H.O., Xavier, E.C., Miyazawa, F.K., Amorim, P. (2022). Heuristic Approaches for the Stochastic Multi-depot Vehicle Routing Problem with Pickup and Delivery. In: Fidanova, S. (eds) Recent Advances in Computational Optimization. WCO 2020. Studies in Computational Intelligence, vol 986. Springer, Cham. https://doi.org/10.1007/978-3-030-82397-9_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-82397-9_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-82396-2
Online ISBN: 978-3-030-82397-9
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)