基于實時交通的城市冷鏈物流路徑優化研究

河北大學電子信息工程學院 鄭敏靜 宗曉萍 郭 會

基于實時交通的城市冷鏈物流路徑優化研究

河北大學電子信息工程學院 鄭敏靜 宗曉萍 郭 會

針對城市冷鏈物流路徑優化問題，提出與實時交通狀況結合，并分步求解的方法。首先利用改進的Dijkstra算法構建動態路網，然后構建城市冷鏈物流路徑優化模型，并運用遺傳算法求解，與企業實際物流配送情況相比，成本降低了4．1%，配送效率提高了19．1%。

冷鏈物流；路徑優化；實時交通；迪杰特斯拉算法；遺傳算法

1 引言

隨著科學技術的發展和人們現代生活水平的提高，人們對入口食物的品質有了更高的要求，從而對冷鏈物流的配送也有了更高的要求。冷鏈物流是指易腐易變質產品在從產品生產、加工、貯藏、運輸、銷售最終至消費者的各個環節始終處于符合產品屬性要求的溫度、濕度環境以有利于保證產品質量，減少產品損耗，防止污染的特殊供應鏈系統。冷鏈物流配送的產品具有易腐性，對運輸溫度要求比較高，并且要保證運送的時效性。

冷鏈物流配送路徑問題是多目標最優解問題，受車載重量、配送產品數量、產品種類等諸多因素影響。目前我國對于冷鏈物流配送問題的研究主要集中在對靜態車輛路徑問題的優化，但是在城市實際路網中影響車輛行駛的因素有很多，例如：天氣因素、交通流量、高峰期、交通事故、路段限行等。如果冷鏈配送不考慮實時交通狀況，車輛很有可能會陷入交通擁堵使配送時間延長，配送成本增加。顯然需要考慮交通狀況對配送的影響，避免單純考慮速度與距離而帶來的偏差，降低冷鏈物流的配送成本。

傳統物流配送道路是靜態的，配送車輛從配送中心出發，經過各配送點后返回到配送中心，通常兩點距離都是歐式距離，未考慮真實路網和交通狀況。城市路網復雜，有成百上千路段和交叉口構成，對路徑規劃影響較大的是交通流和交叉路口延誤時間。城市冷鏈物流配送最優路徑規劃與交通因素結合起來，才比較貼近實際，將交通路網抽象成帶權圖，用圖論方法進行分析。本文將一天中交通流量變化的情況分為H個時段，假設每個時段內，路段交通流量大致相同，則配送車輛在該時間段通過某路段的行駛時間保持不變。

其中，交叉路口延誤時間可以從城市信息系統中實時獲取。城市路網的流暢性受交通流的影響[9]交通流量決定速度。基于此本文對基于交通的城市冷鏈物流路徑進行了優化研究。

2 動態路網構建

2.1 D i j k s t r a算法

Dijkstra算法[7]是經典的最短路算法，用于計算一個節點到其他所有節點的最短路徑。缺點是計算速度慢。在普通dijkstra算法中，弧以距離為權重，節點沒有權重。在城市冷鏈物流配送中要求行駛時間最短，存在交叉口延誤。因此針對dijkstra作了兩方面改進：一方面以路段行駛時間作為權重，并給節點賦予權重，當作新增路段權重弧來處理；另一方面是設立評價函數h(n)=t(n)+b(n),其中t(n)是由任意節點n到固定節點的時間換算而來，b(n)是任意節點n到顧客需求點距離換算而來。評價函數最小的節點為固定節點，通過比較評價節點，找到最短的路徑。

其中，節點之間行駛時間取決于所經過的路段和交叉口數。配送節點時間=各路段行駛時間和+經過的路口延誤時間和。

每一路段行駛速度根據式(1)計算得出，行駛時間根據式(2)計算。

Lab為相鄰節點之間的長度，a1、a2、a3為回歸參數，取值為1.55、1.88、7.00。v0為路段零流量時的行駛車速取值為40km/h，q為實時交通流量，c為路段的基本通行能力，取值為900pcu/h。

算法步驟如下：

（1）標記客戶需求點i為固定節點，j為目標節點，剩余節點為未標號節點。

（2）沿著i，j之間連線搜索未標號節點，按照評價函數計算值從大到小的順序排列。

（3）選取評價值最小的節點，判定是否為目標節點j，若為目標節點則結束算法，若不是則轉步驟（2）繼續搜索，直到尋找出目標節點j。

2.2 路網構建

簡單城市路網如圖1所示，圓圈表示交叉口，圓圈內的數字表示交叉口延誤時間（min），弧的權重為路段行駛時間（min）。不同的時間段，交通流不同，行駛時間也不同。

圖1 簡單城市路網

路網構建過程如圖2所示。O為配送中心，ABC為配送點，運用上述算法，求出任意兩點之間時間最短路徑，構成物流配送網絡。

圖2 動態路網構建過程

3 模型構建與求解

3.1 模型構建

