周曉曄，崔 瑤*，2，何 亮，馬小云，王思聰

(1.沈陽工業(yè)大學(xué)管理學(xué)院，沈陽110000；2.遼寧科技學(xué)院人文藝術(shù)學(xué)院，遼寧本溪117000；3.遼寧省交通高等專科學(xué)校機(jī)電工程系，沈陽110000)

0 引 言

2019年我國快遞年業(yè)務(wù)量突破630億件.貨運需求的大幅增長，引起道路資源與貨物運輸?shù)牟黄胶?，使交通問題日益嚴(yán)重，影響城市配送服務(wù)水平和效率.傳統(tǒng)貨車配送存在延誤高、空駛率高、環(huán)境污染等問題，故學(xué)者提出一種新型配送模式——地鐵配送[1].地鐵具有快速，低污染，沒有運輸交叉矛盾等優(yōu)勢，通過地鐵與貨車聯(lián)合運輸，將地鐵融入末端運輸網(wǎng)絡(luò)，不僅提高了貨物配送效率，還解決了城市道路擁堵引起環(huán)境污染問題，符合綠色物流發(fā)展理念.

J.C.Rijssenbrij 等[2]提出利用城市軌道交通多余運能開展客貨混運的觀點.Masson 等[3-4]提出白天非客運高峰實施客貨混運，夜晚開通貨運專列的想法.譚寅亮等[5]分析了城市軌道交通客運的時空不均衡性，提出利用軌道交通客流低谷時段實施物流快運的構(gòu)想.Yubo L.等[6]估算了北京地鐵閑置時段的運力和車站改造成本.以上研究論證了非高峰時段利用地鐵剩余運能開展貨物運輸?shù)目尚行裕珒H從地鐵角度分析，未考慮地鐵與其他運輸工具的聯(lián)合運輸問題.針對地鐵與貨車聯(lián)運問題的研究較少：楊婷等[7]研究了帶軟時間窗的地鐵網(wǎng)絡(luò)路徑優(yōu)化問題，利用地鐵客貨共線形式實現(xiàn)地鐵與貨車的聯(lián)合運輸；周芳汀等[8]研究了地鐵貨運專列與配送車輛的聯(lián)合運輸，構(gòu)建了帶時間窗的配送網(wǎng)絡(luò)路徑優(yōu)化模型；但均未考慮地鐵實際開行方案及地鐵服務(wù)能力的約束.

綜上，利用地鐵非高峰時段剩余運力開展貨物運輸，優(yōu)化地鐵與貨車聯(lián)運路徑具有現(xiàn)實意義.本文在不改變地鐵運行方案的前提下，考慮地鐵時空約束對聯(lián)運路徑優(yōu)化的影響，利用地鐵列車時刻表信息界定配送時間窗限制；考慮地鐵剩余運能、貨車容量、最大行駛距離、客戶服務(wù)時間窗等限制條件，以配送距離最短為優(yōu)化目標(biāo)，構(gòu)建基于地鐵—貨車聯(lián)運的物流配送路徑優(yōu)化模型.

1 模型構(gòu)建

1.1 問題描述

分析歷史客流數(shù)據(jù)，得到非高峰時段地鐵各車次列車的剩余運能，根據(jù)每趟列車剩余運力和客戶時間窗安排貨物運輸.緊鄰地鐵口的配送中心將貨物運到地鐵進(jìn)站口，第三方物流公司按照地鐵不同車次載貨量調(diào)配貨車提前到達(dá)各出貨站點接運，并按照客戶時間窗要求準(zhǔn)時送達(dá)，使配送距離最短，完成配送后，貨車直接返回車場.地鐵線路和列車時刻表，地鐵進(jìn)出貨站點和客戶位置坐標(biāo)，客戶需求量和時間窗均已知.

1.2 假設(shè)條件

(1)配送中心設(shè)在地鐵始發(fā)站，且配送中心到地鐵始發(fā)站的距離忽略不計.

