An Improved Tabu Search Algorithm for the Stochastic Vehicle Routing Problem With Soft Time Windows

Abstract

In real-world environments, vehicle travel and service time will be affected by unpredictable factors and present a random state. Because of this situation, this article proposes the vehicle routing problem with soft time windows and stochastic travel and service time (SVRP-STW). The probability distribution of vehicle travel and service time are introduced into the model, and a stochastic programming model with modification is established to minimize the distribution cost. An Improved Tabu Search algorithm (I-TS) based on greedy algorithm is proposed, in which adaptive tabu length and neighborhood structure are introduced; the greedy algorithm is used instead of the random methods to generate the initial solution. Experiments on different scale instances prove the effectiveness and superiority of the proposed algorithm.

Keywords

• Stochastic travel times
• stochastic service times
• soft time windows
• stochastic programming model
• tabu search