基于地鐵的地上地下閉環(huán)物流配送路徑優(yōu)化

鄭長江，陳宜恒，沈金星

（河海大學土木與交通學院，江蘇 ，南京 ， 210098）

隨著社會經(jīng)濟的發(fā)展以及環(huán)境污染的加劇，政府和消費者對物流運輸業(yè)提出了更高的要求。 閉環(huán)物流正是順應(yīng)這一趨勢而興起的，它是科學高效規(guī)劃物流網(wǎng)絡(luò)的出發(fā)點，是正向物流網(wǎng)絡(luò)與逆向物流網(wǎng)絡(luò)的集成[1]。 隨著物流需求的增長，日益擁堵的城市路面交通難以保障閉環(huán)物流經(jīng)濟、 綠色的發(fā)展，少占用地面空間的地上地下配送思路逐漸被發(fā)達國家重視[2-3]，其中基于地鐵的物流配送模式，既充分利用低碳環(huán)保的地鐵資源，又在成本上更具可行性，也受到學者們的關(guān)注。

日本札幌的地鐵配送實驗證明，小范圍的地鐵配送服務(wù)可以節(jié)約1/4 的貨車運輸[4]。Dampier等[5]研究了地鐵貨運的可行性和潛在問題， 通過方案比選驗證了該模式能有效緩解交通擁堵、 減少車輛尾氣排放。 以上研究大都集中在配送模式的可行性分析和宏觀影響評估， 但基于地鐵的地上地下配送模式研究需根據(jù)城市貨運現(xiàn)狀， 以提高貨運綜合效能為目標， 對配送路徑和參數(shù)進行優(yōu)化和分析。

Ghane 等[6]以建設(shè)費用和運輸費用最小為目標對物流網(wǎng)絡(luò)進行優(yōu)化。 Eric 等[7]考慮了車輛容量、時間窗約束等， 設(shè)計了一種配送路線的優(yōu)化算法。 湯雅連等[8]引入遺傳算子和客戶點分組策略，改進了蟻群算法以求解軟時間窗約束下的多車型路徑優(yōu)化問題。Zhao 等[9]和周曉曄等[10]提出基于地鐵系統(tǒng)在非高峰期進行物流運輸，以最小運輸距離為目標進行優(yōu)化。 周芳汀等[11-12]考慮了低碳、運輸成本和客戶點時間窗約束，提出以地鐵網(wǎng)絡(luò)為骨干的路徑優(yōu)化模型。 楊婷等[13]研究了帶軟時間窗的地鐵物流配送路徑優(yōu)化問題。 易美等[14]利用分層分級配送思路，以建設(shè)成本、運輸費用及中轉(zhuǎn)服務(wù)費用最低為目標建立地下物流規(guī)劃模型。 以上研究都考慮了不同因素下的配送路徑優(yōu)化， 但大多研究僅關(guān)注了傳統(tǒng)的正向物流網(wǎng)絡(luò)，忽略了物流鏈的重要環(huán)節(jié)——逆向回收，求解方案難滿足時下城市閉環(huán)物流的需求。 此外，大多文獻針對基于單條地鐵線路的配送問題進行研究， 由于地鐵配送貨運需依靠列車運輸貨物，并利用地鐵站完成貨物轉(zhuǎn)移，單線路地鐵配送模式存在因上游貨物轉(zhuǎn)移延遲或阻塞導(dǎo)致貨物堆積或貨運中斷[15]的問題。

面向區(qū)域閉環(huán)物流配送服務(wù)，設(shè)計地下地鐵線網(wǎng)-地面貨車的物流配送模式， 提出考慮地鐵客貨共運方式的帶時間窗閉環(huán)物流配送優(yōu)化問題，并建立以運輸成本、碳排放成本、時間窗懲罰成本、轉(zhuǎn)運成本、固定成本和地鐵貨運運營成本為優(yōu)化目標的地上地下閉環(huán)物流配送路徑優(yōu)化模型。 還根據(jù)配送模式的地下地面分層特點，設(shè)計了基于半初始化子路徑擾動策略的改進自適應(yīng)遺傳算法，并通過案例分析對所建立的模型和算法進行驗證評估。

1 問題描述

1.1 地上地下閉環(huán)物流配送模式

針對一組分布在一定區(qū)域內(nèi)需求已知，時間窗約束已知的客戶點，地上地下閉環(huán)物流配送系統(tǒng)采用客貨共運的地鐵班列和輕型貨車對其進行配送服務(wù)，其中客貨共運的地鐵班列是在不改變現(xiàn)行地鐵發(fā)車時刻表的情況下，利用平峰時段在客運車廂后增設(shè)物流車廂的新型配送模式[15]。

