基于改進節約算法的計量表計運送車輛調度

孫 勇，方彥軍，肖 勇

SUN Yong1, FANG Yan-jun1, XIAO Yong2

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

0 引言

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

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

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

1 問題描述及模型建立

省級電能計量中心服務全省所有地市區二級庫，需要根據各地市區業務需求的不同進行運送車輛調配。基于節約資源的原則，部分箱體需要進行回收再利用，因此運送車輛需要綜合考慮箱體的回收操作。同時，由于每個階段的配送方案即配送業務需求是變化的，最優配送路徑也隨之改變，這就需要根據當次業務需求來制定配送任務和車輛最優運送路徑，進而確定回收任務，以此提高整個運送過程的效率。

在車輛實際運作中，影響目標優化的因素較多，需要考慮的情況較復雜，因此為了方便建模，需要對問題進行簡化和假定，以便在一定的限制條件內進行運送路徑優化問題研究。本文在遵循現有工作模式與時間安排制度的基礎上，對計量表計運送車輛路徑規劃問題進行如下假設：

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

2）計量中心車輛單一，載重限制要求固定，不允許超載；運送車輛按照規劃路線從計量中心出發，依次到達所負責的地市庫，完成配送與回收任務后進行下一節點運送，最終返回計量中心。運送車輛需在12小時內完成整個運送作業并返回計量中心。

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

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

5）通過營銷業務系統，計量中心可以實時獲取各個二級庫的相關數據，即表計需求量、待回收表箱數，其中需求量為剛性需求，待回收表箱數為區間數表示。

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

7）路線規劃是基于多目標優化，即從單純考慮空間距離到考慮速度、成本、天氣因素等多目標。

根據上述描述和相關假定，以綜合優化指標最小為目標，建立以智能計量設備配送為主、兼顧空周轉箱回收需求的車輛路徑規劃模型。

2 求解算法的設計

2.1 基本節約算法

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

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

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

2.2 改進節約算法

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

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

式中：S為綜合指標系數；

N為天氣狀況指數；

P為路面維修、突發事故指數；

Q為運送車車體狀況指數；

T為速度概率；

a、b、c、d為權重系數。

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

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

改進節約算法和傳統的節約算法在綜合指標系數、回收策略制定方面有所不同，整個算法的優化目標為在節約量最大的前提下，盡可能實現回收量的最大化。

3 算例分析

3.1 基本情況

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

圖1 改進節約算法的計算流程圖

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

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

根據改進節約算法對綜合指標系數的定義，將二級庫之間的空間距離轉換為二級庫之間的節點運行時間，如表3所示。改進方法的配送方案采用綜合指標系數，可以大幅度綜合實際運行中可能出現的影響運送的因素。

表3 配送中心與二級庫之間的綜合指標系數

3.2 配送路線的確定

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

表4 配送方案-空間距離

表5 配送方案-綜合指標系數

3.3 回收方案的確定

根據確定的運送路線和回收需求，可以制定每條配送線路的回收策略。本方法不要求分割訂單實現滿載，主要是考慮回收任務，其相關空間可以最大限度滿足各二級庫對空周轉箱回收的需求。回收時必須首先滿足各二級庫回收區間的下限要求，同時盡可能滿足優先級較高的二級庫的上限需求。

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

因此，以綜合指標系數為優化目標制定的配送方案下，不考慮二級庫優先級區分的最終回收方案結果為，除二級庫3、11之外，其余二級庫均可實現需求量上限的回收，而二級庫3、11只能回收需求量中的0.4。整體回收方案基本滿足需求。

4 結束語

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

[1] 劉家利,馬祖軍.存在車輛租賃及共享且有時間窗的多配送中心開環V R P[J].系統工程理論與實踐,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] 謝桂芩,楊玉華,涂井先.帶有時間窗的虛擬場站接駁補貨車輛路徑問題[J].廣東工業大學學報,2013,30(1)∶61-67,72.

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

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

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

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

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

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