A comparative study of metaheuristics for vehicle routing problem with stochastic demands

Abstract

The vehicle routing problem with stochastic demands (VRPSD) is usually modeled as a stochastic program with recourse (SPR). In this paper, we present three metaheuristics, simulated annealing (SA), threshold accepting (TA) and tabu search (TS) for this problem. Based on the same neighborhood structure, a comparative study is carried out to compare the performance of these three metaheuristics. Computational results show that the solution quality of the TS outperforms the other heuristics for all the problems tested. With respect to computational time, metaheuristics are much more time consuming as compared to other local search heuristics. However, when comparing TS with SA, it takes less computational time. Though TA is the least time consuming one, its solution quality is not as good.