基于改進(jìn)節(jié)約算法的計量表計運送車輛調(diào)度

孫 勇，方彥軍，肖 勇

SUN Yong1, FANG Yan-jun1, XIAO Yong2

（1.武漢大學(xué) 自動化系，武漢 430072；2.廣東電網(wǎng)有限責(zé)任公司 電力科學(xué)研究院，廣州 510080）

0 引言

省級電能計量中心的設(shè)立改變了原有的計量設(shè)備檢定模式，新的業(yè)務(wù)流程下電能計量中心承擔(dān)向地市級二級庫進(jìn)行設(shè)備配送的任務(wù)，因此有必要對計量表計運送車輛路徑規(guī)劃進(jìn)行研究。

計量表計運送車輛的路徑規(guī)劃問題屬于VRP問題[1～3]，相關(guān)研究較多，一般可分為啟發(fā)式算法和智能優(yōu)化算法，啟發(fā)式算法中的節(jié)約算法[4,5]相對簡單，便于理解，在具體問題中應(yīng)用較為廣泛[6]。文獻(xiàn)[7]討論了有時間窗約束的非滿載車輛的調(diào)度問題，文獻(xiàn)[8]討論了目標(biāo)函數(shù)總費用具有區(qū)間數(shù)特性的改進(jìn)節(jié)約算法，文獻(xiàn)[9]提出了允許訂貨量分割的改進(jìn)節(jié)約算法。

本文結(jié)合電能計量中心業(yè)務(wù)流程特點，根據(jù)現(xiàn)有工作模式與時間安排方式，提出基于多目標(biāo)優(yōu)化、綜合考慮配送回收策略的改進(jìn)節(jié)約算法。該方法能夠更好的實現(xiàn)計量車輛路徑規(guī)劃需求，實現(xiàn)路徑規(guī)劃的高效節(jié)能，通過相關(guān)實例進(jìn)行對比分析，表明此方法確定的運送方案能夠滿足相關(guān)業(yè)務(wù)需求，最大限度節(jié)約時間、經(jīng)濟(jì)成本。

1 問題描述及模型建立

省級電能計量中心服務(wù)全省所有地市區(qū)二級庫，需要根據(jù)各地市區(qū)業(yè)務(wù)需求的不同進(jìn)行運送車輛調(diào)配?；诠?jié)約資源的原則，部分箱體需要進(jìn)行回收再利用，因此運送車輛需要綜合考慮箱體的回收操作。同時，由于每個階段的配送方案即配送業(yè)務(wù)需求是變化的，最優(yōu)配送路徑也隨之改變，這就需要根據(jù)當(dāng)次業(yè)務(wù)需求來制定配送任務(wù)和車輛最優(yōu)運送路徑，進(jìn)而確定回收任務(wù)，以此提高整個運送過程的效率。

在車輛實際運作中，影響目標(biāo)優(yōu)化的因素較多，需要考慮的情況較復(fù)雜，因此為了方便建模，需要對問題進(jìn)行簡化和假定，以便在一定的限制條件內(nèi)進(jìn)行運送路徑優(yōu)化問題研究。本文在遵循現(xiàn)有工作模式與時間安排制度的基礎(chǔ)上，對計量表計運送車輛路徑規(guī)劃問題進(jìn)行如下假設(shè)：

1）省級電能計量中心只有一個，負(fù)責(zé)向全省地市二級庫進(jìn)行配送，計量中心和二級庫位置固定且兩兩之間行駛路徑指定。

2）計量中心車輛單一，載重限制要求固定，不允許超載；運送車輛按照規(guī)劃路線從計量中心出發(fā)，依次到達(dá)所負(fù)責(zé)的地市庫，完成配送與回收任務(wù)后進(jìn)行下一節(jié)點運送，最終返回計量中心。運送車輛需在12小時內(nèi)完成整個運送作業(yè)并返回計量中心。

3）各個二級庫配送物資可以混裝，即可以同時裝載于一輛運送車輛；同時某一二級庫所需的計量表計允許分裝，由不同運送車輛進(jìn)行配送。

4）運送車輛以配送任務(wù)為主，先根據(jù)配送需求進(jìn)行路徑選擇，再根據(jù)已定路徑，進(jìn)行回收方案制定，并保證在整個運送中任意時刻車輛不超載。

