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

被引：16

作者：

陈萍

黄厚宽

董兴业

机构：

[1] 北京交通大学计算机科学与信息技术学院

来源：

计算机学报 | 2008年 / 04期

关键词：

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

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

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

引用

页码：565 / 573

页数：9

共 7 条

[1] An integrated multi-depot hub-location vehicle routing model for network planning of parcel service
Wasner, M
Zäpfel, G
[J]. INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2004, 90 (03) : 403 - 419
[2] Metaheuristics in combinatorial optimization[J] . Christian Blum,Andrea Roli.ACM Computing Surveys (CSUR) . 2003 (3)
[3] Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up Fahrzeugeinsatzplanung und Redistribution: Tourenplanung mit simultaner Auslieferung und Rückholung
Jan Dethloff
[J]. OR-Spektrum, 2001, 23 (1) : 79 - 96
[4] THE TRUCK DISPATCHING PROBLEM
DANTZIG, GB
RAMSER, JH
[J]. MANAGEMENT SCIENCE, 1959, 6 (01) : 80 - 91
[5] Ant Colony Optimization .2 Dorigo M,Stutzle T. The MIT Press . 2004
[6] Solving a vehicle routing problemarisingin soft drink distribution .2 Priv J,Renaud J,Boctor F,Laporte G. Journal of the Operational Research Society . 2006
[7] Acluster insertion heuristic for single and multiple depot vehicle routing problem with backhauling .2 Salhi S,Nagy G. Journal of the Operational Research Society . 1999

← 1 →