崔 瑤，周曉曄，何 亮

(1.沈陽工業(yè)大學(xué) 管理學(xué)院，遼寧 沈陽 110000；2.遼寧科技學(xué)院 管理學(xué)院，遼寧 本溪 117000；3.遼寧省交通高等?？茖W(xué)校 機電工程系， 遼寧 沈陽 110000)

近年來，隨著電子商務(wù)的快速發(fā)展，小批量、多頻次、高時效貨物的動態(tài)配送需求與日俱增，企業(yè)不斷推出“極速達”、“閃送”等1 h高效配送服務(wù)，來快速響應(yīng)客戶的配送需求，使得求解動態(tài)車輛路徑問題[1](Dynamic Vehicle Routing Problem，DVRP)變得越來越復(fù)雜。傳統(tǒng)DVRP問題僅考慮單一貨車配送的路徑優(yōu)化問題，采用增派車輛或調(diào)度現(xiàn)有車輛往返來實現(xiàn)動態(tài)配送，配送成本較高，而且易受交通限行影響，導(dǎo)致貨物無法按時送達，所以傳統(tǒng)DVRP已然不適于求解目前復(fù)雜多變的動態(tài)配送問題。地鐵作為公共交通工具不僅具有高頻、快速、準(zhǔn)時的特點，而且存在閑置可共享的運輸資源、站點遍布城市中心、與客戶需求點距離較近、不受交通限行因素影響等優(yōu)勢。因此，在交通物流融合的背景下，通過共享地鐵網(wǎng)絡(luò)閑置運能將貨物快速送達城市中心，再由貨車靈活接運實現(xiàn)末端配送，將公共交通工具和傳統(tǒng)配送工具聯(lián)合，發(fā)揮其各自優(yōu)勢，為客戶提供精準(zhǔn)、快速的配送服務(wù)，是未來發(fā)展趨勢[2]。

有關(guān)DVRP方面的研究，Abdallah等[3]構(gòu)建帶容量約束的動態(tài)車輛路徑模型，按時間段將動態(tài)車輛路徑問題轉(zhuǎn)化成一系列靜態(tài)車輛路徑問題進行求解；Armas等[4]構(gòu)建帶軟時間窗和客戶優(yōu)先權(quán)約束的多車型動態(tài)車輛路徑模型，并采用了生成初始路徑和實時動態(tài)調(diào)整的兩階段求解策略。Chen等[5]以總成本最小化為優(yōu)化目標(biāo)，建立帶容量和時間窗約束的動態(tài)車輛路徑模型，并采用生成初始路徑和按時間段定期更新路徑的兩階段求解策略。葛顯龍等[6]研究不同動態(tài)等級場景下，考慮動態(tài)客戶需求量的兩級動態(tài)車輛路徑問題，并設(shè)計禁忌搜索算法求解。張文博等[7]構(gòu)建動態(tài)需求下帶軟時間窗的車輛路徑模型，并設(shè)計啟發(fā)式算法求解。張景玲等[8]提出一種動態(tài)需求下跨區(qū)域多配送中心沿途補貨策略，構(gòu)建兩階段車輛路徑優(yōu)化模型，并設(shè)計自適應(yīng)免疫量子進化算法求解。上述文獻為動態(tài)配送問題提供了多種解決方案，具有一定的借鑒意義，但都僅限于采用單一貨車配送方式，對于多種運輸工具聯(lián)合運輸?shù)膭討B(tài)配送問題還缺少相應(yīng)研究。

關(guān)于地鐵和貨車聯(lián)合運輸配送方面的研究，Trentini等[9]提出使用公共交通實現(xiàn)客貨混運，共享公共資源，包括共享公共汽車、地鐵、地鐵站儲物柜等。Masson等[10]提出共享公共交通資源實現(xiàn)貨物配送，以提高公共交通利用率。Chen等[11]提出利用城市軌道交通多余運能開展客貨混運的觀點。Masson等[12]提出白天非客運高峰實施客貨混運，夜晚開通貨運專列的想法。Kikuta等[13]首次對城市地鐵發(fā)展物流進行實證研究，提出札幌市利用地鐵與卡車聯(lián)合運輸將貨物從郊區(qū)配送到城市中心。周芳汀等[14]研究地鐵和貨車聯(lián)合配送選點-路徑問題，并設(shè)計改進遞歸粒度算法進行求解。周曉曄等[15]研究利用地鐵非高峰時段剩余運能運輸貨物，構(gòu)建帶時間窗的地鐵和貨車聯(lián)合運輸配送路徑優(yōu)化模型，并設(shè)計改進的自適應(yīng)遺傳算法進行求解。上述文獻僅從靜態(tài)的角度研究地鐵貨運服務(wù)網(wǎng)絡(luò)問題，缺少對動態(tài)服務(wù)網(wǎng)絡(luò)的研究，忽略了地鐵高頻、快速的優(yōu)勢。

