基于實(shí)時(shí)交通的城市冷鏈物流路徑優(yōu)化研究

河北大學(xué)電子信息工程學(xué)院 鄭敏靜 宗曉萍 郭 會(huì)

基于實(shí)時(shí)交通的城市冷鏈物流路徑優(yōu)化研究

河北大學(xué)電子信息工程學(xué)院 鄭敏靜 宗曉萍 郭 會(huì)

針對(duì)城市冷鏈物流路徑優(yōu)化問題，提出與實(shí)時(shí)交通狀況結(jié)合，并分步求解的方法。首先利用改進(jìn)的Dijkstra算法構(gòu)建動(dòng)態(tài)路網(wǎng)，然后構(gòu)建城市冷鏈物流路徑優(yōu)化模型，并運(yùn)用遺傳算法求解，與企業(yè)實(shí)際物流配送情況相比，成本降低了4．1%，配送效率提高了19．1%。

冷鏈物流；路徑優(yōu)化；實(shí)時(shí)交通；迪杰特斯拉算法；遺傳算法

1 引言

隨著科學(xué)技術(shù)的發(fā)展和人們現(xiàn)代生活水平的提高，人們對(duì)入口食物的品質(zhì)有了更高的要求，從而對(duì)冷鏈物流的配送也有了更高的要求。冷鏈物流是指易腐易變質(zhì)產(chǎn)品在從產(chǎn)品生產(chǎn)、加工、貯藏、運(yùn)輸、銷售最終至消費(fèi)者的各個(gè)環(huán)節(jié)始終處于符合產(chǎn)品屬性要求的溫度、濕度環(huán)境以有利于保證產(chǎn)品質(zhì)量，減少產(chǎn)品損耗，防止污染的特殊供應(yīng)鏈系統(tǒng)。冷鏈物流配送的產(chǎn)品具有易腐性，對(duì)運(yùn)輸溫度要求比較高，并且要保證運(yùn)送的時(shí)效性。

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

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

其中，交叉路口延誤時(shí)間可以從城市信息系統(tǒng)中實(shí)時(shí)獲取。城市路網(wǎng)的流暢性受交通流的影響[9]交通流量決定速度。基于此本文對(duì)基于交通的城市冷鏈物流路徑進(jìn)行了優(yōu)化研究。

2 動(dòng)態(tài)路網(wǎng)構(gòu)建

2.1 D i j k s t r a算法

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

其中，節(jié)點(diǎn)之間行駛時(shí)間取決于所經(jīng)過的路段和交叉口數(shù)。配送節(jié)點(diǎn)時(shí)間=各路段行駛時(shí)間和+經(jīng)過的路口延誤時(shí)間和。

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

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

算法步驟如下：

（1）標(biāo)記客戶需求點(diǎn)i為固定節(jié)點(diǎn)，j為目標(biāo)節(jié)點(diǎn)，剩余節(jié)點(diǎn)為未標(biāo)號(hào)節(jié)點(diǎn)。

（2）沿著i，j之間連線搜索未標(biāo)號(hào)節(jié)點(diǎn)，按照評(píng)價(jià)函數(shù)計(jì)算值從大到小的順序排列。

（3）選取評(píng)價(jià)值最小的節(jié)點(diǎn)，判定是否為目標(biāo)節(jié)點(diǎn)j，若為目標(biāo)節(jié)點(diǎn)則結(jié)束算法，若不是則轉(zhuǎn)步驟（2）繼續(xù)搜索，直到尋找出目標(biāo)節(jié)點(diǎn)j。

2.2 路網(wǎng)構(gòu)建

簡(jiǎn)單城市路網(wǎng)如圖1所示，圓圈表示交叉口，圓圈內(nèi)的數(shù)字表示交叉口延誤時(shí)間（min），弧的權(quán)重為路段行駛時(shí)間（min）。不同的時(shí)間段，交通流不同，行駛時(shí)間也不同。

圖1 簡(jiǎn)單城市路網(wǎng)

路網(wǎng)構(gòu)建過程如圖2所示。O為配送中心，ABC為配送點(diǎn)，運(yùn)用上述算法，求出任意兩點(diǎn)之間時(shí)間最短路徑，構(gòu)成物流配送網(wǎng)絡(luò)。

圖2 動(dòng)態(tài)路網(wǎng)構(gòu)建過程

