基于電子地圖的非對(duì)稱矩陣車輛路徑問題研究

伊俊敏，蘇志雄

(廈門理工學(xué)院管理學(xué)院，福建 廈門 361024)

基于電子地圖的非對(duì)稱矩陣車輛路徑問題研究

伊俊敏，蘇志雄

(廈門理工學(xué)院管理學(xué)院，福建 廈門 361024)

在建立路徑問題二指數(shù)流量模型的基礎(chǔ)之上，結(jié)合非對(duì)稱性矩陣的變化進(jìn)行靈敏度分析，并運(yùn)用兩種算法得到求解結(jié)果。多個(gè)實(shí)例的比較分析表明，非對(duì)稱性問題與對(duì)稱性問題是兩個(gè)不同的問題，系數(shù)矩陣的差異最終帶來目標(biāo)函數(shù)值和基解的差異。城市物流配送實(shí)際案例檢驗(yàn)表明，運(yùn)用電子地圖路線所得的非對(duì)稱性距離矩陣，能有效縮短車輛路徑總里程；相對(duì)于對(duì)稱性矩陣車輛路徑，非對(duì)稱性距離矩陣車輛路徑更符合當(dāng)前物流的需求和實(shí)際情況，更具合理性。因此，城市物流配送應(yīng)綜合考慮各節(jié)點(diǎn)需求量和車輛選型，以平衡物流成本與服務(wù)要求。

城市物流配送；車輛路徑;非對(duì)稱矩陣;電子地圖

城市物流配送伴隨著城市生產(chǎn)、生活的發(fā)展而越來越普遍，它服務(wù)于城市及相近區(qū)域的貨物取送需求，利用城市發(fā)達(dá)的道路交通網(wǎng)絡(luò)，在經(jīng)濟(jì)合理區(qū)域內(nèi)，按要求完成物流取送作業(yè)。在城市物流配送活動(dòng)中，面對(duì)多客戶需求，優(yōu)化路線，降低成本就離不開車輛路徑問題。自從Dantzig和Ramser于1959年從運(yùn)輸實(shí)踐中提出車輛路徑問題[1]以來，它一直是學(xué)術(shù)界和產(chǎn)業(yè)界十分關(guān)注的熱點(diǎn)和難點(diǎn)問題。車輛路徑問題(Vehicle Routing Problem，VRP)一般定義為：對(duì)一系列發(fā)貨點(diǎn)和/或收貨點(diǎn)，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，在滿足一定的約束條件(如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量限制、行駛里程限制、時(shí)間限制等)下，達(dá)到一定的目標(biāo)(如路程最短、費(fèi)用最小、時(shí)間盡量少、使用車輛盡量少等)。[2]盡管學(xué)界對(duì)此進(jìn)行了大量的理論研究和實(shí)驗(yàn)分析，包括計(jì)算機(jī)求解大規(guī)模問題等研究進(jìn)展不斷涌現(xiàn)，但其研究結(jié)果在物流配送系統(tǒng)中的應(yīng)用還是比較有限的。主要原因在于物流配送過程中涉及到貨物、車輛、路線、時(shí)間和任務(wù)等條件交織的復(fù)雜性和變化性。

