[摘 要] 非满载的车辆调度问题可以看作是有容量限制的TSP问题，本文通过对TSP问题的C-W算法进行改进，从而找到了非满载、有时间约束的VRP问题求解的途径，并通过8个客户的实例进行验证，可以找到满意解。
[关键词] 非满载 车辆调度 启发式算法
一、问题的描述及数学模型的建立
1.问题的描述。为了问题便于叙述，将车场编号为0，任务编号为1，2,…L，任务及车场均以点i(i=0,1,…L)来表示。以Si表示车辆到达点i的时间，tij表示车辆由点i行驶到点j的时间，一般应有以下关系式:So＝0 ETi≤Si≤LTi
设完成任务i需要的时间为Ti，任务i的开始时间需在一定时间范围[ETi，LTi]内，ETi为任务i的允许最早开始时间，LTi为允许最迟开始时间。如果车辆到达i的时间早于ETi，则车辆需在i处等待，如果车辆到达晚于LTi，则任务i要延迟进行。
2.数学模型。定义变量如下:
则:目标函数： （1）
约束条件: （2）
（3）
（4）
（5）
（6）
（7）
（8）
（9）
(1)式中Cij为从点i到点j的运输成本；（2）式为车辆载重约束;(3)式为点i任务由车辆k完成;（4）、(5)式为客户车辆惟一性约束。
二、算法原理及步骤
1.算法原理。连接点i和j在一条线路上费用的节约值为:。
以EFj表示连接点i和点j所在线路后，车辆到达j点的时间比原线路到达j点的时间提前（或推迟）量，则：
为了便于时间问题的讨论，需要定义两个重要的变量：
—车辆在线路上j点后面各任务处均不需要等待的j点的到达的最大提前量。—线路上j点后面的任务不违反时间约束的j点的到达时间的最大允许推迟量。
在连接点 和点 所在线路时，需要检查是否违反时间约束：
(1)当EFj〈0时，如有，车辆在j点后面的任务处不需要等待，否则要等待；(2)EFj〉0时，如有，则j点后面的任务不会延迟，否则，要延迟。
2.算法步骤。根据上面的原理，设计详细的求解步骤如下：
Step1：计算点i和点j连接后的节约值s(i,j)，并将其定义为数组；
Sep2：若s(i,j)均为0，则终止，否则，在数组s(i,j)内找出值最大的项；
Step3：考察对应的(i,j)，若满足下述条件之一，则转Step5，否则，转下步；
(1)点i和点j均不在己构成的线路上;(2)点i和点j在已构成的线路上，但不是内点(即不与车场相连);(3)点i和点j位于己构成的不同线路上，均不是内点，且一个是起点，一个是终点。
Step4：考察点i和点j连接后的线路上总货运量Q，若Q≤q，则转下步，否则转Step7。
Step5：计算EFj。(1)若EFj＝0，则转Step6;(2)若EFj＜0，则计算，当则转Step6，否则转Step7；(3)若EFj＞0，则计算，当，则转Step6，否则转Step7；
Step6：连接点i和点j，计算车辆到达各项任务的新时间，转Step7；
Step7：令M=M-s(i,j)，转Step2。
三、实例应用
某超市有8个分店和一个配送中心，各分店的需求量、服务时间及服务时间范围见表1。由载重为8t的车辆完成配送任务，各分店与配送中心的距离见表2。如果车辆的行驶速度为50km/h，要求合理安排车辆的行驶路线，使运行成本最小。
1.把各点间的距离作为运行费用，则Cij=dij， 可以计算节约值s(i,j)，形成节约值表3。
2.构造线路。①在节约值表中找最大的节约值s(5,7)=270，点5和点7均不在已经构成的线路上。②考察点i和点j连接后的线路上总货运量Q。 Q=q5+q7==4（吨）﹤q，满足载重约束。③计算EFj。EF7=s5+T57 t57-s7=2.8>0，则计算:
△7+=LT7-S7=8—5 =3。由于:ETi<，则j点后面的任务不会延迟，可以连接5→7。 ④计算车辆到达各项任务的新时间:S7+EF7 =7.8。
同样的计算方法得出配送线路：0→8→5→7→0和另外两条线路为0→6→4→0和0→3→1→2→0
3.结果分析。从分析可知：车辆到每一个分店都符合时间要求，货物的载重量满足车辆载重的约束，达到运输成本（车辆走行距离）9100km最小。
四、结束语
有时间约束的VSP问题，是一般VSP问题的延伸和拓展，在实际生活中有广泛的应用。在牛奶的配送线路的选择、铁路实现“门到门”运输都可按照此方法进行计算。
参考文献：
[1]运筹学:《运筹学教材编写组》[M].北京:清华大学出版社，1997
[2]郭耀煌:《运筹学原理与方法》[M].成都:西南交通大学出版社,1997
[3]李 军 郭耀煌:物流配送车辆优化调度理论与方法[M].北京:中国物资出版社，2001.6