但是由于客貨共運地鐵班列的運力限制和時段限制，所有貨物由單一地鐵線路運輸、中轉(zhuǎn)易影響到常規(guī)客運服務(wù)和物流配送效率。 本文采取分層分級分區(qū)域的地上地下配送策略， 以降低對常規(guī)客運的影響，提高地下配送轉(zhuǎn)運效率。 圖1 所示為具體配送模式描述：①根據(jù)區(qū)位因素和周圍交通環(huán)境，選擇1，2 級地鐵站承擔貨物中轉(zhuǎn)功能，確定各2 級地鐵站的配送區(qū)域；②正向物流中，利用地下網(wǎng)絡(luò)貨物從物流園依次運往1，2 級地鐵站，并在2 級地鐵站由貨物電梯運往地面進行裝卸，最終由貨車運往各客戶點；③逆向物流中，客戶點的回收品用貨車運往2 級地鐵站，再由地鐵運輸至市郊回收。

圖1 基于地鐵的地上地下配送模式Fig.1 A ground-underground model based on metro network

綜上，基于地鐵的地上地下閉環(huán)物流配送模式假設(shè)條件如下。

1） 1 級地鐵站至同一2 級地鐵站的運輸任務(wù)由同一線路的地鐵分班次運輸；

2） 1 級地鐵站一次只開行一列至2 級地鐵站的客貨共運模式地鐵，直到2 級地鐵站的配送量均完成才開行下一列至另一2 級地鐵站的地鐵；

3） 一個客戶點僅允許同一輛貨車服務(wù)；

4） 當2 級地鐵站的配送量超過單次列車容量時，需等待下一班次列車；

5） 當客戶點的配送量超過貨車容量時，同一輛貨車需返回至對應(yīng)2 級地鐵站以完成剩余運輸任務(wù)；

6） 貨物由地鐵專用物流車廂運輸，可快速裝卸；

7） 地面路網(wǎng)各路段的行車速度是恒定的，不考慮路段內(nèi)的車輛變速情況；

8） 地鐵的客運發(fā)車時刻表已知，且假設(shè)地鐵線網(wǎng)的發(fā)車間隔是恒定的。

1.2 符號說明

為便于理解， 現(xiàn)將本文用到的參數(shù)匯總?cè)绫?所示。 決策變量定義如表2 所示。

表1 參數(shù)符號描述Tab.1 Notation and description for the parameters

表2 決策變量符號描述Tab.2 Notation and description for the decisive variables

1.3 數(shù)學模型

地下配送時間和地鐵發(fā)車間隔f、2 級地鐵站間的運輸時間tij相關(guān)。 由于地面配送時間易受路面交通狀況影響，根據(jù)百度地圖實時交通擁堵指數(shù)和祝付玲[17]的研究成果，設(shè)路面交通狀況為擁擠、緩行、暢通不穩(wěn)定和暢通時， 貨車路段平均速度V 分別為20，25，30 km/h 和40 km/h。 貨物配送總時長T 如式（1）所示。

為保證地鐵貨運不影響常規(guī)地鐵客運，基于地鐵的地上地下閉環(huán)物流配送模式引入地鐵站配送時間窗。 如果貨物提前到達2 級地鐵站，貨物堆積在地鐵站內(nèi)，產(chǎn)生貨物堆積風險成本，這與堆積的貨物量和堆積時間有關(guān)；如果貨物在指定時間窗內(nèi)到達2 級地鐵站，則不產(chǎn)生額外費用；當貨物延遲抵達2 級地鐵站時， 提前到達的貨車需要?？康却a(chǎn)生?？康却某杀尽?/p>

式中：M 是一個趨近于無窮大的數(shù)；Tt是可容忍的超出時長。

碳排放成本是對貨車的每單位CO2排放量按照稅率0.75[18]征收碳排放稅。 參考英國交通研究所的實載車輛碳排放計算公式[19]和任騰等[20]對車輛碳排放量的修正，設(shè)貨車在路段（i，j）上運載的貨物量為kij，碳排放成本Cctax如式（4）所示。

式中：α0，α1，α2，α3分別為0.98，-0.011，7.3×10-7，22.36；β 取7.5×10-5。

基于上述假設(shè)分析和實際閉環(huán)物流的配送過程，以運輸成本，時間窗懲罰成本，碳排放成本，轉(zhuǎn)運成本，固定成本和地鐵貨運運營成本的總成本W(wǎng) 最小化為目標，建立了基于地鐵的地上地下配送路徑優(yōu)化目標函數(shù)如式（5），約束條件如式（6）～式（16）所示。

