具有时间窗约束累积性车辆路径问题的禁忌搜索优化算法

被引：12

作者：

董蕊

刘冉

江志斌

任盼

机构：

[1] 上海交通大学工业工程与管理系

来源：

工业工程与管理 | 2015年 / 20卷 / 01期

基金：

上海市自然科学基金; 高等学校博士学科点专项科研基金;

关键词：

累积性成本; 车辆路径; 时间窗; 禁忌搜索;

D O I：

10.19495/j.cnki.1007-5429.2015.01.008

中图分类号：

U492.22 []; TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

基于对中国实际物流运输中成本计算方法的研究,考虑到我国高速公路系统计价方式的特殊性,提出了具有时间窗约束的累积性车辆路径问题。以降低实际车辆运输成本为目标,设计了新型的禁忌搜索算法对问题进行有效求解;算法中嵌入多种邻域搜索方法,允许同时在可行和不可行解空间内进行邻域搜索,同时采用Nagata提出的时间窗违反量计算方法[1-2]对解的时间窗约束违反进行评估。针对提出的新型问题的数值试验证明了所采用的时间窗违反量计算方法的时间节约性和有效性;同时由于该问题可以覆盖传统的累积性车辆路径问题,对后者的数值实验以及与其他优化算法的对比验证了所提出算法的优良求解效果。

引用

页码：49 / 55

页数：7

共 8 条

[1] 任务选择与交换的车辆路线优化问题与BETA求解算法 [J].

丛峰 ;

刘冉 ;

江志斌 .

工业工程与管理, 2013, 18 (03) :35-42

[2] 带时间窗的动态车辆路径问题的局部搜索算法 [J].

刘霞 ;

齐欢 .

交通运输工程学报, 2008, (05) :114-120

[3] A note on the time travel approach for handling time windows in vehicle routing problems [J].

Schneider, Michael ;

Sand, Bastian ;

Stenger, Andreas .

COMPUTERS & OPERATIONS RESEARCH, 2013, 40 (10) :2564-2568

[4]

The single vehicle routing problem with toll-by-weight scheme: A branch-and-bound approach[J] . Zizhen Zhang,Hu Qin,Wenbin Zhu,Andrew Lim.European Journal of Operational Research . 2012 (2)

[5]

An effective memetic algorithm for the cumulative capacitated vehicle routing problem[J] . Sandra Ulrich Ngueveu,Christian Prins,Roberto Wolfler Calvo.Computers and Operations Research . 2009 (11)

[6]

A genetic algorithm for the vehicle routing problem[J] . Barrie M. Baker,M.A. Ayechew.Computers and Operations Research . 2002 (5)

[7] Heuristic methods for vehicle routing problem with time windows [J].

Tan, KC ;

Lee, LH ;

Zhu, QL ;

Ou, K .

ARTIFICIAL INTELLIGENCE IN ENGINEERING, 2001, 15 (03) :281-295

[8]

A column generation algorithm for the vehicle routing problem with soft time windows .2 Federico Liberatore,Giovanni Righini,Matteo Salani. 4OR: A Quarterly Journal of Operations Research . 2011

← 1 →