王正國 陳 升* 熊一凡

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

0 引 言

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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ù)作為邊的權(quán)重值．社區(qū)間的通行時間主要會受到道路等級、長度、交通狀況、車輛行駛速度等主要因素的影響．

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

(2)

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

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

Wij=1/tij

(3)

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

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

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

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

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

(4)

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

步驟1每個節(jié)點作為一個獨立社區(qū)，二者編號相同．

步驟2對于節(jié)點i，計算將其劃入至其相鄰節(jié)點所在社區(qū)時的模塊度增量ΔQ，記錄ΔQ最大時所對應的社區(qū)編號，如果max(ΔQ)>0，則把節(jié)點i劃入該社區(qū)，否則不進行移動．

步驟3重復步驟2，直到所有節(jié)點不再發(fā)生移動．

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

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

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

2.1 問題描述

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

2.2 模型假設(shè)

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

2) 各個配送站點的訂單處理能力相同．

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

4) 已知社區(qū)點地理坐標、需求量，以及配送時間窗．

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

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

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

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

2.3 模型符號

2.4 優(yōu)化目標

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

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

(5)

2) 運輸成本C2車輛的運輸成本與配送車輛運輸時間成正比．車輛的運輸成本C2為

(6)

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

O(t)=λO0e-ρt

(7)

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

(8)

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

(9)

2.5 模型構(gòu)建

minC=C1+C2+C3+C4

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

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

3 案例分析

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

圖2 社區(qū)分布圖

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

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

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

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

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

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

表2 節(jié)點間通行時間 單位：min

3.3 問題求解

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

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

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

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

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

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

3.3.2模型求解

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

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

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

3.4 結(jié)果分析

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

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

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

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

4 結(jié) 束 語

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