關(guān)于動態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計方面，本文研究的城市地鐵-貨車聯(lián)運動態(tài)服務(wù)網(wǎng)絡(luò)，解決地鐵的動態(tài)選點以及地鐵-貨車協(xié)同配送路徑的集成優(yōu)化問題，此類問題研究較少。Andersen等[16]以貨物運輸時間最短為目標(biāo)，考慮列車換線情況，構(gòu)建多列車協(xié)同優(yōu)化的動態(tài)服務(wù)網(wǎng)絡(luò)設(shè)計模型。王保華等[17]研究了考慮列車開行時段、編組周轉(zhuǎn)等約束的鐵路動態(tài)貨運服務(wù)網(wǎng)絡(luò)設(shè)計優(yōu)化模型，解決列車利用率問題。Ahmadi等[18]研究動態(tài)服務(wù)網(wǎng)絡(luò)中車輛動態(tài)隨機位置的定位路徑集成問題。Marinakis等[19]構(gòu)建以成本最小化為目標(biāo)的隨機需求選址-路徑模型，并設(shè)計混合算法求解。蔣海青等[20]設(shè)計一種四階段混合量子差分進化算法解決預(yù)優(yōu)化和實時優(yōu)化的兩階段選址-路徑問題。上述文獻雖然提出了諸多可借鑒的方法，但是未考慮地鐵和貨車聯(lián)合運輸?shù)奶卣鳌Ｅc一般動態(tài)服務(wù)網(wǎng)絡(luò)相比，本文研究設(shè)計基于地鐵-貨車的聯(lián)運動態(tài)服務(wù)網(wǎng)絡(luò)，將地鐵選點與貨車路徑的優(yōu)化進行集成，需要綜合考慮地鐵與貨車的時空約束、相對位置和速度、客戶時間窗等因素，優(yōu)化過程更為復(fù)雜。

綜上所述，本文對基于地鐵和貨車聯(lián)合運輸?shù)膭討B(tài)配送選點-路徑優(yōu)化問題開展研究，主要貢獻及創(chuàng)新點是：①利用地鐵共享的運輸資源，從聯(lián)合運輸?shù)慕嵌妊芯縿討B(tài)配送問題，以聯(lián)合運輸配送成本最小為目標(biāo)，構(gòu)建地鐵轉(zhuǎn)運點選擇、貨車調(diào)度及接運配送路徑的兩階段動態(tài)整體優(yōu)化模型；②設(shè)計一種以改進遺傳算法作為外層模塊，以改進蟻群算法作為內(nèi)層模塊，通過內(nèi)外層信息交互求解問題的集成算法；③針對模型特點，根據(jù)不同種類的節(jié)點特征，對外層遺傳算法的編碼結(jié)構(gòu)進行重新設(shè)計，并改進交叉變異操作；根據(jù)貨車先接后送原則，改進內(nèi)層蟻群算法的編碼方式和概率選擇操作。最后設(shè)計仿真算例驗證模型和算法的合理性和有效性。

1 問題描述

本文通過地鐵和貨車的聯(lián)合運輸，完成動態(tài)需求的配送任務(wù)，在滿足地鐵共享剩余運能和貨車最大容量的前提下，按照客戶時間窗需求將貨物從一個臨近地鐵始發(fā)站的配送中心通過地鐵網(wǎng)絡(luò)運送到城市中心的轉(zhuǎn)運點，再從轉(zhuǎn)運點通過貨車運送到客戶手中。為充分利用現(xiàn)有貨車，需要考慮地鐵與接運貨車的有效協(xié)同：一是如何利用地鐵的剩余空間。通過分析歷史客流數(shù)據(jù)可得線路l不同車次r途經(jīng)站點的最大客流量，根據(jù)悲觀主義決策準(zhǔn)則計算lr的最小剩余運能Qlr作為容量上限。對當(dāng)前所有客戶需求，以不超過地鐵容量上限為依據(jù)，按照所屬區(qū)域鄰近，時間窗有序原則依次上車，超出容量限制的需求按相同原則分配到下一車次，同時對接運貨車的貨物進行預(yù)優(yōu)化，以實現(xiàn)地鐵與貨車的空間協(xié)同。二是如何實現(xiàn)與貨車在時間上的銜接。由于地鐵相對速度快，為保證貨車在配送過程中的連續(xù)性，地鐵運輸?shù)呢浳镄柘扔谪涇嚨竭_轉(zhuǎn)運點；同時貨物在轉(zhuǎn)運點的允許等待時間要滿足客戶的最晚送達時間。

