張艷偉，周 萬，向家偉

(1.武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢430063;2.武漢理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢430063)

解決物流配送路線優(yōu)化問題的方法有很多，常用的有旅行商法、動態(tài)規(guī)劃法、節(jié)約法、掃描法、分區(qū)配送法、方案評價法等［1］。相關(guān)研究中，王會云等［2］研究了旅行商法在配送路線優(yōu)化問題中的應(yīng)用，并利用Matlab 和遺傳算法對該問題進(jìn)行了求解。陳彥軍等［3］利用旅行商模型研究了物流配送問題。王勇等［4］利用動態(tài)規(guī)劃法對配送路線及配送時間的優(yōu)化問題進(jìn)行了研究分析。張學(xué)志等［5］提出了一種改進(jìn)節(jié)約算法，并利用該算法對配送路線問題進(jìn)行了研究。楊文霞等［6］采用改進(jìn)掃描算法解決配送路線優(yōu)化問題，并結(jié)合實際案例分析了該優(yōu)化方法的工作性能。霍亮［7］利用分區(qū)配送法研究了基于GIS 的物流配送問題。此外，文獻(xiàn)［8 -11］研究了相關(guān)智能優(yōu)化算法在配送路線優(yōu)化問題中的應(yīng)用，包括免疫算法、遺傳算法、禁忌搜索算法和模擬退火算法。WANG 和LU［12-13］研究了利用遺傳算法及其改進(jìn)算法求解具有容量限制的路徑優(yōu)化問題，其基本思想是將遺傳算法與其他算法(例如掃描法)相結(jié)合，用來改進(jìn)算法的求解質(zhì)量及計算速度。LEUNG 等［14］將二維裝箱問題及配送路線問題結(jié)合起來考慮，并采用模擬退火算法對該問題進(jìn)行求解，而針對同一問題，F(xiàn)UELLERER 等［15］則考慮采用蟻群算法進(jìn)行求解。LIN 等［16］采用了一種模擬退火算法與禁忌搜索算法的混合算法對容量限制的路徑規(guī)劃問題進(jìn)行求解，并通過大規(guī)模的算例實驗驗證了算法的有效性。LECLUYSE等［17］考慮了更加復(fù)雜的情況，如考慮了行程時間會隨時間隨機(jī)變化的車輛路徑問題，并對行程時間可靠性進(jìn)行了分析。由于客戶需求可能產(chǎn)生在區(qū)域內(nèi)的任意位置，確定出客戶與配送中心以及客戶之間的最短運輸距離就十分必要。傳統(tǒng)的配送優(yōu)化模型往往假設(shè)配送中心及各客戶之間的運輸距離為兩點之間的直線距離，并簡單地利用勾股定理進(jìn)行計算，這導(dǎo)致模型的優(yōu)化結(jié)果與實際最優(yōu)路線相差甚遠(yuǎn)。因此，在對配送路線進(jìn)行優(yōu)化時，必須考慮運輸網(wǎng)絡(luò)對配送計劃的影響。

1 配送優(yōu)化模型

考慮到客戶與配送中心以及客戶之間行車距離在實際配送中的重要性，將配送優(yōu)化問題描述為：配送中心負(fù)責(zé)某一特定區(qū)域內(nèi)的貨物配送任務(wù)，滿足該區(qū)域內(nèi)隨機(jī)產(chǎn)生的客戶需求，需要確定配送方案，使送貨車輛行走的總路程最短。結(jié)合配送問題的實際運作，建立如下數(shù)學(xué)模型：

目標(biāo)函數(shù)：約束條件：

模型中各數(shù)學(xué)符號的意義如下：

I為需求點的數(shù)目;i為需求點編號，i=1，2，…，I，i=0 為配送中心編號;W為配送車輛的容量上限;wi為需求點i的貨物需求量，i=1，2，…，I;k為配送路線序號;dij為點i到點j的運輸距離(受運輸網(wǎng)絡(luò)限制的最短路程)，i，j=0，1，2，…，I;M為一個較大的整數(shù)。

決策變量：

