實(shí)時(shí)路況下同城生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化

賈現(xiàn)召+戚恒亮+賈其蘇+李亞琴+黃自治

摘要：在同城生鮮產(chǎn)品配送過(guò)程中，配送時(shí)間可能會(huì)受到路況信息的影響，因此針對(duì)生鮮訂單要及時(shí)送達(dá)客戶的問(wèn)題，結(jié)合實(shí)時(shí)交通信息，對(duì)同城冷鏈物流配送路徑優(yōu)化進(jìn)行研究。根據(jù)問(wèn)題的描述，從配送區(qū)域的實(shí)時(shí)路況信息出發(fā)，提出了基于實(shí)時(shí)交通路況信息的同城生鮮產(chǎn)品配送路徑優(yōu)化方法，建立了最優(yōu)路徑的數(shù)學(xué)模型，采用灰色關(guān)聯(lián)度建立路況矩陣，應(yīng)用改進(jìn)Floyd算法對(duì)算例進(jìn)行求解和分析，通過(guò)可視化界面將路徑結(jié)果輸出，并將在不同時(shí)間窗內(nèi)的配送時(shí)間與靜態(tài)算法下的配送時(shí)間進(jìn)行比較。結(jié)果表明，結(jié)合實(shí)時(shí)交通信息的動(dòng)態(tài)路徑尋優(yōu)方法，在路況擁堵高發(fā)時(shí)間段內(nèi)，物流配送時(shí)間更短、效率更高。

關(guān)鍵詞：生鮮農(nóng)產(chǎn)品；配送；路徑規(guī)劃；Floyd算法；實(shí)時(shí)交通；優(yōu)化模型

中圖分類號(hào)： S126；F252.14文獻(xiàn)標(biāo)志碼： A文章編號(hào)：1002-1302（2017）17-0292-03

收稿日期：2016-04-18

基金項(xiàng)目：國(guó)家科技支撐計(jì)劃（編號(hào)：2011BAF09B01-06）；河南省自然科學(xué)基金（編號(hào)：152300410083）。

作者簡(jiǎn)介：賈現(xiàn)召（1965—），男，河南洛陽(yáng)人，教授、研究員，主要從事農(nóng)產(chǎn)品信息化等方面的研究。E-mail：980833962@qq.com。

通信作者：戚恒亮，碩士研究生，主要從事農(nóng)產(chǎn)品冷鮮配送等方面的研究。E-mail：18638808804@163.com。移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展，極大地促進(jìn)了電商銷售模式和消費(fèi)者購(gòu)買方式的轉(zhuǎn)變，使得送貨上門成為一項(xiàng)不可或缺的服務(wù)。在城市道路環(huán)境下，研究如何將訂單特別是生鮮訂單快速地送達(dá)目的地顯得十分必要。

對(duì)于生鮮產(chǎn)品配送路徑的規(guī)劃，目前國(guó)內(nèi)外學(xué)者都進(jìn)行了較多的研究。Zhang等采用禁忌搜索算法對(duì)冷鏈物流配送路徑進(jìn)行了優(yōu)化研究[1]；Arbelaitz等建立了帶有時(shí)間窗的冷鏈配送路徑問(wèn)題的模型，通過(guò)MEAT啟發(fā)方法和路線規(guī)劃啟發(fā)算法相結(jié)合，從而縮小了可行解的搜索范圍[2-4]。楊丹婷比較了不同路徑算法的優(yōu)化效果，并對(duì)算法進(jìn)行了改進(jìn)[5]；繆小紅等提出了基于地理信息系統(tǒng)（GIS）的冷鏈配送路徑算法，將配送過(guò)程中的不確定因素考慮在內(nèi)[6]。

1問(wèn)題描述與建模

1.1同城生鮮產(chǎn)品配送問(wèn)題描述

本研究的同城生鮮產(chǎn)品配送問(wèn)題可以描述為1個(gè)配送中心具有多輛配送車，每輛配送車從配送中心出發(fā)，以最短的時(shí)間為指定的客戶配貨，配送結(jié)束后返回配送中心。

1.2模型假設(shè)

（1）配送中心具有充足的貨源，不存在缺貨現(xiàn)象；

（2）配送中心具有一定數(shù)量的配送車，每輛配送車的載貨量相同；

（3）配送車必須從配送中心出發(fā)，配送結(jié)束后返回配送中心；

