求解卸装一体化的车辆路径问题的混合启发式算法

作     者：陈萍 黄厚宽 董兴业 CHEN Ping;HUANG Hou-Kuan;DONG Xing-Ye

作者机构：北京交通大学计算机科学与信息技术学院北京100044 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2008年第31卷第4期

页      面：565-573页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家"九七三"重点基础研究发展规划项目基金(2006CB705500)资助 

主　　题：卸装一体化车辆路径问题 混合启发式算法 蚁群系统 变邻域下降搜索 组合优化 NP难 

摘      要：提出一种结合蚁群系统（Ant Colony System,ACS）和变邻域下降搜索（Variable Neighborhood Descent,VND）的混合启发式算法ACS_VND,求解卸装一体化车辆路径问题.利用基于插入的ACS解构造方法产生多个弱可行解,再逐个转换成强可行解,并选择其中最好的作为VND的初始解.在VND过程中使用三种不同的邻域结构：插入、交换和2-opt依次对解进行迭代优化.对55个规模为22~199的benchmark算例的求解结果表明,算法ACS_VND能在较短时间内获得52个算例的已知最好解,并且更新了其中44个算例的已知最好解,求解性能优于现有算法.