yki為當(dāng)配送路線k滿足客戶i的需求時，yki=1，否則，yki=0;xkij為當(dāng)配送路線k滿足i和j的需求，且j的訪問順序緊隨i之后時，xkij=1，否則xkij=0;uki為0 -1 變量，用于消除配送路線模型中可能產(chǎn)生子回路的情況。

目標(biāo)函數(shù)式(1)表示多條配送路線的總路程最短;約束條件式(2)表示單條配送路線裝載的貨物必須小于配送車輛的容量上限;約束條件式(3)表示客戶需求有且只有一條配送路線為其服務(wù);約束條件式(4)和式(5)保證了配送路線進(jìn)出需求點的流量平衡;約束條件式(6)限定只有從配送中心出發(fā)的回路才是有效的配送路線;約束條件式(7)用來消除可能存在的子回路。

2 運輸距離矩陣

由于客戶需求是在特定區(qū)域內(nèi)隨機(jī)產(chǎn)生的，考慮到運輸網(wǎng)絡(luò)的限制，不能簡單地用兩點之間的直線距離作為運輸距離。圖1 為某實際的運輸網(wǎng)絡(luò)，0 為配送中心所在位置，位置固定，1 ～10 為客戶所在位置(客戶所在位置位于既定路網(wǎng))，在絕大多數(shù)情況下，兩點之間沒有直線道路連接，且由于運輸網(wǎng)絡(luò)較為復(fù)雜，當(dāng)兩個點相距較遠(yuǎn)時，可供選擇的路徑較多，兩點之間的最短路程很難通過觀察得知。

針對實際運輸網(wǎng)絡(luò)中任意兩點之間最短路程未知的情況，筆者采用弗洛伊德算法計算不同點之間的最短路程。在利用弗洛伊德算法進(jìn)行計算時，首先需要將運輸網(wǎng)絡(luò)轉(zhuǎn)化為一個距離矩陣，該矩陣包含了運輸網(wǎng)絡(luò)的所有空間信息。對于如圖1 所示的運輸網(wǎng)絡(luò)，需要對其中所有的節(jié)點(即實際交通網(wǎng)絡(luò)中所有的丁字路口和十字路口)編排序號。此外，配送中心和各客戶需求點也需要編排序號。

圖1 實際運輸網(wǎng)絡(luò)示意圖

用G(V，E)表示如圖1 所示的無向連通圖，用vi表示點i，(vi，vj)表示連接i和j的弧，d(vi，vj)表示弧的長度。圖1 中共有101 個路口，1 個配送中心和10 個客戶需求點，則需要構(gòu)建一個112 ×112 的初始距離矩陣D(0)={a(0)ij}112×112。

當(dāng)運輸網(wǎng)絡(luò)中的兩點之間有弧直接連接時，弧的長度即為初始距離矩陣中對應(yīng)元素的值;當(dāng)兩點重合時，對應(yīng)元素(矩陣主對角線上的元素)的值為零;當(dāng)兩點不重合且沒有弧直接連接時，初始矩陣中對應(yīng)元素的值則為無窮大，在進(jìn)行運算時，取一個足夠大的整數(shù)M即可。

對于k=1，2，…，n，計算：

當(dāng)k=n時，D(n)={a(n)ij}112×112為任意兩點之間的最短路程。利用LINGO 能夠方便地實現(xiàn)弗洛伊德算法，可以將初始距離矩陣D(0)從EXCEL導(dǎo)入到LINGO，求解結(jié)果則可以從LINGO 導(dǎo)入到EXCEL。對于如圖1 所示的運輸路網(wǎng)，可以在3秒之內(nèi)求出最短路程矩陣，該矩陣即為配送路線優(yōu)化模型中需要的距離矩陣。LINGO 中的程序代碼如下所示：

最短運輸距離矩陣的求解結(jié)果如表1 所示，可以發(fā)現(xiàn)運輸距離矩陣是對稱矩陣，該距離矩陣將作為后續(xù)配送路線優(yōu)化的輸入量。

表1 運輸距離矩陣

3 LINGO 算例分析

