淺議零星物資配送路徑優(yōu)化

楊洋

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

關(guān)鍵詞：零星物資；車輛路徑問題；模糊聚類—節(jié)約混合算法

一、配送路徑優(yōu)化的模型

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

二、配送路徑優(yōu)化的算法

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

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

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

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

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

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

假定為網(wǎng)點、為用戶、為用戶需求量、為到的最短距離、為到的最短距離、有種車、載重量為的車有臺，且。其基本思路是依據(jù)節(jié)約量公式，在汽車負(fù)載允許條件下，將供貨范圍內(nèi)的用戶按節(jié)約量的大?。ㄏ却蠛笮。┮来芜B接入巡回路線，直至汽車滿載為止。

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

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

三、零星物資配送路徑優(yōu)化的數(shù)學(xué)模型

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

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

四、零星物資配送路徑優(yōu)化的算法——模糊聚類—節(jié)約混合算法

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

五、實際運用

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

1.配送點及客戶坐標(biāo)位置可計量；

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

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

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

（作者單位：國網(wǎng)四川省電力公司成都供電公司）

參考文獻(xiàn)

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

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

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

[4]王轉(zhuǎn)，程國全，馮愛蘭.物流系統(tǒng)工程[M].高等教育出版社，2004.

[5]張潛.物流配送路徑優(yōu)化調(diào)度建模與實物[M].中國物資出版社，2006