初始階段，貨車在轉(zhuǎn)運點等待接運貨物，按最小成本規(guī)劃初始地鐵路徑、轉(zhuǎn)運點以及貨車接運路徑。動態(tài)階段，時刻t更新需求，將動態(tài)問題轉(zhuǎn)化為t時刻的靜態(tài)問題，利用t時刻現(xiàn)有貨車到轉(zhuǎn)運點接運，對于新增和剩余需求規(guī)劃地鐵轉(zhuǎn)運點、接運貨車以及配送路徑，對于貨車未接運需求重新規(guī)劃接運貨車及配送路徑，對于貨車已接運未送達需求繼續(xù)由原貨車配送，僅重新規(guī)劃配送路徑。因此，如何選擇轉(zhuǎn)運點、調(diào)度貨車協(xié)同接運，并優(yōu)化貨車接運配送路徑，使聯(lián)合運輸配送成本最小是本文研究的關(guān)鍵問題。

初始階段，貨物從配送中心O出發(fā)經(jīng)地鐵，在轉(zhuǎn)運點A、B、C中轉(zhuǎn)，由貨車v1、v2、v3接運配送，路徑為O-A-1-2-3，O-B-4-5-6，O-C-7-8-9-10，見圖1。假定t時刻，產(chǎn)生新增需求11、12，首先確定關(guān)鍵點位置，貨車正在前往或正在服務(wù)(包括中轉(zhuǎn)服務(wù)、配送服務(wù))的節(jié)點為關(guān)鍵點(可以是地鐵轉(zhuǎn)運點或客戶點)，并將其作為t時刻貨車出發(fā)點，然后對未完成客戶、新增客戶以及開放轉(zhuǎn)運點C、D、E統(tǒng)一重新規(guī)劃路徑：2-(O)D-11-3、5-6-C-7-8、C-9-(O)E-12-10，見圖2。

圖1 初始階段地鐵-貨車聯(lián)運配送網(wǎng)絡(luò)選點-路徑示意圖

圖2 動態(tài)階段地鐵-貨車聯(lián)運配送網(wǎng)絡(luò)選點-路徑示意圖

2 模型構(gòu)建

2.1 假設(shè)條件

(1) 地鐵(開行方案、線路、轉(zhuǎn)運點位置坐標(biāo))和客戶需求(客戶位置坐標(biāo)、需求量、時間窗)的相關(guān)數(shù)據(jù)已知。

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

(3) 轉(zhuǎn)運點可被用于暫存和轉(zhuǎn)運貨物。

(4) 地鐵線路站間行駛時間固定，且換線時間固定。

(5) 貨物中轉(zhuǎn)作業(yè)時間和客戶服務(wù)時間固定。

(6)t時刻任意兩個開放轉(zhuǎn)運點之間無貨車路徑直接相連。

(7) 貨車無需返回轉(zhuǎn)運點，路徑開放。

(8) 地鐵線路運輸貨物不會影響客運服務(wù)質(zhì)量。

2.2 模型中用到的參數(shù)和變量

2.3 模型建立

建立“初始階段(t=0)+動態(tài)階段(t≠0)”兩階段選點-路徑整體優(yōu)化模型

(1)

s.t.

(2)

(3)

(4)

(5)

?j∈Va(t)∪Vb(t)

(6)

(7)

(8)

(9)

v∈Vv(t)j∈Vu(t)t≠0

(10)

v∈Vv(t)o∈Voi∈Vg(t)

k∈Vk(t)∪Vabg(t)j∈Vu(t)t≠0

(11)

(12)

i∈Vg(t)j∈Vb(t)

