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

摘要：

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

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

所属期刊栏目：31

分类号：TP301(计算技术、计算机技术)

资助基金：国家重点基础研究发展计划973计划2006CB05500

在线出版日期：2008-06-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：565-573