Ｃ－Ｋ節約算法在配載車輛調度問題上的應用研究

[摘 要] 本文借鑒多重旅行商問題的模型結構，建立配載車輛調度模型。通過改進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→…→i→0”的貨運量為Qi，線路“0→j→…→0”的貨運量為Qj，只有Qi+Qj≤q時，才允許連接點i和j，形成線路“0→…→i→j→…→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節約算法，在點對連接前插入約束條件檢驗子程序，能夠求解配載車輛調度問題，得到滿意的調度方案。文中模型和算法還可以進一步擴展，如添加駕駛員途中工作時間限制或單車線路長度約束等，處理方法同車輛容量約束類似。配載車輛調度問題有多種類型，本文只研究了單車場純送貨情況下的配載車輛調度問題，對于多車場、集貨送貨相結合的配載車輛調度問題有待于進一步研究。