依據(jù)對(duì)物流配送過程復(fù)雜性考慮的側(cè)重不同，VRP有多種分類方式，但帶容量約束的車輛路徑問題(CVRP)是最常見的VRP問題之一，也是物流配送車輛線路優(yōu)化的基礎(chǔ)。在CVRP模型中，各需求點(diǎn)兩兩之間的距離矩陣必須是確定已知的。傳統(tǒng)的算例都是以二維平面來定位各需求點(diǎn)位置，以兩兩之間的直線距離構(gòu)成一個(gè)對(duì)稱性矩陣；但這只是一種理想假設(shè)，實(shí)際物流配送中各點(diǎn)間的距離是由它們之間的交通路線所決定的。[3]隨著城市交通的發(fā)展，立交橋、轉(zhuǎn)盤、高架路、隧道的不斷出現(xiàn)豐富了道路的選擇；單行線、禁左轉(zhuǎn)、調(diào)頭控制等交通管理措施也影響車輛路線的最終確定；甚至需要根據(jù)實(shí)時(shí)交通信息來動(dòng)態(tài)確定車輛路線[4]。面對(duì)城市物流配送復(fù)雜的交通情況，CVRP模型的實(shí)際應(yīng)用就不得不考慮如何構(gòu)建合理的距離矩陣。盡管在CVRP各種算例的求解上研究很多，但是目前國內(nèi)還未見考慮非對(duì)稱距離矩陣的CVRP問題研究，本文以實(shí)際案例的電子地圖非對(duì)稱矩陣數(shù)據(jù)來探討CVRP問題在城市物流中的應(yīng)用。

一、基于電子地圖的非對(duì)稱距離矩陣的提出

近年來地理信息系統(tǒng)、遙感、測(cè)繪、計(jì)算機(jī)等技術(shù)的蓬勃發(fā)展為傳統(tǒng)地圖注入了新的活力，電子地圖應(yīng)運(yùn)而生并發(fā)展迅猛，它的信息豐富，查閱顯示方便，已經(jīng)構(gòu)成了一個(gè)龐大的地理信息系統(tǒng)。[5]成熟的商業(yè)地圖在線軟件功能強(qiáng)大，如谷歌地圖和國內(nèi)的百度、高德等地圖等已經(jīng)可以為交通出行、物流運(yùn)輸提供實(shí)時(shí)的信息和有價(jià)值的路線參考[6]。

在電子地圖上，城市內(nèi)各需求節(jié)點(diǎn)可以精確定位到所在街道門牌號(hào)上，兩個(gè)節(jié)點(diǎn)間的駕車路線可由地圖數(shù)據(jù)庫按一定規(guī)則來確定，路線規(guī)則通常有多個(gè)選項(xiàng)供用戶選擇。例如百度地圖給出“推薦路線” “最短路程”和“不走高速”3種選項(xiàng)，每種選項(xiàng)均給出路程和駕車時(shí)間，可用于實(shí)時(shí)導(dǎo)航。圖1分別是兩個(gè)節(jié)點(diǎn)間去程和回程的百度地圖截圖，可以看到，不僅距離有差別，更重要的路線有差別，去程先右轉(zhuǎn)繞了一個(gè)大彎，還在立交橋下繞了一個(gè)小圈；而回程則簡(jiǎn)短直接得多，兩個(gè)小右轉(zhuǎn)后沿著一條馬路直線走。在城市物流配送中，這種距離的差別特別明顯，而在長(zhǎng)途運(yùn)輸及物流中，這種短程的雙向差別相對(duì)長(zhǎng)距離就幾乎可以忽略。

