摘" 要：目前，地面車輛配送難以滿足日益增長的貨運需求，地下物流將成為未來解決貨運問題的有效方式。地鐵作為現(xiàn)有的地下資源，可依托其開展地下貨運配送。以貨物在地鐵網絡中送達時間最短為目標，考慮地鐵列車發(fā)出時間表、換線點選取、換線點時間窗等現(xiàn)實約束，構建考慮換線時間窗的地鐵網絡配送路徑優(yōu)化模型。將地鐵站點間的運行時間和換線時間作為權重，引入換線時間窗限制，并設計改進Dijkstra算法求解該模型。文章基于武漢市地鐵網絡的算例驗證了所提模型的可行性，該模型更貼合地鐵網絡的現(xiàn)實情況，且能有效地提高配送效率。

" 關鍵詞：路徑優(yōu)化；改進Dijkstra算法；硬時間窗；地鐵換線

" 中圖分類號：F252.14" " 文獻標志碼：A" " DOI：10.13714/j.cnki.1002-3100.2024.21.006

Abstract： At present， ground vehicle distribution is difficult to meet the growing demand for freight transportation， and underground logistics will become an effective way to solve freight transportation problems in the future. As an existing underground resource， the subway can be relied on to carry out underground freight distribution. Taking the shortest delivery time of goods in the subway network as the goal， and considering the subway train issuing schedule， line-change point selection， line-change point time window and other realistic constraints， we construct the subway network distribution path optimization model considering the line-change time window. The running time between subway stations and line change time are taken as weights， line change time window restriction is introduced， and an improved Dijkstra's algorithm is designed to solve the model. This paper verifies the feasibility of the proposed model based on the example of Wuhan metro network， which is more suitable for the reality of metro network and can effectively improve the distribution efficiency.

Key words： route optimization; improvement of Dijkstra algorithm; hard time window; change line

0" 引" 言

隨著生活節(jié)奏的不斷加快，現(xiàn)有的地面配送方式難以滿足目前城市中心高密度的貨運需求。因此，需要探索新的城市配送模式來減輕交通擁堵，提高配送效率。1990年，國外就開始關注城市地下物流系統(tǒng)（Underground Logistics System， ULS），其又稱之為地下貨運系統(tǒng)[1]。無論是管道式與隧道式ULS，新建ULS的建造成本、運營成本以及施工風險均較高[2]。而地鐵作為現(xiàn)有的地下資源，可以直接被用于運輸和配送貨物。荷蘭最先對地鐵貨運進行了實踐性的嘗試[3]。目前，日本東京都會在早高峰前使用輕軌運送貨物，日本企業(yè)YAMATO也已經實現(xiàn)了利用地鐵運送貨物[4]。Dampier A et al.[5]從地鐵系統(tǒng)的優(yōu)勢、技術等不同方面分析了利用地鐵進行配送服務的必要性和可行性。劉崇獻[6]分析了利用地鐵作為城市物流系統(tǒng)的可行性以及技術要求。He K et al.[7]提出了基于軌道交通的城市物流配送系統(tǒng)概念模型，并設計了成本計算模型和線路選擇策略。Masson R et al.[8-9]提出在客運低峰實施客貨混運，并在夜晚開通貨運專列。

" 針對基于地鐵進行物流配送的研究，彭玫貞等[10]分析了地下物流系統(tǒng)與地鐵在技術操作、網絡布局、實施與運營上的異同，提出二者協(xié)同運輸具有較大可行性。周曉曄等[11]提出了地鐵與貨車聯(lián)合運輸，通過地鐵配送路徑設計改進自適應遺傳算法求解。崔瑤等[12]提出了基于地鐵-貨車聯(lián)動的動態(tài)選點-路徑問題，并針對模型特征設計了兩階段啟發(fā)式算法和雙層啟發(fā)式集成算法，有效提高了配送的精準性。周芳汀等[13]以配送時間最小化為目標建立了地鐵貨運配送選址-路徑規(guī)劃模型，設計了改進遞歸粒度算法進行求解。Ghilas V et al.[14]考慮時間窗下預定路線的取貨和交付問題，并提出了自適應大鄰域搜索啟發(fā)式算法來解決PDPTW-SL問題。楊婷等[15]提出了帶軟時間窗的地鐵網絡路徑優(yōu)化問題，并利用地鐵客貨共線的特點實現(xiàn)地鐵與貨車的聯(lián)合運輸。周芳汀等[16]研究了帶時間窗的地鐵網絡配送路徑優(yōu)化問題，整體優(yōu)化地鐵與地上交通銜接的轉運點選擇，以及后續(xù)的路面配送路徑。

