【doc】车辆路径问题Clarke-Wright算法的改进与实现
车辆路径问题Clarke-Wright算法的改进与
实现
交通与计算机2004年第6期第22卷(总第121期)
车辆路径问题Clarke—Wright算法的改进与实现
林晓字李金铭.纪寿文.
(福建农林大学福州350002)(清华大学.北京100084)
摘要对车辆路径问题Clarke—Wright算法进行改进，增加体积约束条件以提高算法的
适用性，用Java语言实现，并且应用于车辆调度系统.
关键词Clarke—Wright算法；车辆路径问题；车辆调度
Abstract:ClarkeWrightalgorithmofvehicleroutingproblemisimprovedinthispaper.
V olumeconstraintisaddedtothealgorithmtoimprovetheapplicability.ImplementedbyJava ,
thealgorithmisappliedtovehicledispatchingsystem.
Keywords:ClarkeWrightalgorithm;vehicleroutingproblem;vehicledispatching
1VRP
VRP即车辆路径问题(vehiclerouting
problem).它可分为确定性和不确定性两类.所
谓确定性是指节点的需求和信息是已知的.确定
性VRP的解决又分为:①精确算法;②人工智能
算法.精确算法可以分为3个大类：直接树搜索算
法，动态规划方法和整数线性规划.精确性算法基
于严格的数学手段，在可以求解的情况下，其解通
常要优于人工智能算法.但由于引入严格的数学
方法，因而无法避开指数爆炸问题，从而使该类算
法只能有效求解中小规模的确定性VRP.在求
解中小规模VRP时，人工智能算法与精确算法
相比，在精度上不占优势.但在求解大规模VRP 时，人工智能方法总可以在有限时间里，到满意的次优解/可行解，这是精确算法难以做到的.因此，在实际应用中，人工智能算法应用更广泛.
常见的有特的人工智能算法有启发式算
法，遗传算法，神经网络算法等等.
2CW算法研究与改进
Clarke—Wright算法简称CW算法是启发式
算法中的一种，用来解决车辆数不固定的VRPuJ.自提出后，得到了普遍的认同.它简单，易于理解，灵活性好，可分析性及交互式特性都较好，不少算法都局部或是全部应用了该方法.国内用该算法解决车辆路径优化问题的研究还较少. 收稿日期:2004—07—05
1)问题的定义和描述.车辆路径问题一般定
义为：对一系列装货点和(或)卸货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如交发货时间，车辆容量限制等)下，达到一定的目标(如路最短，费用最少，时间尽量少, 使用车辆尽量少等).
集货或送货非满载车辆优化调度问题一般描
述为：有一个车场，拥有容量为g的车辆，现有足项货物运输任务需要完成，以1,2,…k表示，已知任务的货运量为g(=1,2,…志)，且g<g，求
满足货运需求的费用最小的车辆行驶线路.
如果把每项任务要求在一定的时间范围内完成，则问题就成为有时间窗的车辆优化调度问题. 有时间窗约束的单车场单车型调度问题的描
述如下.
以.s表示任务i的开始时间，任务i处需要
耽搁的时间(卸货)为T(即服务时间)，设开始时
间需在一定的时间范围EET,]内，其中砑
为任务i的允许最早开始时间，为任务的允库丘林
许最迟开始时间，则有≤≤.如果车辆
到达i的时间早于砑，则车辆需等待；如果车辆
到达时间晚于，则任务要延迟进行.
在一个中心货场给各分店配送的情况下，通
常，货物只要在当天送到，第2天可使用即可，各
分店对货物送达时间没有严格的要求.在这种情
况下，可以应用无时间窗的车辆优化调度算法.
在一个中心货场给各顾客配送的情况下，客
户通常要求货物在某个时间段送达.对于物流中
心向物流结点分派货物，为了提高生产效率或保
车辆路径问题Clarke—Wright算法的改进与实现——林晓宇李金铭纪寿文73 证货物及时供给，也要求工人在规定的时间段内
送达货物.因而，有时间窗的车辆优化算法的应用
也成为必要.
2)算法原理.假设以Cu表示车辆从点行驶
到点的费用，可以得到点i和点连接在一条
线路上的费用节约值s(i,)一Cm+Cjo—GJ
抄税若各项任务要求在一定的时间范围内完成,
按费用节约值s(i,)连接点i和点时，可能会使
后面任务的执行不满足时间要求.当连接点i和
所在线路时，若车辆到达点的时间比原线路
上点任务的开始时间提前，则车辆在后面的
任务处有可能需要等待；若连接后到达点的时
间比原线路上点任务的开始时间推迟，则后
面的任务在执行时可能会发生延迟.
以EF表示连接点i和点所在的线路后,
车辆到达点的时间比原线路上车辆到达点时
间的推迟量(或提前量)，计算如下:
EFi—sijrTi+tij—si
显然,EFJ<O时，车辆到达点任务的时间
提前;EF一0时，到达时间不变;EF>0时，到达时间推迟.
为便于说明问题，定义参数如下.
△一为车辆在线路上点后面的各任务处
均不需要等待的点的到达时间的最大提前量; △+J为路上J点后面的任务不违反时间窗
约束的点的到达时间的最大允许推迟量.
△一和△+可分别按下列公式计算
△一一min{S，一Et,)(,.≥)
△+—min{LT，一.s,)(r≥)
当考虑连接点i和点所在的线路时，需检
黄山市旅游景点
查是否违反时间窗约束.
当EFJ<O时，若IEFI≤△一，车辆在后
面的任务处不需要等待，否则，要等待;
当EF>O时，若有IEFJI≤△+，则后面
的任务处不会延迟，否则，延迟进行.
由于时间窗的引入，在对称的费用情况下，连
接点和点i与点i和点不再相同.
3)增加体积约束条件.我们发现,CW算法
最大的优点是便于扩展.在前人的算法中，仅时间有约束和载重约束.但是在实际运输过程中，两个约束条件是不够的.因为车的容积是有限的，所以不得不考虑在算法中增加容积约束条件.
这样，在连接点对时，一条线路上各任务的货
运量之和应不大于车辆的载重；并且货运总体积
北京什么时候供暖不能超过车辆的容积.求总容积最简单的方法是
把所有货物的体积相加.但是由于各种货物形状
万千，装载时不可能致密无缝.按照经验数据，在
求总容积时，乘以一个经验系数0.75，由此来考
虑容积约束.以下将详细描述算法求解步骤.
由于增加了容积限制，所以整个优化路径的
工伤认定标准求解过程如图1所示.
一任务要求llI时问窗，完成时问，卜——卜叫载重，容积限制等llL二==车辆特征zIl车速，载重等l图1优化路径求解过程
4)改进CW算法的实现.
(1)算法求解步骤.
步骤1计算s(,)，令m一{s(,)Is(,)
>0).
步骤2在内按s(i,)从大到小的顺序排
列.
中秋节多少号步骤3若一声，则终止，否则对第一项
s(i,)，考察对应的(,)，若满足下述条件之一:
①点i和点均不在已构成的线路上;②点i或点
在已构成的线路上，但不是线路的内点(即不与
车场相连);③点i和点位于已构成的不同线
路，均不是内点，且一个是起点，一个是终点.则转
下步，否则转步骤7.
步骤4考察点和点连接后的线路上总
货运量Q，及总容积，若Q≤g且≤，则转下
步，否则转步骤7.
步骤5计算EFJ=(s+Tf+tij-S)：若EF
一0；则转步骤6；若EF<0，则计算△一，当

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。