(2)非高峰時段所有車次均能載貨，每趟車次貨運量不能超過地鐵剩余運能限制.

(3) 地鐵各出貨站點出貨量不能超過接運貨車最大載重量.

(4)貨物中轉(zhuǎn)作業(yè)時間固定.

(5)不考慮地鐵的存儲功能，貨物到站后直接裝車配送.

(6)貨車完成配送后不返回地鐵出貨站點，且載貨能力固定.

(7) 貨物由地鐵專用貨箱統(tǒng)一運輸，可快速裝卸.

1.3 符號說明

(1)參數(shù)描述.

V為配送中心d的集合，d∈V；K為地鐵站點c的集合，c∈K；L為地鐵出貨站點f的集合，f∈L，L?K；C為出貨站點f所需配送客戶if，jf的集合，if,jf∈C；R為在非高峰時段α地鐵列車班次rα的集合，rα∈R；G為貨車v的集合，v∈G；W為非高峰時段α的集合，α∈W；為第rα次列車由配送中心d到出貨站點f的行駛時間為貨車v到達(dá)出貨站點f的時刻；Qv為貨車v的容量；Qrα為非高峰時段α地鐵列車班次rα的剩余運能；Sjf為服務(wù)客戶jf的時間；tf,jf為地鐵出貨站點f到客戶jf的行駛時間；tif,jf為末端配送路徑客戶if到客戶jf的行駛時間；dif,jf為末端配送路徑客戶if到客戶jf的行駛距離；qjf為客戶jf的需求量；tjf為貨車開始服務(wù)客戶jf的時間；If為貨物在出貨站點f所需的轉(zhuǎn)運時間；[Ejf,Fjf]為客戶服務(wù)時間窗，Ejf為最早開始服務(wù)時間，F(xiàn)jf為客戶最晚開始服務(wù)時間；為第rα次列車從配送中心d到出貨站點f的出發(fā)時刻；D為貨車最大行駛距離；A為地鐵平均行車速度；B為貨車平均行駛速度；M為一個大的正整數(shù).

(2)決策變量.

表示從客戶if到客戶jf由貨車v提供服務(wù)時，取值為1，否則為0；表示貨物由配送中心d到出貨站點f通過第rα次列車運送給客戶jf時，取值為1，否則為0.

1.4 模型建立

式(1)為目標(biāo)函數(shù)，表示地鐵配送和貨車配送總距離最短；式(2)表示每輛車對每個客戶只能訪問一次，且客戶需求不可拆分；式(3)表示貨車負(fù)載限制；式(4)表示貨車最大行駛距離約束；式(5)表示非高峰時段地鐵存在剩余運能，則用地鐵進(jìn)行運貨；式(6)表示地鐵第rα次列車的剩余運能滿足客戶需求；式(7)表示貨車在第rα次列車到站前到達(dá)出貨站點；式(8)表示貨物從配送中心到客戶jf的最早到達(dá)時間限制；式(9)表示客戶if，jf在時間窗內(nèi)接受服務(wù)；式(10)和式(11)表示二進(jìn)制決策變量.

2 算法設(shè)計

地鐵—貨車聯(lián)運物流配送路徑優(yōu)化問題屬于NP難題，傳統(tǒng)精確算法難以快速求解，故結(jié)合地鐵配送路徑特點采用改進(jìn)的自適應(yīng)遺傳算法求解.

(1)編 碼.

采用多維不等長數(shù)組編碼方式，由字母與自然數(shù)組成.假設(shè)A、B、C為出貨站點，1～11為客戶，利用元胞數(shù)組元素多樣性、多維度特征，隨機(jī)生成一條染色體編碼，如圖1 所示.配送路徑分別是A→9→3，B→10→4→6→7→11，C→8→2→5→1.

圖1 染色體編碼Fig.1 Chromosomal coding

(2)解 碼.