（4）目標(biāo)客戶的需求量、位置信息已知，配送過(guò)程中無(wú)訂單增加或退訂；

（5）目標(biāo)客戶的需求量小于配送車的最大運(yùn)輸量；

（6）每個(gè)目標(biāo)客戶的訂單只能由1輛配送車配送；

（7）每個(gè)目標(biāo)客戶的配送距離都小于配送車的最大運(yùn)輸距離。

1.3同城生鮮產(chǎn)品配送模型的建立

本研究將要建立的模型以綜合配送時(shí)間最短作為目標(biāo)函數(shù)。綜合配送時(shí)間成本包括道路通行時(shí)間、道路擁堵時(shí)間、交通管制時(shí)間以及道路交叉口通過(guò)時(shí)間等。

1.3.1道路通行時(shí)間車輛道路通行時(shí)間（不包括路口等待時(shí)間）可表示為

T1=∑ni=0 ∑nj=0dijxij×1Cij·vij。（1）

式中：dij為路口i到下一個(gè)路口j之間的距離；xij為變量，當(dāng)配送車輛經(jīng)過(guò)（pi，pj）路段時(shí)，xij為1，否則為0；vij為配送車輛在（pi，pj）路段時(shí)的平均行駛速度；Cij為（pi，pj）路段的單方向通行能力，公式如下：

Cij=∑ni=1C0α條α交α車道。（2）

式中：C0為一條車道的理論通行能力；α條為車道折減系數(shù)；α交為交叉口折減系數(shù)；α車道為車道寬度折減系數(shù)。

1.3.2道路擁堵時(shí)間道路擁堵時(shí)間為在道路受到天氣、紅綠燈等待時(shí)間、車流量等影響時(shí)配送車輛的行駛延長(zhǎng)時(shí)間。擁堵時(shí)間可表示為

T2=∑ni=0∑nj=0Pijλijdij×（1vij-1v0）。（3）

式中：Pij為配送車輛經(jīng)過(guò)（pi，pj）路段時(shí)的實(shí)際車流量；λij為（pi，pj）路段的日常擁堵系數(shù)；dij為（pi，pj）路段的長(zhǎng)度；vij為配送車輛在（pi，pj）路段時(shí)的平均行駛速度；v0為理想配送車速。

1.3.3交通管制時(shí)間當(dāng)配送車輛經(jīng)過(guò)的路段出現(xiàn)突發(fā)事件進(jìn)行交通管制時(shí)，則認(rèn)為車輛通過(guò)該路段的時(shí)間為無(wú)窮長(zhǎng)，為了節(jié)約配送時(shí)間，車輛改變行駛路線；反之，則為0。交通管制時(shí)間可表示為

T3=tij。（4）

式中：tij為變量，當(dāng)（pi，pj）路段出現(xiàn)交通管制時(shí)，tij為∞，否則為0。

1.3.4道路交叉口通過(guò)時(shí)間不同類型的道路交叉口、路口長(zhǎng)度、車輛流的平均到達(dá)率均會(huì)對(duì)車輛的路口通行時(shí)間造成影響。道路交叉口通過(guò)時(shí)間可表示為

T4=∑nj=0∑nk=0βθijkdijk×1vijk。（5）

式中：β為不同類型的道路交叉口通行系數(shù)；θijk為（pi，pj）路段內(nèi)的車輛流到達(dá)下一個(gè)路口k的平均到達(dá)率；dijk為緊接（pi，pj）路段的交叉口k的長(zhǎng)度；vijk為車輛在交叉口的通行速度。

1.4同城生鮮車輛配送路徑優(yōu)化模型

綜上所述，生鮮車輛配送路徑優(yōu)化模型目標(biāo)函數(shù)如下：

minf=T1+T2+T3+T4=∑ni=0∑nj=0xijdij×1∑ni=1C0α條α交α車道·vij+∑ni=0∑nj=0Pijλijdij×（1vij-1v0）+tij+∑nj=0∑nk=0βθijkdijk×1vijk；（6）endprint

s.t.∑ni=0∑mj=0xij≤m（i=0）；（7）

∑mj=0xij≤1（i=0）；（8）

∑ni=1xij=1（j=0，1，…，n；i≠j）；（9）

∑nj=1xij=1（i=0，1，…，n；i≠j）。（10）

