[摘 要] 本文借鑒多重旅行商問題的模型結(jié)構(gòu)，建立配載車輛調(diào)度模型。通過改進(jìn)C-K節(jié)約算法，在線路連接過程中插入時(shí)間窗約束和車輛容量約束的檢驗(yàn)子程序，求解調(diào)度模型。研究表明改進(jìn)C-K節(jié)約算法是求解配載車輛調(diào)度問題的有效算法。

[關(guān)鍵詞] 配載車輛調(diào)度 C-K節(jié)約算法 時(shí)間窗約束

車輛調(diào)度問題可分為滿載車輛調(diào)度和配載車輛調(diào)度兩大類。配載車輛調(diào)度中，每臺(tái)車給多個(gè)客戶送貨，運(yùn)輸途中需要多次?？?、卸貨，調(diào)度人員不但要將多項(xiàng)運(yùn)輸任務(wù)分組，為每組指派1臺(tái)運(yùn)輸車輛，還要確定每臺(tái)車輛的運(yùn)輸線路（客戶停靠順序），因此其求解過程比滿載車輛調(diào)度問題復(fù)雜得多。本文通過改進(jìn)C-K節(jié)約算法以求得滿意解。

一、建立配載車輛調(diào)度模型

配載車輛調(diào)度問題可以描述為：車場(chǎng)向n個(gè)客戶送貨，第i個(gè)客戶貨運(yùn)量為gi，卸貨時(shí)間為UTi，最早允許車輛到達(dá)時(shí)間為ETi，最遲允許車輛到達(dá)時(shí)間為LTi，中心與客戶、客戶與客戶兩兩間的廣義運(yùn)輸費(fèi)用為cij，運(yùn)輸時(shí)間為tij（i，j = 0，1，2，…，n，車場(chǎng)編號(hào)為0，客戶編號(hào)為1，2，…，n），送貨卡車裝載容量為q（q＞gi，i = 1，2，…，n）。車輛不允許超載且必須在時(shí)間窗內(nèi)把貨物送達(dá)客戶。要求指派運(yùn)輸車輛，并確定每臺(tái)車運(yùn)輸線路，使得總運(yùn)輸費(fèi)用Z最低。

把車場(chǎng)和客戶統(tǒng)一看作是運(yùn)輸網(wǎng)絡(luò)中的節(jié)點(diǎn)。設(shè)在同一條線路上點(diǎn)h是點(diǎn)i前面的相鄰點(diǎn)，車輛到達(dá)點(diǎn)h的時(shí)間為RTh，到達(dá)點(diǎn)i的時(shí)間為RTi，則有：

RTi=RTh=+UTh=Thi （1）

為建立調(diào)度模型，并定義二進(jìn)制變量xijk、yki：

帶時(shí)間窗約束的配載車輛調(diào)度模型為：

目標(biāo)函數(shù)：（2）

約束條件： （4）

（6）

（8）

二、改進(jìn)的C-K節(jié)約算法

C-K節(jié)約算法是為求解旅行商問題設(shè)計(jì)的，它不考慮各種約束條件，不能直接求解配載車輛調(diào)度模型。本文通過在C-K節(jié)約算法中插入時(shí)間窗和車輛容量約束的檢驗(yàn)子程序，使之能夠處理時(shí)間窗和車輛容量約束，從而構(gòu)造出能夠求解配載車輛調(diào)度問題的啟發(fā)式算法。啟發(fā)式算法強(qiáng)調(diào)滿意解，即決策者認(rèn)為解決方案是令人滿意即可，而不去刻意追求最優(yōu)性和最優(yōu)解。

對(duì)于車輛容量約束，可以在考察點(diǎn)i和j時(shí)，插入車輛的裝載量驗(yàn)算子程序，如果連接后的車輛裝載量大于車輛容量，則不允許連接點(diǎn)i和j。設(shè)線路“0→…→i→0”的貨運(yùn)量為Qi，線路“0→j→…→0”的貨運(yùn)量為Qj，只有Qi+Qj≤q時(shí)，才允許連接點(diǎn)i和j，形成線路“0→…→i→j→…→0”。Qi和Qj通過累加線路上的客戶貨運(yùn)量得到。

