基于復(fù)雜網(wǎng)絡(luò)和實(shí)際交通數(shù)據(jù)的城市冷鏈物流末端配送規(guī)劃

王正國(guó) 陳 升* 熊一凡

(武漢理工大學(xué)交通與物流工程學(xué)院1) 武漢 430063) (武漢烽火國(guó)際技術(shù)有限責(zé)任公司2) 武漢 430074)

0 引 言

冷鏈產(chǎn)品具有易腐敗、難保存等特點(diǎn)，導(dǎo)致冷鏈物流末端配送對(duì)時(shí)效性要求更高，這也是我國(guó)冷鏈物流末端配送成本配送居高不下的主要原因．城市冷鏈末端配送通道為實(shí)際的路網(wǎng)，復(fù)雜的城市交通狀況對(duì)配送造成了很大影響．因此，考慮交通路網(wǎng)的影響對(duì)配送區(qū)域進(jìn)行合理規(guī)劃對(duì)提高冷鏈配送效率，降低配送成本具有重要意義．

針對(duì)配送區(qū)域劃分問(wèn)題，何夢(mèng)軍等[1]考慮到配送點(diǎn)之間的關(guān)聯(lián)因素，采用改進(jìn)的吸引子傳播聚類算法實(shí)現(xiàn)對(duì)配送區(qū)域的劃分．房慶軍等[2]構(gòu)建生鮮冷鏈配送“區(qū)域劃分+區(qū)域調(diào)整”兩階段模型，利用k均值算法以最短配送時(shí)間為聚類準(zhǔn)則進(jìn)行初始區(qū)域劃分，引入均衡載貨指標(biāo)，調(diào)整初始劃分區(qū)域．楊雯婷等[3]基于泰森多邊形理論，以某一地區(qū)現(xiàn)役油庫(kù)為例，對(duì)該地區(qū)現(xiàn)有油庫(kù)的配送區(qū)域進(jìn)行重新劃分，縮短了配送距離，提高了配送效率．吳亮然等[4]通過(guò)配送區(qū)域間的拓?fù)潢P(guān)系生成區(qū)域協(xié)同配送網(wǎng)絡(luò)，進(jìn)而依據(jù)一次配送中的有貨區(qū)域信息生成車輛初始配送線路，并對(duì)具有相鄰關(guān)系的線路進(jìn)行配送線路間調(diào)整，從而形成最終的車輛途徑配送區(qū)域的配送線路．上述文獻(xiàn)未能考慮到在城市末端配送過(guò)程中復(fù)雜的交通路況對(duì)配送造成的影響．李玉鵬等[5]考慮了路況條件、道路條件和停車難易等因素并對(duì)其進(jìn)行了權(quán)重分析，構(gòu)建了現(xiàn)實(shí)生活中物流配送的復(fù)雜網(wǎng)絡(luò)模型，然后基于兩階段的LinkRank社區(qū)發(fā)現(xiàn)算法實(shí)現(xiàn)了物流配送區(qū)域的劃分．周程等[6]考慮了車輛行駛速度與實(shí)時(shí)路況帶來(lái)的影響，建立配送優(yōu)化決策模型，更貼近現(xiàn)實(shí)．趙邦磊等[7]研究了不同天氣狀況、不同時(shí)間段道路擁堵情況等因素對(duì)行駛速度產(chǎn)生的影響，建立車速特征影響模型，構(gòu)建冷鏈物流配送模型．

考慮到司機(jī)常根據(jù)地圖軟件導(dǎo)航路線行駛，文中利用高德地圖獲取客戶點(diǎn)間雙向?qū)嶋H通行時(shí)間來(lái)描述節(jié)點(diǎn)間物流聯(lián)系，構(gòu)建有向的城市配送復(fù)雜網(wǎng)絡(luò)模型，利用社區(qū)發(fā)現(xiàn)法進(jìn)行配送區(qū)域劃分，提高冷鏈物流末端配送網(wǎng)絡(luò)規(guī)劃的合理性．

1 基于復(fù)雜網(wǎng)絡(luò)的冷鏈配送區(qū)域劃分

1.1 復(fù)雜網(wǎng)絡(luò)

