车辆路径规划问题及其求解方法研究进展

《车辆路径规划问题及其求解方法研究进展》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第)%卷第""期(总第"HH期+系统工程075V)%/G7V"")##*年""月WXC91?CY:;3:11=3:;G7DV/)##*文章编号!"##"$%#&’()##*+""$##,"$#-车辆路径规划问题及其求解方法研究进展.孙丽君/胡祥培/王征(大连理工大学系统工程研究所/辽宁大连""*#),+摘要!对车辆路径规划问题(012345167893:;<=7>51?/06<+领域的研究进行综述/根据目前的研究状况对该问题进行分类@分析该问题的图模型和数学模型两大类模型各自的优缺点@分四大类讨论求解该问题的

2、算法!精确算法(1AB49B5;7=392?+/构造启发式算法(47:C9=8493D1218=3C934B5;7=392?+/改进启发式算法(3?E=7D3:;218=3C934B5;7=392?+/和亚启发式算法(?19B$218=3C934B5;7=392?+/评述各类算法适用的问题求解阶段以及各自的优缺点@探讨国内在06<领域的研究成果F在此基础上/对求解该问题的方法进一步的研究方向做了展望F关键词!车辆路径规划问题(012345167893:;<=7>51?/06<+@模型@综述@算法中图分类号!G

3、&%H@I<"’文献标识码!J车辆数最小等+N)OF"引言在实际应用过程中/06<可以按照不同的分类原则车辆路径规划是物流配送过程中的关键环节/该环节细分为许多子问题F不同的分类属性的不同取值(见表"+处理的好坏将直接影响对客户需求的响应速度K客户对物的组合形成了各种类型的问题F例如!当车辆装载状况取流环节的满意度以及服务商的配送成本F车辆路径规划问值为!非满载@配送中心数目取值为!多配送中心@车型数题(012345167893:;<=7>51?/06<+最早是由LB:9M3;和目取值为!单车型@时间限制取值

4、为!硬时间窗@而需求信6B?C1=N"O于"&H&年首次提出的F由于该问题是一个G<息取值为需求不确定@那么该问题就是一个载重量限制难题/随着节点数目的不断增多/问题的求解过程将会极下的多配送中心K单车型K硬时间窗的随机需求的06<问大地消耗系统的运行时间和存储空间/因此它的提出很快题F引起了运筹学K应用数学K组合数学K图论与网络分析K物考虑的属性越多/问题越复杂/求解越困难F目前研究流科学K计算机应用等学科的专家与运输计划制订者和管的较为复杂的问题类型一般最多考虑,P%个属性F多数理者的极大重视F随着近年来

5、电子商务以及物流供应链系的研究都是只针对考虑了"P)个属性的问题展开F比如!N,O研究的满载问题/李军等N%O研究的非满载问题/统的高速发展/06<也成为上述领域的研究热点FL=7=等NHO研究的带有时间窗的问题/S1:R=1B8等N*O研Q7=R1B8等)车辆路径规划问题及其分类究的多车型的问题等等都是针对"P)个属性进行研究F近年来随着计算机科学/通讯科技的发展/06<问题车辆路径规划问题一般指的是!对一系列发货点和收的研究领域逐渐拓宽/最近几年研究的较多的问题类型货点/调用一定的车辆/组织适当的行车路线

6、/使车辆有序有!地通过它们/在满足指定的约束条件下(例如!货物的需求T多供货点问题(U8593E51L1E7906

7、H)+@教育部博士点基金资助项目()##"#"%"#)H+@辽宁省自然科学基金资助项目()##""#"#-%+作者简万方数据介!孙丽君("&-&$+/女/山东烟台人/大连理工大学系统工程研究所博士研究生/研究方向!电子商务/物流工程等研究@胡祥培("&*)$+/男/安徽黄山人/大连理工大学系统工程研究所教授/博士生导师/研究方向!电子商务/智能运筹学/信息系统集成等@王征("&-’$+/男/辽宁大连人/大连理工大学系统工程研究所博士研究生/研究方向!电子商务/信息系统工程等FOb系统工程bWW~年表!车辆路径

8、问题的分类属性及其取值供货点%’每个客户只应该被车辆访问一次%>每条路径中的所有客户需求的总和不能超过车辆的载重量^P该分类属性属性的取值经典()*模型定义的前提条件是所有的需求都是集货或车辆载货状况满载"非满载者都是供货"而非集货供货一体化B车场#或货场"单车场#货场"配送中心$"多车场网络图模型的优点是直观性强"容易理解%缺点是对配送中心$数目#货场"配送中心$参数的容纳能力有限"能够使用的求解