关键词: 车辆路径问题, 多软时间窗, 禁忌搜索, 物流配送

Abstract: The practical application background and characteristics of the Vehicle Routing Problem with Multiple Soft Time Windows（VRPMSTW） are analyzed. Taking the number of vehicles required, total travel cost and time window deviation as the optimization objective, combined with constraints such as vehicle capacity, maximum route length, a corresponding mathematical model is constructed. An adaptive tabu search algorithm is designed to solve the problem. In order to enhance the optimization ability of the algorithm, a multi neighborhood structure is designed and an adaptive mechanism is embedded in the algorithm to accept the infeasible solution. The algorithm is tested with examples in the literature and new instances based on the Solomon benchmark problems. Computational results are compared with other methods in the literature. The comparison results show that the algorithm proposed in this paper has better performance, and it can get the solution with less transportation cost and higher satisfaction in acceptable time.

Key words: vehicle routing problem, multiple soft time windows, tabu search, distribution management