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

摘要： 分析了带多软时间窗VRP实际应用背景和特点，以使用的车辆数、行驶费用和偏离时间窗的惩罚费用为优化目标，结合车辆载重、最大路长等限制，建立该问题的数学模型，并设计求解该问题的自适应禁忌搜索算法。为增强算法的全局寻优能力，设计了多邻域结构并在算法中嵌入一种有限地接受不可行解的自适应机制。分别用文献中的算例和以Solomon标准算例为基础构建的新算例测试该算法，并将结果与其他方法进行对比分析。对比结果表明，所提出的算法性能较好，能在可接受的时间内求出运输成本更少、满意度更高的解。

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