為保證多維不等長數(shù)組編碼索引的一致性，進(jìn)行解碼操作，如圖2 所示.①將染色體按支路拆分，轉(zhuǎn)換成多個基因段；②將字母編碼對應(yīng)放入各行基因段最后，并在客戶總數(shù)基礎(chǔ)上遞增.

圖2 染色體解碼規(guī)則Fig.2 Chromosome decoding rules

(3)初始化種群.

地鐵配送路徑優(yōu)化問題可看作分區(qū)域開放式路徑優(yōu)化問題[9]，按客戶到各出貨站點距離遠(yuǎn)近劃分配送區(qū)域，各區(qū)域內(nèi)的客戶按時間窗和地理位置進(jìn)行配送.初始化種群流程如圖3 所示.第1 階段依據(jù)第rα次列車能夠提供服務(wù)的時間范圍，對不同時間窗客戶進(jìn)行聚類；第2階段依據(jù)地鐵剩余運能確定第rα次列車的客戶需求；第3階段通過掃描算法產(chǎn)生初始種群.

(4)適應(yīng)度函數(shù).

本文目標(biāo)函數(shù)為配送距離最短，故適應(yīng)度函數(shù)為目標(biāo)函數(shù)值的倒數(shù)，適應(yīng)度函數(shù)值越大，染色體越優(yōu).

圖3 初始化種群流程圖Fig.3 Initial population flowchart

(5)遺傳算子.

①選擇算子.計算種群個體適應(yīng)值，適應(yīng)值越大被選中的概率越大，采用輪盤賭選擇和精英保留相結(jié)合策略.首先，保留適應(yīng)值最大的個體，替換子代適應(yīng)值最差個體.其次，采用輪盤賭選擇父代個體，交叉與變異的概率通過自適應(yīng)調(diào)整策略[10]計算獲取.

②交叉算子.依據(jù)自適應(yīng)交叉概率，選擇兩個父代染色體I和II進(jìn)行解碼操作，對拆分出的基因段[a1(n-1),a1n]和[b1(n-1),b1n]，[a22]和[b22]，[a31,a32]和[b31,b32]按照映射法交叉，重組形成子代染色體I*和II*.檢驗子代染色體是否滿足約束條件，若不滿足則刪除.采用改進(jìn)部分匹配交叉法避免破壞優(yōu)秀基因串，如圖4所示.

圖4 交叉示意圖Fig.4 Crossover diagram

③變異算子.依據(jù)自適應(yīng)變異概率，選擇一條染色體；隨機(jī)產(chǎn)生兩個不相等的自然數(shù)索引k1和k2，找到對應(yīng)基因.若基因為各基因段最后一個基因，則重新生成；否則，交換位置，形成新的子代變異染色體.對變異后的染色體進(jìn)行約束條件檢驗，如不符合則刪除.

④種群擴(kuò)充機(jī)制.為保證子代種群與原種群具有相同數(shù)量個體，實現(xiàn)對優(yōu)秀個體的保護(hù)，同時保持種群的多樣性，從外部種群挑選適應(yīng)值大的個體補充到子代中.

(6)終止條件.

最大適應(yīng)度值和平均適應(yīng)度值趨于穩(wěn)定或達(dá)到最大迭代次數(shù)時，運算終止，輸出最優(yōu)解.

3 算例分析

3.1 算例數(shù)據(jù)

以某市地鐵2號線下行方向作為研究對象，行車間隔10 min，某工作日非高峰時段為：05:30-06:30，09:00-17:00，20:00-23:00.分析歷史客流數(shù)據(jù)，得到當(dāng)天非高峰時段各車次剩余運能，最多可服務(wù)3 000～3 500 個客戶，如圖5 所示.客戶時間窗在[06:00，24:00]范圍內(nèi)服從均勻分布，時間窗周期為60 min.配送中心、出貨站點及客戶點的位置坐標(biāo)通過百度地圖獲得，客戶地理位置服從均勻分布.出貨站點為工業(yè)展覽館、岐山路、醫(yī)學(xué)院.配送中心到各出貨站點的距離和運行時間分別為：工業(yè)展覽館9.2 km，16 min；岐山路15.3 km，30 min；醫(yī)學(xué)院22.9 km，44 min.貨車平均行駛速度為15 km/h，地鐵平均行車速度為60 km/h，貨車最大行駛距離為65 km，轉(zhuǎn)運時間為5 min，客戶服務(wù)時間為1 min.

