混合蚁群算法求解带软时间窗的车辆路径问题

Hybrid Ant Colony Algorithm for Solving Vehicle Routing Problem with Soft Time Window

针对车辆路径问题中传统硬时间窗过于刚性的问题,将软时间窗引入模型约束,建立基于总配送费用最小化的优化模型.同时,考虑到蚁群算法在求解该类问题上的不足,提出萤火虫算法与蚁群算法混合来突破原有算法的瓶颈.将萤火虫个体间的寻优过程引入蚁群算法,以指导蚂蚁搜索额外解空间,以此改善每代可行解的多样性,从而在蚂蚁信息素更新过程中进行扰动,提高算法求解质量.数值实验表明,相较于传统蚁群算法,混合算法在求解的精确性与稳健性上具有显著优势,验证了算法的可行性与有效性.

Aiming at the problem that the traditional hard time window is too rigid in the vehicle routing problem, the soft time window was introduced into the model constraint, and an optimization model based on minimizing the total distribution cost was established. Considering the shortcomings of ant colony algorithm in solving this kind of problems, a hybrid of firefly algorithm and ant colony algorithm was proposed to break through the bottleneck of the original algorithm. The optimization process between firefly individuals waaas introduced into ant colony algorithm to guide ants to search for additional solution space and improve the diversity of feasible solutions for each generation, thus disturbing the pheromone update process of ants and improving the solution quality of the algorithm. Numerical experiments show that, compared with the traditional ant colony algorithm, the hybrid algorithm has significant advantages in accuracy and robustness, which verifies the feasibility and effectiveness of the algorithm.