Stochastic multi-depot vehicle routing problem with pickup and delivery: an ILS approach

• Autorzy: Rios Brenner H. O. , Xavier Eduardo C. , Miyazawa Flávio K. , Amorim Pedro

Identyfikatory

DOI

10.15439/2020F127

• Konferencja: Federated Conference on Computer Science and Information Systems (15 ; 06-09.09.2020 ; Sofia, Bulgaria)
• Języki publikacji: EN

Abstrakty

EN

We present a natural probabilistic variation of the multi-depot vehicle routing problem with pickup and delivery (MDVRPPD). In this paper, we present a variation of this deterministic problem, where each pair of pickup and delivery points are present with some probability, and their realization are only known after the routes are computed. We denote this stochastic version by S-MDVRPPD. One route for each depot must be computed satisfying precedence constraints, where each pickup point must appear before its delivery pair in the route. The objective is to find a solution with minimum expected traveling distance. We present a closed-form expression to compute the expected length of an a priori route under general probabilistic assumptions. To solve the S-MDVRPPD we propose an Iterated Local Search (ILS) that uses the Variable Neighborhood Descent (VND) as local search procedure. The proposed heuristic was compared with a Tabu Search (TS) algorithm based on a previous work. We evaluate the performance of these heuristics on a data set adapted from TSPLIB instances. The results show that the ILS proposed is efficient and effective to solve S-MDVRPPD.

Słowa kluczowe

EN

deterministic algorithms; probability; search problems; stochastic processes; travelling salesman problem; vehicle routing

PL

algorytmy deterministyczne; prawdopodobieństwo; problemy wyszukiwawcze; procesy stochastyczne; problem komiwojażera; wyznaczanie tras pojazdów

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2020
• Tom: Vol. 21
• Strony: 307--315
• Opis fizyczny: Bibliogr. 20 poz., wz., il., tab.

Twórcy

autor

Rios Brenner H. O.

• Institute of Computing, University of Campinas, São Paulo, Brazil

autor

Xavier Eduardo C.

• Institute of Computing, University of Campinas, São Paulo, Brazil

autor

Miyazawa Flávio K.

• Institute of Computing, University of Campinas, São Paulo, Brazil

autor

Amorim Pedro

• INESC TEC, Faculty of Engineering, University of Porto, Porto, Portugal

Bibliografia

