基于運(yùn)輸網(wǎng)絡(luò)的配送路線優(yōu)化模型

張艷偉，周 萬(wàn)，向家偉

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

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

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

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

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

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

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

決策變量：

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

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

2 運(yùn)輸距離矩陣

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

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

圖1 實(shí)際運(yùn)輸網(wǎng)絡(luò)示意圖

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

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

對(duì)于k=1，2，…，n，計(jì)算：

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

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

表1 運(yùn)輸距離矩陣

3 LINGO 算例分析

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

表2 客戶點(diǎn)的貨物需求量

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

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

4 模擬退火算法求解

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

圖2 模擬退火算法流程圖

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

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

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

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

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

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

5 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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

［11］楊宇棟，郎茂祥，胡思繼.有時(shí)間窗車輛路徑問(wèn)題的模型及其改進(jìn)模擬退火算法研究［J］.管理工程學(xué)報(bào)，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 個(gè)案例分析［M］.北京：北京航空航天大學(xué)出版社，2011：178 -187.