求解带容量约束车辆路径问题的混合变邻域生物共栖搜索算法

Hybrid variable neighborhood symbiotic organisms search for capacitated vehicle routing problem

针对带容量约束的车辆路径问题,提出一种混合变邻域生物共栖搜索算法.设计基于客户点优先序列及车辆参考点模拟信息的有序编码,该编码方案使生物共栖搜索算法可以参与CVRP的离散优化;为了提高算法的全局搜索能力,根据有序编码特点构造3种共栖搜索算子,扩大搜索空间;同时,结合变邻域搜索算法设计客户点重置、交换和2-OPT三种局部搜索策略,以提高解方案质量.算例验证分析表明,所提算法能够有效地解决容量约束车辆路径问题,求解质量优于所对比算法,具有可靠的全局稳定性.

In order to solve the capacitated vehicle routing problem（CVRP）, a hybrid variable neighborhood symbiotic organisms search（HVNSOS） algorithm is proposed. A new encoding scheme called ordered encoding is designed, which connects customers＇ priority sequence with vehicle reference points. Based on the ordered encoding, the SOS algorithm can be applied to discrete optimization problems（e.g. CVRP）. For the sake of enhancing the global searching ability of the algorithm, three symbiotic operators are constructed according to the features of the encoding scheme. The symbiotic operators can also expand the search space of the CVRP. To improve the quality of solutions, the algorithm combines the variable neighborhood search algorithm to design three new local search operators of relocate, exchange and 2-OPT. The comparison and analysis of the results show that the proposed algorithm can solve the CVRP effectively, and it is superior in the performance of computing efficiency and global stability to the algorithms compared.