满载车辆调度中，每台车只给一个客户送货，运输线路取广义费用（费用、时间或距离）的最短路，可以采用图论中Ｄｉｊｋｓｔｒａ或Ｆｌｏｙｄ算法求解。车辆调度问题可分为满载车辆调度和配载车辆调度两大类。配载车辆调度中，每台车给多个客户送货，运输途中需要多次停靠、卸货，调度人员不但要将多项运输任务分组，为每组指派１台运输车辆，还要确定每台车辆的运输线路（客户停靠顺序），因此其求解过程比满载车辆调度问题复杂得多。时间窗约束是指客户对货物送达的时间要求，用客户允许送货车辆最早到达和最迟到达的时间范围来描述。
配载车辆调度问题属于ＮＰ－ｈａｒｄ问题，只有在问题规模很小时才可能存在可行的精确算法，通常采用启发式算法求得满意解?１?。如果不考虑时间窗和车辆容量约束，配载车辆调度问题就转化为图论中的多重旅行商问题，可以采用Ｃｌａｒｋｅ和Ｗｒｉｇｈｔ提出的Ｃ－Ｋ节约算法求解。Ｃ－Ｋ节约算法自从１９６４年被提出后就得到普遍认同，它原理简单、灵活性强、交互性好，许多优化算法都局部或全部采用Ｃ－Ｋ节约算法。本文通过改进Ｃ－Ｋ节约算法，构造配载车辆调度问题的启发式算法。
１ 配载车辆调度模型
配载车辆调度问题可以描述为：车场向ｎ个客户送货，第 ｉ个客户货运量为ｇｉ，卸货时间为ＵＴｉ，最早允许车辆到达时间为ＥＴｉ，最迟允许车辆到达时间为ＬＴｉ，中心与客户、客户与客户两两间的广义运输费用为ｃｉｊ，运输时间为ｔｉｊ（ｉ，ｊ ＝ ０，１，２，…，ｎ，车场编号为０，客户编号为１，２，…，ｎ），送货卡车装载容量为ｑ（ｑ＞ｇｉ，ｉ ＝ １，２，…，ｎ）。车辆不允许超载且必须在时间窗内把货物送达客户。要求指派运输车辆，并确定每台车运输线路，使得总运输费用Ｚ最低。
把车场和客户统一看作是运输网络中的节点。设在同一条线路上点ｈ是点ｉ前面的相邻点，车辆到达点ｈ的时间为ＲＴｈ，到达点ｉ的时间为ＲＴｉ，则有：
ＲＴｉ＝ＲＴｈ＋ＵＴｈ＋ｔｈｉ（１）
为建立调度模型，并定义二进制变量ｘｉｊｋ、ｙｋｉ：
ｘｉｊｋ＝
ｙｋｉ＝
带时间窗约束的配载车辆调度模型为：
目标函数：ｍｉｎＺ＝ｃｉｊｘｉｊｋ（２）
约束条件：ｇｉｙｋｉ≤ｑ ∨ｋ（３）
ＥＴｉ≤ＲＴｉ≤ＬＴｉ ｉ＝１?２?…，ｎ（４）
ｙｋｉ＝１ ｉ＝１?２?…，ｎ （５）
ｘｉｊｋ＝ｙｋｉ ｊ＝１?２?…，ｎ? ∨ｋ（６）
ｘｉｊｋ＝ｙｋｉ ｉ＝１?２?…，ｎ? ∨ｋ（７）
Ｘ＝（ｘｉｊｋ）∈Ｓ（８）
目标函数（２）表示总运输里程最低，约束条件（３）表示任一台车装载量不允许车辆超过容量约束，约束条件（４）货物送到各个客户的时间必须在时间窗范围内，约束条件（５）表示任一客户只有１台车停靠卸货，约束条件（６）表示车辆ｋ只驶入分配给其运输任务的客户，约束条件（７）表示车辆ｋ只驶出分配给其运输任务的客户，约束条件（８）表示车辆ｋ的线路必须是连通的。
２ 启发式算法
２．１ Ｃ－Ｋ节约算法
Ｃ－Ｋ节约算法的基本思想是首先把各个客户单独与车场相连，构成ｎ条“０→ｉ→０”（ｉ＝１，２，…，ｎ）初始化线路，第ｉ条线路的运输费用为：
ｚｉ＝ｃ０ｉ＋ｃｉ０（９）
然后把客户ｉ和客户ｊ连接在一起，形成线路“０→ｉ→ｊ→０”（ｉ，ｊ＝１，２，…，ｎ），计算连接后费用“节约值”：
ｓ（ｉ?ｊ）＝ｃｉ０＋ｃｏｊ－ｃｉｊ（１０）
ｓ（ｉ，ｊ）越大，说明把客户ｉ和客户ｊ连接在一起时总费用节约值越多，因此应优先连接ｓ（ｉ，ｊ）值大的点ｉ和ｊ。基于这一原则，Ｃｌａｒｋｅ和Ｗｒｉｇｈｔ在１９６４年提出Ｃ－Ｋ节约算法。约定把只有一个客户的线路（如“０→ｉ→０”）称为初始化线路，把包含两个或两个以上客户的线路（如“０→…→ｉ→…→０”）称为已构成线路，则Ｃ－Ｋ节约算法可以描述如下：
ｓｔｅｐ１：计算费用节约值ｓ（ｉ，ｊ），ｉ，ｊ＝１，２，…，ｎ，并排列成二维表格。
ｓｔｅｐ２：在表格中选择最大元素ｓ（ｉ，ｊ）。
ｓｔｅｐ３：考察ｓ（ｉ，ｊ）对应的点ｉ和ｊ：
①若点ｉ和ｊ都在初始化线路上，则连接点ｉ和ｊ，形成已构成线路“０→ｉ→ｊ→０”，转ｓｔｅｐ４；②若点ｉ和ｊ中有一个点在已构成线路上，且与车场“０”相连，而另一个点在初始化线路上，则连接点ｉ和ｊ，得到线路“０→ｉ→ｊ→…→０”或“０→…→ｉ→ｊ→０”，转ｓｔｅｐ４；③若点ｉ和ｊ分别在两条不同已构成线路上，且均与车场相连，则连接点ｉ和ｊ，得到线路“０→…→ｉ→ｊ→…→０”，转ｓｔｅｐ４。
ｓｔｅｐ４：划去表格中的第ｉ行和第ｊ列，即ｉ点不能再作为车辆的发点，点ｊ不能再作为车辆的收点。
ｓｔｅｐ５：若表格中所有元素ｓ（ｉ，ｊ）都被划去，则已通过不断连接点对得到完整的旅行线路方案，算法终止；否则，在未划去的元素中选择最大元素，并转ｓｔｅｐ３。
２．２ Ｃ－Ｋ节约算法的改进
Ｃ－Ｋ节约算法是为求解旅行商问题设计的，它不考虑各种约束条件，不能直接求解配载车辆调度模型。本文通过在Ｃ－Ｋ节约算法中插入时间窗和车辆容量约束的检验子程序，使之能够处理时间窗和车辆容量约束，从而构造出能够求解配载车辆调度问题的启发式算法。所谓启发式算法是指借助归纳推理和实验分析来解决问题的方法，它从与研究问题有关而较基本的模型和算法中寻求联系，得到启发，发现解决问题的思路和途径?２?。启发式算法强调满意解，即决策者认为解决方案是令人满意即可，而不去刻意追求最优性和最优解，这对求解ＮＰ－ｈａｒｄ问题具有不可估量的作用。
对于车辆容量约束，可以在考察点ｉ和ｊ时，插入车辆的装载量验算子程序，如果连接后的车辆装载量大于车辆容量，则不允许连接点ｉ和ｊ。设线路“０→…→ｉ→０”的货运量为Ｑｉ，线路“０→ｊ→…→０”的货运量为Ｑｊ，只有Ｑｉ＋Ｑｊ≤ｑ时，才允许连接点ｉ和ｊ，形成线路“０→…→ｉ→ｊ→…→０”。Ｑｉ和Ｑｊ通过累加线路上的客户货运量得到。
对于时间窗约束需要考虑连接点ｉ和ｊ后会引起车辆到达ｊ点的时间发生变化。设ＥＦｊ表示连接点ｉ和ｊ后车辆到达ｊ点的时间变化量，则有：
ＥＦｊ＝ＲＴｉ＋ＵＴｉ＋ｔｉｊ－ＲＴｊ（１１）
显然ＥＦｊ＜０时，车辆到达ｊ点时间提前；ＥＦｊ＝０，车辆到达ｊ点时间不变；ＥＦｊ＞０，车辆到达ｊ点时间推迟。设ｒ表示同一条线路上ｊ及其后面各点，Δｊ－表示车辆到达ｊ及其后面各点不违反时间窗约束的最大允许时间提前量，Δｊ＋表示车辆到达ｊ及其后面各点不违反时间窗约束的最大允许时间推迟量，则有：
Δｊ－＝ｍｉｎ?ｓｒ－ＥＴｒ?（１２）
Δｊ＋＝ｍｉｎ?ＬＴｒ－ｓｒ?（１３）
因此，当连接点ｉ和ｊ时，若有ＥＦｊ＜０且｜ＥＦｊ｜≤Δｊ－，或者ＥＦｊ＞０且ＥＦｊ≤Δｊ＋，则连接点ｉ和ｊ后不会违反时间窗约束。利用这一原理，可以编写时间窗约束检验子程序，插入到Ｃ－Ｋ节约算法的ｓｔｅｐ３中，只有在不违反时间窗约束情况下，才允许连接点ｉ和ｊ。改进的Ｃ－Ｋ节约算法如下：
ｓｔｅｐ１：计算ｓ（ｉ，ｊ），令Ｍ＝｛ｓ（ｉ，ｊ）｜ｓ（ｉ，ｊ）＞０，ｉ，ｊ＝１，２，…，ｎ｝，并把集合Ｍ内的元素ｓ（ｉ，ｊ）从大到小排序。
ｓｔｅｐ２：选择集合Ｍ内的第１个元素ｓ（ｉ，ｊ），考察点ｉ和ｊ，是否满足下列条件之一：
①点ｉ和ｊ均在初始化线路上；②点ｉ和ｊ一个在已构成线路上，且与车场相连，另一个在初始化线路上；③点ｉ和ｊ位于不同线已构成线路上，且都与车场相连。
若满足则转ｓｔｅｐ３，否则转ｓｔｅｐ６。
ｓｔｅｐ３：计算若连接点ｉ和ｊ后车辆的总装载容量Ｑ，若Ｑ≤ｑ，转ｓｔｅｐ４，否则转ｓｔｅｐ６。
ｓｔｅｐ４：计算若连接点ｉ和ｊ后的ＥＦｊ值：
①若ＥＦｊ＝０，转ｓｔｅｐ５；②若ＥＦｊ＜０，计算Δｊ－，若｜ＥＦｊ｜≤Δｊ－，转ｓｔｅｐ５，否则转ｓｔｅｐ６；③若ＥＦｊ＞０，计算Δｊ＋，若ＥＦｊ≤Δｊ＋，转ｓｔｅｐ５，否则转ｓｔｅｐ６。
ｓｔｅｐ５：连接点ｉ和ｊ，计算车辆到达各个客户的时间。
ｓｔｅｐ６：在集合Ｍ中消去这个最大元素ｓ（ｉ，ｊ）。若Ｍ＝φ，算法终止，否则转ｓｔｅｐ２。
把改进Ｃ－Ｋ节约算法编写成计算机程序，上机运算就能够很快求解出配载车辆调度问题的满意解，输出结果应包括运输线路的图形界面。配载车辆运输线路是多个闭合回路，每一个闭合回路代表１台的行驶线路?３?。如果有客户不在闭合回路上，说明该客户时间窗约束太紧，不存在满足时间窗约束解。
３ 模拟分析
某物流中心经营啤酒配送业务，每天向１２个客户运送箱装的啤酒。测量比例为１：１ ０００ ０００地图得到中心和客户坐标（ｘｉ，ｙｉ），为简化起见，中心与客户、客户与客户两两之间的运输距离通过公式ｄｉｊ＝１．２ｘｉ－ｘｊ?２＋?ｙｉ－ｙｊ０．５近似计算。车辆调度的基础数据如表１所示，送货车辆装载容量是６００箱，行驶速度为６０ｋｍｈ，发车时间为早晨６?３０。试确定车辆调度方案，使总运输里程最短。
求解过程如下：
（１）由公式ｄｉｊ＝１．２ｘｉ－ｘｊ?２＋?ｙｉ－ｙｊ０．５计算中心与客户、客户与客户的运输距离矩阵（ｄｉｊ）１３×１３。因为地图比例尺为１? １ ０００ ０００，所以图中１ｍｍ代表１ｋｍ，按表１数据带入公式后计算的距离单位为ｋｍ。把运输距离矩阵除以车速（６０ｋｍｈ）得到运输时间矩阵（ｔｉｊ）１３×１３。
（２）把车辆容量和车辆数，各客户的时间窗约束、啤酒需求量和卸货时间数据，以及运输时间矩阵和早晨发车时间输入到改进Ｃ－Ｋ节约算法程序，上机运算得到如下结果：
第１台车：运输线路“０→５→８→１２→７→０”，行驶里程为２５０ｋｍ，在途时间６．２ｈ；
第２台车：运输线路“０→９→１→３→４→０”，行驶里程１７４ｋｍ，在途时间６．２ｈ；
第３台车：运输线路“０→１０→２→１１→６→０”，行驶里程３７０ｋｍ，在途时间８．２ｈ。
运输线路如图１所示。３台车总运输里程为７９４ｋｍ，各车的发车、停靠和收车时间、装载量变化情况和各路段里程如表２所示。
４ 结束语
配载车辆调度是一种异化的多重旅行商问题，在多重旅行商模型中添加符合配载车辆线路构形的各种约束条件后，就可以建立配载车辆调度模型。通过改进求解旅行商问题的Ｃ－Ｋ节约算法，在点对连接前插入约束条件检验子程序，能够求解配载车辆调度问题，得到满意的调度方案。文中模型和算法还可以进一步扩展，如添加驾驶员途中工作时间限制或单车线路长度约束等，处理方法同车辆容量约束类似。配载车辆调度问题有多种类型，本文只研究了单车场纯送货情况下的配载车辆调度问题，对于多车场、集货送货相结合的配载车辆调度问题有待于进一步研究。
