Dynamic Vehicle Routing Problem with a Return Strategy and Tabu Search Algorithm

摘要

In this paper, a mathematical description of the dynamic vehicle routing problem is presented with the objective of minimizing the total cost in the process of vehicle distribution. The problem is transformed into a series of static vehicle routing sub-problems by partitioning the period as a sequence of time slices. A new vehicle return strategy is proposed by introducing the concept of waiting threshold while having no service requests. A heuristic algorithm based on tabu search is built to solve a series of static vehicle routing problem with soft time windows. An approach of using insertion algorithm to construct the initial solution and continuously updating the tabu search space in the internal search stage is achieved in this paper. Finally, the presented method was applied to a numerical case study. The analysis of results by using the direct return strategy and the proposed return strategy, and the effects of time slices division on the solution quality are also discussed. The calculation shows that the proposed method could effectively solve the dynamic vehicle routing problem.