淺議零星物資配送路徑優化

楊洋

摘要：隨著物資集約化的深化，零星物資應用電商化采購，零星物資采購單價低、規格品種多、需求頻次高的特點使得其配送具有多品種、小批量、多批次的特點，而較高的送貨頻率和較多的車輛數量導致了配送效率的下降和配送成本的增加，本文通過介紹配送路徑優化的模型和算法，以零星物資配送的特點為出發點，考慮運輸成本和懲罰成本來建立相應的數學模型，并提出了模糊聚類分析和節約算法相結合的混合算法，為路徑優化問題提供了一種思路。

關鍵詞：零星物資；車輛路徑問題；模糊聚類—節約混合算法

一、配送路徑優化的模型

（1）旅行商問題（TSP）。旅行商問題是指旅行商從一個城市出發去其他城市，每個城市他去一次，并且只去一次，最后回到出發城市，如何選擇行程路線使總路程最短。（2）中國郵遞員問題。中國郵遞員問題也稱“一筆畫”問題。如果在某郵遞員所負責的范圍內，街道圖中沒有奇點（邊的個數為奇數），那么他就可以從郵局出發，走過每條街道一次且僅一次，最后回到郵局，這樣他所走的路程也就是最短的路程。對于有奇點的街道圖，就必須在某些街道上重復走一次或多次。（3）車輛路徑問題（VRP）。車輛路徑問題是設計合理的路線，使車輛有序地通過一系列客戶的需求點，在滿足物資需求量、發貨時間、發貨量、行駛里程限制、車輛載重量限制、時間限制等約束條件下，達到時間最短、費用最少、里程最短、車輛利用率高的優化目標。

二、配送路徑優化的算法

（一）解決兩點之間最短路問題的算法——狄克斯法

解決兩點之間最短路問題的算法是狄克斯（Dijkstra）法。這種算法的基本思路是找出從起點到終點的最短路徑點的順序，算法進行時對每一個點給定一個標號，分為臨時標號和固定標號：表示從起點到點的最短距離的上界，表示從起點到點的實際最短距離。

（二）解決中國郵遞員問題的算法——奇偶點圖上作業法

解決中國郵遞員問題的算法也稱作奇偶點圖上作業法。這種算法的基本思路是在含有奇點的圖中增加一些重復邊，并且使重復邊的總權數最小。

（三）解決TSP和VRP問題的算法

解決旅行商問題和車輛路徑問題的算法有精確算法、傳統啟發式算法、現代啟發式算法。精確算法包括動態規劃法、分支定界法、切平面法。傳統啟發式算法在路徑優化問題求解時是從初始解出發，以鄰域搜索的方式改進解，并在短時間內獲得一個可接受的解：包括鄰接算法、掃除算法、插入算法、節約算法。這里介紹一下節約算法（算法）：

假定為網點、為用戶、為用戶需求量、為到的最短距離、為到的最短距離、有種車、載重量為的車有臺，且。其基本思路是依據節約量公式，在汽車負載允許條件下，將供貨范圍內的用戶按節約量的大小（先大后小）依次連接入巡回路線，直至汽車滿載為止。

現代啟發式算法不要求在每次迭代中均沿目標值下降，允許在算法中適當接受目標值有所上升甚至不可行的解，其目的是能夠跳出局部搜索領域：包括遺傳算法、蟻群算法、禁忌搜索算法、模擬退火算法。

解決旅行商問題和車輛路徑問題的三種算法中，精確算法適用于求解小規模問題，傳統的啟發式算法不太適用于現在實際遇到的問題，現代啟發式算法由于跳出了局部搜索領域，能解決實際當中所遇到各種復雜問題，而遺傳算法和蟻群算法又是經常被用來解決車輛路徑問題。

三、零星物資配送路徑優化的數學模型

零星物資配送具有多品種、小批量、多批次的特點，據此在建立數學模型時要考慮兩個目標數：總費用最小和運輸時間及時，其中運輸時間及時指物資能否按照要求及時送到客戶手中，若提前或及時送到則不進行懲罰，否則要進行懲罰。

零星物資配送路徑優化問題可描述為在設施位置、客戶點位置已知并且各道路狀況一致的條件下，由一個配送中心用輛車對個客戶進行配送，確定一套車輛運輸路線以滿足運輸成本和懲罰成本最小。其中每條路線的總負荷不能超過負責該配送路線的汽車的最大載重量，并且每個客戶必須而且只能被服務一次。

四、零星物資配送路徑優化的算法——模糊聚類—節約混合算法

遺傳算法和蟻群算法被經常用來解決VRP問題，在實際應用遺傳算法時，往往出現早熟收斂等缺點，因此出現了許多用來改進遺傳算法的策略。由于遺傳算法實際應用需要使用mat lab軟件，而本文只是提出了其使用原理，并未探究軟件編程，所以本文將模糊聚類分析法和節約算法相結合，先用最大樹法原理對客戶進行模糊聚類分析，將客戶分為若干子類，然后對每類采用節約算法求解零星物資配送路徑優化。

五、實際運用

在實際配送情況中，不同時間段和路段的交通擁擠程度不同，而本文所提出的模型假設了各道路狀況一致，所以本文只是對零星物資配送路徑優化問題作了初步的模型建立和相應算法探討。本文建立的數學模型及算法在進行配送路線決策時比較適用于以下條件：

1.配送點及客戶坐標位置可計量；

2.各點間道路交通狀況一致；

3.客戶重點關心物資是否延期送到，將提前送到與及時送到認為效率一致。

在實際運用方面，對于滿足上述三點條件的配送情況，可通過軟件編程的方式，將本文建立的數學模型及算法轉化為操作軟件，通過將實際客戶轉化為坐標值的方式，在軟件中錄入信息值，然后運用軟件自動匹配出配送方案，避免人工決策的片面性和計算的復雜性、低效率性。

（作者單位：國網四川省電力公司成都供電公司）

參考文獻

[1]孫洪茹.城市物流配送體系及其路線優化的研究[D].山東科技大學，2005.

[2]王濤.城市物流外部不經濟問題研究[D].武漢理工大學管理學院，2007.

[3]劉云忠，宣慧玉.車輛路徑問題的模型及算法研究綜述[N].管理工程學報，2005-01（19）.

[4]王轉，程國全，馮愛蘭.物流系統工程[M].高等教育出版社，2004.

[5]張潛.物流配送路徑優化調度建模與實物[M].中國物資出版社，2006