3.2 結(jié)果分析

計算獲得每趟列車的服務(wù)客戶，各車次計算模型相同，故以09:30 發(fā)車的第25 次列車為例，服務(wù)客戶信息如表1所示.

圖5 某工作日非高峰時段地鐵各車次剩余運能Fig.5 Remaining capacity of each train in non-traffic peak time of a workday

表1 配送客戶信息Table 1 Distribution customer information

根據(jù)模型和算法，優(yōu)化20位客戶配送路徑，對比分析地鐵—貨車聯(lián)合配送與貨車單獨配送兩種模式，如表2和表3所示.

表2 地鐵—貨車聯(lián)合配送方案Table 2 Subway-freight truck intermodal distribution plan

表3 貨車配送方案Table 3 Freight truck distribution plan

由表2 和表3 可知：地鐵—貨車聯(lián)合配送，配送總距離126 km，在用戶時間窗內(nèi)全部送達(dá)；貨車配送，3輛貨車同時從○出發(fā)，總距離為160 km，未按時送達(dá)客戶數(shù)9個；地鐵—貨車聯(lián)合配送距離節(jié)省34 km，利用地鐵高準(zhǔn)時性配送大幅度提高客戶滿意度；實現(xiàn)客戶需求與各出貨站點最優(yōu)匹配，確定了各出貨站點的出貨量.兩種不同方式的配送路徑如圖6和圖7所示.

圖6 地鐵—貨車聯(lián)合配送路徑Fig.6 Subway-freight truck intermodal distribution route

圖7 貨車配送路徑Fig.7 Freight truck distribution route

3.3 算法性能分析

與迭代局部搜索算法進(jìn)行對比，驗證本文算法對地鐵—貨車聯(lián)合配送路徑問題的求解效果，如圖8和圖9所示，計算結(jié)果如表4所示.

圖8 迭代局部搜索算法Fig.8 Iterative local search algorithm

圖9 改進(jìn)的遺傳算法Fig.9 Improved genetic algorithm

通過比較分析，迭代局部搜索算法收斂速度較快，但配送總距離相對較長.本文通過編碼方式的創(chuàng)新，初始化種群的設(shè)置和交叉操作的改進(jìn)，使改進(jìn)的自適應(yīng)遺傳算法不僅運行時間短，計算效率高，而且能夠獲得較好的最優(yōu)解，驗證了算法的有效性.

表4 計算結(jié)果對比分析Table 4 Comparison and analysis of calculation results

4 結(jié) 論

地鐵—貨車聯(lián)合配送是一種新型城市配送模式，利用地鐵非高峰時段剩余運能開展貨物運輸更符合實際.為適應(yīng)地鐵和貨車聯(lián)合配送特征，本文考慮地鐵時空因素，建立聯(lián)合配送優(yōu)化模型，改進(jìn)自適應(yīng)遺傳算法求解.結(jié)果表明，地鐵—貨車聯(lián)合配送能夠為客戶提供更精準(zhǔn)的配送服務(wù)，比貨車單獨配送效率更高，對指導(dǎo)實際應(yīng)用具有一定的理論意義.

本文僅研究了單條地鐵線路貨物運輸，沒有考慮整個地鐵配送網(wǎng)絡(luò)，以及與干線運輸?shù)你暯优浜希@些問題對地鐵配送系統(tǒng)整體性研究是必不可少的，為下一步研究方向.