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

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