[摘 要] 非滿載的車輛調(diào)度問題可以看作是有容量限制的TSP問題，本文通過對TSP問題的C-W算法進(jìn)行改進(jìn)，從而找到了非滿載、有時(shí)間約束的VRP問題求解的途徑，并通過8個(gè)客戶的實(shí)例進(jìn)行驗(yàn)證，可以找到滿意解。

[關(guān)鍵詞] 非滿載 車輛調(diào)度 啟發(fā)式算法

一、問題的描述及數(shù)學(xué)模型的建立

1.問題的描述。為了問題便于敘述，將車場編號為0，任務(wù)編號為1，2，…L，任務(wù)及車場均以點(diǎn)i(i=0，1，…L)來表示。以Si表示車輛到達(dá)點(diǎn)i的時(shí)間，tij表示車輛由點(diǎn)i行駛到點(diǎn)j的時(shí)間，一般應(yīng)有以下關(guān)系式:So＝0 ETi≤Si≤LTi

設(shè)完成任務(wù)i需要的時(shí)間為Ti，任務(wù)i的開始時(shí)間需在一定時(shí)間范圍[ETi，LTi]內(nèi)，ETi為任務(wù)i的允許最早開始時(shí)間，LTi為允許最遲開始時(shí)間。如果車輛到達(dá)i的時(shí)間早于ETi，則車輛需在i處等待，如果車輛到達(dá)晚于LTi，則任務(wù)i要延遲進(jìn)行。

2.數(shù)學(xué)模型。定義變量如下:

則:目標(biāo)函數(shù)： （1）

約束條件: （2）

（3）

（4）

（5）

（6）

（7）

（8）

（9）

(1)式中Cij為從點(diǎn)i到點(diǎn)j的運(yùn)輸成本；（2）式為車輛載重約束;(3)式為點(diǎn)i任務(wù)由車輛k完成;（4）、(5)式為客戶車輛惟一性約束。

二、算法原理及步驟

1.算法原理。連接點(diǎn)i和j在一條線路上費(fèi)用的節(jié)約值為:。

以EFj表示連接點(diǎn)i和點(diǎn)j所在線路后，車輛到達(dá)j點(diǎn)的時(shí)間比原線路到達(dá)j點(diǎn)的時(shí)間提前（或推遲）量，則：

為了便于時(shí)間問題的討論，需要定義兩個(gè)重要的變量：

—車輛在線路上j點(diǎn)后面各任務(wù)處均不需要等待的j點(diǎn)的到達(dá)的最大提前量?！€路上j點(diǎn)后面的任務(wù)不違反時(shí)間約束的j點(diǎn)的到達(dá)時(shí)間的最大允許推遲量。

在連接點(diǎn) 和點(diǎn) 所在線路時(shí)，需要檢查是否違反時(shí)間約束：

(1)當(dāng)EFj〈0時(shí)，如有，車輛在j點(diǎn)后面的任務(wù)處不需要等待，否則要等待；(2)EFj〉0時(shí)，如有，則j點(diǎn)后面的任務(wù)不會(huì)延遲，否則，要延遲。

2.算法步驟。根據(jù)上面的原理，設(shè)計(jì)詳細(xì)的求解步驟如下：

Step1：計(jì)算點(diǎn)i和點(diǎn)j連接后的節(jié)約值s(i，j)，并將其定義為數(shù)組；

Sep2：若s(i，j)均為0，則終止，否則，在數(shù)組s(i，j)內(nèi)找出值最大的項(xiàng)；

Step3：考察對應(yīng)的(i，j)，若滿足下述條件之一，則轉(zhuǎn)Step5，否則，轉(zhuǎn)下步；

(1)點(diǎn)i和點(diǎn)j均不在己構(gòu)成的線路上;(2)點(diǎn)i和點(diǎn)j在已構(gòu)成的線路上，但不是內(nèi)點(diǎn)(即不與車場相連);(3)點(diǎn)i和點(diǎn)j位于己構(gòu)成的不同線路上，均不是內(nèi)點(diǎn)，且一個(gè)是起點(diǎn)，一個(gè)是終點(diǎn)。

Step4：考察點(diǎn)i和點(diǎn)j連接后的線路上總貨運(yùn)量Q，若Q≤q，則轉(zhuǎn)下步，否則轉(zhuǎn)Step7。

Step5：計(jì)算EFj。(1)若EFj＝0，則轉(zhuǎn)Step6;(2)若EFj＜0，則計(jì)算，當(dāng)則轉(zhuǎn)Step6，否則轉(zhuǎn)Step7；(3)若EFj＞0，則計(jì)算，當(dāng)，則轉(zhuǎn)Step6，否則轉(zhuǎn)Step7；

Step6：連接點(diǎn)i和點(diǎn)j，計(jì)算車輛到達(dá)各項(xiàng)任務(wù)的新時(shí)間，轉(zhuǎn)Step7；

Step7：令M=M-s(i，j)，轉(zhuǎn)Step2。

三、實(shí)例應(yīng)用

某超市有8個(gè)分店和一個(gè)配送中心，各分店的需求量、服務(wù)時(shí)間及服務(wù)時(shí)間范圍見表1。由載重為8t的車輛完成配送任務(wù)，各分店與配送中心的距離見表2。如果車輛的行駛速度為50km/h，要求合理安排車輛的行駛路線，使運(yùn)行成本最小。

1.把各點(diǎn)間的距離作為運(yùn)行費(fèi)用，則Cij=dij， 可以計(jì)算節(jié)約值s(i，j)，形成節(jié)約值表3。

2.構(gòu)造線路。①在節(jié)約值表中找最大的節(jié)約值s(5，7)=270，點(diǎn)5和點(diǎn)7均不在已經(jīng)構(gòu)成的線路上。②考察點(diǎn)i和點(diǎn)j連接后的線路上總貨運(yùn)量Q。 Q=q5+q7==4（噸）﹤q，滿足載重約束。③計(jì)算EFj。EF7=s5+T57 t57-s7=2.8>0，則計(jì)算:

△7+=LT7-S7=8—5 =3。由于:ETi<，則j點(diǎn)后面的任務(wù)不會(huì)延遲，可以連接5→7。 ④計(jì)算車輛到達(dá)各項(xiàng)任務(wù)的新時(shí)間:S7+EF7 =7.8。

同樣的計(jì)算方法得出配送線路：0→8→5→7→0和另外兩條線路為0→6→4→0和0→3→1→2→0

3.結(jié)果分析。從分析可知：車輛到每一個(gè)分店都符合時(shí)間要求，貨物的載重量滿足車輛載重的約束，達(dá)到運(yùn)輸成本（車輛走行距離）9100km最小。

四、結(jié)束語

有時(shí)間約束的VSP問題，是一般VSP問題的延伸和拓展，在實(shí)際生活中有廣泛的應(yīng)用。在牛奶的配送線路的選擇、鐵路實(shí)現(xiàn)“門到門”運(yùn)輸都可按照此方法進(jìn)行計(jì)算。

參考文獻(xiàn)：

[1]運(yùn)籌學(xué):《運(yùn)籌學(xué)教材編寫組》[M].北京:清華大學(xué)出版社，1997

[2]郭耀煌:《運(yùn)籌學(xué)原理與方法》[M].成都:西南交通大學(xué)出版社，1997

[3]李 軍 郭耀煌:物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京:中國物資出版社，2001.6