(13)

v∈Vv(t)o∈Voi∈Vg(t)j∈Va(t)∪Vb(t)

(14)

?v∈Vv(t)j∈Va(t)∪Vb(t)i∈Vabg(t)

(15)

(16)

Tij=dij/v?i,j∈Vabg(t)i≠j

(17)

(18)

i∈Vg(t)j∈Vb(t)

(19)

(20)

ni∈{0,1} ?i∈Vg(t)

在參加這次哈佛管理課程之后，我認識到了這種現(xiàn)象的出現(xiàn)固然與公司的體系與氛圍有關(guān)，但如果雙方都有著足夠的溝通意識和技巧，對此類問題會有極大的促進作用。

(21)

3 算法設(shè)計

本文研究的是動態(tài)問題，因此采用“初始優(yōu)化階段+動態(tài)優(yōu)化階段”的兩階段動態(tài)調(diào)度策略求解[17]，同時依據(jù)地鐵發(fā)車間隔設(shè)置新增客戶的監(jiān)測系統(tǒng)，以判斷m=m+1時刻是否進行動態(tài)優(yōu)化，見圖3。

圖3 兩階段動態(tài)調(diào)度策略流程

初始優(yōu)化階段，首先，將具有相近空間和時間分布的客戶進行聚類，實現(xiàn)不同配送區(qū)域的時空劃分，并將各配送區(qū)域所覆蓋的地鐵出口作為備選轉(zhuǎn)運點。其次，在生成初始配送方案階段，采用Mark-Sweep算法確定開放轉(zhuǎn)運點：①根據(jù)距離最短原則，將客戶分配給各備選轉(zhuǎn)運點，獲得初始轉(zhuǎn)運點和客戶分配結(jié)果；②確定配送中心到初始轉(zhuǎn)運點的地鐵最短線路；③依據(jù)地鐵最短線路的共享剩余運能和客戶時間窗優(yōu)先原則，確定轉(zhuǎn)運點和客戶點，同時進行標(biāo)記；④整理不滿足地鐵共享剩余運能的客戶，清除標(biāo)記點并返回步驟①重新分配，直到找到符合要求的轉(zhuǎn)運點；對確定的轉(zhuǎn)運點進行開放操作。最后，對分配到開放轉(zhuǎn)運點的客戶采用帶時間窗和車容量約束的蟻群算法獲得初始配送路徑，并計算目標(biāo)函數(shù)值。

動態(tài)優(yōu)化階段，結(jié)合問題研究特征，設(shè)計雙層啟發(fā)式集成算法進行求解，遺傳算法具有良好的收斂性和全局搜索能力，蟻群算法具有良好的魯棒性和局部尋優(yōu)能力，將兩種算法的優(yōu)點相結(jié)合[21]，使其適應(yīng)于求解基于地鐵-貨車聯(lián)運的選點-路徑的整體優(yōu)化問題，本文算法流程見圖4。首先，將改進的遺傳算法作為外層模塊，根據(jù)t時刻確定新增客戶的時空分布、所屬配送區(qū)域，以及所屬區(qū)域范圍內(nèi)執(zhí)行任務(wù)的貨車的關(guān)鍵位置和未送完客戶點等信息；為客戶隨機分配執(zhí)行貨車和備選轉(zhuǎn)運點，生成動態(tài)階段選點-分配染色體和初始種群。然后，將外層染色體信息傳遞給內(nèi)層模塊，依據(jù)染色體的客戶-轉(zhuǎn)運點-貨車分配信息，設(shè)計改進的蟻群算法對接運貨車進行多轉(zhuǎn)運點接送路徑優(yōu)化，計算配送成本，再反饋給外層模塊，并與地鐵運輸成本相加，即為染色體的適應(yīng)度值。最后，進行遺傳操作，直到達到終止條件。

圖4 本文算法流程

3.1 外層遺傳算法的選點-分配編碼

由于涉及轉(zhuǎn)運點和接運貨車的分配，采用二維矩陣編碼方式。其中，列為客戶點，行為轉(zhuǎn)運點分配、接運貨車選擇。例如，新增客戶①～⑤，開放轉(zhuǎn)運點為A、B、C，t時刻執(zhí)行任務(wù)車輛為v1和v2，新增車輛v3和v4，編碼見圖5。車輛v1已接運客戶1、3，到轉(zhuǎn)運點A接客戶4、6、①和②；車輛v2已接運客戶2，到轉(zhuǎn)運點B接客戶5和④；車輛v3到轉(zhuǎn)運點B接客戶③；車輛v4到轉(zhuǎn)運點C接客戶⑤；為保證初始種群中染色體的可行性，需要判斷是否滿足約束條件，如果不滿足則重新生成，直到滿足約束條件為止。