復(fù)雜網(wǎng)絡(luò)實(shí)質(zhì)上是由網(wǎng)絡(luò)中所有的頂點(diǎn)V和所有頂點(diǎn)聯(lián)系的邊所構(gòu)建成的圖形．復(fù)雜網(wǎng)路可用鄰接矩陣A=(aij)表示．其中aij的取值可以表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間是否存在連接關(guān)系，對(duì)于無(wú)權(quán)網(wǎng)絡(luò)，節(jié)點(diǎn)間存在連接則取值為1，否則，取值為0．對(duì)于有權(quán)網(wǎng)絡(luò)，可以將對(duì)節(jié)點(diǎn)間連接關(guān)系的評(píng)價(jià)值作為權(quán)重．

一個(gè)復(fù)雜網(wǎng)絡(luò)可由若干個(gè)“社區(qū)”構(gòu)成，社區(qū)內(nèi)部的結(jié)點(diǎn)間的連接相對(duì)緊密，而社區(qū)之間的節(jié)點(diǎn)間連接相對(duì)稀疏．圖1為一帶有社區(qū)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)．

圖1 帶有社區(qū)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)

社區(qū)發(fā)現(xiàn)是指尋找網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的過(guò)程，社區(qū)發(fā)現(xiàn)結(jié)果的好壞可用模塊度衡量．對(duì)于有向帶權(quán)網(wǎng)絡(luò)圖，模塊度的計(jì)算公式為

(1)

1.2 帶社區(qū)結(jié)構(gòu)復(fù)雜網(wǎng)絡(luò)模型的建立

構(gòu)建合理的配送網(wǎng)絡(luò)模型是進(jìn)行冷鏈物流末端配送區(qū)域劃分的前提．建立社區(qū)結(jié)構(gòu)網(wǎng)絡(luò)模型的需要明確網(wǎng)絡(luò)中的節(jié)點(diǎn)、邊以及邊的方向和權(quán)重，針對(duì)社區(qū)結(jié)構(gòu)網(wǎng)絡(luò)模型的建立提出三點(diǎn)轉(zhuǎn)化規(guī)則．

1) 將有冷鏈需求的社區(qū)轉(zhuǎn)化為網(wǎng)絡(luò)模型中的節(jié)點(diǎn)．

2) 將社區(qū)之間所具有的物流關(guān)系轉(zhuǎn)化為社區(qū)結(jié)構(gòu)網(wǎng)絡(luò)之中有方向有權(quán)重的邊，即A社區(qū)到B社區(qū)與B社區(qū)到A社區(qū)是兩條方向相反的邊．

3) 將社區(qū)間通行時(shí)間的倒數(shù)作為邊的權(quán)重值．社區(qū)間的通行時(shí)間主要會(huì)受到道路等級(jí)、長(zhǎng)度、交通狀況、車輛行駛速度等主要因素的影響．

若網(wǎng)絡(luò)模型中存在由社區(qū)i指向社區(qū)j的邊，由于從社區(qū)i到社區(qū)j的通行路線中存在多個(gè)路段，通行時(shí)間的計(jì)算方法為

(2)

式中：tij為從i到j(luò)間的通行時(shí)間；dk為第k條路段的長(zhǎng)度；ck為路段k的道路等級(jí)；vck為車輛在路段k暢通情況下的行駛速度；qk為路段k的擁堵情況對(duì)車輛行駛速度的影響系數(shù)；v為車輛最大行駛速度.

則邊的權(quán)重Wij計(jì)算公式為

Wij=1/tij

(3)

考慮到地圖軟件工具擁有海量道路網(wǎng)絡(luò)數(shù)據(jù)，能全面考慮到上述因素的影響來(lái)估測(cè)兩節(jié)點(diǎn)間最短通行路徑與通行時(shí)間，因此利用地圖軟件獲取節(jié)點(diǎn)間的通行時(shí)間作為通行時(shí)間數(shù)據(jù)來(lái)源．

1.3 帶社區(qū)結(jié)構(gòu)復(fù)雜網(wǎng)絡(luò)的劃分

建立了社區(qū)結(jié)構(gòu)網(wǎng)絡(luò)模型之后，需要挖掘網(wǎng)絡(luò)模型中所存在的社區(qū)結(jié)構(gòu)．Louvain社區(qū)發(fā)現(xiàn)算法利用貪心策略將節(jié)點(diǎn)劃入與其具有連接關(guān)系的節(jié)點(diǎn)所在的社區(qū)，從而使模塊度增量最大，優(yōu)化整體網(wǎng)絡(luò)模塊度[8]．