5）通過營銷業(yè)務(wù)系統(tǒng)，計量中心可以實時獲取各個二級庫的相關(guān)數(shù)據(jù)，即表計需求量、待回收表箱數(shù)，其中需求量為剛性需求，待回收表箱數(shù)為區(qū)間數(shù)表示。

6）配送的計量表計和回收的周轉(zhuǎn)箱可以混裝，同時根據(jù)運送車輛的載重載容限制，滿裝周轉(zhuǎn)箱與空周轉(zhuǎn)箱的占據(jù)容積比為1∶1.2，即運送車輛相同空間可以放置更多的空周轉(zhuǎn)箱。

7）路線規(guī)劃是基于多目標(biāo)優(yōu)化，即從單純考慮空間距離到考慮速度、成本、天氣因素等多目標(biāo)。

根據(jù)上述描述和相關(guān)假定，以綜合優(yōu)化指標(biāo)最小為目標(biāo)，建立以智能計量設(shè)備配送為主、兼顧空周轉(zhuǎn)箱回收需求的車輛路徑規(guī)劃模型。

2 求解算法的設(shè)計

2.1 基本節(jié)約算法

節(jié)約算法是路徑優(yōu)化中的一種啟發(fā)式算法，根據(jù)優(yōu)化目標(biāo)的不同有具體的表現(xiàn)形式。下面以空間距離為優(yōu)化目標(biāo)來說明節(jié)約算法的基本思想。設(shè)配送中心為M0，N個二級地市級配送庫分別為已知任意兩個節(jié)點之間的距離為則對于任意兩個二級地市級配送庫，計量中心配送方案可分為單獨配送和合并配送兩種模式，后者比前者的節(jié)約量為：此即為節(jié)約算法進(jìn)行運算的基礎(chǔ)。

通過計算任意兩個地市區(qū)二級庫的節(jié)約量，可以構(gòu)造出所有配送點的節(jié)約量表，按照節(jié)約量從大到小的順序進(jìn)行配送路徑的確定。先選取節(jié)約量最大的兩個配送點作為某條配送線路的兩個端點，同時檢查兩個配送點的貨運量之和是否超過車輛限制條件；再從節(jié)約量表中選擇包含這兩個配送端點之一的最大節(jié)約量，將有關(guān)二級庫點加入配送路線，計算是否超過限制條件并確定配送端點；依次進(jìn)行這種操作，直至配送線路載貨量超過車輛限制條件，再尋找節(jié)約量表中包含兩個配送端點之一的較小節(jié)約量，看是否不超過限制條件。直到所有可能的連接都連接完成，則得到一條配送路線。

依次循環(huán)上述操作，可確定計量中心配送方案。

2.2 改進(jìn)節(jié)約算法

改進(jìn)節(jié)約算法是在節(jié)約算法的基礎(chǔ)上，進(jìn)行必要的改進(jìn)，使之更加適應(yīng)具體問題和應(yīng)用實例。相關(guān)研究提出了基于貨物分割、單位距離載重的選擇性滿載等思想的改進(jìn)節(jié)約算法，較好的解決了相關(guān)實際問題。

本文結(jié)合實際運行情況，提出改進(jìn)的節(jié)約算法，首先以綜合指標(biāo)系數(shù)作為節(jié)約算法的優(yōu)化目標(biāo)，而不再是單一的空間距離。綜合指標(biāo)系數(shù)根據(jù)城市間實際路程公里數(shù)、汽車實際行駛速度概率、行駛經(jīng)濟(jì)費用、突發(fā)事件等情況進(jìn)行綜合得出，最終反映到節(jié)點運行時間，節(jié)點運行時間是動態(tài)調(diào)整變化的。以空間距離為優(yōu)化目標(biāo)的基本節(jié)約算法是假定空間距離為唯一決定車輛運行狀況的因素，而實際情況下，相關(guān)因素對運行狀況影響也較大，如局部地區(qū)天氣狀況、路面維修及突發(fā)事故交通受阻狀況、運送車性能狀態(tài)、車輛行駛正常速度與非正常速度概率，這些因素都會影響優(yōu)化結(jié)果，因此改進(jìn)節(jié)約算法對基本節(jié)約算法的第一個改進(jìn)即為引進(jìn)綜合指標(biāo)系數(shù)，系數(shù)構(gòu)成如下式：

式中：S為綜合指標(biāo)系數(shù)；

N為天氣狀況指數(shù)；

P為路面維修、突發(fā)事故指數(shù)；

