Annals of Computer Science and Information Systems, Volume 21

DOI: http://dx.doi.org/10.15439/2020F127

Citation: Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 21, pages 307–315 (2020)

Full text

Abstract. 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.

References

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