楊洋

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

五、實(shí)際運(yùn)用

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

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

2.各點(diǎn)間道路交通狀況一致；

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

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

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

參考文獻(xiàn)

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

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

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

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

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