因此在實(shí)際問題中要考慮路線的差距給兩兩節(jié)點(diǎn)距離帶來的差異，距離矩陣就應(yīng)當(dāng)是非對(duì)稱的。為便于計(jì)算比較，我們不但給出非對(duì)稱矩陣，還給出對(duì)稱矩陣。不管是對(duì)稱的，還是非對(duì)稱的距離矩陣，它們的上半矩陣各元素均為{cij，ij，i，j=1,…，n}={cij，i

(1)

(2)

二、非對(duì)稱矩陣CVRP問題及靈敏度分析

考慮上述實(shí)際情況下的CVRP問題就是非對(duì)稱矩陣的車輛路徑問題AVRP，在單倉庫、全同車型、每節(jié)點(diǎn)進(jìn)出一次的基本假設(shè)不變的情況下，路徑問題的目標(biāo)函數(shù)總是minZ=CX。按照式(2)中對(duì)稱矩陣和非對(duì)稱矩陣情況的不同，CVRP和AVRP的目標(biāo)函數(shù)可分別為minZ=SX和minZ=AX。AVRP問題模型采用二指數(shù)車輛流模型[7]，目標(biāo)函數(shù)寫成求和形式如式(3)所示，其中xij為0～1變量，i，j= 2,…，n且i，j=1表示倉庫。為此，模型表述如下：

(3)

(4)

(5)

(6)

(7)

ui-uj+Qxij≤Q-qj，qi+qj

(8)

qi≤ui≤Q， ?i=2,…,n。

(9)

模型中，約束條件式(4)和式(5)是對(duì)各需求節(jié)點(diǎn)的訪問約束，每節(jié)點(diǎn)只由一輛車來拜訪，進(jìn)出各一次；式(6)和式(7)為倉庫節(jié)點(diǎn)約束，共m輛車從倉庫出發(fā)并回到倉庫；式(8)為子回路消除約束，式中Q為車輛容量，qj(j=2,…,n)為每節(jié)點(diǎn)需求量，ui(i=2,…,n)表示車輛訪問節(jié)點(diǎn)i后的實(shí)際裝車量，為連續(xù)變量。式(8)和式(9)這兩個(gè)約束條件也共同形成車輛的容量約束。

從目標(biāo)函數(shù)式(3)來看，從對(duì)稱矩陣到非對(duì)稱矩陣的不同體現(xiàn)在價(jià)值系數(shù)(兩兩距離)cij的變化，而針對(duì)價(jià)值系數(shù)的變化對(duì)問題最優(yōu)解的影響可以采用靈敏度分析，這一分析主要考慮基變量和非基變量?jī)煞N情況[8]。由于非對(duì)稱矩陣涉及(n-1)2/2個(gè)價(jià)值系數(shù)的變化，相比對(duì)稱矩陣時(shí)的最優(yōu)解，非對(duì)稱矩陣情況下，應(yīng)當(dāng)同時(shí)都有基變量和非基變量的價(jià)值系數(shù)變化，很容易超出基解不變條件下對(duì)價(jià)值系數(shù)變化所要求的范圍，形成新的基解。即使基解不變，由于基解所對(duì)應(yīng)價(jià)值系數(shù)的變化，最優(yōu)解值也會(huì)發(fā)生變化。

三、基于城市物流配送案例的AVRP算例

本文案例是基于上海某物流公司的循環(huán)取貨實(shí)例數(shù)據(jù)的VRP分析。案例中，倉庫節(jié)點(diǎn)為該公司位于安亭的總庫，在嘉定西部及城區(qū)范圍內(nèi)另有18個(gè)需求節(jié)點(diǎn)，19個(gè)節(jié)點(diǎn)在百度地圖上的分布如圖2所示。

以百度地圖算出的兩兩推薦路線距離對(duì)稱矩陣和非對(duì)稱矩陣如圖3所示。從圖3可見，對(duì)稱矩陣A是以右上角(即i

案例中車輛為載重8t的中型廂式貨車，容積Q=33.609，各節(jié)點(diǎn)需求量為qj={11.901 92，31.141 474，15.713 732，2.257 92，1.005，0.794 88，13.854 51，0.1492 96，0.061 056，6.275 76，0.794 88，14.634 38，0.691 641，7.1035 96，11.603 268，10.228 988，11.061 471，0.488 448}。將兩個(gè)不同的矩陣數(shù)據(jù)代入VRP模型中，采用LINGO精確算法和遺傳算法得到的結(jié)果如表1所示。從表1可見，對(duì)稱與非對(duì)稱這兩種情況除一條線路相同外，其他都不同；這條相同的路線1-18-1也因?yàn)榫仃囋夭粚?duì)稱，而線路長(zhǎng)度不一樣?？偟慕Y(jié)果是5條路線中非對(duì)稱矩陣時(shí)路徑總里程更小。圖4是非對(duì)稱矩陣時(shí)電子地圖上所反映的實(shí)際路線。

表1 對(duì)稱矩陣與非對(duì)稱矩陣的計(jì)算結(jié)果

四、分析與討論