在物流配送中，車輛從配送中心裝載一定量的貨物對客戶進行服務，完成后返回配送中心[5]。配送須保證每個客戶被服務一次，車輛載重不能超過額定載重，不考慮時間窗問題，依賴于行駛時間構建以總成本為目標函數的模型（總成本包括運輸成本、能耗成本、貨損成本）。假設企業車輛集合K={1,2,3,…,m}，客戶集合N={1,……,n}，車輛額定裝載量為Q，客戶點i的需求量為qi，從客戶i到j的行駛時間為tij，單位時間耗油量為c1，單位時間貨損系數為λ1，運送單位時間制冷能耗為l1，則配送總成本目標函數為：

其中xij為決策變量，若為1，則配送車輛經過客戶點（Ni，Nj），若為0，則不經過。

約束條件為：

(3)式表示每輛車裝的貨物不能超過額定裝載量；(4)式表示每個客戶只能由一輛車服務；(5)式表示每個客戶點都有車輛配送；(6)表示所用車輛數不能超過配送中心車輛數。

3.2 模型求解

遺傳算法是一種求解組合優化問題的強大搜索方法，標準遺傳算法包括種群初始化，個體適應度計算，選擇操作，交叉操作，變異操作，終止條件判斷操作等。

針對上述動態冷鏈物流路徑模型，本文選用遺傳算法進行求解[4-6]。具體算法步驟如下：

（1）隨機生成初始化種群，設置種群規模為100，染色體長度為8；

（2）計算每個染色體適應度（目標函數的倒數）并標記；

（3）采用Monte-Carlo選擇策略選擇N個適應度高的染色體。

（4）采用部分匹配交叉法，以交叉概率0.7選擇染色體進行交叉操作生成新個體。

（5）以變異概率0.03進行變異操作。

（6）產生新代種群，達到收斂代數則終止算法，否則重新進入達到步驟2。

4 實例分析

本文結合某企業城市配送的真實路網情況進行了簡化處理，選取86個路網節點，經過118條路段。該企業有一個配送中心，八個需求點。在matlab中用坐標圖模擬真實配送節點位置。對早高峰時段（6∶30-9∶30）配送進行了優化仿真。

表1 需求點坐標及需求量

表2 配送節點時間矩陣（單位：mi n）

4.1 參數設置

參數設置：單位油耗成本1元/min，每輛車使用一次固定成本50元，l1、c1，λ1，k，n,Q,取值分別為1元/min，1.5元/min，0.003，l2為0.5元/min。

（1）各需求點位置坐標、需求量見表1，其中0為配送中心位置，坐標為（0,25）。

（2）配送節點實際配送時間見表2。時間矩陣經過改進的dijkstra算法在MATLAB中進行計算得到。

4.2 結果分析

對所建模型，利用上述遺傳算法進行求解，實驗結果表明對需求點的配送需要兩輛車，配送路線如圖3、圖4所示，本文基于實時交通的配送情況和企業實際配送情況見表3、表4。

圖3 基于實時交通的最優配送路線

圖4 企業傳統配送路線

表3 基于實時交通的配送情況

表4 企業傳統配送情況

由實驗結果可以看出，基于實時交通配送路徑與企業實際配送路線不同，行駛距離、總配送成本、配送時間都不相同，企業時間配送距離為144km、配送時間為164min，總成本為502.5元，基于實時交通信息配送距離為153.8km、配送時間132.6min、總配送成本為482.7元，優化后，雖然配送距離增加，但配送成本降低了4.1%，配送效率提高了19.1%。

5 結論

本文提出將冷鏈物流配送與實時交通將結合的模型，實驗證明，基于實時交通的配送，更貼近實際具有可行性，并且有效的規避了擁堵，減少了配送成本，提高了配送效率。今后將進一步研究實時交通狀況下同時送取貨物的配送路徑。

[1]蘭輝,何琴飛,邊展,靳志宏．考慮道路通行狀況的冷鏈物流配送路徑優化[J]．大連海事大學學報,2015：67-74．

[2]王一松,王直杰．基于實時交通信息的路徑規劃算法研究[J]．計算機與現代化,2013：52-55．

[3]李亞南．基于車聯網的冷鏈物流配送路徑優化研究[D]．長安大學,2016．

[4]唐坤．車輛路徑問題中的遺傳算法設計[J]．東華大學學報(自然科學版),2002,28(1)：66-70．

[5]宗曉萍,劉森,王培光,路瑞寬．基于企業冷鏈物流MAS的車輛調度問題研究[J]．物流技術,2014,33(12)：253-255．

[6]周詠．冷鏈物流同時送取貨車輛路徑優化[J]．數學實踐與認識,2016,46(20)：18-26．

[7]袁彬,劉建勝,錢丹．一種基于改進Dijkstra的物流網絡路徑優化算法分析[J]．制造業自動化,2014：86-89．

[8]鄧麗君．基于客戶滿意度的物流配送車輛調度優化模型與算法研究[D]．北京：北京交通大學,2012．

鄭敏靜（1992—），女，河北石家莊人，研究生，研究方向：智能物流。