有時間約束的非滿載車輛調(diào)度問題的啟發(fā)式改進算法

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

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

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

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

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

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

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

約束條件: （2）

（3）

（4）

（5）

（6）

（7）

（8）

（9）

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

二、算法原理及步驟

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

以EFj表示連接點i和點j所在線路后，車輛到達j點的時間比原線路到達j點的時間提前（或推遲）量，則：

為了便于時間問題的討論，需要定義兩個重要的變量：

—車輛在線路上j點后面各任務處均不需要等待的j點的到達的最大提前量。—線路上j點后面的任務不違反時間約束的j點的到達時間的最大允許推遲量。

在連接點 和點 所在線路時，需要檢查是否違反時間約束：

(1)當EFj〈0時，如有，車輛在j點后面的任務處不需要等待，否則要等待；(2)EFj〉0時，如有，則j點后面的任務不會延遲，否則，要延遲。

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

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

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

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

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

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

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

Step6：連接點i和點j，計算車輛到達各項任務的新時間，轉(zhuǎn)Step7；

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

三、實例應用

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

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

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

△7+=LT7-S7=8—5 =3。由于:ETi<，則j點后面的任務不會延遲，可以連接5→7。 ④計算車輛到達各項任務的新時間:S7+EF7 =7.8。

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

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

四、結(jié)束語

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

參考文獻：

[1]運籌學:《運籌學教材編寫組》[M].北京:清華大學出版社，1997

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

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