圖5 選點-分配矩陣編碼結(jié)構(gòu)

3.2 適應(yīng)度計算

針對聯(lián)合運輸多轉(zhuǎn)運點接送特征，改進傳統(tǒng)蟻群算法的編碼方式和概率選擇操作，求解貨車最優(yōu)配送路徑，并獲得貨車配送成本，再與地鐵運輸成本相加，最終獲得染色體的適應(yīng)度值，適應(yīng)度值越小被選擇的概率越大。

3.3 內(nèi)層蟻群算法的改進

采用鍵值對編碼形式，v為節(jié)點，ω為來源點。接收外層傳輸信息并構(gòu)造貨車路徑的解，路徑節(jié)點由新增客戶點、開放轉(zhuǎn)運點、關(guān)鍵節(jié)點和未送完客戶點4部分構(gòu)成，其中轉(zhuǎn)運點由字母表示，其他節(jié)點由自然數(shù)表示。針對多轉(zhuǎn)運點接送特征，需為客戶節(jié)點定義來源點，在訪問客戶節(jié)點時必須先訪問其來源點，這樣才能表達出貨物先接后送的情況；客戶節(jié)點的來源點定義為對應(yīng)轉(zhuǎn)運點，如果編碼結(jié)構(gòu)中不存在客戶節(jié)點來源點，則將其來源點替換成關(guān)鍵節(jié)點，轉(zhuǎn)運點的來源點定義為關(guān)鍵節(jié)點，貨車只能從關(guān)鍵節(jié)點出發(fā)。如車輛v1：<3,3*>→<1,3*>→→<4,3*>→<6,3*>→<②,B>→<①,B>，其中關(guān)鍵節(jié)點3*，未送完客戶點1、4、6的來源點是A，由于編碼中不存在A，所以轉(zhuǎn)換為3*，開放轉(zhuǎn)運點B的來源點是O，同理轉(zhuǎn)換為3*；新增客戶點①、②的來源點是B，見圖6。

圖6 鍵值對編碼結(jié)構(gòu)和多點接送概率選擇操作示意

傳統(tǒng)蟻群算法采用Tabu表節(jié)點的順序記錄路徑，Tabu表中的節(jié)點是按照選擇概率對待訪問節(jié)點集合Unvisited(k)中元素隨機獲取，由于本文考慮先接后送的情況，在節(jié)點選擇時受Tabu表中來源點的影響，可能存在不可行路徑，因此本文對蟻群算法的概率選擇操作進行如下改進：

(22)

δ(i,j)=dik+dkj-dij-P

(23)

P=ψmax(Ei-hi,0)+ζmax(hi-Fi,0)

(24)

改進編碼結(jié)構(gòu)與概率選擇操作后的算法過程偽代碼如下：

M=50； ∥初始化種群規(guī)模

form=1:M∥種群循環(huán)

Tabu(m)←keynode; ∥初始化禁忌表，從關(guān)鍵節(jié)點出發(fā)

whileUnvisited(m)≠?; do

fori=1:size(Unvisited(m)) ∥遍歷待訪問節(jié)點集合

ifUnvisited(i)(ω) inTabu(m) then ∥判斷節(jié)點來源點已存在

J(m)←Unvisited(i); ∥生成可訪問節(jié)點集合

End

End

fori=1:size(J(m)) ∥遍歷可訪問節(jié)點集合

p(J(m),i)=式(22); ∥節(jié)點選擇概率

Tabu(m)←j=find(p(J(m),i)>rand);∥選定下一節(jié)，并將其加入禁忌表

End

Unvisited(j)=?; ∥待訪問表中刪除選定節(jié)點

End

End

returnTabu(best); ∥輸出最優(yōu)解

3.4 遺傳操作

(1)選擇算子。采用輪盤賭選擇和精英保留相結(jié)合的選擇策略。

