Open AccessStochastic multi-depot capacitated vehicle routing problem with pickup and delivery: heuristic approaches
Author(s) -
Brenner Humberto Ojeda Rios,
Eduardo C. Xavier,
Flávio Keidi Miyazawa,
Pedro Amorim
Publication year - 2021
Language(s) - English
Resource type - Conference proceedings
DOI - 10.5753/etc.2021.16388
Subject(s) - vehicle routing problem , iterated local search , heuristics , pickup , probabilistic logic , mathematical optimization , computer science , variable neighborhood search , routing (electronic design automation) , heuristic , depot , variable (mathematics) , set (abstract data type) , local search (optimization) , metaheuristic , mathematics , artificial intelligence , computer network , mathematical analysis , archaeology , image (mathematics) , history , programming language
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.