" 地鐵網絡配送路徑優(yōu)化問題是一個經典的組合優(yōu)化問題[17]，雖然已有研究考慮了客戶收貨時間窗和單條地鐵線路的配送路徑優(yōu)化問題，但均未考慮到地鐵網絡中多條線路之間產生的換線因素對時間總成本的影響。因此，本文以地鐵網絡為對象，考慮現(xiàn)實約束對地鐵配送路徑的影響，利用列車發(fā)車時刻表界定換線時間窗限制，綜合優(yōu)化地鐵列車班次的客戶分配、換線點的選取及地鐵配送路徑選擇。構建考慮換線硬時間窗的地鐵網絡路徑優(yōu)化模型，并設計改進Dijkstra算法進行求解。

1" 地鐵網絡配送路徑優(yōu)化問題

1.1" 問題描述

在由若干地鐵線路組成的地鐵物流網絡中，有V個地鐵初始點、V個換線點和V個終點。地鐵線路、列車時間表、時間窗均已知。貨物從地鐵初始站點進入地鐵網絡，需要途經多個地鐵站點運送至終點。如何對地鐵線路進行規(guī)劃，以最小化貨物配送時間成本是本文研究重點。

" 由于地鐵線路網絡中存在多個換線點，貨物在途經換線站點時，需要對地鐵線路進行重新決策規(guī)劃，一旦選擇換線，則會產生貨物搬運時間和換線等待時間。為減少貨運需求的延遲時間，設置換線硬時間窗約束，即貨物需要在規(guī)定時間內完成換線搬運活動。

1.2" 問題假設

" 不失一般性，該問題的假設為：

（1）地鐵換線站是貨物不出地鐵站就可直接轉換到另一條線路的站點，一般為地鐵換乘站；

（2）地鐵列車按照運行時間表發(fā)車，每列地鐵列車能夠裝下所需貨物；

" （3）貨物沒有固定分配給哪一個換線站點；

（4）貨物到達換線站必須滿足換線站的硬時間窗限制；

" （5）貨物不可以迂回、返回行走，且地鐵列車?？繒r間能夠滿足正在等待上車的貨物全部被搬運上列車。

1.3" 參數(shù)設置

基于上述問題描述與假設，模型參數(shù)符號及含義如表1所示。

1.4" 模型構建

minZ=txy+FtaZ" " " " " " " " " " " " " " " " " " " （1）

xq≤Q" " i∈V， k∈V， j∈V" " " " " " " " " " " " " " " " "（2）

p+t-1-

xM≤t" " i∈V， k∈V， j∈V" " " " " " " " " " " " " " " " （3）

t+t-1-

yM≤E" " k∈V， j∈V" " " " " " " " " " " " " " " " " "（4）

t=t+h" " k∈V" " " " " " " " " " " " " " " " " " " " " "（5）

L=E+t" " k∈V" " " " " " " " " " " " " " " " " " " " " "（6）

e≤E≤l" " k∈V" " " " " " " " " " " " " " " " " " " " " （7）

x≤a" " i∈V， k∈V" " " " " " " " " " " " " " " " " " " "（8）

a≤N" " k∈V" " " " " " " " " " " " " " " " " " " " " "（9）

x=1" " i∈V， k∈V" " " " " " " " " " " " " " " " " " " （10）

x∈0，1" " i∈V， k∈V" " " " " " " " " " " " " " " " " " " （11）

y∈0，1" " k∈V， j∈V" " " " " " " " " " " " " " " " " " " （12）

a∈0，1" " k∈V" " " " " " " " " " " nbsp; " " " " " " " " " （13）

F∈0，1" " k∈V" " " " " " " " " " " " " " " " " " " " " （14）

其中：式（1）為最小化地鐵配送總成本，第一部分為運輸時間成本，第二部分為地鐵換線時間成本。式（2）為地鐵列車容量限制。式（3）為線路O上r列車運載貨物到達換線站k的時間約束，式（4）為貨物到達中轉站k且在此點中轉的時間約束，貨物在k點完成中轉的時間應小于線路L上列車r'的到達時間。式（5）為在中轉站k處，列車r'的到達時間和出發(fā)時間約束，在此時間點內，貨物能完成全部裝車活動。式（6）為在換線點k處點換線活動開始時刻和中止時刻關系。式（7）為換線點k的時間窗限制。式（8）每個中轉站僅被裝載該貨物的地鐵訪問一次。式（9）為換線站數(shù)量限制。式（10）從初始站到終點站之間只能選擇一條運輸路徑。式（11）至式（14）為決策變量的取值。

