带相容性约束的车辆路径问题及其混合蚁群算法

A Hybrid Ant Colony Algorithm for the Vehicle Routing Problem with Compatibility Constraints

【目的】着力设计带相容性约束的车辆路径问题的高效启发式算法。【方法】针对带相容性约束的车辆路径问题的特点,提出了一种混合蚁群算法。该算法的核心由蚁群搜索和禁忌搜索组成,对蚁群搜索的状态转移公式和信息素更新规则进行了改进,并在蚁群搜索过程中加入了一个扰动机制,同时在禁忌搜索部分采用了新的邻域结构和禁忌规则。【结果】得到了关于带相容性约束的车辆路径问题的混合蚁群算法。【结论】通过多个算例对算法进行了测试,计算结果表明该算法具有很高的求解效率。

[Purposes]The vehicle routing problem with compatibility constraints（VRPCC）that appears in the cold-chain logistics is a type of complicated vehicle routing problem.So far,research on this problem is scarce.[Methods]In this study,the VRPCC is described in detail and then a hybrid ant colony algorithm is proposed for it according to its characteristics.The main components of our algorithm are ant colony search and tabu search.In the ant colony search,new state transition probability formula and pheromone updating rule are applied and a perturbation phase is added.[Findings]Moreover,a new neighborhood structure and tabu rules are designed for the tabu search.[Conclusions]The algorithm is evaluated based on several test instances,and the results show that our hybrid ant colony algorithm is effective and efficient.