Q為運送車車體狀況指數(shù)；

T為速度概率；

a、b、c、d為權(quán)重系數(shù)。

建立科學(xué)可行的綜合性能指數(shù)模型對于真實反映優(yōu)化目標(biāo)，以及優(yōu)化結(jié)果的真實性和可操作性有很大幫助。而綜合性能指數(shù)最終以節(jié)點運行時間作為衡量參考，節(jié)點運行時間與簡單的用空間距離除以車輛行駛速度有很大區(qū)別，綜合性能指數(shù)是在綜合相關(guān)因素的基礎(chǔ)上得到的節(jié)點運行時間，更能真實反映運行中的各種因素，優(yōu)化結(jié)果更具真實性。

改進(jìn)節(jié)約算法在采用綜合指標(biāo)系數(shù)為優(yōu)化目標(biāo)后，其運算流程如圖1所示，可以看出和基本節(jié)約算法相似，同樣是得出節(jié)約量表，依次尋找節(jié)約量最大的節(jié)點進(jìn)行線路規(guī)劃。本文提出的改進(jìn)節(jié)約算法并不對運送車輛滿載作進(jìn)一步要求，主要是考慮回收策略的制定。實際操作過程中，二級庫需要回收的空周轉(zhuǎn)箱數(shù)并不是一個定數(shù)，而是在一定范圍內(nèi)變化，因此采用區(qū)間數(shù)的表達(dá)方式，回收策略的回收量必須在區(qū)間數(shù)表達(dá)的范圍內(nèi)，這樣更符合業(yè)務(wù)需求。

改進(jìn)節(jié)約算法和傳統(tǒng)的節(jié)約算法在綜合指標(biāo)系數(shù)、回收策略制定方面有所不同，整個算法的優(yōu)化目標(biāo)為在節(jié)約量最大的前提下，盡可能實現(xiàn)回收量的最大化。

3 算例分析

3.1 基本情況

根據(jù)第1節(jié)對運送車輛路徑規(guī)劃問題做的分析，選取廣東中東部地區(qū)11個地級城市作為假定算例進(jìn)行分析。表1列出了省級計量中心（配送中心）、各地市區(qū)二級庫之間的距離，其中城市序號1代表計量中心。表中數(shù)值為指定行駛線路下的空間距離。同時假定計量中心運送車能夠載重300個滿載計量箱體，則根據(jù)第1節(jié)假設(shè)6，運送車可裝360個空箱體。某次運送策略制定前，根據(jù)相關(guān)業(yè)務(wù)系統(tǒng)獲取各二級庫有關(guān)信息，并依照運送車載貨情況進(jìn)行歸一化處理，則各二級庫箱體需求量及回收量如表2所示。

圖1 改進(jìn)節(jié)約算法的計算流程圖

表1 配送中心與各二級庫之間的空間距離

表2 各配送點需求量及回收量

根據(jù)改進(jìn)節(jié)約算法對綜合指標(biāo)系數(shù)的定義，將二級庫之間的空間距離轉(zhuǎn)換為二級庫之間的節(jié)點運行時間，如表3所示。改進(jìn)方法的配送方案采用綜合指標(biāo)系數(shù)，可以大幅度綜合實際運行中可能出現(xiàn)的影響運送的因素。

表3 配送中心與二級庫之間的綜合指標(biāo)系數(shù)

3.2 配送路線的確定

根據(jù)表1和表3中的數(shù)據(jù)，進(jìn)行節(jié)約算法及改進(jìn)節(jié)約算法的運算，可以得到配送路線如表4、表5所示。兩種方法得出的配送方案有所不同，路線1和路線2相同，路線3和4的結(jié)果不同。對比路線3和路線4的總耗時和總行駛路程，改進(jìn)節(jié)約算法的結(jié)果更加省時，同時總路程也較短。更有利的是以綜合指標(biāo)系數(shù)為優(yōu)化目標(biāo)的方法得出的配載率也相對均衡，這樣為后續(xù)回收方案的制定提供了更大的可操作空間。

表4 配送方案-空間距離

表5 配送方案-綜合指標(biāo)系數(shù)

3.3 回收方案的確定