我們對(duì)案例其他區(qū)域的節(jié)點(diǎn)問題也進(jìn)行了計(jì)算，各區(qū)域的節(jié)點(diǎn)規(guī)模從6，9，11，13，16，17，19，28，32到47不等，它們的兩兩距離均按百度地圖路線所得。其中有些區(qū)域分別考慮了選用不同車輛容積的兩種情況，結(jié)果總結(jié)如表2所示。

表2 其他區(qū)域?qū)ΨQ與非對(duì)稱距離矩陣實(shí)例計(jì)算結(jié)果

*節(jié)點(diǎn)數(shù)超過20時(shí)，精確求解耗時(shí)過長(zhǎng)，僅用遺傳算法求解，不能保證一定是最優(yōu)解。

可以看到，對(duì)稱和非對(duì)稱的最優(yōu)解值均不相同，最優(yōu)路線除個(gè)別路線相同外，一般均不同，也有對(duì)稱與非對(duì)稱的路線順序剛好相反的，如2號(hào)的兩個(gè)4)號(hào)路線和3號(hào)的對(duì)稱2)和非對(duì)稱1)路線。但是從0～1變量xij的值來看，不管是線路不同還是順序不同，都是基變量的不同，也就是說矩陣的變化都引起了基的變化，最優(yōu)解值當(dāng)然更發(fā)生改變。例如，對(duì)表1中的例子，非對(duì)稱矩陣S，Δcij最大值為-6.1，最小為0，Δcij的均值為-0.001 36，按百分比計(jì)最大為61.86%，平均差距為10.33%。非對(duì)稱矩陣下目標(biāo)函數(shù)值略小的原因不僅在于Δcij的均值小于0，還有基解的變化。

非對(duì)稱矩陣VRP問題的最早并沒有引起研究人員的重視，在經(jīng)典直線距離對(duì)稱矩陣算例的情況下，研究主要是追求各種算法的求解。最早考慮非對(duì)稱矩陣的是采用精確算法的小規(guī)模問題[9]，另外就是ADVRP(asymmetric distance-constrained vehicle routing problem)問題，但它同時(shí)對(duì)每輛車所走的總距離有一定限制[10-11]，近年來，有研究開始考慮純非對(duì)稱矩陣情況的VRP問題AVRP，多算例證明非對(duì)稱性問題和對(duì)稱性問題是兩個(gè)不同的問題[12]。由于非對(duì)稱矩陣元素改變眾多(共(n-1)2/2個(gè))，很難以對(duì)稱的結(jié)果經(jīng)過基變換得到非對(duì)稱的結(jié)果，只能重新計(jì)算。因此結(jié)果可以是路線的不同，或者路線經(jīng)過節(jié)點(diǎn)相同但順序不同，但這都是反映基解的不同，目標(biāo)函數(shù)值當(dāng)然就更不一樣。

另外，比較表2中相同結(jié)點(diǎn)的4與5，6和7的結(jié)果也表明，車輛容量也顯著影響最終的路線結(jié)果，在城市配送小距離的范圍內(nèi)，車輛容量越小，需要的車輛數(shù)量就越多，同時(shí)所走的總距離也就越大。因?yàn)橐恍┏鞘袑?duì)配送貨車的限制措施，物流配送需要綜合考慮各節(jié)點(diǎn)需求量和車輛的選型，以平衡成本與服務(wù)要求。

五、結(jié)語

城市物流配送因?yàn)槭苁袃?nèi)復(fù)雜的道路交通網(wǎng)絡(luò)的影響，兩兩節(jié)點(diǎn)間的路線呈現(xiàn)不對(duì)稱性，現(xiàn)代電子地圖技術(shù)可以較好地描述展現(xiàn)這些線路的不對(duì)稱性，從而為非對(duì)稱性距離矩陣CVRP問題的求解帶來了方便。本文以實(shí)際物流案例中的問題揭示了非對(duì)稱矩陣車輛路徑問題的建模、求解、靈敏度分析與實(shí)施的整個(gè)過程，為科學(xué)解決城市物流配送問題奠定了堅(jiān)實(shí)的基礎(chǔ)。若能進(jìn)一步結(jié)合電子地圖API編程與VRP模型求解，將為路徑問題應(yīng)用于物流實(shí)踐提供實(shí)用化的可行方案。

