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

Hybrid variable neighborhood symbiotic organisms search for capacitated vehicle routing problem

作　　者：李阳[1] 范厚明[1] LI Yang;FAN Hou-ming(Institute of Strategy Management and System Planning, Dalian Maritime University, Dalian 116026, China)

机构地区：[1]大连海事大学战略管理与系统规划研究所,辽宁大连116026

出　　处：《控制与决策》2018年第7期1190-1198,共9页Control and Decision

基　　金：国家自然科学基金项目(61473053;70801007);辽宁省社会科学规划基金重点项目(L16AGL004);辽宁省教育厅科学技术研究一般项目(L2014046);大连市科学技术计划项目(2010A16GX084)

摘　　要：针对带容量约束的车辆路径问题,提出一种混合变邻域生物共栖搜索算法.设计基于客户点优先序列及车辆参考点模拟信息的有序编码,该编码方案使生物共栖搜索算法可以参与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.

关 键 词：交通工程 容量约束车辆路径问题 生物共栖搜索算法 变邻域搜索算法 有序编码 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]