約束條件（6）～（10）與地下運輸有關(guān)，其中：約束條件（6）保證一個2 級地鐵站僅由同一地鐵線路服務(wù)，約束條件（7）保證2 級地鐵站間路徑不連通，約束條件（8）表示一個2 級地鐵站至多允許同一地鐵線路額外發(fā)車一次，約束條件（9）確保同一線路地鐵至多發(fā)車兩次就完成運輸任務(wù)，約束條件（10）保證2 級地鐵站的配送量等于客戶點的配貨量之和。 約束條件（11）～（13）與地面運輸有關(guān)，其中：約束條件（11）保證一個客戶點僅由一輛貨車服務(wù)，約束條件（12）表示一個客戶點至多允許貨車返程一次，約束條件（13）確保貨車至多往返一次就完成運輸任務(wù)。 約束條件（14）確保同一節(jié)點內(nèi)無路徑。 約束條件（15）確保配送路徑的單向性。 約束條件（16）表示決策變量的屬性。

2 算法設(shè)計

地上地下物流配送線路聯(lián)合優(yōu)化問題實質(zhì)上是2E-VRP 問題，屬于NP 難題，許多學者都采用遺傳算法（genetic algorithm，GA）求解目標模型。 但遺傳算法在尋優(yōu)過程中存在收斂速度慢、易早熟等問題。首先，基于配送模式分層分級分區(qū)域特點，對2級地鐵站和客戶點進行聚類；其次，采用改進的自適應(yīng)遺傳算法（adaptive genetic algorithm，AGA）提高收斂速度，并引入半初始化策略和子路徑擾動策略增加算法迭代后期的種群多樣性。

1） 基于K-means 的聚類。 地上地下物流配送路徑優(yōu)化問題包含多車輛分區(qū)域配送。 根據(jù)2 級地鐵站數(shù)Nd、客戶點的配送量qi和可派遣貨車數(shù)等約束條件，基于地理位置信息，利用K-means 法對配送區(qū)域進行聚類劃分，并確定各2 級地鐵站配送區(qū)域內(nèi)的客戶點。

2） 編碼與初始化。采取排列編碼：①隨機選取2 級地鐵站生成Nt個序列； ②將2 級地鐵站服務(wù)范圍內(nèi)的客戶點隨機排列成子路徑，并插入到對應(yīng)的2 級地鐵站序列中；③插入1 級地鐵站，生成一條染色體編碼；④評估該染色體的目標值，并標注需要貨車返程的節(jié)點。 例如Nt=2 的配送路徑為

其中1 為1 級地鐵站，2-3 為2 級地鐵站。地下運輸順序為先配送2 號站點，再配送3 號站點；2 級地鐵站節(jié)點2 服務(wù)節(jié)點4，5，6 和8， 配送完節(jié)點8后貨車需返回節(jié)點2 再前往節(jié)點5，2 級地鐵站節(jié)點3 服務(wù)節(jié)點7，9。

3） 子路徑交叉和變異。 為加快種群進化速度，引進反映種群集中分散程度的參數(shù)γ=arcsin（fmin/favg），favg和fmin為當前種群的平均適應(yīng)度和最優(yōu)適應(yīng)度；改進的交叉概率Pc和變異概率Pm如式（17）和（18）所示。 當γ＜π/6 時，種群適應(yīng)度較分散，應(yīng)增加Pc值以快速生成新的優(yōu)質(zhì)解，同時降低Pm值，減小破壞優(yōu)質(zhì)解的概率；當γ＜π/6 時，適應(yīng)度較集中、個體過于相似，需降低Pc值、提高Pm值。

式中：Pc1和Pc2為預(yù)設(shè)的交叉概率最大值和最小值，可取0.8，0.6；Pm1和Pm2為預(yù)設(shè)的變異概率最大值和最小值，可取0.1，0.01。

如圖2 以概率Pc，Pm隨機選擇客戶點子路徑執(zhí)行交叉和變異。 執(zhí)行交叉操作時，選擇2 個父代染色體1 和2，隨機選擇一組節(jié)點序號，交換2 個染色體的對應(yīng)節(jié)點，生成2 個子代染色體1 和2；執(zhí)行變異操作時，針對同一編碼中的客戶點子路徑，隨機產(chǎn)生2 組同數(shù)目不同數(shù)的索引，找到對應(yīng)節(jié)點進行翻轉(zhuǎn)。