• 1. I. H. Dridi, E. B. Alaïa, P. Borne, and H. Bouchriha, “Optimisation of the multi-depots pick-up and delivery problems with time windows and multi-vehicles using PSO algorithm,” International Journal of Production Research, pp. 1–14, sep 2019. http://dx.doi.org/10.1080/00207543.2019.1650975
• 2. A. Subramanian, L. Drummond, C. Bentes, L. Ochi, and R. Farias, “A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery,” Computers & Operations Research, vol. 37, no. 11, pp. 1899–1911, nov 2010. http://dx.doi.org/10.1016/j.cor.2009.10.011
• 3. M. Gendreau, G. Laporte, and R. Séguin, “A tabu search heuristic for the vehicle routing problem with stochastic demands and customers,” Operations Research, vol. 44, no. 3, pp. 469–477, jun 1996. http://dx.doi.org/10.1287/opre.44.3.469
• 4. H. N. Psaraftis, M. Wen, and C. A. Kontovas, “Dynamic vehicle routing problems: Three decades and counting,” Networks, vol. 67, no. 1, pp. 3–31, aug 2015. http://dx.doi.org/10.1002/net.21628
• 5. I. Kara and T. Bektas, “Integer linear programming formulations of multiple salesman problems and its variations,” European Journal of Operational Research, vol. 174, no. 3, pp. 1449–1458, nov 2006. http://dx.doi.org/10.1016/j.ejor.2005.03.008
• 6. M. Assaf and M. Ndiaye, “Multi travelling salesman problem formulation,” in 2017 4th International Conference on Industrial Engineering and Applications (ICIEA). IEEE, apr 2017. http://dx.doi.org/10.1109/iea.2017.7939224
• 7. T. Bektas, “The multiple traveling salesman problem: an overview of formulations and solution procedures,” Omega, vol. 34, no. 3, pp. 209–219, jun 2006. http://dx.doi.org/10.1016/j.omega.2004.10.004
• 8. V. N. Pereira, M. C. San Felice, P. H. D. Hokama, and E. C. Xavier, “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. http://dx.doi.org/10.4230/LIPICS.SEA.2018.26
• 9. M. Polacek, R. F. Hartl, K. Doerner, and M. Reimann, “A variable neighborhood search for the multi depot vehicle routing problem with time windows,” Journal of Heuristics, vol. 10, no. 6, pp. 613–627, dec 2004. http://dx.doi.org/10.1007/s10732-005-5432-5
• 10. G. Laporte, R. Musmanno, and F. Vocaturo, “An adaptive large neighbourhood search heuristic for the capacitated arc-routing problem with stochastic demands,” Transportation Science, vol. 44, no. 1, pp. 125–135, feb 2010. http://dx.doi.org/10.1287/trsc.1090.0290
• 11. P. Stodola, “Hybrid ant colony optimization algorithm applied to the multi-depot vehicle routing problem,” Natural Computing, vol. 19, no. 2, pp. 463–475, jan 2020. http://dx.doi.org/10.1007/s11047-020-09783-6
• 12. J. E. Mendoza and J. G. Villegas, “A multi-space sampling heuristic for the vehicle routing problem with stochastic demands,” Optimization Letters, vol. 7, no. 7, pp. 1503–1516, sep 2012. http://dx.doi.org/10.1007/s11590-012-0555-8
• 13. A. L. Erera, M. Savelsbergh, and E. Uyar, “Fixed routes with backup vehicles for stochastic vehicle routing problems with time constraints,” Networks, vol. 54, no. 4, pp. 270–283, dec 2009. http://dx.doi.org/10.1002/net.20338
• 14. J. C. Goodson, “A priori policy evaluation and cyclic-order-based simulated annealing for the multi-compartment vehicle routing problem with stochastic demands,” European Journal of Operational Research, vol. 241, no. 2, pp. 361–369, mar 2015. http://dx.doi.org/10.1016/j.ejor.2014.09.031
• 15. B. H. O. Rios, E. F. G. Goldbarg, and G. Y. O. Quesquen, “A hybrid metaheuristic using a corrected formulation for the traveling car renter salesman problem,” in 2017 IEEE Congress on Evolutionary Computation (CEC). IEEE, jun 2017. http://dx.doi.org/10.1109/cec.2017.7969584
• 16. B. H. O. Rios, E. F. G. Goldbarg, and M. C. Goldbarg, “A hybrid metaheuristic for the traveling car renter salesman problem,” in 2017 Brazilian Conference on Intelligent Systems (BRACIS). IEEE, oct 2017. http://dx.doi.org/10.1109/bracis.2017.20
• 17. J. Oyola, H. Arntzen, and D. L. Woodruff, “The stochastic vehicle routing problem, a literature review, part II: solution methods,” EURO Journal on Transportation and Logistics, vol. 6, no. 4, pp. 349–388, nov 2016. http://dx.doi.org/10.1007/s13676-016-0099-7
• 18. Y. Kuo and C.-C. Wang, “A variable neighborhood search for the multi-depot vehicle routing problem with loading cost,” Expert Systems with Applications, vol. 39, no. 8, pp. 6949–6954, jun 2012. doi: 10.1016/j.eswa.2012.01.024
• 19. N. Mladenović and P. Hansen, “Variable neighborhood search,” Computers & Operations Research, vol. 24, no. 11, pp. 1097–1100, nov 1997. http://dx.doi.org/10.1016/s0305-0548(97)00031-2
• 20. D. J. Bertsimas, “A vehicle routing problem with stochastic demand,” Operations Research, vol. 40, no. 3, pp. 574–585, jun 1992. http://dx.doi.org/10.1287/opre.40.3.574

Uwagi

1. This work is financed by FAPESP (Proc. 2015/11937-9, 2016/01860-1, 2018/08879-5), CNPq (Proc. 314366/2018-0, 425340/2016-3, 304856/2017-7), ERDF - European Regional Development Fund through the Operational Programme for Competitiveness and Internationalisation - COMPETE 2020 Programme and by National Funds through the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia within project POCI-01-0145-FEDER-031908.

2. Track 1: Artificial Intelligence

3. Technical Session: 13th International Workshop on Computational Optimization

4. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).