算法的流程可以分為兩個(gè)階段．首先假設(shè)存在一個(gè)加權(quán)網(wǎng)絡(luò)，具有n個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)作為一個(gè)獨(dú)立社區(qū)．將節(jié)點(diǎn)i劃入其相鄰節(jié)點(diǎn)所在社區(qū)并計(jì)算此次移動(dòng)產(chǎn)生的模塊度增量ΔQ，如果最大的模塊度增量ΔQ大于0，則將其加入對(duì)應(yīng)社區(qū)，否則，不進(jìn)行移動(dòng)．重復(fù)該過(guò)程直到所有節(jié)點(diǎn)都不再發(fā)生移動(dòng)．

在有權(quán)有向網(wǎng)絡(luò)中，模塊度增量ΔQ的計(jì)算公式為

(4)

算法第二階段的主要任務(wù)是重構(gòu)整個(gè)網(wǎng)絡(luò)，將第一階段發(fā)現(xiàn)的社區(qū)作為新的節(jié)點(diǎn)，新節(jié)點(diǎn)繼承社區(qū)中所包含節(jié)點(diǎn)與外部節(jié)點(diǎn)的連接關(guān)系，出入度等于該社區(qū)中所有節(jié)點(diǎn)的出入度之和．網(wǎng)絡(luò)重構(gòu)結(jié)束后，重復(fù)第一階段過(guò)程至得出最優(yōu)的社區(qū)結(jié)構(gòu)．步驟如下.

步驟1每個(gè)節(jié)點(diǎn)作為一個(gè)獨(dú)立社區(qū)，二者編號(hào)相同．

步驟2對(duì)于節(jié)點(diǎn)i，計(jì)算將其劃入至其相鄰節(jié)點(diǎn)所在社區(qū)時(shí)的模塊度增量ΔQ，記錄ΔQ最大時(shí)所對(duì)應(yīng)的社區(qū)編號(hào)，如果max(ΔQ)>0，則把節(jié)點(diǎn)i劃入該社區(qū)，否則不進(jìn)行移動(dòng)．

步驟3重復(fù)步驟2，直到所有節(jié)點(diǎn)不再發(fā)生移動(dòng)．

步驟4重構(gòu)新圖，將每個(gè)社區(qū)壓縮為一個(gè)新的節(jié)點(diǎn)，新節(jié)點(diǎn)繼承社區(qū)內(nèi)部節(jié)點(diǎn)與外部節(jié)點(diǎn)間的連接關(guān)系，其屬性值為內(nèi)部節(jié)點(diǎn)屬性值之和．

步驟5重復(fù)步驟2～步驟4,直到網(wǎng)絡(luò)的模塊度不再發(fā)生變化．

2 基于復(fù)雜網(wǎng)絡(luò)的冷鏈配送路徑模型建立

2.1 問(wèn)題描述

冷鏈末端配送中的網(wǎng)絡(luò)節(jié)點(diǎn)有兩種屬性：配送站點(diǎn)及社區(qū)．上一節(jié)利用社區(qū)發(fā)現(xiàn)法對(duì)網(wǎng)絡(luò)模型進(jìn)行了劃分，解決了末端配送網(wǎng)絡(luò)區(qū)域劃分問(wèn)題．在配送區(qū)域劃分已經(jīng)完成的情況下，現(xiàn)需從備選配送站點(diǎn)中選出與劃分出的區(qū)域數(shù)量相等的配送站點(diǎn)，并確定每個(gè)區(qū)域?qū)?yīng)的末端配送站點(diǎn)以及每個(gè)配送站點(diǎn)服務(wù)該區(qū)域所有社區(qū)時(shí)所應(yīng)該安排的車輛與車輛的配送路徑，驗(yàn)證所提區(qū)域劃分方案的有效性．

2.2 模型假設(shè)

1) 已知各個(gè)配送站點(diǎn)的地理位置，從現(xiàn)有配送站點(diǎn)中選取備選配送站點(diǎn)，不另外新建配送站點(diǎn)．

2) 各個(gè)配送站點(diǎn)的訂單處理能力相同．

3) 僅考慮單一冷鏈產(chǎn)品需求的配送．

4) 已知社區(qū)點(diǎn)地理坐標(biāo)、需求量，以及配送時(shí)間窗．

5) 每個(gè)配送區(qū)域都由一個(gè)固定的配送站點(diǎn)進(jìn)行服務(wù)，配送站點(diǎn)不進(jìn)行跨區(qū)服務(wù)，社區(qū)的配送需求要一次完成，不能拆分．

