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

A Hybrid Heuristic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pickup

作　　者：陈萍[1] 黄厚宽[1] 董兴业[1] 

机构地区：[1]北京交通大学计算机科学与信息技术学院,北京100044

出　　处：《计算机学报》2008年第4期565-573,共9页Chinese Journal of Computers

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

摘　　要：提出一种结合蚁群系统（Ant Colony System,ACS）和变邻域下降搜索（Variable Neighborhood Descent,VND）的混合启发式算法ACS_VND,求解卸装一体化车辆路径问题.利用基于插入的ACS解构造方法产生多个弱可行解,再逐个转换成强可行解,并选择其中最好的作为VND的初始解.在VND过程中使用三种不同的邻域结构：插入、交换和2-opt依次对解进行迭代优化.对55个规模为22~199的benchmark算例的求解结果表明,算法ACS_VND能在较短时间内获得52个算例的已知最好解,并且更新了其中44个算例的已知最好解,求解性能优于现有算法.A hybrid heuristic algorithm ACS_VND is proposed and applied to solving the vehicle routing problem with simultaneous delivery and pickup, which combines two metaheuristics, i. e. , Ant Colony System and Variable Neighborhood Descent. Several weakly feasible solutions are built by an insertion based ACS solution construction method, which are then transformed into strongly feasible ones, the best of which is taken as the initial solution of the VND procedure. During the VND procedure, three different neighborhood structures, i. e. , insertion, swap and 2-opt are successively used. Computational results on the 55 benchmark problems with the size ranging from 22 to 199, show that the proposed hybrid heuristic algorithm can find the best known solution for 52 problems in a short time; furthermore, the best known solutions for 44 problems are updated, which indicates that the proposed ACS_VND outperforms other algorithms in literatures.

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

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