Stochastic multi-depot capacitated vehicle routing problem with pickup and delivery: heuristic approaches

• Brenner H. O. Rios Unicamp
• Eduardo C. Xavier Unicamp
• Flávio K. Miyazawa Unicamp
• Pedro Amorim Universidade do Porto

DOI: https://doi.org/10.5753/etc.2021.16388

Resumo

We present a natural probabilistic variation of the multi-depot vehicle routing problem with pickup and delivery. We denote this variation by Stochastic multi-depot capacitated vehicle routing problem with pickup and delivery (SMCVRPPD). We present an algorithm to compute the expected length of an apriori route under general probabilistic assumptions. To solve the SMCVRPPD we propose an Iterated Local Search (ILS) and a Variable Neighborhood Search(VNS). We evaluate the performance of these heuristics on a data set adapted from TSPLIB instances. The results show that the ILS is effective to solve SMCVRPPD.

Palavras-chave: Stochastic VRP, Iterated Local Search, Variable Neighborhood Search

Referências

Cao, W. and Yang, W. (2017). A survey of vehicle routing problem. In MATEC Web of Conferences, volume 100, page 01006. EDP Sciences.

Kuo, Y. and Wang, C.-C. (2012). A variable neighborhood search for the multi-depot vehicle routing problem with loading cost. Expert Systems with Applications, 39(8):6949–6954.

Oyola, J., Arntzen, H., and Woodruff, D. L. (2017). The stochastic vehicle routing problem, a literature review, part ii: solution methods. EURO Journal on Transportationand Logistics, 6(4):349–388.

Rios, B., Xavier, E. C., Miyazawa, F. K., and Amorim, P. (2020a). Multi-depot mul-tiple tsp with pickup and delivery: an vns approach. In ANAIS DO LII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL (SBPO).

Rios, B., Xavier, E. C., Miyazawa, F. K., and Amorim, P. (2020b). Stochastic multi-depot vehicle routing problem with pickup and delivery: an ils approach. In 2020 15th Conference on Computer Science and Information Systems (FedCSIS), pages 307–315. IEEE.