[1]DANTIZIGGB，RAMSERJH.Thetruckdispatchingproblem[J].ManagementScience，1959，6(1):80-91.

[2]劉云忠，宣慧玉.車輛路徑問題的模型及算法研究綜述[J].管理工程學(xué)報(bào)，2005，19(1):124-130.

[3]李軍，曹立明，王小平.基于GIS的物流配送路徑計(jì)算[J].計(jì)算機(jī)應(yīng)用與軟件，2007，24(3):12-14.

[4]李研鋒，高自友，李軍.基于實(shí)時(shí)交通信息的城市動(dòng)態(tài)網(wǎng)絡(luò)車輛路徑優(yōu)化問題[J].系統(tǒng)工程理論與實(shí)踐，2013，33(7):1813～1819.

[5]龍毅，溫永寧，盛業(yè)華.電子地圖學(xué)[M].北京：科學(xué)出版社，2006.

[6]田智慧，苗全生，武舫.大區(qū)域物流配送中車輛路徑選擇的GIS研究[J].測(cè)繪科學(xué)，2008，33(5):155-157.

[7]TOTHP.VIGOD.Models，relaxationsandexactapproachesforthecapacitatedvehicleroutingproblem[J].DiscreteAppliedMathematics，2002，123(1-3):487-512.

[8]錢頌迪.運(yùn)籌學(xué)[M].3版.北京：清華大學(xué)出版社，2003.

[9]LAPORTEG，MERCUREH，NOBERTY.Anexactalgorithmfortheasymmetricalcapacitatedvehicleroutingproblem[J].Networks，1986，16，33-46.

[10]LAPORTG，NOBERTY，TAILLEFERS.Abranchandboundalgorithmforthesymmetricaldistance-constraintedvehicleroutingproblem[J].MathematicalModelling，1987，9：857-868.

[11]ALMOUSTAFAS，HANAFIS，MLADENOVIN.Newexactmethodforlargeasymmetricdistance-constrainedvehicleroutingproblem[J].EuropeanJournalofOperationalResearch，2013，226(3):386-394.

[12]RODRIGUEZA，RUIZR.Astudyontheeffectoftheasymmetryonrealcapacitatedvehicleroutingproblems[J].ComputerandOperationsResearch，2012，39： 2142-2151.

(責(zé)任編輯 馬 誠)

A Study of Vehicle Routes with Asymmetric Matrix based on E-map

YI Jun-min,SU Zhi-xiong

(School of Management,Xiamen University of Technology,Xiamen 361024,China)

To deal with the asymmetric routes in unban delivery,a two-index vehicle flow model of CVRP was setup and solutions by two algorithms were conducted on many instances.Sensitivity analysis showed that the difference from asymmetric matrix leads to substantial change of objective value and optimal base,which implied that the asymmetric and symmetric problems are,indeed,two different problems.Using the asymmetric matrix from e-map service,the mileage of routes can be effectively shortened.The asymmetric matrix better meets the current logistics requirements and hence more practical and logical than the symmetric one.It is concluded that the node location,demand and routing should be synthesized for urban delivery to balance logistics cost and service.

urban logistics and delivery;vehicle routing;asymmetric matrix;e-map

2015-04-13

2015-04-29

國家自然科學(xué)基金項(xiàng)目(71371162)；福建省自然科學(xué)基金項(xiàng)目(2014J01271)

伊俊敏(1969-)，男，教授，博士，研究方向?yàn)槲锪鞴こ?、集裝箱運(yùn)輸管理。E-mail：yijunmin@xmut.edu.cn

F252;O221;P289

A

1673-4432(2015)03-0032-07