4） 半初始化策略和子路徑擾動策略。采取精英保留和半初始化策略以改進后期個體過于相似的問題。 若新一代種群最優(yōu)適應(yīng)度高于歷史最優(yōu)值，則未更新次數(shù)的計數(shù)φ 增1；當φ 大于閾值μ，則認為迭代已陷入局部最優(yōu)，此時隨機選擇除最優(yōu)個體外的一半個體進行初始化，另一半個體進行子路徑交叉變異。

為增加后期種群多樣性，借鑒粒子群算法的擾動方式[21]，引入式（19）的擾動概率Pr和圖2 的子路徑擾動操作：①隨機選擇客戶點i；②以所屬的子路徑總距離最小為目標， 重排客戶點i 所屬的子路徑；③以概率exp（－（fi-fmin）/Riter）接受新編碼。

圖2 子路徑交叉變異擾動Fig.2 The crossover, mutation and disturbance of sub path

Pr＝pr×exp（（Ri-1）/Riter）（19）

式中：fi為擾動后的適應(yīng)度；pr為預(yù)設(shè)擾動概率最小值， 可取0.15；Riter為最大迭代次數(shù)；Ri為當前迭代次數(shù)。

5） 改進AGA 算法流程簡述。 ①生成初始種群，種群規(guī)模為S；②存儲歷史最優(yōu)個體，收斂次數(shù)加1；③輪盤賭法選擇個體，計算Pc，Pm，Pr；④若φ≤μ，以概率Pc，Pm執(zhí)行子路徑交叉變異；若φ＞μ，執(zhí)行半初始化策略的交叉變異； ⑤若0-1 隨機數(shù)r

3 實例分析

3.1 背景

根據(jù)周芳汀等[11]的地鐵服務(wù)范圍敏感度分析，地鐵配送模式對服務(wù)范圍大小不敏感，參考該文設(shè)定的100 km2服務(wù)范圍， 如圖3 選取南京市地鐵站作為1 級地鐵站（節(jié)點1）和附近6 km 內(nèi)為研究區(qū)域；考慮區(qū)位因素和人流量，選取5 個現(xiàn)有站點（節(jié)點2-3，5-7）、2 個候選的改建站點 （節(jié)點4，8）作為2 級地鐵站，選取20 個客戶點，表3 展示了各節(jié)點經(jīng)緯度轉(zhuǎn)換為XY 坐標的相關(guān)信息， 表4 展示了各客戶點配送量、取貨量和時間窗需求。

表3 節(jié)點位置Tab.3 Node location information

表4 節(jié)點基本信息Tab.4 Node specific information

圖3 案例背景Fig.3 Case background

參考英國地下物流系統(tǒng)單位里程的總投資額為1.32 億元[22]和地鐵使用年限為30 年，設(shè)改建地鐵站點的固定成本和運營成本每工作小時折舊額為500 元。根據(jù)周曉曄等[10]對地鐵轉(zhuǎn)運點轉(zhuǎn)運時間的設(shè)置，設(shè)地上地下單位貨物中轉(zhuǎn)時間為0.003 min/件。結(jié)合鄧紅星等[23]對地面貨物裝卸時長的設(shè)置，設(shè)地面單位貨物裝卸時間為0.02 min/件。

3.2 地鐵客貨共線時段確定

選取1 級地鐵站2016 年10 月24 日（周一）至28 日（周五）的AFC 刷卡數(shù)據(jù)，繪制如圖4 的1 級地鐵站到站人數(shù)時間曲線圖。 根據(jù)到站人數(shù)的非高峰段確定地鐵客貨共線運營時段為10：00～15：00，即1 級地鐵站時間窗限制為[10，15]，同理各2 級地鐵站的時間窗限制為[10，20]。

圖4 工作日期間1 級地鐵站到站人數(shù)曲線圖Fig.4 The number of people arriving at Metro 1 station within a workday

3.3 討論與分析

1） 算法性能分析。 取不同種群規(guī)模和最大迭代次數(shù)，分別用AGA 算法[25]（k1=k3=1，k3=k4=0.5）和本文改進AGA 算法（μ=Riter/3）求解表5 的案例1，結(jié)果如圖5 所示， 并與在Cplex12.8 求解器得出的精確解進行對比。

表5 案例1～6 的50 次求解結(jié)果平均值Tab.5 The average value of 50 algorithm results of Case 1 to 6

圖5 迭代結(jié)果對比圖Fig.5 The comparison of iteration results

