Abstract: Multi-depot open vehicle routing problem with soft time windows is a variation of the open vehicle routing problem constrained by time windows and multi-depot, which is a typical NP-hard problem. To solve this problem, an improved ant colony algorithm is proposed, and the corresponding mathematical model is established. By introducing a virtual depot, the multi-depot VRP is transformed into a single depot VRP. Then a new ant colony algorithm with parameter adaptation combined with 2-opt algorithm is proposed to solve the problem. At the early stage of the algorithm, a clustering technology based on the bacterial foraging chemotaxis algorithm  and K-means algorithm is used to judge the state of the ant colony, and the parameters are adjusted adaptively to make the algorithm converge to the neighborhood of the global optimal solution. At the late stage, the parameters are tuned based on the characteristics of chaos theory to jump out of local optima. Experimental results verify the effectiveness of the proposed algorithm for solving the MDOVRPSTW problem.

Key words: open vehicle routing problem, time windows, ant colony algorithm, clustering technology, 2-opt

摘要： 带软时间窗的多车场开放式车辆调度问题是在开放式车辆路径问题的基础上，考虑了多车场和客户服务时间的约束，是一类典型的NP难解问题。针对该问题，提出了一种改进的蚁群算法求解方案，并建立了相应的数学模型。首先通过设置一个虚拟车场将多车场VRP转化为单车场VRP，然后利用参数控制的改进蚁群算法与2-opt算法结合来对模型求解。算法先利用K-means与细菌觅食算法相结合的聚类技术判断蚁群状态，进而动态调整算法参数，使其快速收敛到全局最优解附近，再依据混沌理论的特点来调整参数，使其跳出局部最优。最后，再利用2-opt算法对最优解进行优化。实验结果验证了该算法求解MDOVRPSTW问题的有效性。

关键词: 开放式车辆路径问题, 时间窗, 蚁群算法, 聚类技术, 2-opt