利用上述求最短路程矩陣的方法和建立的整數(shù)線性規(guī)劃模型，可以對配送路線問題的算例進(jìn)行求解。利用圖1 中隨機(jī)生成的10 個客戶點，設(shè)配送車輛的容量上限為24，隨機(jī)生成10 個客戶點的需求量，這些需求量為3 ～8 之間的整數(shù)，且服從均勻分布，如表2 所示。

表2 客戶點的貨物需求量

利用LINGO 及相關(guān)數(shù)據(jù)，可以求出該算例的最優(yōu)解，在一般筆記本電腦上的求解時間為38 min。LINGO 中的程序代碼如下所示：

其中，路線1 完成的貨運量為21，路線2 為17，路線3 為15。最優(yōu)解下的目標(biāo)函數(shù)值為30.736(地圖上距離)。需要注意的是，在定義路線集合時無法精確預(yù)知最優(yōu)條件下的配送回路個數(shù)。為此，在LINGO 編程時，綜合考慮車輛容量和客戶點總需求量，路線集合元素設(shè)置為一個足夠大的值。算例中設(shè)置為4 個，大于最優(yōu)解的配送回路個數(shù)(3 個)，設(shè)置合理。

4 模擬退火算法求解

模擬退火算法是一種基于蒙特卡羅迭代求解策略的隨機(jī)尋優(yōu)算法。模擬退火算法與初始解狀態(tài)無關(guān)，具有漸進(jìn)收斂性。模擬退火算法的求解流程如圖2 所示。

圖2 模擬退火算法流程圖

模擬退火算法的功能模塊主要包括：設(shè)置控制參數(shù)，生成初始解，變換生成新解，Metropolis 準(zhǔn)則和降溫模塊［18］。其中控制參數(shù)的設(shè)置對算法的求解質(zhì)量有較大影響，主要控制參數(shù)包括初始溫度、降溫速率、迭代步長和終止準(zhǔn)則(筆者限定溫度下降次數(shù)超過500 次時停止運算)。

利用C 語言編寫配送路線優(yōu)化問題的模擬退火算法程序，對算例進(jìn)行多次求解。通過多次試驗得到求解質(zhì)量較高的算法控制參數(shù)，如表3所示。在設(shè)定的控制參數(shù)下，隨機(jī)運行程序12次，由于程序以降溫次數(shù)作為終止準(zhǔn)則，在一般筆記本電腦上程序每次的運行時間為9.89 s，記錄每次試驗的運行結(jié)果，包括目標(biāo)函數(shù)值以及首次得到該函數(shù)值的降溫次數(shù)等，如表4 所示。從表4 可以看出，算法程序在12 次試驗中，有6 次收斂到了全局最優(yōu)解，5 次收斂到相對誤差僅為0.228%的局部最優(yōu)解，最差的局部最優(yōu)解為第9次試驗結(jié)果，相對誤差也僅為0.309%。

表3 模擬退火算法參數(shù)設(shè)置

LINGO 及模擬退火算法的求解結(jié)果表明，模擬退火算法能夠有效地解決所提出的路線配送優(yōu)化問題。筆者利用弗洛伊德算法和模擬退火算法對配送路線優(yōu)化問題進(jìn)行求解，得到的配送路線圖更加符合配送活動的生產(chǎn)實際，如圖3(a)所示。相關(guān)文獻(xiàn)由于沒有考慮運輸網(wǎng)絡(luò)的約束，配送路線的優(yōu)化結(jié)果通常如圖3(b)所示。

表4 算法程序試驗結(jié)果

圖3 路線優(yōu)化結(jié)果對比

5 結(jié)論

筆者基于實際運輸網(wǎng)絡(luò)考慮物流配送路線優(yōu)化問題，針對運輸距離受限于運輸網(wǎng)絡(luò)，而不能簡單利用勾股定理以直線距離作為運輸距離的實際情況，利用弗洛伊德算法以及LINGO 和EXCEL軟件計算運輸網(wǎng)絡(luò)中任意兩點之間的最短路程，并以此構(gòu)造配送路線優(yōu)化模型中的距離矩陣。利用求得的運輸距離矩陣以及所提出的用于解決配送路線優(yōu)化問題的整數(shù)線性規(guī)劃模型，可以在LINGO 環(huán)境下對小型算例進(jìn)行求解，求解結(jié)果證明，該整數(shù)線性規(guī)劃模型正確，能夠用于解決配送路線優(yōu)化問題。