2" 改進Dijksra算法

地鐵網絡路徑優(yōu)化問題是NP-hard問題[17]，而考慮換線時間窗的地鐵網絡路徑優(yōu)化問題則更為復雜，同樣具有NP-hard特性。Dijksra算法優(yōu)點在于它能夠找到最短路徑，并且對于權重非負的圖，能夠保證結果的正確性，被廣泛用于求解最短路問

題[18-20]。傳統(tǒng)的Dijkstra算法以節(jié)點間的長度作為權值進行最短路搜索。在多條地鐵線路組成的地鐵網絡中，當初始點和終點在同一線路時，該方式可以快速獲得最優(yōu)解。然而，當初始點和終點在不同線路時，貨物需要在換線點進行換線。不同地鐵線路的運行速度可能不同，這可能導致地鐵站點間線段長，但運輸時間更短的情況。此外，當貨物需要換線時，所花費的運輸時間也會增加。同時，列車班次也會影響換線時間和貨物在站臺的等待時間。因此，需要考慮貨物所在的線路要素和換線點決策。為了解決考慮換線時間窗地鐵網絡路徑優(yōu)化問題，本文設計了改進的Dijkstra算法進行優(yōu)化求解。

2.1" 算法思路

在地鐵網絡中，存在多個可供選擇的換線點。因此，在換線點處設置換線時間窗約束，當貨物選擇在某個換線點進行換線時，要求裝載貨物的列車必須在換線時間窗內到達該換線點，并開始進行換線活動，以使配送時間最短，地鐵網絡如圖1所示。

如圖2所示，假設有一批貨物需要在站1處換線運送至站3，并要求在時間窗規(guī)定時間內，即時刻0到時刻5完成換線作業(yè)。已知地鐵列車發(fā)車時間表，如果希望貨物在時刻5登上班次1，那么根據(jù)倒推可知，在時刻0該批貨物必須到達站1。

如果在時刻0之后到達，那么該批貨物只能由班次2和班次3運送，這將導致貨物的等待時間增加。硬時間窗反映了貨運的及時性，即貨物在換線站的等待時間不超出某個范圍。如圖2陰影部分所示，假設貨物在站1換線，如果無法在陰影區(qū)間內到達站臺并完成換線活動，那么貨物將無法登上班次1，即要求貨物不能晚于班次1離開站1的時間。

" 本文通過標記地鐵站點之間的連接邊來計算地鐵的運行時間。每個站點間的連接邊信息包含其所在線路，用于確定換線點和計算貨物換線所需的時間。通過記錄標記后的路線集合和對應的時間花費集合，可以得到當前線路的總時間。當起始站為換線站時不計算換線時間也不考慮換線時間窗限制。

" 在搜索過程中，首先確定起始站和終點站所在線路，并標記所有可換線的換線點。然后，對于每個站點，按照最短時間到達的標準進行標記，形成初步的最短路徑。同時，記錄每個站點的列車到達時間和承載貨物的列車到達每個站點的時間。

" 最后，根據(jù)同一線路站點間運行時間由長到短以及不同線路相差一個換線站時間常量之差進行回溯。在回溯的過程中，需要考慮列車班次帶來的時間差是否滿足時間窗限制，以確定在哪個換線點進行換線，比較每個換線點的到達時間與時間窗要求，選擇滿足時間窗限制且等待時間最短的換線點作為最優(yōu)選擇。這樣可以確保貨物能夠在規(guī)定時間內完成換線，并使得整體運輸時間最短。

" 本文基于Dijkstra算法的改進思路，引入不同線路的換線時間權重和換線點選擇作為新的決策機制，并引入時間窗約束，而不僅僅考慮路徑長度。這使得算法適用于考慮換線時間窗的地鐵物流網絡路徑優(yōu)化問題。傳統(tǒng)的Dijkstra算法在存儲數(shù)據(jù)時大多使用鄰接矩陣，而這種方式不僅空間浪費多，算法時間復雜度也較高。本文使用鄰接表法存儲數(shù)據(jù)，并利用優(yōu)先隊列法排序，在優(yōu)化儲存結構的同時提高了算法的運行速度。

2.2" 算法步驟

" 步驟1：設置兩個不同的節(jié)點集合S和T，集合S表示已經被標記過的節(jié)點集合，即已經找到的最短路徑的節(jié)點，集合T表示未被標記過的節(jié)點集合，即未找到最短路徑的節(jié)點。

" 步驟2：初始化，集合S中只包含起始點i。

" 步驟3：分別在集合T和集合S中尋找與起始點i直接連接的點，并比價二者與起始點i的權重選擇，權重最小的點做標記，將其加入到集合S中。