其中，公式（7）約束配送路徑數(shù)不超過(guò)配送中心車輛總數(shù)；公式（8）約束配送車輛的起點(diǎn)和終點(diǎn)均為配送中心；公式（9）、公式（10）約束每個(gè)目標(biāo)訂單只能由1輛配送車配送1次。

2基于實(shí)時(shí)路況信息改進(jìn)的Floyd算法

與原有的Floyd算法相比，本研究提出的優(yōu)化路徑算法不再單純地用各道路節(jié)點(diǎn)間距的鄰接矩陣作為權(quán)重矩陣，而是根據(jù)公式（6）提出的優(yōu)化模型目標(biāo)函數(shù)，綜合考慮節(jié)點(diǎn)距離、車流量、道路施工、管制、擁堵等路況信息，建立實(shí)時(shí)路況的關(guān)鍵評(píng)價(jià)指標(biāo)體系，然后利用灰色關(guān)聯(lián)分析法得到各路段路況之間的灰色關(guān)聯(lián)矩陣，最后將灰色關(guān)聯(lián)矩陣作為Floyd算法的權(quán)重矩陣進(jìn)行最優(yōu)路徑求解。

2.1構(gòu)建路況評(píng)價(jià)指標(biāo)體系

本研究采用定量與定性分析相結(jié)合的方法對(duì)實(shí)時(shí)交通路況進(jìn)行評(píng)價(jià)。根據(jù)城市道路交通的特點(diǎn)，通過(guò)實(shí)證分析和問(wèn)卷調(diào)查建立了如表1所示的路況評(píng)價(jià)指標(biāo)體系。在該體系中可通過(guò)專家評(píng)分法來(lái)確定定性指標(biāo)權(quán)重，而定量指標(biāo)則可通過(guò)上述相應(yīng)的公式進(jìn)行求解計(jì)算[7]。

2.2求解路況灰色關(guān)聯(lián)矩陣

對(duì)于道路交通狀況的實(shí)時(shí)變化態(tài)勢(shì)，采用灰色關(guān)聯(lián)分析法可以對(duì)其發(fā)展程度進(jìn)行量化的度量，較好地彌補(bǔ)傳統(tǒng)評(píng)價(jià)分析方法的不足[8]。利用灰色關(guān)聯(lián)分析法分析實(shí)時(shí)路況變化，求解灰色關(guān)聯(lián)矩陣的步驟如下[9]：

（1）確定反映路況特征的參考序列和影響路況的比較序列；

（2）對(duì)各路況指標(biāo)權(quán)重進(jìn)行初值化處理；

（3）求參考序列和比較序列的灰色關(guān)聯(lián)系數(shù)；

（4）求各指標(biāo)間的關(guān)聯(lián)度；（5）排關(guān)聯(lián)序，得到灰色關(guān)聯(lián)矩陣。

各個(gè)路段間的路況關(guān)聯(lián)程度不僅僅是關(guān)聯(lián)度的大小，而主要是用關(guān)聯(lián)度的大小次序來(lái)進(jìn)行描述?；疑P(guān)聯(lián)矩陣由各個(gè)比較序列對(duì)各個(gè)參考序列的灰色關(guān)聯(lián)度rij（i=1，2，…，n）構(gòu)成，將rij進(jìn)行適當(dāng)排列可得到路況灰色關(guān)聯(lián)矩陣：

R=r11r12…r1n

r21r22…r2n

rn1rn2…rnm。（11）

2.3改進(jìn)Floyd算法求解最優(yōu)配送路徑

根據(jù)各個(gè)路況評(píng)價(jià)指標(biāo)，采用灰色關(guān)聯(lián)分析法得到路況矩陣R。以路況矩陣R作為路網(wǎng)的鄰接矩陣，即R=D=（rij）n×n，rij為節(jié)點(diǎn)vi到vj的路況權(quán)重。最優(yōu)配送路徑求解步驟：

（1）輸入路況權(quán)重矩陣D0=D；

（2）計(jì)算Dk=（rkij）n×n（k=1，2，…，n），其中：rkij=min[rk-1ij，rk-1ik+rk-1kj]；

（3）Dn=（rnij）n×n中元素rnij就是節(jié)點(diǎn)vi到vj的最優(yōu)路徑。