3 模型構(gòu)建與求解

3.1 模型構(gòu)建

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

其中xij為決策變量，若為1，則配送車輛經(jīng)過客戶點(diǎn)（Ni，Nj），若為0，則不經(jīng)過。

約束條件為：

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

3.2 模型求解

遺傳算法是一種求解組合優(yōu)化問題的強(qiáng)大搜索方法，標(biāo)準(zhǔn)遺傳算法包括種群初始化，個(gè)體適應(yīng)度計(jì)算，選擇操作，交叉操作，變異操作，終止條件判斷操作等。

針對(duì)上述動(dòng)態(tài)冷鏈物流路徑模型，本文選用遺傳算法進(jìn)行求解[4-6]。具體算法步驟如下：

（1）隨機(jī)生成初始化種群，設(shè)置種群規(guī)模為100，染色體長(zhǎng)度為8；

（2）計(jì)算每個(gè)染色體適應(yīng)度（目標(biāo)函數(shù)的倒數(shù)）并標(biāo)記；

（3）采用Monte-Carlo選擇策略選擇N個(gè)適應(yīng)度高的染色體。

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

（5）以變異概率0.03進(jìn)行變異操作。

（6）產(chǎn)生新代種群，達(dá)到收斂代數(shù)則終止算法，否則重新進(jìn)入達(dá)到步驟2。

4 實(shí)例分析

本文結(jié)合某企業(yè)城市配送的真實(shí)路網(wǎng)情況進(jìn)行了簡(jiǎn)化處理，選取86個(gè)路網(wǎng)節(jié)點(diǎn)，經(jīng)過118條路段。該企業(yè)有一個(gè)配送中心，八個(gè)需求點(diǎn)。在matlab中用坐標(biāo)圖模擬真實(shí)配送節(jié)點(diǎn)位置。對(duì)早高峰時(shí)段（6∶30-9∶30）配送進(jìn)行了優(yōu)化仿真。

表1 需求點(diǎn)坐標(biāo)及需求量

表2 配送節(jié)點(diǎn)時(shí)間矩陣（單位：mi n）

4.1 參數(shù)設(shè)置

參數(shù)設(shè)置：?jiǎn)挝挥秃某杀?元/min，每輛車使用一次固定成本50元，l1、c1，λ1，k，n,Q,取值分別為1元/min，1.5元/min，0.003，l2為0.5元/min。

（1）各需求點(diǎn)位置坐標(biāo)、需求量見表1，其中0為配送中心位置，坐標(biāo)為（0,25）。

（2）配送節(jié)點(diǎn)實(shí)際配送時(shí)間見表2。時(shí)間矩陣經(jīng)過改進(jìn)的dijkstra算法在MATLAB中進(jìn)行計(jì)算得到。

4.2 結(jié)果分析

對(duì)所建模型，利用上述遺傳算法進(jìn)行求解，實(shí)驗(yàn)結(jié)果表明對(duì)需求點(diǎn)的配送需要兩輛車，配送路線如圖3、圖4所示，本文基于實(shí)時(shí)交通的配送情況和企業(yè)實(shí)際配送情況見表3、表4。

圖3 基于實(shí)時(shí)交通的最優(yōu)配送路線

圖4 企業(yè)傳統(tǒng)配送路線

表3 基于實(shí)時(shí)交通的配送情況

表4 企業(yè)傳統(tǒng)配送情況

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

5 結(jié)論

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

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

[2]王一松,王直杰．基于實(shí)時(shí)交通信息的路徑規(guī)劃算法研究[J]．計(jì)算機(jī)與現(xiàn)代化,2013：52-55．

[3]李亞南．基于車聯(lián)網(wǎng)的冷鏈物流配送路徑優(yōu)化研究[D]．長(zhǎng)安大學(xué),2016．

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

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

[6]周詠．冷鏈物流同時(shí)送取貨車輛路徑優(yōu)化[J]．?dāng)?shù)學(xué)實(shí)踐與認(rèn)識(shí),2016,46(20)：18-26．

[7]袁彬,劉建勝,錢丹．一種基于改進(jìn)Dijkstra的物流網(wǎng)絡(luò)路徑優(yōu)化算法分析[J]．制造業(yè)自動(dòng)化,2014：86-89．

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

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