可以看出改進的AGA 算法， 能在有限的迭代次數(shù)內(nèi)更快求得優(yōu)質(zhì)解， 其運算時間比AGA 算法平均縮短了49.14%；此外基于半初始化和子路徑擾動策略的改進AGA 算法求解的偏差小，更穩(wěn)定，易求得優(yōu)質(zhì)解。 由改進AGA 算法求得的最優(yōu)配送路徑如圖6 所示，目標值23 174.54，具體路徑如下，其中，10，13，25 為貨車返程點。

圖6 改進算法求解的路徑優(yōu)化結(jié)果Fig.6 The result of routing optimization

在同案例背景下，基于CPLEX 12.8 運算精確求得的目標值為22 978.20， 即在有限的迭代次數(shù)內(nèi)，改進算法求得平均最小目標值的相對誤差為0.894%，平均值的誤差為1.415%，該誤差在可接受范圍內(nèi)。

2） 地下網(wǎng)絡(luò)運輸因素分析。 選擇7 個2 級地鐵站、7 輛貨車，設(shè)計如表5 的案例1～6。分析可知總成本與地下運輸時間、節(jié)點平均服務(wù)時間成正相關(guān)關(guān)系； 從案例1～3 可知， 案例1 單次列車運量小、發(fā)車頻次高導(dǎo)致地下運輸時間長，進而平均服務(wù)時間較長和總成本較高，而對比案例1，可靈活調(diào)整物流車廂數(shù)的案例3 有效減少了15.4%的地下運輸時間，平均送達時間和總成本也相應(yīng)減少了4.6%和3.8%；對比案例3～6 可知，增大發(fā)車間隔、 減少物流車廂容量均會增加地下運輸時間、平均服務(wù)時間和總成本，此時求得的配送路徑具有較次的送達時效性和經(jīng)濟性。

3） 不同資源配置策略分析?；诒? 中總成本小、送達時效性好的案例3 參數(shù)設(shè)置，設(shè)計了如表6的案例。 分析可知： 對比僅依靠地面運輸?shù)陌咐?和案例3 可知，地上地下閉環(huán)物流配送路徑的碳排放量和平均服務(wù)時間分別降低了57.5%，8.1%，可見地上地下的配送模式在保證經(jīng)濟性的同時可提供送達時效性好，低碳環(huán)保的配送路徑；由案例7～8可知，合理的貨車數(shù)可以優(yōu)化地面運輸路徑、減少碳排放量，但貨車數(shù)的增加會導(dǎo)致服務(wù)時間和總成本的上升，總成本的平均增長率為4.1%；從案例9～10 可知，合理利用現(xiàn)有地鐵線網(wǎng)完成地下地上配送可以在保證貨物送達時效性的同時降低49.4%的總成本，但地鐵站服務(wù)區(qū)域的縮小會導(dǎo)致配送方案的碳排放量上升3.5%；此外由案例11 可知，較少的客貨共運地鐵站點會導(dǎo)致貨運中轉(zhuǎn)時間超出站點時間窗，進而使總成本上升了66.0%，即此時貨物中轉(zhuǎn)影響到了地鐵客運，同樣也使得配送方案的碳排放量和平均服務(wù)時間增加了54.2%和7.5%，貨運送達穩(wěn)定性和低碳無法滿足。

表6 不同資源配置案例的50 次求解結(jié)果平均值Tab.6 The average value of 50 algorithm results in resource allocation cases

4 結(jié)論

共享地鐵資源配送貨物是一種提高地下資源利用率，減少地面交通擁堵和環(huán)境污染的模式。 本文考慮城市閉環(huán)物流需求，提出地上地下閉環(huán)物流的配送模式和路徑優(yōu)化模型， 改進AGA 算法求解，并從地下網(wǎng)絡(luò)運輸因素和資源配置策略兩個方面進行案例分析。

1） 基于半初始化子路徑擾動策略的改進AGA算法可以較快求得優(yōu)質(zhì)解，求解更高效、穩(wěn)定。

2） 基于地鐵的地上地下路徑優(yōu)化模型的總成本與地下運輸時間、節(jié)點平均服務(wù)時間和地面貨車數(shù)成正相關(guān)關(guān)系；采用多編組的開行方式、3 000 件的物流車廂容量和5 min 的發(fā)車間隔， 可以有效減少閉環(huán)物流配送模式的4.6%的配送時間和3.8%的總成本，具有較好的送達時效性和經(jīng)濟性。

3） 相比傳統(tǒng)地面貨車配送模式，基于地鐵的地上地下配送方案可以降低57.5%的碳排放量、 減少8.1%的平均配送時間；此外合理地利用現(xiàn)有地鐵線網(wǎng)可以進一步優(yōu)化配送方案，其資源配置策略可為未來城市物流與地鐵的發(fā)展提供參考依據(jù)。