(2)截取掩碼交叉算子。采用掩碼形式的交叉操作算子，首先依據(jù)選擇概率在初始種群中選取兩條父代染色體，然后截取參與遺傳操作基因段，按截取部分生成隨機二維結(jié)構(gòu)的0-1掩碼矩陣，其他位置用-1替代，不進行交叉操作。在交叉過程中，如果掩碼對應(yīng)位置為1，則從對應(yīng)父代染色體中取得該位置基因；若掩碼對應(yīng)位置為0，則從另一父代染色體取得該位置基因[22]。檢驗子代染色體是否滿足約束條件，若不滿足則刪除，見圖7。

圖7 截取掩碼交叉操作示意圖

(3)截取掩碼變異算子。依據(jù)變異概率選擇一條染色體；然后截取參與遺傳操作基因段，按截取部分隨機產(chǎn)生兩個自然數(shù)索引k1和k2，從染色體中找到對應(yīng)k1位置基因，從備選轉(zhuǎn)運點中找到對應(yīng)k2位置元素，如果相等，則重新生成索引，否則進行替換，形成新的子代變異染色體。對變異后的染色體進行約束條件檢驗，如不符合則刪除。

(4)種群擴充機制。為保證子代種群與原種群具有相同數(shù)量個體，實現(xiàn)對優(yōu)秀個體的保護，同時保持種群的多樣性，從外部種群隨機挑選可行個體補充到子代中。

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

4 算例分析

4.1 算例數(shù)據(jù)及結(jié)果分析

以某市地鐵網(wǎng)絡(luò)貨物運輸為例，分析某日歷史客流數(shù)據(jù)，得到地鐵線路各車次最小剩余空間，見圖8，取第25次列車為開始時刻，地鐵車次行車間隔7 min。根據(jù)客戶時空聚類劃分配送區(qū)域，當(dāng)前配送子區(qū)域服務(wù)范圍在(36.98,77.68)，(46.18,85.19)經(jīng)緯度之間，該區(qū)域經(jīng)過4條地鐵線路，分別是1號線、2號線、9號線、10號線，備選轉(zhuǎn)運點(地鐵站點)有12個，配送中心位置為O(48.89,71.39)。

圖8 某日地鐵線路各車次最小剩余空間

表1 初始客戶信息

表2 地鐵運行時間和距離

利用Mark-Sweep算法和蟻群算法對初始階段的地鐵-貨車聯(lián)運動態(tài)配送選點-路徑模型進行優(yōu)化求解，產(chǎn)生初始配送方案，見圖9、表3。

表3 初始配送方案

圖9 初始選點-路徑

動態(tài)優(yōu)化階段，取t=35時刻作為動態(tài)需求更新時刻，此時有10個新增客戶產(chǎn)生，客戶信息見表4，配送網(wǎng)絡(luò)關(guān)鍵節(jié)點集合為{17,13,7,16,10}，配送網(wǎng)絡(luò)中貨車在關(guān)鍵點出發(fā)時的剩余容量為{3,4,2,10,8}，貨車未完成客戶的集合為{{6,20};{1,9,15};{5,11,14,19};?;{2}}；未出地鐵客戶集合{4,3,18}，根據(jù)當(dāng)前已知信息對動態(tài)配送網(wǎng)絡(luò)進行優(yōu)化，利用集成算法對t時刻的聯(lián)合運輸配送選點-路徑模型進行求解，并產(chǎn)生t時刻的配送方案，見表5、圖10。

表4 新增客戶信息

表5 t時刻的配送方案

圖10 動態(tài)階段選點-路徑

從動態(tài)配送方案中可以看出，采用地鐵-貨車聯(lián)運的動態(tài)配送成本和傳統(tǒng)貨車動態(tài)配送成本相比，減少了18.44%，原因在于：①本文利用共享的城市地鐵網(wǎng)絡(luò)運輸貨物，減少了貨車的數(shù)量；②動態(tài)客戶需求通過地鐵到達開放轉(zhuǎn)運點，利用現(xiàn)有執(zhí)行車輛到相應(yīng)轉(zhuǎn)運點實現(xiàn)短距離接運，無需返回配送中心取貨或重新派車配送，節(jié)省了車輛運輸距離和車輛數(shù)量。聯(lián)合運輸成本中地鐵的運輸成本略高，這是由于地鐵線路固定導(dǎo)致運輸距離稍大于傳統(tǒng)貨車，但是通過地鐵可將貨物快速送達指定轉(zhuǎn)運點，實現(xiàn)地鐵與貨車的精準(zhǔn)銜接，提高配送時效，在t=98時刻所有客戶全部完成配送，符合動態(tài)客戶的高時效需求，進一步說明采用基于地鐵和貨車聯(lián)運配送模式更適于動態(tài)配送情景。