對(duì)于時(shí)間窗約束需要考慮連接點(diǎn)i和j后會(huì)引起車輛到達(dá)j點(diǎn)的時(shí)間發(fā)生變化。設(shè)EFj表示連接點(diǎn)i和j后車輛到達(dá)j點(diǎn)的時(shí)間變化量，則有：EFj=RTi+UTi+tij-RTj

顯然EFj＜0時(shí)，車輛到達(dá)j點(diǎn)時(shí)間提前；EFj=0，車輛到達(dá)j點(diǎn)時(shí)間不變；EFj＞0，車輛到達(dá)j點(diǎn)時(shí)間推遲。設(shè)r表示同一條線路上j及其后面各點(diǎn)，Δj-表示車輛到達(dá)j及其后面各點(diǎn)不違反時(shí)間窗約束的最大允許時(shí)間提前量，Δj+表示車輛到達(dá)j及其后面各點(diǎn)不違反時(shí)間窗約束的最大允許時(shí)間推遲量，則有：

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

因此，當(dāng)連接點(diǎn)i和j時(shí)，

1.計(jì)算s（i，j），令M=｛s（i，j）︱s（i，j）＞0，i，j=1，2，…，n｝，并把集合M內(nèi)的元素s（i，j）從大到小排序。

2.選擇集合M內(nèi)的第1個(gè)元素s（i，j），考察點(diǎn)i和j，是否滿足下列條件之一：

(1)點(diǎn)i和j均在初始化線路上；(2)點(diǎn)i和j一個(gè)在已構(gòu)成線路上，且與車場(chǎng)相連，另一個(gè)在初始化線路上；(3)點(diǎn)i和j位于不同線已構(gòu)成線路路上，且都與車場(chǎng)相連。

若滿足則轉(zhuǎn)至（3），否則轉(zhuǎn)至（6）。

3.計(jì)算若連接點(diǎn)i和j后車輛的總裝載容量Q，若Q≤q，轉(zhuǎn)至（4），否則轉(zhuǎn)至（6）。

4.計(jì)算若連接點(diǎn)i和j后的EFj值：

(1)若EFj=0，轉(zhuǎn)至（5）；(2)若EFj＜0，計(jì)算Δj-，若︱EFj︱≤Δj-，轉(zhuǎn)至（5），否則轉(zhuǎn)至（6）；(3)若EFj＞0，計(jì)算Δj+，若EFj≤Δj+，轉(zhuǎn)至（5），否則轉(zhuǎn)至（6）。

5.連接點(diǎn)i和j，計(jì)算車輛到達(dá)各個(gè)客戶的時(shí)間。

6.在集合M中消去這個(gè)最大元素s（i，j）。若M=φ，算法終止，否則轉(zhuǎn)至（2）。

把改進(jìn)C-K節(jié)約算法編寫成計(jì)算機(jī)程序，上機(jī)運(yùn)算就能夠很快求解出配載車輛調(diào)度問題的滿意解，輸出結(jié)果應(yīng)包括運(yùn)輸線路的圖形界面。配載車輛運(yùn)輸線路是多個(gè)閉合回路，每一個(gè)閉合回路代表1臺(tái)的行駛線路。如果有客戶不在閉合回路上，說明該客戶時(shí)間窗約束太緊，不存在滿足時(shí)間窗約束解。

三、結(jié)束語

配載車輛調(diào)度是一種異化的多重旅行商問題，在多重旅行商模型中添加符合配載車輛線路構(gòu)形的各種約束條件后，就可以建立配載車輛調(diào)度模型。通過改進(jìn)求解旅行商問題的C-K節(jié)約算法，在點(diǎn)對(duì)連接前插入約束條件檢驗(yàn)子程序，能夠求解配載車輛調(diào)度問題，得到滿意的調(diào)度方案。文中模型和算法還可以進(jìn)一步擴(kuò)展，如添加駕駛員途中工作時(shí)間限制或單車線路長度約束等，處理方法同車輛容量約束類似。配載車輛調(diào)度問題有多種類型，本文只研究了單車場(chǎng)純送貨情況下的配載車輛調(diào)度問題，對(duì)于多車場(chǎng)、集貨送貨相結(jié)合的配載車輛調(diào)度問題有待于進(jìn)一步研究。