根據(jù)確定的運送路線和回收需求，可以制定每條配送線路的回收策略。本方法不要求分割訂單實現(xiàn)滿載，主要是考慮回收任務(wù)，其相關(guān)空間可以最大限度滿足各二級庫對空周轉(zhuǎn)箱回收的需求?；厥諘r必須首先滿足各二級庫回收區(qū)間的下限要求，同時盡可能滿足優(yōu)先級較高的二級庫的上限需求。

以第1條配送線路為例說明回收方案的制定，如果三個城市沒有優(yōu)先級的區(qū)別，只是根據(jù)行駛路線上的順序按照最大的可能性進(jìn)行操作，則序號9、11、10這三個二級庫的回收量依次為0.5、0.4、0.15，即二級庫11不能實現(xiàn)最大量的回收，其余兩個二級庫可以實現(xiàn)最大回收量；如果二級庫11優(yōu)先級高于線路上其他二級庫，則回收策略變化為0.4、0.6、0.15，即為保證序號11的二級庫的回收需求，在9號二級庫時預(yù)留空間為11號做準(zhǔn)備；如果序號9、11的優(yōu)先級相同，則回收策略變化為0.45、0.55、0.15，即兩者同時受到了影響。一般情況下，優(yōu)先級的設(shè)置是為了保證二級庫庫存管理的靈活性，結(jié)合相關(guān)業(yè)務(wù)系統(tǒng)的優(yōu)化調(diào)度，一般不會存在一條線路上多個高優(yōu)先級二級庫的情況，因此高優(yōu)先級二級庫的需求都能得到滿足。

因此，以綜合指標(biāo)系數(shù)為優(yōu)化目標(biāo)制定的配送方案下，不考慮二級庫優(yōu)先級區(qū)分的最終回收方案結(jié)果為，除二級庫3、11之外，其余二級庫均可實現(xiàn)需求量上限的回收，而二級庫3、11只能回收需求量中的0.4。整體回收方案基本滿足需求。

4 結(jié)束語

本文提出的改進(jìn)節(jié)約算法能夠根據(jù)實際情況進(jìn)行改善，更加符合配送需求。依照空間距離的方式，并不能直接將相關(guān)因素考慮在內(nèi)，而通過綜合指標(biāo)系數(shù)，可以將道路信息進(jìn)行整合，更加完善的反映相關(guān)情況。通過算例分析，得出兩者的規(guī)劃路徑不同，對比配載率、時間消耗、總行駛路程等指標(biāo)，可以看出本文的配送策略更為有效。同時，在更加可靠的配送任務(wù)解決后，再進(jìn)行回收路徑規(guī)劃，完成配送-回收任務(wù)，實現(xiàn)業(yè)務(wù)需求。

[1] 劉家利,馬祖軍.存在車輛租賃及共享且有時間窗的多配送中心開環(huán)V R P[J].系統(tǒng)工程理論與實踐,2013,33(3)∶666-675.

[2] Yiyo Kuo. Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem[J].Computers & Industrial Engineering, 2010,59(2010)∶157-165.

[3] 謝桂芩,楊玉華,涂井先.帶有時間窗的虛擬場站接駁補(bǔ)貨車輛路徑問題[J].廣東工業(yè)大學(xué)學(xué)報,2013,30(1)∶61-67,72.

[4] 張建勇,郭耀煌,李軍.一種具有模糊費用系數(shù)的VSP的修正C-W節(jié)約算法[J].西南交通大學(xué)學(xué)報,2004,39(3)∶281-284,310.

[5] 付連寧,崔文,曾華.并行節(jié)約算法的自適應(yīng)鄰域選擇策略[J]. 山東大學(xué)學(xué)報（工學(xué)版）,2012,42(1)∶72-80.

[6] 張學(xué)志,陳功玉.車輛路線安排的改進(jìn)節(jié)約算法[J].系統(tǒng)工程,2008,26(11)∶67-70.

[7] 宋偉剛,張宏霞,佟玲.有時間窗約束非滿載車輛調(diào)度問題的節(jié)約算法[J].東北大學(xué)學(xué)報（自然科學(xué)版）,2006,27(1)∶65-68.

[8] 劉誠,顧坤坤.具有區(qū)間參數(shù)的VRP及其改進(jìn)的C-W節(jié)約算法[J].武漢理工大學(xué)學(xué)報（信息與管理工程版）,2010,32(2)∶182-185.

[9] 范潔,曹俊琴.改進(jìn)節(jié)約算法在電表配送路線選擇中的應(yīng)用[J].物流工程與管理,2012,34(4)∶102-105.