车辆路径规划问题及其求解方法研究进展(1)
第24卷第11期(总第155期) 系 统 工 程2006年11月 System s Engineering 文章编号:100124098(2006) 1120031207
V o l . 24, N o. 11
N ov . , 2006
车辆路径规划问题及其求解方法研究进展
孙丽君, 胡祥培, 王 征
(大连理工大学)
Ξ
摘 要:对车辆路径规划问题(V eh icle P , , 根据目前的研究状况对该问题进行分类; ; 分四大类讨论求解该问题的算法:精确算法(exact ) , 发算法(constructive heuristic algo rithm ) , 改进启发式算法
(i m p roving algo , 和亚启发式算法(m eta 2heuristic algo rithm ) , 评述各类算法适用的问题求解; 探讨国内在V R P 领域的研究成果。在此基础上, 对求解该问题的方法进一步的研究方向做了展望。
关键词:车辆路径规划问题(V eh icle Routing P roblem , V R P ) ; 模型; 综述; 算法中图分类号:N 945; T P 18 文献标识码:A
1 引言
车辆路径规划是物流配送过程中的关键环节, 该环节处理的好坏将直接影响对客户需求的响应速度、客户对物流环节的满意度以及服务商的配送成本。车辆路径规划问题(V eh icle Routing P roblem , V R P ) 最早是由D antzig 和由于该问题是一个N P 难R am ser [1]于1959年首次提出的。
题, 随着节点数目的不断增多, 问题的求解过程将会极大地消耗系统的运行时间和存储空间, 因此它的提出很快引起了运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制订者和管理者的极大重视。随着近年来电子商务以及物流供应链系统的高速发展, V R P 也成为上述领域的研究热点。
车辆数最小等) [2]。
在实际应用过程中, V R P 可以按照不同的分类原则
细分为许多子问题。不同的分类属性的不同取值(见表1) 的组合形成了各种类型的问题。例如:当车辆装载状况取值为:非满载; 配送中心数目取值为:多配送中心; 车型数目取值为:单车型; 时间限制取值为:硬时间窗; 而需求信息取值为需求不确定; 那么该问题就是一个载重量限制下的多配送中心、单车型、硬时间窗的随机需求的V R P 问题。
考虑的属性越多, 问题越复杂, 求解越困难。目前研究的较为复杂的问题类型一般最多考虑3～4个属性。多数的研究都是只针对考虑了1～2个属性的问题展开。比如:
D ro r 等[3]研究的满载问题, 李军等[4]研究的非满载问题, Co rdeau 等[5]研究的带有时间窗的问题, Gendreau 等[6]研
2 车辆路径规划问题及其分类
车辆路径规划问题一般指的是:对一系列发货点和收货点, 调用一定的车辆, 组织适当的行车路线, 使车辆有序地通过它们, 在满足指定的约束条件下(例如:货物的需求量与发货量, 交发货时间, 车辆可载量限制, 行驶里程限制, 行驶时间限制等) , 力争实现一定的目标(如车辆空驶里程最短, 运输总费用最低, 车辆按一定时间到达, 使用的
究的多车型的问题等等都是针对1～2个属性进行研究。
近年来随着计算机科学, 通讯科技的发展, V R P 问题的研究领域逐渐拓宽, 最近几年研究的较多的问题类型有:
①多供货点问题(M ulti p le D epo t V R P , M DV R P ) :多个供货点可以同时对客户进行供货, 该类问题的研究涉及到供货点如何选择;
Ξ收稿日期:2006209215
基金项目:国家自然科学基金资助项目(70571009; 70171040; 70031020) ; 教育部科学技术研究重点项目(03052) ; 教育部博士点基金资助项目([1**********]) ; 辽宁省自然科学基金资助项目(2001101074)
作者简介:孙丽君(19792) , 女, 山东烟台人, 大连理工大学系统工程研究所博士研究生, 研究方向:电子商务, 物流工程等研究; 胡祥培(19622) , 男, 安徽黄山人, 大连理工大学系统工程研究所教授, 博士生导师, 研究方向:电子商务, 智能运筹学, 信息系统集成等; 王征(19782) , 男, 辽宁大连人, 大连理工大学系统工程研究所博士研究生, 研究方向:电子商务, 信息系统工程等。
32系 统 工 程 2006年
供货点; ②每个客户只应该被车辆访问一次; ③每条路径中的所有客户需求的总和不能超过车辆的载重量Q . 该经典V R P 模型定义的前提条件是所有的需求都是集货或者都是供货, 而非集货供货一体化。
网络图模型的优点是直观性强, 容易理解; 缺点是对参数的容纳能力有限, , 因此该 表1 车辆路径问题的分类属性及其取值
分类属性车辆载货状况车场(或货场, 配送中心) 数目车型数目时间要求
属性的取值
满载, 非满载
单车场(货场, 配送中心) , 多车场
(货场, 配送中心)
单车型, 多车型
无时间窗, 硬时间窗, 软时间窗确定需求, 随机需求; 3. V P 其数学模型针对不同问题条, , 以车流或物流为基础的数学。式(1) [8]与式(2) [9]分别给出了两类模型的一个例子, 其中式(1) 是针对单车型、带有硬时间窗、且有装载能力约束的V R P 编制的基于三下标车流变量的数学模型, 式(2) 则针对多车型、有最长行驶距离限制、集货送货一体化的V R P 给出了双下标物流变量组成的数学模型。
l
l
m
ij
信息的确定性间, 随机服务时间; 时间, …… (V R P w ith T i m e W indow s ,
V R PTW ) :每个客户对车辆的最早到达时间(earliest 最迟到达时间(latest ti m e ) 及服务时间(service ti m e ) 、
ti m e ) 均有一定的要求;
m in z =
l
∑∑∑c
i =0j =0k =1i ik
x ijk 目标函数
③随机问题(Stochastic V R P , SV R P ) :问题涉及的某类元素具有随机性, 比如需求的到达, 服务时间等等, 也有研究者将该类问题定义为动态车辆路径问题(D ynam ic
V R P , DV R P ) 。谢秉磊等[7]对DV R P 特征进行总结, 延伸
s . t .
∑g y
i =1m
≤q , k =1, …, m 车辆载重约束
∑y
k =1m
ik
=1, k =i , …, l
了该问题的定义, 对近些年该问题模型、渐进结果和算法的研究成果做了较为详细的回顾。
④分批交货问题(Sp lit D elivery V R P , SDV R P ) :相当于满载问题, 一个客户的需求需要多个车来满足。
⑤回程时集货的问题(V R P w ith Backhauls , V R PB ) :该类型的问题是指当所有的货物都送完之后车辆还要到一些客户处取货的问题。
⑥集货供货一体化问题(V R P w ith P ick 2U p s and
D eliveries , V R PPD ) :即车辆在送货之前要先取货的问题。
国内的研究一般分为对传统确定性V R P 的研究和对动态V R P 的研究两大类。近几年的研究多集中在对动态
V R P 的研究上。
基本任务约束
0k
∑y
k =1l
=m
∑x
i =0l
ijk
=y jk , j =0, 1, …, l ; k =1, …, m
道路约束
ijk
∑x
j =0
=y ik , i =0, 1, …, l ; k =1, …, m
s 0=0x ijk =1]
s i +t i +t ij =s j ,
i , j =0, …, l ; i ≠j
a j ≤s j ≤b j , j =1, …, l t i =m ax{a i -s i , 0}
x ijk =0或1, y ik =0或1,
时间窗约束
i , j =0, …, l ; k =1, …, m
变量
sig n (n k ) )
(1)
3 车辆路径规划模型形式及其特点
目前研究的车辆路径规划模型有两类, 一类为网络图模型另一类为数学模型。
m in z =
n k
∑(∑d
k =1
i =1
r k i
K
n k
r k (i -1) r k i
+d r kn
r k k 0
s . t .
3. 1 网络图模型
经典V R P 定义在图G =(V , E ) 上, 其中V ={v 0, v 1,
…, v n },E =(v i , v j ) , v i , v j ∈V . v 0表示供货点, 该供货点拥有m 辆载重量为Q 的同型车辆(m 可以是已知的, 也可以是决策变量) 。v 1, …, v n 代表n 个需求量分别为q i (i =1, …, n ) 的待访问的客户点。c ij 是弧或者说路段(v i , v j ) ∈E 的费用或者距离。经典V R P 在以下的约束条件下求解m 条路径的总行驶成本最小:①每条路径的起点和终点都是
∑q
i =1j i =1
≤Q k
∑u r k i +
i =j +1
∑q
n k
r k i
≤Q k ,
车辆载重约束
j =1, 2, …, n k -1 ∑u r k i ≤Q k
i =1n k n k
∑d r k (i -i =1
1) r k i
+d r kn
r k k 0
sig n (n k ) ≤D k 道路约束
第11期 孙丽君, 胡祥培等:车辆路径规划问题及其求解方法研究进展
0≤n k ≤L
K
33
的研究成果主要有:F isher [11]提出的K 2树法、Padberg 等[12]的分枝剪枝法、Koh l 和M adsen [13]用拉格朗日松弛算法求解带有时间窗的V R P 、Fum ero 等[14]的修正拉格朗日
[15]松弛及子梯度优化方法、L o rena L uiz 等对列生成方法
∑n k =L
k =1任务约
R k ={r k i r k i ∈{1,…, L },i =1, …, n k }
R k 1∩R k 2= , Πk 1≠k 2
的改进等。
、所含各元素之间的关系明确、。这些问
(2)
束
sig n (n k ) =
变量
0, 其他
数学模型的特点是:①容量大。该种模型对参数的容
1, n k ≥1
) 的明确准则, 得, 求解工作所需的计算。另外, 还有许多实际的V R P 不具, 并且有些问题不存在严格最优解(例如, 目标之间相互矛盾的多目标决策问题) , 或者有些问题要得到最优解需花费过大的代价, 当采用精确算法求解这种类型的问题时难以得到理想的效果, 它们的解决就需依赖于近似算法。
纳能力很大, 能够表达任何大规模的问题; 着实际应用需求的出现, 条件的变化而发生一些改变, 形式, 基于V R P (3) m in or m z f (x )
与车辆能力相关的约束与时间窗相关的约束
s . t . 与任务相关的约束与道路网络流量相关的约束其他约束
变量设定在该结构中要增加、减少或者改变一些约束, 只需要对相应约束内容对应的式子进行操作; ③通用性强。一旦将路径规划问题抽象成上述的数学模型, 从模型本身就很难看出原问题所属的领域, 任何可以抽象成该类型模型的其他管理决策问题都可以用这类模型表示。这一特点也使得
V R P 在抽象成上述数学模型的过程中失去了本身的问题
(3)
4. 2 构造启发式算法
构造启发式算法是将尚未指定路线的客户按照某些标准插入到现有的已部分形成的路线中去, 以最终形成解。该算法是求解V R P 问题最早使用的近似算法。C larke 和W righ t 提出的C 2W 节约算法[16], Gillett 和M iller 提出的扫描算法[17], 以及So lomon 提出的最近邻启发式算法[18]都是构造启发式算法中最为经典的算法。其后虽有很多学者将这些经典算法加以改进, 但这些改进大都以缩短计算时间和减少内存的占用为目标, 对于当代如此发达的计算机而言, 这些改进都是微不足道的。
虽然构造启发式算法简单易懂, 但有时找到的解离最优解差的较远, 因此该算法现已不单独用来求解V R P 问题, 而是与改进算法相结合, 用在构造初始解阶段。
特征, 其求解过程单纯是对数据的操作, 因此求解的结果将是不带任何领域知识和信息的数据, 要将这些数据包含的意思还原成用户能够理解的形式, 需要寻找建模之初对这些变量做的假定含义, 这个过程往往需要专家来实现, 这样就造成了模型使用过程的复杂化。
4. 3 改进启发式算法
改进启发式算法可以将构造启发式算法得到的比较差的解, 通过邻域的搜索反复改进, 得到较好的解。改进启发式算法大概可以分为路线内部改进和路线间改进两种, 路线内部改进是将某条路线内部的某些边和结点互换位置, 而路线间改进是在相邻路线之间交换一些边和结点来改进当前的解。
具有代表性的求解V R P 的改进启发式算法有k 2op t 以及Κ2interchange 算法。Op t 算法来自于L in [19]提出一种旅行商问题(T raveling Sales m an P roblem , T SP ) 的路径优化思想, 其思想是对给定的初始回路, 通过每次交换k 条边来改进当前解。后续的研究者对该算法加以扩展, 延伸应用到V R P 领域, 出现了32op t 算法和42op t 3算法等一系列op t 算法[20-22]
4 车辆路径规划问题求解算法概述
由于V R P 包含了旅行商问题(T raveling Sales m an P roblem , T SP ) , 而T SP 本身就是N P 难题, 所以V R P 也是一个N P 组合优化难题[10]。自该问题被提出之日起, 国内外学者力求构造高效的算法来解决这一难题, 这些求解算法大体可分为两类, 一类为精确算法(exact algo rithm ) , 另一类为近似算法(app roxi m ati on algo rithm ) , 其中的近似算法又可以大致分为三类:构造启发式(constructive
heuristics ) 算法, 改进启发式(i m p roving heuristics ) 算法,
。该算法在求解V R P 问题时, k 条边可以
亚启发式(m etaheuristics ) 算法。下文就这四类算法近些年的研究成果做简要评述。
是路线内部的, 也可以是路线之间的。Κ2interchange 算法由O s m an [23]发起, 它的思想是在几条线路之间相互交换一些客户来改进路线。该算法在后续的研究中也被应用解决多类V R P 问题, 如有时间窗的V R P [24]。
4. 1 精确算法
基于V R P 的传统数学模型的精确型求解算法代表性
34系 统 工 程 2006年
该类算法的优点是得到最优解的概率较高, 缺点是随
蚁群算法是近士几年来新兴起的一种摹仿蚂蚁觅食行为的算法。可以查到的最早将该算法应用到路径规划问题上的文献的年代始于1995年[35]。此后, Gam bardella 和Do rigo [36,37], Stutzle 和Hoo s [38], Bullnhei m er , H artl 和
Strauss [39]以及M azzeo 和L o iseau [40]都有将该算法应用到
着k 和Κ值的增大, 运算时间会成倍增长, 不利于实时系统的处理。
4. 4 亚启发式算法
构造启发式算法和改进启发式算法都不允许劣质中间解的产生, 而只允许解的优化结果朝好的方向单向递增, 因此这两种算法都较容易陷入局部最优, 为了克服这一缺点, 多种亚启发式算法相继出现。亚启发式算法在优化问题的过程中允许劣质的中间解出现, 能够跳出局部最优而在全局内寻优。
用于求解V R P 、模拟退火、遗传算法、蚁群算法等。[25]在
1986年首次提出, 效率高, 适
路径规划问题中并获得成功。、正反馈选择、并且可以根据需要为人、。因此, 该算。但是这种算法也存在一, 容易出现停滞现象(stagnati on
r ) , 即搜索进行到一定程度后, 所有个体所发现的
解完全一致, 不能对解空间进一步进行搜索, 不利于发现更好的解。现在对该算法的研究大多数都集中在对这些缺陷进行改进上。
综合上文分析可以发现, 每一种算法单独工作都会存在一些比较大的缺陷, 而且随着社会的发展, 问题规模不断扩大化, 结构不断复杂化, 单一的算法很难解决现实中复杂化的问题。如果将几类算法融合贯通, 取长补短, 就可以克服很多缺点, 构造出比较好的算法。近10几年对算法的研究开始侧重于融合多种算法, 构造混合算法上。
, V R P 复杂性的提高和问题领域的延伸, 该算法在近些年来更是备受研究者的亲睐, 很多复杂的问题都用该算法解决。例如:Chao [26]、
Scheuerer [27]用该算法解决了带拖车的货车V R P ; B randao [28]用该算法解决了开放的V R P ; Ho 和H augland [29]解决了带时间窗的分批交货的V R P ; M ontane 和Galvao [30]用该算法解决了集货供货一体化的
但禁忌搜索算法具有对初始解有较强的依赖性和搜V R P 。
索过程中只能对一个解操作的缺陷, 所以往往需要使用别的启发式方法先获得一个较好的初始解。
模拟退火算法(si m ulated annealing algo rithm ) 是由
K irkpatrick 等[31]提出的一种求解组合最优化问题的算
5 国内在V R P 领域的
研究成果与进展
国内对V R P 问题的研究是随着近几年电子商务物流配送业的发展而发展起来的。根据研究的问题类型的不同, 可以将国内的研究工作大体分为两个阶段:第一个阶段是对确定性V R P 的研究, 第二个阶段是对动态V R P 的研究。
在第一个阶段的研究中, 国内学者的研究多集中于对已有V R P 算法的改进, 其中较多的是对C 2遗W 节约算法、传算法两类算法的改进。较有代表性的成果有:李军等人用C 2W 节约算法实现了有时间窗的车辆路径安排[41]; 设计了基于自然数编码的遗传算法, 并将其用于求解非满载车辆调度问题, 在实验分析中获得了较好的结果[42]; 采用先分组、后组内安排路线的启发式方法解决多车场情况的非满载的小货运量运输问题[43], 提高了车辆的使用效率; 另有文献[44]～[48]的研究都是对C 2遗传W 节约算法、算法两类算法的改进应用到求解各种不同类型的确定性
V R P 问题中。
法。该方法适用的领域较多, 具有较强的实用性, 并可人为地控制迭代次数, 反复求解。然而该方法所得解的好坏与初始状态、温度函数等都有一定的联系, 降温较快的效果不一定很好, 效果好的, 其降温过程又极其缓慢。该法创立之初对于解决单目标路径规划问题可以得到非常满意的解, 虽然后经过一些学者如U lungu 和T eghem [32](1994) 的研究改进, 可以解决多目标问题, 但是就其运算过程和得到的解来说不如遗传算法的效果好。
遗传算法通过多个个体间的选择、交叉等的遗传操作, 相互协力地进行解的探索, 与以前的算法中对单纯的并列的解的探索相比, 容易发现更好的解。遗传算法运用到V R P 上, 对于解诸如带有时间窗的V R P
[33,34]
, 先分组后
安排路径的路径规划问题等等一些具有多目标的路径规划问题, 取得了很好的效果。然而在运用该方法的过程中, 问题的遗传因子型的表现依赖于设计者的能力。并且该算法所得结果的好坏, 主要依赖于遗传代数和解组规模, 在实际应用中只能根据具体要求, 在合理的时间内对问题进行求解, 若所得解不能令人满意, 就要增大解组规模或遗传代数, 从而有希望得到问题的全局最优解, 当然, 这是以延长计算时间为代价的。
动态车辆路径问题是近年来V R P 研究领域的一个新发展, 它比传统的确定性车辆路径问题更符合实际, 更有理论和应用价值。最近几年, 国内对该问题的关注与研究逐渐增多, 其中有代表性的研究成果之一是出自于西南交通大学郭耀煌教授带领下的团队[49-52]
; 另外还有刘浩等
人将快速扫描算法与模拟退火算法相结合, 首先用快速扫描算法求一个初始可行解, 然后用模拟退火思想求近似最
第11期 孙丽君, 胡祥培等:车辆路径规划问题及其求解方法研究进展优解, 用该混合算法实现了求解单类型车辆随机需求问题的一个例子[53]; 张涛等将遗传算法和禁忌搜索算法的结合混合算法引入到求解V R P 中[54], 实现了不确定车辆数的车辆路径问题的求解。
由于国内对V R P 问题的研究起步较晚, 有国外研究学者的研究成果作基础, 因此国内第一个阶段的研究中, 基础性的工作较少, 都是直接对已有的算法进行改进以使其能够运用到较复杂的问题中; 或者直接利用已有的算法构造混合算法, 以弥补单一算法求解过程的不足或者单一算法不能够求解多目标约束的V R P 的不足; 的研究则涉及到对模型的建立与分析, 等各个方面。
35
融合了问题领域知识的仿真模型和知识化模型则可以克服这一缺点, 因此使用仿真手段和知识工程领域内的技术手段来解决路径规划问题, 以使求解结果更符合实际问题的要求是未来V R P 研究领域应该拓展的方向。
(3) 算法的改进。算法方面的研究将在原来的纯数学
模型的更快、更简单的、, 以满R 。上述各研究方面的改变将促使原先为特定的车辆路径规划问题构造高效的求解算法, 由此形成计算机程序, 并给出最优规划方案这种面向数学模型的决策支持方法逐渐向由计算机自动识别V R P →自动生成模型→自动求解模型获得最优行车路径的决策支持方法转变。该种决策支持系统具有动态适应性, 能够对动态
V R P 进行实时调控, 可以满足目前电子商务环境对V R P
6, 在现有V R P 问题与求解方法研究成果基础上, 车辆路径规划问题领域的研究趋势将向以下几个方向发展:
(1) 模型与算法的研究角度将由离线、非实时的应用
提出的在线实时和快速高效的要求。该类系统将进一步提高决策的自动化程度, 并为其它领域的决策支持系统的研究提供借鉴。
车辆路径规划作为物流系统中关键的环节, 已经受到越来越多的重视。本文在对物流配送系统中的车辆路径规划问题的定义和分类做了简要评述的基础上, 分析了该类问题的模型的特征, 回顾了国内外求解该问题的现有算法并总结了它们的优缺点, 对V R P 的未来研究方向做了分析, 为下一步的研究提供指导, 并期能为在该领域内从事研究工作的学者提供借鉴。
转向在线实时应用上。综合分析V R P 模型和算法的现有研究, 可以发现研究的角度大都是面向离线的、非实时的应用, 不能满足某些应用场合进行实时动态调度的需要。鉴于传统纯数学模型与求解算法通常需要较长的建模与计算时间, 因此, 应用人工智能技术和专家系统来构建模型并求解, 从而提高响应速度, 是一种现实的途径。
(2) 模型的知识化与智能化程度将提高。现有的V R P
模型通用性强的特点使得该类问题在抽象成传统数学模型的过程中失去了本身的问题特征, 这样就造成了模型求解必然要脱离原问题, 得到的解将很难满足实际的要求。
参考文献:
[1] D antzig G , R am ser J . T he truck dispatch ing p roblem [J ]. M anagem ent science , 1959, (6) :80～91. [2] 胡运权, 郭耀煌. 运筹学教程[M ]. 北京:清华大学出版社, 1998:410.
[3] D ro r M , L apo rte G , T rudeau P . V eh icle routing w ith sp lit deliveries [J ]. D iscrete A pp lied M athem atics , 1994, 50
(3) :239～254.
[4] 李军, 谢秉磊, 郭耀煌. 非满载车辆调度问题的遗传算法[J ]. 系统工程理论方法应用, 2000, 9(3) :235～239. [5] Co rdeau J F , D esaulniers G , D esro siers J , So lomon M , Soum is F . V R P w ith ti m e w indow s [A ]. To th P , V igo D .
T he veh icle routing p roblem [C ]. Ph iladelph ia :S I AM M onograph s on D iscrete M athem atics and A pp licati ons , 2002:157～194.
[6] Gendreau M , L apo rte G , M usaraganyi C , T aillard E D . A tabu search heuristic fo r the heterogeneous fleet
～1173. veh icle routing p roblem [J ]. Computers &Operati ons R esearch , 1999, 26(12) :1153
[7] 谢秉磊, 郭耀煌, 郭强. 动态车辆路径问题:现状与展望[J ]. 系统工程理论方法应用, 2002, 11(2) :116～120. [8] 谢秉磊, 李军, 郭耀煌. 有时间窗的非满载车辆调度问题的遗传算法[J ]. 系统工程学报, 2000, 15(3) :290～294. [9] 郎茂祥. 装卸混合车辆路径问题的模拟退火算法研究[J ]. 系统工程学报, 2005, 20(5) :485～491.
[10] Garey M R , Johnson D S . Computers and intractability :a guide to the theo ry of N p 2comp leteness [M ]. N ew
Yo rk :W H F reem an &Co , 1979.
[11] F isherM L . Op ti m al so luti on of veh icle routing p roblem s using m ini m um k 2trees [J ]. Operati ons R esearch , 1994,
36
42(4) :141～153.
系 统 工 程 2006年
[12] Padberg M , R inaldi G . A branch 2and 2cut algo rithm fo r the reso luti on of large 2scale symm etric traveling sales m an
～100. p roblem s [J ]. S I AM R eview , 1991, 33(1) :60
[13] Koh l N , M adsen O B G . A n op ti m izati on algo rithm fo r the veh icle routing p roblem w ith ti m e w indow s based on
～406. lagrangian relaxati on [J ]. Operati ons R esearch , 1997, 45(3) :395
[14] Fum ero F . A modified subgradient algo rithm fo r L agrangean relaxati on [J ].
and Operati ons
～52. R esearch , 2000, 28(1) :33
[15] L o rena L uiz A N , Senne Edson L F . A co lum n on roach edian p roblem s [J ].
～Computers and Operati ons R esearch , 2004, 31(6) :863
[16] C larke G , W righ t J W . Scheduling of veh icles t a ber of delivery po ints [J ]. Operati ons
～581. R esearch , 1964, 12(4) :568
[17] Gillett B E , M iller L R . r veh icle 2dispatch p roblem [J ]. Operati ons R esearch , 1974, 22
(2) :240～.
[18] So lomon . lgo s r the veh icle routing and scheduling p roblem s w ith ti m e w indow constrains [J ].
～265. Operati ons R , 1987, 35(2) :254
[19] L in S . Computer so luti ons of the traveling sales m an p roblem [J ]. Bell System T echnical Journal , 1965, 44(10) :
2245～2269.
[20] T aillard E , Badeau P , Gendreau M , Guertin F , Po tvin J Y . A tabu search heuristic fo r the veh icle routing p roblem
～186. w ith soft ti m e w indow s [J ]. T ranspo rtati on Science , 1997, 31(2) :170
[21] Po tvin J Y , Kervahut T , Gareau B I , Rousseau J M . T he veh icle routing p roblem w ith ti m e w indow s , Part I :
～164. T abu search [J ]. I N FORM S Journal on Computing , 1996, 8(2) :158
[22] Po tvin J Y , Bengi o S . T he veh icle routing p roblem w ith ti m e w indow s , Part II :genetic search [J ]. Info r m s Journal
～172. on Computing , 1996, 8(2) :165
[23] O s m an I H . M etastrategy si m ulated annealing and tabu search algo rithm s fo r the veh icle routing p roblem [J ].
～451. A nnals of Operati ons R esearch , 1993, 41(4) :421
[24] T an K C , L ee L H , Zhu Q L , O u K . H euristic m ethods fo r veh icle routing p roblem w ith ti m e w indow s [J ].
～295. A rtificial Intelligence in Engineering , 2001, 15(3) :281
[25] Glover F . T abu search :part I [J ]. Journal on Computing , 1989, 1(3) :190～206.
[26] Chao I M . A tabu search m ethod fo r the truck and trailer routing p roblem [J ]. Computers &Operati ons
～51. R esearch , 2002, 29(1) :33
[27] Scheuerer S . A tabu search heuristic fo r the truck and trailer routing p roblem [J ]. Computers &Operati ons
～909. R esearch , 2006, 33(4) :894
[28] B randao J . A tabu search algo rithm fo r the open veh icle routing p roblem [J ]. European Journal of Operati onal
～564. R esearch , 2004, 157(3) :552
[29] Ho S C , H augland D . A tabu search heuristic fo r the veh icle routing p roblem w ith ti m e w indow s and sp lit
～1964. deliveries [J ]. Computers &Operati ons R esearch , 2004, 31(12) :1947
[30] M ontane F A T , Galvao R D . A tabu search algo rithm fo r the veh icle routing p roblem w ith si m ultaneous p ick 2up
～619. and delivery service [J ]. Computers &Operati ons R esearch , 2006, 33(3) :595
[31] K irkpatrick S , Gelatt C D , V ech i J r M P . Op ti m izati on by si m ulated annealing [J ]. Science , 1983, 220(4598) :671
～680.
[32] U lulgu L E , T eghem J . M ulti objective com binato rial op ti m izati on p roblem s :a survey [J ]. Journal ofM ulticriteria
～104. D ecisi on A nalysis , 1994, 3(2) :83
[33] Berger J , BarkaouiM , O llibraysy . A route 2directed hybrid genetic app roach fo r the veh icle routing p roblem w ith
～194. ti m e w indow s [J ]. I N FOR , 2003, 41(2) :179
[34] Berger J , BarkaouiM . A parallel hybrid genetic algo rithm fo r the veh icle routing p roblem w ith ti m e w indow s [J ].
～2053. Computers &Operati ons R esearch , 2004, 31(12) :2037
第11期 孙丽君, 胡祥培等:车辆路径规划问题及其求解方法研究进展37
[35] Gam bardella L M , Do rigo M . A nt 2Q :a reinfo rcem ent learning app roach to the traveling sales m an p roblem [A ].
～260. P roc . 12th Internati onal Conference on M ach ine L earning [C ]. T ahoe C ity , CA , 1995:252
[36] Gam bardella L M , Do rigo M .
So lving symm etric and asymm etric T SP s by ant co lonies [A ].
P roc .
IEEE
～627. Internati onal Conference on Evo luti onary Computati on [C ]. 1996:622
[37] Do rigo M , Gam bardella L M . A nt co lony system :a cooperative learning app roach to the traveling sales m an
～66. p roblem [J ]. IEEE T rans Evo luti onary Computati on , 1997, 1(1) :53
[38] Stutzle T , Hoo s H . T he M A X 2M I N ant system and local search fo r the an p roblem [A ]. P roc .
IEEE Internati onal Conference on Evo luti onary Computati [C ]. [39] Bullnhei m er B , H artl R F , Strauss C . A n i m p roved ant rithm r veh icle routing p roblem [J ].
～A nnals of Operati ons R esearch , 1999, 89:319
[40] M azzeo S , L o iseau I . A n ant co lony algo fo r veh icle routing [J ]. E lectronic N o tes in D iscrete
M athem atics , 2004, 18:181
[41] 李军. [J ]. 系统工程, 1996, 14(5) :45～50.
[42] 李军, . [J ]. 系统工程理论方法应用, 2000, 9(3) :235～239. [43] 李军, 郭强, . 组合运输的优化调度[J ]. 系统工程理论与实践, 2001, (2) :117～121.
[44] 林晓宇, 李金铭, 纪寿文. 车辆路径问题C larke 2～W righ t 算法的改进与实现[J ]. 交通与计算机, 2004, 6(22) :72
75.
[45] 廖洁君, 陈燕. 城市物流中多目标配送模型[J ]. 大连海事大学学报, 2004, 30(4) :82～85.
[46] 王惠, 陈燕. 基于遗传算法的多目标的有时间窗的车辆调度[J ]. 计算机应用, 2004, 24(9) :144～146. [47] 鄢洁, 熊桂喜. 基于遗传算法的商用车辆调度策略研究[J ]. 计算机与现代化, 2004, (12) :9～12.
[48] 张翠军, 刘坤起, 刘永军. 求解一般车辆优化调度问题的一种改进遗传算法[J ]. 计算机工程与应用, 2004, (33) :
201～211.
[49] 郭耀煌, 谢秉磊. 一类随机动态车辆路径问题的策略分析[J ]. 管理工程学报, 2003, 17(4) :114～115.
[50] 张建勇, 李军, 郭耀煌. 模糊需求信息条件下的实时动态车辆调度问题研究[J ]. 管理工程学报, 2004, 18(4) :69～
72.
[51] 郭强, 谢秉磊. 随机旅行时间车辆路径问题的模型及其算[J ]. 系统工程学报, 2003, 18(3) :244～247.
[52] 张建勇, 郭耀煌, 李军. 基于顾客满意度的多目标模糊车辆优化调度问题研究[J ]. 铁道学报, 2003, 25(2) :15～17. [53] 刘浩, 钱小燕, 李舒展. 单类型车辆随机需求V R P 的一个算法[J ]. 南京建筑工程学院学报, 2001, (4) :25～29. [54] 张涛, 张杰, 王梦光. 不确定车辆数的车辆路径问题模型和混合算法[J ]. 系统工程理论方法应用, 2002, 11(2) :
121～130.
Rev iews on Veh icle Routi ng Problem and Its Solution M ethods
SUN L i 2jun , HU X iang 2p ei , W AN G Zheng
(Institute of System s Engineering , D alian U niversity of T echno logy , D alian 116023, Ch ina )
Abstract :Focusing on veh icle routing p roblem s (V R P ) , th is paper summ arizes and review s dom estic and abroad researches on models and algo rithm s in th is field comp rehensively . F irst of all , w e divide veh icle routing p roblem s into . different k inds acco rding to values of their common attributes
T hen , after introducing the graph model and
. Besides m athem atical model of the p roblem , w e analyze the advantages and disadvantages of the tw o k inds of models
that , w e review four k inds of algo rithm s fo r V R P , exact algo rithm , constructive heuristic algo rithm , i m p roving heuristic algo rithm and m eta 2heuristic algo rithm . O n the basis of analyzing the past ach ievem ents and sho rtages , next research directi ons in the field are discussed . Key words :V R P ; M odel ; R eview ; A lgo rithm