C-K节约算法在配载车辆调度问题上的应用研究

[摘 要] 本文借鉴多重旅行商问题的模型结构,建立配载车辆调度模型。通过改进C-K节约算法,在线路连接过程中插入时间窗约束和车辆容量约束的检验子程序,求解调度模型。研究表明改进C-K节约算法是求解配载车辆调度问题的有效算法。

[关键词] 配载车辆调度 C-K节约算法 时间窗约束

车辆调度问题可分为满载车辆调度和配载车辆调度两大类。配载车辆调度中，每台车给多个客户送货，运输途中需要多次停靠、卸货，调度人员不但要将多项运输任务分组，为每组指派1台运输车辆，还要确定每台车辆的运输线路（客户停靠顺序），因此其求解过程比满载车辆调度问题复杂得多。本文通过改进C-K节约算法以求得满意解。

一、建立配载车辆调度模型

配载车辆调度问题可以描述为：车场向n个客户送货，第i个客户货运量为gi，卸货时间为UTi，最早允许车辆到达时间为ETi，最迟允许车辆到达时间为LTi，中心与客户、客户与客户两两间的广义运输费用为cij，运输时间为tij（i，j = 0，1，2，…，n，车场编号为0，客户编号为1，2，…，n），送货卡车装载容量为q（q＞gi，i = 1，2，…，n）。车辆不允许超载且必须在时间窗内把货物送达客户。要求指派运输车辆，并确定每台车运输线路，使得总运输费用Z最低。

把车场和客户统一看作是运输网络中的节点。设在同一条线路上点h是点i前面的相邻点，车辆到达点h的时间为RTh，到达点i的时间为RTi，则有：

RTi=RTh=+UTh=Thi （1）

为建立调度模型，并定义二进制变量xijk、yki：

带时间窗约束的配载车辆调度模型为：

目标函数：（2）

约束条件： （4）

（6）

（8）

二、改进的C-K节约算法

C-K节约算法是为求解旅行商问题设计的，它不考虑各种约束条件，不能直接求解配载车辆调度模型。本文通过在C-K节约算法中插入时间窗和车辆容量约束的检验子程序，使之能够处理时间窗和车辆容量约束，从而构造出能够求解配载车辆调度问题的启发式算法。启发式算法强调满意解，即决策者认为解决方案是令人满意即可，而不去刻意追求最优性和最优解。

对于车辆容量约束，可以在考察点i和j时，插入车辆的装载量验算子程序，如果连接后的车辆装载量大于车辆容量，则不允许连接点i和j。设线路“0…i0”的货运量为Qi，线路“0j…0”的货运量为Qj，只有Qi+Qj≤q时，才允许连接点i和j，形成线路“0…ij…0”。Qi和Qj通过累加线路上的客户货运量得到。

对于时间窗约束需要考虑连接点i和j后会引起车辆到达j点的时间发生变化。设EFj表示连接点i和j后车辆到达j点的时间变化量，则有：EFj=RTi+UTi+tij-RTj

显然EFj＜0时，车辆到达j点时间提前；EFj=0，车辆到达j点时间不变；EFj＞0，车辆到达j点时间推迟。设r表示同一条线路上j及其后面各点，Δj-表示车辆到达j及其后面各点不违反时间窗约束的最大允许时间提前量，Δj+表示车辆到达j及其后面各点不违反时间窗约束的最大允许时间推迟量，则有：

Δj-=min{sr-ETr} Δj+=min{LTr-sr}

因此，当连接点i和j时，

1.计算s（i，j），令M=｛s（i，j）s（i，j）＞0，i，j=1，2，…，n｝，并把集合M内的元素s（i，j）从大到小排序。

2.选择集合M内的第1个元素s（i，j），考察点i和j，是否满足下列条件之一：

(1)点i和j均在初始化线路上；(2)点i和j一个在已构成线路上，且与车场相连，另一个在初始化线路上；(3)点i和j位于不同线已构成线路路上，且都与车场相连。

若满足则转至（3），否则转至（6）。

3.计算若连接点i和j后车辆的总装载容量Q，若Q≤q，转至（4），否则转至（6）。

4.计算若连接点i和j后的EFj值：

(1)若EFj=0，转至（5）；(2)若EFj＜0，计算Δj-，若EFj≤Δj-，转至（5），否则转至（6）；(3)若EFj＞0，计算Δj+，若EFj≤Δj+，转至（5），否则转至（6）。

5.连接点i和j，计算车辆到达各个客户的时间。

6.在集合M中消去这个最大元素s（i，j）。若M=φ，算法终止，否则转至（2）。

把改进C-K节约算法编写成计算机程序，上机运算就能够很快求解出配载车辆调度问题的满意解，输出结果应包括运输线路的图形界面。配载车辆运输线路是多个闭合回路，每一个闭合回路代表1台的行驶线路。如果有客户不在闭合回路上，说明该客户时间窗约束太紧，不存在满足时间窗约束解。

三、结束语

配载车辆调度是一种异化的多重旅行商问题，在多重旅行商模型中添加符合配载车辆线路构形的各种约束条件后，就可以建立配载车辆调度模型。通过改进求解旅行商问题的C-K节约算法，在点对连接前插入约束条件检验子程序，能够求解配载车辆调度问题，得到满意的调度方案。文中模型和算法还可以进一步扩展，如添加驾驶员途中工作时间限制或单车线路长度约束等，处理方法同车辆容量约束类似。配载车辆调度问题有多种类型，本文只研究了单车场纯送货情况下的配载车辆调度问题，对于多车场、集货送货相结合的配载车辆调度问题有待于进一步研究。