選取洛陽(yáng)市某地區(qū)局部道路作為路網(wǎng)模型，以Visual Studio 2010作為開發(fā)環(huán)境，利用C#語(yǔ)言編制最優(yōu)路徑可視化界面，輸出的最優(yōu)路徑如圖1所示。

3算例分析

本研究給出13個(gè)不同時(shí)間窗口算例驗(yàn)證上述改進(jìn)的Floyd算法。具體描述如下：某冷鮮配送中心在全天13個(gè)時(shí)間窗口內(nèi)分別向目標(biāo)客戶1和客戶2配送訂單，要求訂單以最短時(shí)間送達(dá)客戶，配送車輛從配送中心出發(fā)，訂單送達(dá)后返回配送中心，配送過(guò)程中期望理想安全速度為30 km/h。根據(jù)產(chǎn)品配送要求，利用改進(jìn)后的Floyd算法對(duì)問(wèn)題進(jìn)行求解，得到的配送時(shí)間和最優(yōu)路徑如表2所示。

4結(jié)論

在城市路網(wǎng)中，冷鮮產(chǎn)品的配送過(guò)程很容易受到交通路況的影響，從而延誤訂單配送。本研究在一般路徑規(guī)劃算法的基礎(chǔ)上，充分考慮了實(shí)際道路狀況，提出了基于實(shí)時(shí)交通路況信息的同城生鮮產(chǎn)品配送路徑優(yōu)化方法，建立了以最短配送時(shí)間為目標(biāo)函數(shù)的數(shù)學(xué)模型，結(jié)合灰色關(guān)聯(lián)分析法建立路況矩陣對(duì)Floyd算法進(jìn)行了改進(jìn)，并用實(shí)際算例對(duì)改進(jìn)算法

進(jìn)行了驗(yàn)證。通過(guò)驗(yàn)證結(jié)果分析了實(shí)時(shí)配送路徑和配送時(shí)間

的變化情況，并與靜態(tài)條件下的配送時(shí)間進(jìn)行了比較。結(jié)果表明，在路況擁堵高發(fā)時(shí)間段內(nèi)，動(dòng)態(tài)尋優(yōu)方法的物流配送時(shí)間更短、效率更高，從而驗(yàn)證了該算法的優(yōu)化效果。

參考文獻(xiàn)：

[1]Zhang G M，Habenicht W，Spiess W E L. Improving the structure of deep frozen and chilled food chain with tabu search procedure[J]. Journal of Food Engineering，2003，60（1）：67-79.

[2]Arbelaitz O，Rodriguez C. Comparison of systems based on evolutionary search and simulated annealing to solve the VRPTW problem[J]. International Journal of Computational Intelligence and Applications，2004，4（1）：27-39.

[3]Ahumada O，Villalobos J R. Operational model for planning the harvest and distribution of perishable agricultural products[J]. International Journal of Production Economics，2011，133（2）：677-687.

[4]Ahumada O，Villalobos J R，Mason A N. Tactical planning of the production and distribution of fresh agricultural products under uncertainty[J]. Agricultural Systems，2012，112（13）：17-26.

[5]楊丹婷. 冷鏈物流配送路徑優(yōu)化研究[D]. 大連：大連海事大學(xué)，2014.

[6]繆小紅，周新年，林森，等. 第3方冷鏈物流配送路徑優(yōu)化研究[J]. 運(yùn)籌與管理，2011，20（4）：32-38.

[7]楊艷群，梁鈺，鄭新夷，等. 城市道路交叉口交通設(shè)施有效性評(píng)價(jià)[J]. 福州大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，43（4）：530-535.

[8]劉思峰，黨耀國(guó)，方志耕. 灰色系統(tǒng)理論及其應(yīng)用[M]. 開封：河南大學(xué)出版社，1991.

[9]張曉明，王芳，金玉雪，等. 基于灰關(guān)聯(lián)和靈敏度的BP網(wǎng)絡(luò)隱含層結(jié)構(gòu)優(yōu)化[J]. 計(jì)算機(jī)測(cè)量與控制，2014，22（9）：3055-3057，3080.張穎，周金坤. 多位一體農(nóng)業(yè)科研院所基礎(chǔ)設(shè)施使用與維護(hù)的管理機(jī)制思考——以江蘇省農(nóng)業(yè)科學(xué)院為例[J]. 江蘇農(nóng)業(yè)科學(xué)，2017，45（17）：295-297.endprint