" 步驟4：將上一步驟中連接值最小的點作為新的起始點，并在T中尋找與之直接相連的點，計算兩點間的權重g，尋權重更小的點，若gi，jgt;gk，j+ gi，k，則意味著起始點i經過節(jié)點k到節(jié)點j的代價比起始點i直接到j的代價要小，因此將gi，j更新為gk，j+gi，k，并將新的節(jié)點k加入到集合S中。

" 步驟5：當訪問到的點為換線點時，判斷與之相連的前一個點和后一個點所在線路，該線路列車到達換線點時間能否滿足時間窗約束。若能則計算換線時間和等待時間，若不能，等待下一趟列車或更換換線點，比較不同換線點之間路徑的總時間。選擇時間權重最小的換線點加入集合S中。

" 步驟6：重復步驟3至步驟5，最終可找到源點i到所有點的權重值最小的路徑。

" 步驟7：依次輸出起始點、中間點、終點連成路徑。

2.3" 算例說明

" 假定有A、B兩條地鐵線路，a、b兩個換線點。貨物從初始站出發(fā)運輸至終點，現(xiàn)有兩條可選路徑如圖3所示。選擇路線A、B，當列車均在0時刻出發(fā)時，在a處換線，貨物需要等待4分鐘、b處換線需要等待5分鐘，且均在31時刻到達。但任意調節(jié)某一趟列車發(fā)車時間使B在2時刻出發(fā)，A仍然在0時刻出發(fā)，貨物運輸總時間發(fā)生變化如表2所示：當在a處換線時需要等待6分鐘在33時刻到達，而在b處換線則只需要等待1分鐘在26時刻到達。

2.4" 算例說明

以武漢市為例，選取了5個遠離市中心但緊鄰地鐵的配送中心，客戶地理位置隨機選取，換線時間窗在06：00，24：00范圍服從隨機分布，地鐵站點均以阿拉伯數(shù)字進行編號。貨物在換線站的搬運時間為3min，地鐵列車在站臺停靠時間足夠長，以確保貨物全部搬運上車。被選取的地鐵線路的發(fā)車間隔和速度如表3所示。

2.5" 結果分析

本文采用遺傳算法和改進Dijsktra算法分別進行求解，兩種算法的優(yōu)化結果如表4所示。經過分析比較，改進Dijsktra算法的速度更快，收斂速度也更快、最優(yōu)解的質量也更高。本文在Dijsktra算法中引入新的權重來作為決策原則，在搜索過程中多循環(huán)一次搜索到的節(jié)點。使得復雜程度從OV上升到OV。

根據(jù)上述數(shù)據(jù)，分別計算了20個客戶點的地鐵和貨車兩種配送的最優(yōu)方案如表5至表7所示，表格中括號內數(shù)值為貨物到達該站點的時間。根據(jù)不同線路之間的發(fā)車間隔和運輸時間，確定貨物的發(fā)出時間和列車裝載班次。在時間窗約束下，通過改變列車班次來減少貨物在站臺的等待時間，并選擇其他換線點來優(yōu)化配送方案。由于該方法非常依賴時間這一緯度，所以當改變發(fā)車時間時，選擇裝載貨物的地鐵列車也不同，因此在不同時間點最優(yōu)解可能會發(fā)生變化。因此表6的配送方案是在運行30次后，取被選中最多次的路徑值。通過多次實驗，發(fā)現(xiàn)在列車發(fā)車間隔越大的情況下，考慮換線時間窗的優(yōu)化結果更明顯。

3" 結" 論

本文構建了考慮換線時間窗的地鐵物流網絡路徑優(yōu)化模型，建立了以貨物運輸總時間成本最短為目標的數(shù)學模型，并設計了改進的Dijkstra算法求解該問題?；谖錆h市地鐵網絡的算例結果表明，考慮換線時間窗的地鐵物流網絡路徑優(yōu)化能夠提供更加準時高效的配送服務，合理優(yōu)化地鐵網絡配送路徑。未來可考慮地鐵列車的容量以及各站點的儲存能力，以及多線路地鐵網絡配送路徑優(yōu)化問題。

參考文獻：

[1]" VISSER J G S N. The development of underground freight transport： An overview[J]. Tunnelling and Underground Space Technology， 2018，80：123-127.

[2] 徐國峰. 城市地下物流系統(tǒng)構架研究[D]. 武漢：華中科技大學，2012.

[3]" KIKUTA J， ITO T， TOMIYAMA L， et al. New subway-integrated city logistics szystem[J]. Procedia-social and" Behavioral Sciences， 2012，39：476-489.

