實時路況下同城生鮮農產品配送路徑優化

賈現召+戚恒亮+賈其蘇+李亞琴+黃自治

摘要：在同城生鮮產品配送過程中，配送時間可能會受到路況信息的影響，因此針對生鮮訂單要及時送達客戶的問題，結合實時交通信息，對同城冷鏈物流配送路徑優化進行研究。根據問題的描述，從配送區域的實時路況信息出發，提出了基于實時交通路況信息的同城生鮮產品配送路徑優化方法，建立了最優路徑的數學模型，采用灰色關聯度建立路況矩陣，應用改進Floyd算法對算例進行求解和分析，通過可視化界面將路徑結果輸出，并將在不同時間窗內的配送時間與靜態算法下的配送時間進行比較。結果表明，結合實時交通信息的動態路徑尋優方法，在路況擁堵高發時間段內，物流配送時間更短、效率更高。

關鍵詞：生鮮農產品；配送；路徑規劃；Floyd算法；實時交通；優化模型

中圖分類號： S126；F252.14文獻標志碼： A文章編號：1002-1302（2017）17-0292-03

收稿日期：2016-04-18

基金項目：國家科技支撐計劃（編號：2011BAF09B01-06）；河南省自然科學基金（編號：152300410083）。

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

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

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

1問題描述與建模

1.1同城生鮮產品配送問題描述

本研究的同城生鮮產品配送問題可以描述為1個配送中心具有多輛配送車，每輛配送車從配送中心出發，以最短的時間為指定的客戶配貨，配送結束后返回配送中心。

1.2模型假設

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

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

（3）配送車必須從配送中心出發，配送結束后返回配送中心；

（4）目標客戶的需求量、位置信息已知，配送過程中無訂單增加或退訂；

（5）目標客戶的需求量小于配送車的最大運輸量；

（6）每個目標客戶的訂單只能由1輛配送車配送；

（7）每個目標客戶的配送距離都小于配送車的最大運輸距離。

1.3同城生鮮產品配送模型的建立

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

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

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

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

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

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

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

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

式中：Pij為配送車輛經過（pi，pj）路段時的實際車流量；λij為（pi，pj）路段的日常擁堵系數；dij為（pi，pj）路段的長度；vij為配送車輛在（pi，pj）路段時的平均行駛速度；v0為理想配送車速。

1.3.3交通管制時間當配送車輛經過的路段出現突發事件進行交通管制時，則認為車輛通過該路段的時間為無窮長，為了節約配送時間，車輛改變行駛路線；反之，則為0。交通管制時間可表示為

T3=tij。（4）

式中：tij為變量，當（pi，pj）路段出現交通管制時，tij為∞，否則為0。

1.3.4道路交叉口通過時間不同類型的道路交叉口、路口長度、車輛流的平均到達率均會對車輛的路口通行時間造成影響。道路交叉口通過時間可表示為

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

式中：β為不同類型的道路交叉口通行系數；θijk為（pi，pj）路段內的車輛流到達下一個路口k的平均到達率；dijk為緊接（pi，pj）路段的交叉口k的長度；vijk為車輛在交叉口的通行速度。

1.4同城生鮮車輛配送路徑優化模型

綜上所述，生鮮車輛配送路徑優化模型目標函數如下：

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）約束配送路徑數不超過配送中心車輛總數；公式（8）約束配送車輛的起點和終點均為配送中心；公式（9）、公式（10）約束每個目標訂單只能由1輛配送車配送1次。

2基于實時路況信息改進的Floyd算法

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

2.1構建路況評價指標體系

本研究采用定量與定性分析相結合的方法對實時交通路況進行評價。根據城市道路交通的特點，通過實證分析和問卷調查建立了如表1所示的路況評價指標體系。在該體系中可通過專家評分法來確定定性指標權重，而定量指標則可通過上述相應的公式進行求解計算[7]。

2.2求解路況灰色關聯矩陣

對于道路交通狀況的實時變化態勢，采用灰色關聯分析法可以對其發展程度進行量化的度量，較好地彌補傳統評價分析方法的不足[8]。利用灰色關聯分析法分析實時路況變化，求解灰色關聯矩陣的步驟如下[9]：

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

（2）對各路況指標權重進行初值化處理；

（3）求參考序列和比較序列的灰色關聯系數；

（4）求各指標間的關聯度；（5）排關聯序，得到灰色關聯矩陣。

各個路段間的路況關聯程度不僅僅是關聯度的大小，而主要是用關聯度的大小次序來進行描述。灰色關聯矩陣由各個比較序列對各個參考序列的灰色關聯度rij（i=1，2，…，n）構成，將rij進行適當排列可得到路況灰色關聯矩陣：

R=r11r12…r1n

r21r22…r2n

rn1rn2…rnm。（11）

2.3改進Floyd算法求解最優配送路徑

根據各個路況評價指標，采用灰色關聯分析法得到路況矩陣R。以路況矩陣R作為路網的鄰接矩陣，即R=D=（rij）n×n，rij為節點vi到vj的路況權重。最優配送路徑求解步驟：

（1）輸入路況權重矩陣D0=D；

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

（3）Dn=（rnij）n×n中元素rnij就是節點vi到vj的最優路徑。

選取洛陽市某地區局部道路作為路網模型，以Visual Studio 2010作為開發環境，利用C#語言編制最優路徑可視化界面，輸出的最優路徑如圖1所示。

3算例分析

本研究給出13個不同時間窗口算例驗證上述改進的Floyd算法。具體描述如下：某冷鮮配送中心在全天13個時間窗口內分別向目標客戶1和客戶2配送訂單，要求訂單以最短時間送達客戶，配送車輛從配送中心出發，訂單送達后返回配送中心，配送過程中期望理想安全速度為30 km/h。根據產品配送要求，利用改進后的Floyd算法對問題進行求解，得到的配送時間和最優路徑如表2所示。

4結論

在城市路網中，冷鮮產品的配送過程很容易受到交通路況的影響，從而延誤訂單配送。本研究在一般路徑規劃算法的基礎上，充分考慮了實際道路狀況，提出了基于實時交通路況信息的同城生鮮產品配送路徑優化方法，建立了以最短配送時間為目標函數的數學模型，結合灰色關聯分析法建立路況矩陣對Floyd算法進行了改進，并用實際算例對改進算法

進行了驗證。通過驗證結果分析了實時配送路徑和配送時間

的變化情況，并與靜態條件下的配送時間進行了比較。結果表明，在路況擁堵高發時間段內，動態尋優方法的物流配送時間更短、效率更高，從而驗證了該算法的優化效果。

參考文獻：

[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]楊丹婷. 冷鏈物流配送路徑優化研究[D]. 大連：大連海事大學，2014.

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

[7]楊艷群，梁鈺，鄭新夷，等. 城市道路交叉口交通設施有效性評價[J]. 福州大學學報（自然科學版），2015，43（4）：530-535.

[8]劉思峰，黨耀國，方志耕. 灰色系統理論及其應用[M]. 開封：河南大學出版社，1991.

[9]張曉明，王芳，金玉雪，等. 基于灰關聯和靈敏度的BP網絡隱含層結構優化[J]. 計算機測量與控制，2014，22（9）：3055-3057，3080.張穎，周金坤. 多位一體農業科研院所基礎設施使用與維護的管理機制思考——以江蘇省農業科學院為例[J]. 江蘇農業科學，2017，45（17）：295-297.endprint