考慮到LINGO 求解速度較慢的弱點，開發(fā)了基于C 語言的模擬退火算法程序?qū)ο鄳?yīng)的配送路線優(yōu)化問題進(jìn)行求解，求解結(jié)果顯示，在合適的控制參數(shù)條件下，模擬退火算法能夠得到相對誤差較小的優(yōu)化解，并且算法求解時間相對于LINGO 精確求解具有較大的優(yōu)勢。

［1］CHEN W，EBERHART R C. Genetic algorithm for logistics scheduling problem［M］.［S.l.］：IEEE Press，2002：512 -516.

［2］王會云，肖建祿，劉登泰，等. 基于遺傳算法的配送路線優(yōu)化［J］.后勤工程學(xué)院學(xué)報，2008，24(3)：91-94.

［3］陳彥軍，吳國平，李敬民. 基于GIS 空間分析的物流配送模型研究及應(yīng)用［J］.南京師范大學(xué)學(xué)報：工程技術(shù)版，2004，4(3)：68 -72.

［4］王勇，池潔. 物流配送路線及配送時間的優(yōu)化分析［J］. 重慶交通大學(xué)學(xué)報：自然科學(xué)版，2008，27(4)：647 -650.

［5］張學(xué)志，陳功玉. 車輛路線安排的改進(jìn)節(jié)約算法［J］.系統(tǒng)工程，2008，26(11)：67 -70.

［6］楊文霞，郭海湘，楊娟，等.改進(jìn)的掃描法求解單車場多車型車輛路徑問題［J］. 物流技術(shù)，2010，21(4)：50 -53.

［7］霍亮.基于GIS 的物流分區(qū)配送方法研究［J］.測繪學(xué)院學(xué)報，2003，20(2)：145 -147.

［8］張彥敏，芮小平. 用免疫遺傳算法實現(xiàn)配送路線求解［J］.武漢理工大學(xué)學(xué)報，2011，33(9)：72 -76.

［9］黃明，林廣智，梁旭，等.改進(jìn)的遺傳算法在車輛路徑問題中的應(yīng)用［J］. 大連交通大學(xué)學(xué)報，2010，31(1)：95 -99.

［10］郎茂祥，胡思繼.車輛路徑問題的禁忌搜索算法研究［J］.管理工程學(xué)報，2004，18(1)：81 -84.

［11］楊宇棟，郎茂祥，胡思繼.有時間窗車輛路徑問題的模型及其改進(jìn)模擬退火算法研究［J］.管理工程學(xué)報，2006，20(3)：104 -107.

［12］WANG C H，LU J. An effective evolutionary algorithm for the practical capacitated vehicle routing problems［J］. Computers ＆ Operations Research，2010，37(11)：1870 -1876.

［13］WANG C H，LU J. A hybrid genetic algorithm that optimizes capacitated vehicle routing problems［J］. Expert Systems with Applications，2009(36)：2921-2936.

［14］LEUNG S C H，ZHENG J. Simulated annealing for the vehicle routing problem with two - dimensional loading constraints［J］. Flexible Services and Manufacturing Journal，2010，20(1 -2)：61 -82.

［15］FUELLERER G，DOERNER K F，HARTL R F，et al.Ant colony optimization for the two - dimensional loading vehicle routing problem［J］. Computers ＆Operations Research，2009，36(3)：655 -673.

［16］LIN S W，LEE Z J，YING K C，et al. Applying hybrid meta - heuristics for capacitated vehicle routing problem［J］. Expert Systems with Applications，2009(36)：1505 -1521.

［17］LECLUYSE C，WOENSEL T V，PEREMANS H.Vehicle routing with stochastic time-dependent travel times［J］.40R - Q J Operations Research，2009(7)：363 -377.

［18］史峰，王輝，郁磊，等. Matlab 智能算法30 個案例分析［M］.北京：北京航空航天大學(xué)出版社，2011：178 -187.