改进蚁群算法求解带时间窗的应急物流开环车辆路径问题
Solution of emergency logistics open-loop vehicle routing problem with time window based on improved ant colony algorithm

为解决受灾区域的物资运输问题，研究应急物流背景下带时间窗的开环车辆路径问题。将灾后道路通行性能差异及物资运输优先级考虑入约束范围，在确保应急物资运输可靠性的基础上，提出基于物流响应能力最大化的车辆路径模型。同时，考虑到传统优化算法收敛性差、易陷入局部最优的缺点，提出一种改进的蚁群算法以突破已有的算法瓶颈。该算法混合了人工鱼群算法与蚁群算法，将拥挤度因子引入蚁群算法以指导蚁群的聚集，从而提高蚁群算法求解的质量。通过一个基础算例对所提出模型与算法进行验证，得到最优解优化曲线并求解最优解，采用1组CMT与GWKC标准算例对提出的改进蚁群算法的性能进行评估计算试验。分别采用模拟退火算法、变邻域搜索算法及邻域搜索算法对标准算例进行求解。研究结果表明：提出的改进蚁群算法在求解收敛性与精确性上有显著优势，提出的算法在迭代60次后得到最优解，收敛速度比蚁群算法提前了68个迭代循环，最优解优化接近7.8%；在相同试验环境下，实例数据的规模与算法所求得最优解的差值无关，即算例规模并不影响算法求解的精确度；提出的改进蚁群算法在可接受时间范围内，通过适当延长邻域搜索运算时间可显著提升求解精度，在各组试验结果中相比于其他算法均求得了最优的结果，在CMT2中改进蚁群算法求得的最优解比已知上界优化了超过40%。
In order to solve the problem of material transportation in the affected area, an emergency logistics open-loop vehicle routing problem with time window (EL-OLVRPTW) was studied. Taking into account the difference of road traffic performance and the priority of material transportation after disaster, a vehicle routing model based on the maximization of logistics response ability was proposed on the basis of ensuring the reliability of emergency material transportation. Meanwhile, an improved ant colony algorithm (IAC) was proposed to break through the bottleneck of traditional optimization algorithm. The new algorithm improved its convergence and had a great ability to keep from falling into local optimum. This algorithm combined the artificial fish swarm algorithm and the ant colony algorithm. Crowding factor was used for guiding the ant colony for its process of aggregation and finally improved the quality of its solution. The proposed model and algorithm were verified by a basic numerical case. The optimized solution curve was obtained and the optimal solution was solved. The evaluation calculation experiment was conducted on the performance of improved ant colony algorithm by adopting one CMT and GWKC standard example. Numerical calculation adopted simulated annealing algorithm, variable neighborhood search algorithm and neighborhood search algorithm on the standard examples. The results show that the IAC proposed in this paper has a significant advantage in its solving convergence and accuracy. Among these numerical results, the optimal solution solved by IAC is obtained after 60 iterations, which advances 68 iterative cycles compared with the ant colony algorithm. And optimization of the solution is close to 7.8%. Under the same experimental conditions, the scale of the instance data is independent of the difference of the optimal solution, which means the scale of the example does not affect the accuracy of the algorithms. The proposed IAC can significantly improve the accuracy of the solution by