6) 利用高德地圖大數(shù)據(jù)獲取網(wǎng)絡(luò)中兩點(diǎn)間的行駛路線，兩點(diǎn)間路線可能因起始點(diǎn)不同而發(fā)生變化．

7) 車輛行駛路線是固定的，不能中途更改．

8) 配送時(shí)冷鏈產(chǎn)品的變質(zhì)只與配送時(shí)間相關(guān)．

2.3 模型符號(hào)

2.4 優(yōu)化目標(biāo)

城市冷鏈物流末端配送成本主要包括固定成本，運(yùn)輸成本以及貨損成本，各成本要素如下.

1) 固定成本C1主要包括車輛的折舊、配送員的工資以及與運(yùn)輸相關(guān)的固定損耗，配送過(guò)程產(chǎn)生的固定成本C1為

(5)

2) 運(yùn)輸成本C2車輛的運(yùn)輸成本與配送車輛運(yùn)輸時(shí)間成正比．車輛的運(yùn)輸成本C2為

(6)

3) 貨損成本C3根據(jù)“3T”理論，同一冷鏈產(chǎn)品的變質(zhì)率主要受溫度和時(shí)間的影響，因此，假設(shè)在溫度恒定時(shí)，同一冷鏈產(chǎn)品變質(zhì)率只與配送時(shí)長(zhǎng)有關(guān)，本文中冷鏈品的變質(zhì)函數(shù)為

O(t)=λO0e-ρt

(7)

式中：O(t)為冷鏈產(chǎn)品在經(jīng)過(guò)t時(shí)間后的品質(zhì)；O0為冷鏈產(chǎn)品的初始品質(zhì)；λ為冷鏈產(chǎn)品常數(shù)值，與保溫箱中的溫度有關(guān)；ρ為冷鏈產(chǎn)品對(duì)于時(shí)間的敏感系數(shù)．則貨損成本為

(8)

4) 時(shí)間懲罰成本C4由于冷鏈產(chǎn)品具有易腐性，客戶對(duì)收貨時(shí)間要求更嚴(yán)格，配送車輛需在規(guī)定時(shí)間窗內(nèi)到達(dá)，但是由于道路擁堵、調(diào)度失誤等因素的影響，配送車輛難以在規(guī)定的時(shí)間段內(nèi)送達(dá)，對(duì)此予以一定懲罰，冷藏車輛配送過(guò)程中時(shí)間窗懲罰成本為

(9)

2.5 模型構(gòu)建

minC=C1+C2+C3+C4

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

式(10)為模型目標(biāo)函數(shù)，使網(wǎng)絡(luò)總成本最低；式(11)～式(12)為配送站點(diǎn)與配送區(qū)域是一一對(duì)應(yīng)的；式(13)為車輛必須從站點(diǎn)出發(fā)，完成任務(wù)后返回該站點(diǎn)；式(14)為配送車輛只為固定站點(diǎn)服務(wù)；式(15)為一個(gè)社區(qū)只能被一輛車服務(wù)一次；式(16)萬(wàn)車輛必須從進(jìn)入的節(jié)點(diǎn)離開(kāi)；式(17)為車輛不能超載．

3 案例分析

文中以SF公司在M地區(qū)城市冷鏈物流末端配送網(wǎng)絡(luò)為例展開(kāi)研究．假設(shè)只考慮單一冷鏈商品的需求，針對(duì)M區(qū)有冷鏈配送需求的67個(gè)社區(qū)建立社區(qū)網(wǎng)絡(luò)模型，運(yùn)用louvain社區(qū)發(fā)現(xiàn)算法實(shí)現(xiàn)社區(qū)網(wǎng)絡(luò)模型的劃分，得到配送區(qū)域劃分方案．為驗(yàn)證本文所提方案的有效性建立配送優(yōu)化數(shù)學(xué)模型，分別基于SF公司原始配送區(qū)域劃分方案和本文所求方案利用遺傳算法求解，比較兩種方案下配送成本．利用網(wǎng)絡(luò)爬蟲(chóng)技術(shù)[9]對(duì)高德地圖進(jìn)行社區(qū)地理位置以及社區(qū)間通行時(shí)間等數(shù)據(jù)信息的獲?。?7個(gè)社區(qū)的實(shí)際位置分布見(jiàn)圖2．

圖2 社區(qū)分布圖

3.1 相關(guān)數(shù)據(jù)

圖2中各社區(qū)點(diǎn)經(jīng)緯度數(shù)據(jù)可通過(guò)高德地圖獲取，相關(guān)數(shù)據(jù)見(jiàn)表1．