[4]" DIZIAIN D， TANIGUCHI E， DABLANC L， et al. Urban logistics by rail and waterways in France and Japan[J]. Procedia-social and Behavioral Sciences， 2014，125：159-170.

[5]" DAMPIER A， MARINOV M. A study of the feasibility and potential implementation of metro-based freight transportation in newcastle upon tyne[J]. Urban Rail Transit， 2015，1：164-182.

[6] 劉崇獻. 北京地鐵晚間和非高峰期用作城市物流系統(tǒng)探討[J]. 城市發(fā)展研究，2011，18（6）：122-124.

[7]" HE K， SHAO J， LIU Y， et al. Conceptual design of rail transit based urban logistics delivery system[C] // 2008 6th IEEE International Conference on Industrial Informatics. IEEE， 2008：221-226.

[8]" MASSON R， ROPKE S， LEHUéDé F， et al. A branch-and-cut-and-price approach for the pickup and delivery problem with shuttle routes[J]. European Journal of Operational Research， 2014，236（3）：849-862.

[9]" MASSON R， TRENTINI A， LEHUéDé F， et al. Optimization of a city logistics transportation system with mixed passengers and goods[J]. EURO Journal on Transportation and Logistics， 2017，6（1）：81-109.

[10] 彭玫貞，陳一樹，等. 城市地下物流系統(tǒng)探析[J]. 江蘇科技信息，2017（19）：65-67.

[11] 周曉曄，崔瑤，何亮，等. 基于地鐵—貨車聯(lián)運的物流配送路徑優(yōu)化[J]. 交通運輸系統(tǒng)工程與信息，2020，20（3）：111-117.

[12] 崔瑤，周曉曄，何亮. 基于地鐵—貨車聯(lián)運的動態(tài)配送選點-路徑問題[J]. 鐵道學報，2023，45（1）：9-19.

[13] 周芳汀，周國華，張錦. 基于地鐵開展城市配送的選點-路徑問題[J]. 控制與決策，2018，33（7）：1247-1254.

[14]" GHILAS V， DEMIR E， WOENSEL T V， et al. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows and scheduled lines[J]. Computers and Operations Research， 2016，72：12-30.

[15] 楊婷，鄭長江，馬庚華. 基于地鐵的帶時間窗地下物流路徑優(yōu)化研究[J]. 華東交通大學學報，2019，36（4）：67-74.

[16] 周芳汀，張錦，周國華. 帶時間窗的地鐵配送網絡路徑優(yōu)化問題[J]. 交通運輸系統(tǒng)工程與信息，2018，18（5）：88-94.

[17] 周芳汀. 基于地鐵的城市配送網絡選點及路徑優(yōu)化研究[D]. 四川：西南交通大學，2021.

[18] 王樹西，李安渝. Dijkstra算法中的多鄰接點與多條最短路徑問題[J]. 計算機科學，2014，41（6）：217-224.

[19]" SEDE?O-NODA A， COLEBROOK M. A biobjective Dijkstra algorithm[J]. European Journal of Operational Research， 2019，276（1）：106-118.

[20] 張渭軍，王華. 城市道路最短路徑的Dijkstra算法優(yōu)化[J]. 長安大學學報（自然科學版），2005（6）：62-65.

收稿日期：2023-10-26

基金項目：教育部人文社會科學研究規(guī)劃基金項目（21YJAZH050）；湖北省教育廳哲學社會科學研究重點項目（22D022）；武漢市知識創(chuàng)新專項曙光計劃項目（2022010801020317）；湖北省高等學校優(yōu)秀中青年科技創(chuàng)新團隊計劃項目（T2022003）；武漢科技大學資助項目“智慧物流數(shù)字運營平臺開發(fā)研究”（2022H20537）

作者簡介：彭秀秀（1998—），女，湖北黃石人，武漢科技大學管理學院碩士研究生，研究方向：物流系統(tǒng)優(yōu)化；劉" 翱（1987—），本文通信作者，男，江西吉安人，武漢科技大學管理學院，副教授，研究方向：管理優(yōu)化與決策；李儒博（1994—），男，湖北黃石人，武漢科技大學管理學院博士研究生，研究方向：物流系統(tǒng)優(yōu)化；任" 亮（1985—），男，湖北黃岡人，武漢科技大學管理學院，講師，研究方向：管理優(yōu)化與決策。

引文格式：彭秀秀，劉翱，李儒博，等. 考慮換線時間窗的地鐵網絡配送路徑優(yōu)化問題[J]. 物流科技，2024，47（21）：24-28，38.