節約里程算法在車輛路徑優化中的應用研究

齊建強

【摘 要】 高效地配送會使物流系統的順利運行得到保障，對配送車輛的路徑優化，可以節省配送時間，提高配送的效率，進而提高整個企業的經濟效益和社會效益。本文從企業配送貨物時，配送車輛存在空載率高、迂回運輸現象嚴重和配送時間長等問題的角度出發，采用節約里程法對車輛路徑進行優化。進而提高物流服務水平。

【關鍵詞】 配送路線 車輛路徑問題 節約里程法

1 引言

隨著我國經濟的高速發展，各種工業制造型企業不斷發展壯大，市場競爭日趨激烈。企業為了降低成本，提高競爭力，越來越重視物流的發展，物流領域也成為繼降低人工、材料費用和擴大銷售之后，企業的“第三利潤源泉”。在這種大背景的情況下，企業想提高收益，降低物流成本成為企業獲取利潤的必選之路。對配送線路進行優化對企業乃至對社會都有重大意義，

2 節約里程算法概述

節約里程算法的核心思想是將運輸問題中存在的兩個回路合并成為一個回路。在上面的合并操作中，整個運輸的總運輸距離會發生變化，如果變化后總運輸距離下降，則節省了運輸距離。相應的變化值，叫做節約距離， 如式子所示：。

已知條件：需求點集={1，2，……n}，各個點的需求量為，各點之間的最短距離為。第一步形成一個初始解。確定各車輛配送點集，，……令={j}，j=1，2，……n（先采取單點配送）。第二步，進行節約度的計算，計算所有點對的節約度，然后對計算結果進行升序排列。第三步，進行回路的合并。從升序排列的節約度序列中的最上面的值開始，直到節約里程的序列空為止，重復下列步驟。按照節約里程隊列從大到小的順序，分析客戶和之間合并的可能性將，連接起來，如果不是這樣，則從節約里程隊列中去除當前的節約里程，分析下一個網點。

3 算法實現

3.1 A公司配送現狀

本文以A公司為例研究節約里程算法在車輛路徑優化問題中的應用，A公司是一家電子商務公司，每天需要給客戶配送貨物，本文以該公司的配送中心為研究對象。經過調查，該配送中心需要向固定的9個網點配送貨物，通過合理布局和擺放可發現，該類型貨車最多可裝載30個周轉箱。已知1-9號網點周轉箱的數量分別為10、11、8、10、11、12、8、10、7個。

同時得到原有的配送路線和配送車輛情況，該公司由四輛車和四名司機進行配送，配送的總運輸里程為134.2公里。

3.2 基于節約里程法路徑優化

節約里程數是由公式，0，1，2…，9計算得出，其中0代表該企業的配送中心，1-9代表該企業各個配送網點。由各個網點之間的距離可求的，將從大到小排列可以得到如下分析。

a）=25.8為最大值，所以我們首先從最大值開始考慮，表示各個網點配送量中周轉箱的個數。=11+11=22<30，所以可以選擇這條路線進行配送。

b）=22.9，是余下的最大值，所以我們把網點7考慮到回路當中，++=11+11+8=30，所以可以把網點7放入到回路當中，配送路線為0-2-5-7，由于該車輛已經滿載，所以可得出0-2-5-7-0為一條完整的回路。

c）在余下的節約里程數中選擇最大的節約里程數，由于網點2、5、7已經形成了完整的配送回路，所以中含有2、5、7的不在考慮。為最大值，由于=8+10=18<30，所以0-3-8可以構成回路。

d）為符合節約里程算法中滿足條件的最大值，所以我們把網點1考慮到配送回路當中=8+10+10=28<30，所以可以把網點1放入當回路當中，配送路線為0-3-8-1，由于所剩空間只能容納兩個周轉箱，不滿足任意網點配送所需周轉箱的個數，所以可得出0-3-8-1-0為一條完整的回路。

e）在余下的節約里程數中，只有網點4、6、9沒有形成閉合的配送回路，所以余下的節約里程數當中，我們只考慮含有4、6、9的節約里程數，為最大值，由于=10+12=22<30，所以0-4-6可以構成回路。

f）將網點9插入到該配送回路當中，發現+為29，所以可以把網點9插入到該回路當中，0-4-6-9-0為一條完整的配送回路，并且符合節約里程算法的要求。

因此用節約里程算法對A企業配送線路的優化。最后得到的優化結果為，第一條配送路線為0-2-5-7-0，運輸距離為42.1公里，周轉箱有30個，裝載率為100%；第二條配送路線為0-3-8-1-0，運輸距離為27.7公里，周轉箱有28個，裝載率為93.3%；最后一條配送路線為0-4-6-9-0，運輸距離為36.1公里，周轉箱個數為29個，裝載率為96.7%。

4 結論

用節約里程法對原有配送路線進行優化，配送車輛由原來的四輛車變成了三輛，由原來的需要四名司機變成現在的三名司機進行配送，降低了人工成本，同時也減少了配送車輛的數量，使車輛的裝載率得到提高，充分利用了車輛的空間。節約了里程數28.3公里，節約了油耗3.4升，人工成本和燃油成本每天共節省費用173元。用節約里程算法對車輛路徑進行優化，可以明顯減少企業的配送成本，降低勞動力，提高車輛的裝載率，與之前相比，大大提高了物流的配送效率。同時，降低了燃油排放，對社會效益也有很大的幫助。所以，節約里程算法在求解車輛路徑優化問題上是一種良好且實用的解決方法，對企業經濟效益和社會效益都有所幫助。

【參考文獻】

[1] 張穎敏.基于節約里程法的物流配送線路優化與改進研究.物流科技，2011（04）：113～115

[2] 張敏.基于中國郵遞員問題的圖書配送線路優化.物流技術，2012（12）：320～322

[3] 尚文芳.電子商務環境下基于B2C的物流配送路徑優化.物流技術，2014（07）：100～103