表1 社區(qū)點(diǎn)相關(guān)數(shù)據(jù)

3.2 相關(guān)參數(shù)含義及數(shù)值

f為車輛固定成本，80元/輛；c為車輛單位時(shí)間運(yùn)輸成本，0.5元/min；P為冷鏈產(chǎn)品單價(jià)，20元/件；λ為冷鏈品常數(shù)，0.95；ρ為冷鏈品對(duì)時(shí)間的敏感系數(shù)，0.01；Qk為車輛最大容量約束，30件；tc為時(shí)間懲罰，5元．

由高德地圖大數(shù)據(jù)可得個(gè)節(jié)點(diǎn)間通行時(shí)間，節(jié)點(diǎn)間通行時(shí)間見(jiàn)表2．

表2 節(jié)點(diǎn)間通行時(shí)間 單位：min

3.3 問(wèn)題求解

3.3.1配送區(qū)域的劃分

由高德地圖大數(shù)據(jù)可獲得各社區(qū)點(diǎn)間最短通行時(shí)間，根據(jù)式(3)計(jì)算各邊所占權(quán)重構(gòu)建網(wǎng)絡(luò)模型，基于M地區(qū)的社區(qū)網(wǎng)絡(luò)模型，運(yùn)用Louvain社區(qū)發(fā)現(xiàn)算法對(duì)該網(wǎng)絡(luò)模型進(jìn)行社區(qū)發(fā)現(xiàn)．配送區(qū)域劃分方案見(jiàn)表3．

表3 配送區(qū)域劃分方案

在SF公司官網(wǎng)上可以查得該地區(qū)已有的配送站點(diǎn)及原始配送區(qū)域劃分方案見(jiàn)表4．

表4 原始配送區(qū)域劃分方案

由表4可知：SF公司原有配送站點(diǎn)中，站點(diǎn)1、2、4負(fù)責(zé)社區(qū)點(diǎn)最多且分別位于文中方法得出的三個(gè)配送區(qū)域中，因此選取這三個(gè)原有站點(diǎn)作為求解得到的配送區(qū)域的配送站點(diǎn)．

3.3.2模型求解

基于配送區(qū)域劃分結(jié)果以及SF公司原始配送區(qū)域劃分方案，利用遺傳算法對(duì)模型進(jìn)行求解，遺傳算法參數(shù)設(shè)定為：種群規(guī)模為100，交叉概率為0.85，變異概率為0.2，最大迭代次數(shù)為150．實(shí)驗(yàn)結(jié)果見(jiàn)圖3和表5～8．

圖3 基于原始配送區(qū)域和社區(qū)發(fā)現(xiàn)的配送路線

表5 基于社區(qū)發(fā)現(xiàn)的站點(diǎn)任務(wù)分配情況

3.4 結(jié)果分析

通過(guò)數(shù)據(jù)分析可以發(fā)現(xiàn)，在滿足客戶需求的前提下，利用社區(qū)發(fā)現(xiàn)法進(jìn)行配送區(qū)域劃分可以將配送站點(diǎn)從原來(lái)的7個(gè)降低至現(xiàn)在的4個(gè)，配送車輛從13輛減少至11輛，車輛裝載率提升了14.1%，固定成本減少了15.4%，而運(yùn)輸成本與貨損成本僅增加了7.1%，時(shí)間懲罰成本減少了4.6%，總成本降低了5.4%．結(jié)果表明利用社區(qū)發(fā)現(xiàn)方法對(duì)客戶進(jìn)行聚類劃分配送區(qū)域可以保證配送時(shí)效性并有效降低整體配送成本．

表6 基于原始方案的站點(diǎn)任務(wù)分配情況

表7 基于社區(qū)發(fā)現(xiàn)的配送成本 單位：元

表8 基于原始區(qū)域劃分的配送成本 單位：元

4 結(jié) 束 語(yǔ)

合理規(guī)劃配送區(qū)域?qū)μ岣吲渌托?，降低冷倆物流末端配送成本具有重要意義，文中從實(shí)際交通網(wǎng)絡(luò)的角度考慮，利用客戶點(diǎn)間通行時(shí)間來(lái)描述節(jié)點(diǎn)間物流聯(lián)系，引入復(fù)雜網(wǎng)絡(luò)理論，利用網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)進(jìn)行客戶點(diǎn)聚類劃分配送區(qū)域，最終劃分方案能有效保證配送時(shí)效性，降低整體配送成本．