4.2 不同規(guī)模算例結(jié)果分析

為了討論本文算法對地鐵和貨車聯(lián)運的動態(tài)配送選點-路徑問題的適用性，對不同問題規(guī)模的算例采用該算法進行求解分析，仿真計算結(jié)果對比見表6。

表6 仿真計算結(jié)果對比分析

在相同時刻對不同規(guī)模的動態(tài)客戶進行分析可以看出，動態(tài)客戶數(shù)量小于50時，算法的穩(wěn)定性較高，可得出較好的優(yōu)化結(jié)果；當(dāng)問題規(guī)模增大時，最優(yōu)解的搜索成功率下降，并且計算時間和迭代次數(shù)較長，主要是因為該集成算法的時間復(fù)雜度為O(n5)，隨著動態(tài)客戶節(jié)點數(shù)的增加，計算規(guī)模成5次方增長。因此，本文所提出的集成算法適用于求解中小規(guī)模動態(tài)問題，并且全局搜索能力強。

4.3 算法性能分析

與禁忌搜索(TS)和遺傳算法(GA)進行對比，驗證本文算法對地鐵和貨車聯(lián)運的動態(tài)配送選點-路徑問題的求解效果見圖11，算法性能對比見表7。

圖11 算法收斂圖比較

表7 本文算法與TS和GA的算法性能對比

通過比較分析，本文算法的搜索成功率較高，能夠獲得較好滿意解。對于TS算法求解，雖然在收斂速度和計算時間方面占有優(yōu)勢，但容易陷入局部最優(yōu)，解的質(zhì)量不高，而且該算法的搜索成功概率較低。對于GA算法求解，雖然同樣可以搜索到較好滿意解，但在搜索成功率、計算時間等方面與本文算法相比結(jié)果較差。這是因為本文算法對內(nèi)層蟻群算法的概率選擇操作進行了改進，保證了解的可行性，最大程度地縮小了搜索空間，提高算法運行效率和精確度，但本文算法為獲取全局解以及外層遺傳算法的多樣性，在收斂速度和計算時間方面還需進一步提高。

5 結(jié)論

本文對共享公共交通工具和傳統(tǒng)配送工具聯(lián)合運輸?shù)膭討B(tài)配送問題進行了研究，在考慮地鐵共享剩余運能、貨車容量、客戶服務(wù)時間窗、多轉(zhuǎn)運點接送等因素基礎(chǔ)上，建立了兩階段動態(tài)整體優(yōu)化模型；為了提高求解效率，提出了雙層啟發(fā)式集成算法，外層遺傳算法改進了截取掩碼交叉變異算子，解決了轉(zhuǎn)運點、貨車選擇問題，同時保證了解的多樣性；內(nèi)層蟻群算法改進了鍵值對編碼結(jié)構(gòu)和多點接送概率選擇操作，優(yōu)化了接運配送路徑。設(shè)計仿真算例驗證了模型和算法的有效性，與目前傳統(tǒng)貨車動態(tài)配送模式進行了比較，研究表明在實際中當(dāng)高時效動態(tài)客戶需求產(chǎn)生時，應(yīng)用本文所提出的數(shù)學(xué)模型進行處理比傳統(tǒng)動態(tài)配送模式能夠更快速、精準(zhǔn)的響應(yīng)動態(tài)需求，同時可以有效降低整體配送成本，是DVRP理論的擴展，也是一種共享型經(jīng)濟模式的體現(xiàn)，對指導(dǎo)實際應(yīng)用具有一定的理論意義。同時地鐵作為客運交通工具，運送貨物可通過專用帶輪貨箱、專用安檢通道、設(shè)置隔倉、隔離卡扣等技術(shù)手段減少對乘客的影響。本文僅考慮新增需求的地鐵和貨車聯(lián)運動態(tài)配送問題，沒有考慮需求變更、取消需求等情況。此類問題對基于地鐵-貨車聯(lián)運的動態(tài)配送問題的研究必不可少，是下一步需要研究的內(nèi)容。