地鐵-貨車聯運的地鐵轉運站選址算法比較

摘 要：針對傳統算法解決復雜非線性規劃收斂速度慢、尋優精確度低等問題，文章介紹并設計了模擬退火算法、自適應免疫遺傳算法以及Python調用COPT求解器三種算法對地鐵-貨車聯運的地鐵轉運站選址問題進行求解。最后，以西安市地鐵網絡為例，分別運用這三種算法對地鐵轉運站選址問題進行求解，并對求解結果進行比較分析。結果表明，Python調用COPT求解器的算法在解決地鐵轉運站選址問題時，相較于自適應免疫遺傳算法和模擬退火算法有著卓越的計算效能和精確度。

關鍵詞：地鐵貨運；選址問題；COPT求解器；自適應免疫遺傳算法；模擬退火算法

中圖分類號：F572 文獻標志碼：A DOI：10.13714/j.cnki.1002-3100.2025.02.006

Abstract： Aiming at problems such as slow convergence speed and low accuracy of optimization when using the traditional algorithms to solve the problems of complex nonlinear planning， this paper introduces and designs three algorithms， namely， simulated annealing algorithm， adaptive immune genetic algorithm， and Python calling the COPT solver， for solving the metro-truck intermodal transportation metro transfer station siting problem. Finally， taking Xi'an metro network as an example， these three algorithms are applied to solve the metro transfer station siting problem， and the results are compared and analyzed. The results show that the Python algorithm calling the COPT solver has superior computational efficiency and accuracy compared with the adaptive immune genetic algorithm and simulated annealing algorithm in solving the metro transfer station siting problem.

Key words： metro freight; siting problem; COPT solver; adaptive immune genetic algorithm; simulated annealing algorithm

0 " "引 " "言

隨著電子商務的快速發展，城市物流需求量激增，多頻次、小批量、高時效性的物流配送是現代物流業適應現代市場需求的重要發展方向。傳統的貨車配送方式，有著占用道路交通資源比例大、周轉次數多和遭到限行等特點，不僅降低了配送的及時性，且更容易造成城市中心區的交通擁堵和環境污染。地鐵具有大運量、高時效性、低污染和網絡化運營的特點，滿足國家節能減排，綠色共享的物流發展趨勢。同時，開展基于地鐵-貨車聯運配送的城市物流新型配送模型，不僅能夠實現對非高峰時段地鐵資源的充分利用，還能通過貨運增加收入，彌補地鐵運營虧損，因此開展基于地鐵-貨車聯運配送的城市物流新型配送模式研究十分必要。

目前，在關于地鐵-貨車聯運配送的研究中，地鐵-貨車聯運配送的物流網絡選址布局和路徑優化是探討最為廣泛且成果最為豐富的領域。周芳汀等[1]以成都市地鐵網絡為例，建立以總成本最小化為目標函數的基于地鐵網絡的城市配送系統轉運站選址模型，設計并改進模擬植物生長算法對模型進行求解。米雪麗[2]建立總成本最小化的依托地鐵的城市物流網絡中轉節點選址模型和線路優化模型，并分別使用免疫遺傳算法和自適應遺傳算法對模型進行求解。王寅[3]提出了引入軌道交通之后的城市物流配送中心的雙層規劃選址模型，并設計了遺傳算法對雙層規劃模型進行求解。聶文聰等[4]研究依托地鐵的城市物流配送的可行性及其運營模式，提出了“灌溉”概念的城市單向軌道配送模式，建立雙層規劃選址模型，并用遺傳算法對模型進行求解。張秋星[5]在對城市物流準確分析和精準預測的基礎上，建立了基于地鐵的城市配送中心選址模型，并采用遺傳算法對模型進行求解。然而，從現代物流的全局角度來看，該領域的研究仍然處于初級階段，許多先進的優化技術、算法尚未在地鐵-貨車聯運配送的物流網絡選址布局和路徑優化的研究中得到應用和提及。

現有研究對地鐵-貨車聯運配送的地鐵轉運站選址模型的求解方法，大多為遺傳算法、粒子群算法等啟發式算法。本文通過整合道路網絡和地鐵網絡，構建總成本最小化的地鐵轉運站選址模型，分別采用MATLAB設計模擬退火算法、MATLAB設計自適應免疫遺傳算法以及Python調用COPT求解器三種算法對該選址模型進行求解，并進行對比分析。最后，以西安市地鐵網絡為例驗證算法和模型的可行性和有效性。

1 " "模型構建

1.1 " "問題描述

基于地鐵-貨車聯運配送的地鐵轉運站選址問題可描述如下：貨物通過貨車、飛機等大宗貨物運輸方式運輸至位于城市郊區的物流中心，再從物流中心運輸至地鐵始發站的地鐵配送站進入地鐵系統，通過地鐵線路配送至各個地鐵轉運站，最后通過第三方物流公司，以小貨車、三輪車等配送方式配送至驛站再至客戶，地鐵-貨車聯運配送的城市物流配送模式見圖1。

1.2 " "地鐵轉運站選址模型構建

1.2.1 " "問題假設

備選的地鐵轉運站均為地鐵中轉站；

從任意一個地鐵配送站向需求點配送貨物，都必須經過一個地鐵轉運站；

任意一個需求點只能由一個地鐵轉運站進行配送；

單位貨物單位距離地鐵運輸成本小于單位貨物單位距離貨車運輸成本。

1.2.2 " "參數定義

DM、DN、DQ分別表示地鐵轉運站集合、需求點集合以及地鐵配送站集合，表示地鐵配送站，表示地鐵轉運站，表示需求點。表示地鐵轉運站個數，表示需求點個數， 表示地鐵配送站個數；表示地鐵轉運站最大覆蓋范圍；表示開放地鐵轉運站的個數；表示地鐵配送站經過地鐵轉運站至需求點 j 的運量；表示單位貨物單位距離地鐵運輸成本；表示公路與地鐵的單位成本比值；表示單位貨物單位距離公路運輸成本；表示單位貨物轉運成本；表示單位貨物換線成本；表示地鐵轉運站固定運營成本；表示地鐵配送站至地鐵轉運站的地鐵線路長度；表示地鐵轉運站至需求點的距離；表示從地鐵配送站至地鐵轉運站所選地鐵線路的換線次數；表示地鐵轉運站的最大服務能力。

決策變量表示是否從地鐵配送站經過地鐵轉運站至需求點，是為1，否為0；決策變量表示是否開放地鐵轉運站，是取1，否取0。

1.2.3 " "模型建立

a.目標函數

所建模型為混合整數規劃模型，其中，式（1）為目標函數，表示地鐵-貨車聯運配送總成本最小，第一項為地鐵運輸成本和貨車運輸成本，第二項為換線成本，第三項為轉運成本，第四項為地鐵轉運站點固定運營成本；式（2）表示地鐵轉運站的開放個數限制；式（3）表示只有地鐵轉運站開放時，貨物才能通過地鐵轉運站進行配送；式（4）表示地鐵轉運站的覆蓋范圍限制；式（5）表示地鐵配送站至客戶只能選擇一條線路進行配送；式（6）表示備選地鐵轉運站的最大服務能力；式（7）表示決策變量的取值范圍；式（8）表示若地鐵轉運站未開放則地鐵配送站不通過該地鐵轉運站向需求點配送貨物。

2 " "算法設計

基于地鐵-貨車聯運配送的地鐵轉運站選址問題，為選址分配問題，屬于NP-hard問題，本文將采用模擬退火算法、自適應免疫遺傳算法以及Python調用COPT三種算法進行地鐵轉運站和客戶分配的優化。

2.1 " "模擬退火算法

模擬退火算法是一種基于概率的啟發式隨機搜索算法，它模仿金屬退火過程中的物理現象，通過控制一個溫度參數來平衡解的接受概率，使得算法在高溫時能夠探索廣泛的解空間，其又因概率突跳特性能在解空間中隨機尋找目標函數的全局最優解，即在局部最優解能概率性地跳出并隨著溫度參數的下降最終趨于全局最優解[6-7]。模擬退火算法具體步驟如下。

Step1：生成初始解，并設定初始溫度參數、終止溫度、內循環迭代次數、退火速率等。

Step2：進行內循環，即進行Step3至Step5。

Step3：生成新解。

Step4：計算能量差，即新解的函數值與當前解的函數值的差，并采用Metropolis準則判斷是否接受新解。

Step5：如果達到內循環迭代次數，則輸出當前解作為最優解。

Step6：根據退火速率將溫度參數減小。

Step7：執行外循環即返回Step2，直至溫度參數小于終止溫度。

2.2 " "自適應免疫遺傳算法

自適應免疫遺傳算法是一種結合了遺傳算法和免疫算法優點的優化算法。在遺傳算法的基礎上，自適應免疫遺傳算法增加了自適應調整交叉和變異概率的能力以及免疫算法的記憶和多樣性維持機制，有效避免了早熟收斂現象，增強了算法的全局搜索能力和局部搜索能力，使其在解決復雜優化問題時更加高效和穩定[8-11]。自適應免疫遺傳算法具體步驟如下。

Step1：編碼。編碼是表示問題的解空間的方法，自適應免疫遺傳算法的編碼發生主要有二進制編碼、實數編碼、浮點數編碼等。Step2：生成初始種群，根據使用編碼，確定種群的大小、記憶庫大小、迭代次數等。Step3：計算個體適應度、濃度以及激勵度。Step4：選擇激勵度最大的前指定個抗體，加入記憶庫，將記憶庫更新。Step5：進行復制、交叉和變異。Step6：將復制、交叉和變異后得到的抗體與記憶庫中抗體結合形成新的抗體。Step7：返回步驟Step3，直至達到最大迭代次數。

2.3 " "Python調用COPT

杉數公司獨立研發了一款名為COPT（Cardinal Optimizer）的高效數學規劃求解器，專門用于處理大規模優化問題。COPT具備解決多種復雜數學規劃問題的能力，包括大規?；旌险麛狄巹?、線性規劃（采用單純形法和內點法）、半定規劃、混合整數二階錐規劃、混合整數凸二次規劃以及混合整數凸二次約束規劃問題。Python調用COPT求解器具體步驟如下。

Step1：導入COPT模塊。使用import coptpy as cp以及from coptpy import COPT將COPT模塊導入。

Step2：創建求解環境和模型。使用創建求解環境，使用創建模型。

Step3：定義優化問題。使用 COPT 提供的類和方法來定義優化問題，主要包括問題的決策變量、約束條件以及目標函數。

Step4：求解優化問題。使用對優化問題進行求解。

3 " "案例分析

3.1 " "數據分析

以西安市地鐵網路為例，綜合考慮貨車-地鐵銜接便利性、地鐵線路通達度、地鐵站點規模以及客戶需求與分布等因素，選取常寧宮站、創新港站以及草灘站作為地鐵配送站，依次編號為1，2，3。選取西安市二環線內的地鐵中轉站作為備選地鐵轉運站，共計9個，依次編號為P1，P2，...，P9。再選取西安市二環內的居住區、學校等地作為需求點，共32個，依次編號為1，2，...，32。地鐵配送站和備選地鐵轉運站分布見圖2，并將二環線映射至圖2中，各備選地鐵轉運站和需求點經緯度見表1。

依據公鐵聯運相關參數、地鐵票價、貨車油耗等進行類比估計，該選址分配模型的參數取值見表2，其中從地鐵配送站至地鐵轉運站所選地鐵線路的換線次數Tik、地鐵配送站至地鐵轉運站的地鐵線路長度dik、地鐵轉運站k至需求點j的距離dkj以及客戶需求量均已知，其中客戶總需求量為640件。

3.2 " "結果與分析

3.2.1 " "MATLAB設計模擬退火算法

使用MATLAB R2022a設計模擬退火算法對該案例進行求解，設置初始溫度為100，終止溫度為0.01，內循環迭代次數為100，降溫系數為0.95。算法迭代142次后最優解不再發生改變，求得最優目標函數值為6 606.7，其中地鐵轉運站固定運營成本占總成本的45.41%，模擬退火算法迭代曲線見圖3。

迭代總耗時35.6s，得到最終地鐵轉運站選址方案為P2，P3，即五路口站和北大街站，各地鐵轉運站與需求點的對應關系見圖4。

3.2.2 " "MATLAB設計自適應免疫遺傳算法

使用MATLAB R2022a設計自適應免疫遺傳算法對該案例進行求解，設置種群規模為100，記憶庫容量為20，最大迭代次數為600。求得最優目標函數值為

6 460.8，其中地鐵轉運站固定運營成本占總成本的46.43%。最優迭代曲線見圖5。由圖5可知，算法迭代至182代后目標函數值不再發生改變。

迭代總耗時422.4s，得到最終地鐵轉運站選址方案為P2，P3，即五路口站和北大街站，各地鐵轉運站與需求點的對應關系見圖6。

3.2.3 " "Python調用COPT求解器

使用Python調用版本為v7.0.2的COPT求解器，對該混合整數規劃問題進行求解，求解時間為1.4s，最優目標函數值為6 120.3，其中轉運站固定運營成本占總成本的49.02%，得最優地鐵轉運站選址結果為P3，P8，即北大街站和南稍門站，轉運站與需求點關聯圖如圖7所示。

通過MATLAB設計模擬退火算法、MATLAB設計自適應免疫遺傳算法和Python調用COPT求解器三種算法對問題進行求解，三種算法在單次總配送快遞件數為640件的情況下，迭代10次計算結果對比如表3所示。

對比表3中最優解可知，Python調用COPT求解器求得的最優解相較于模擬退火算法和自適應免疫遺傳算法求得的最優解各優化了5.27%和7.36%，這一結果表明，COPT求解器在處理該問題時，不僅能夠找到更接近全局最優解的解，而且優化效率也相對較高。對比表3中平均值可知，Python調用COPT求解器的穩定性相較于模擬退火算法和自適應免疫遺傳算法更好。對比表3中算法運行時間可知，Python調用COPT求解器的最優運行時間占模擬退火算法的最優運行時間的3.93%，僅占自適應免疫遺傳算法的最優運行時間的0.33%，可見在計算效率上Python調用COPT求解器有著傳統啟發式算法無法媲美的求解效率。Python調用COPT求解器的高效率和優化能力對于實際的物流和供應鏈管理等領域具有重要的應用價值，能夠幫助企業降低成本、提高服務質量，并在競爭激烈的市場中獲得優勢。

綜上所述，三種算法均能對問題進行求解，其中模擬退火算法和自適應免疫遺傳算法得到了相同的地鐵轉運站最優選址結果，但因其地鐵轉運站對應配送的需求點不同，導致最優解不同。綜合考慮三種算法的求解效率和精確性，三種算法中Python調用COPT求解器的算法遠遠優于另外兩種算法，自適應免疫遺傳算法次之，最后是模擬退火算法。

4 " " 結 " "論

本文構建了地鐵-貨車聯運配送的地鐵轉運站選址模型，通過MATLAB設計模擬退火算法、MATLAB設計自適應免疫遺傳算法和Python調用COPT求解器三種算法對模型進行求解。以西安市地鐵網絡為例進行了案例分析，并對三種算法的求解結果進行對比分析，不僅驗證了三種算法的有效性，還證明了Python調用COPT求解器計算該選址分配問題相較于其他算法有著絕對的優勢。對其他更為復雜的大規模優化問題的求解，當所求問題擁有明確數學模型時，Python調用COPT求解器的算法相較于傳統啟發式算法有著更高的實用價值、求解效率以及精確性。

參考文獻：

[1] 周芳汀，周國華，張錦.依托地鐵網絡的城市配送系統轉運站選址研究[J].鐵道學報，2019，41（7）：16-25.

[2] 米雪麗.基于地鐵的城市物流配送網絡規劃研究[D].蘭州：蘭州交通大學，2022.

[3] 王寅.引入軌道運輸方法的城市配送系統及配送中心選址研究[D].重慶：重慶工商大學，2013.

[4] 聶聞聰，楚龍娟，向楠，等.城市軌道物流配送模式研究及節點選址優化[J].地下空間與工程學報，2023，19（增刊1）：17-25.

[5] 張秋星.基于地鐵運輸系統的城市配送中心選址研究[D].北京：北京郵電大學，2021.

[6] 張平東，馬軍.物流配送中心選址問題研究[J].計算機與數字工程，2023，51（9）：2177-2183.

[7] 裴姝藝，葉曉飛，洪鋼，等.基于啟發式算法的應急物資儲備點選址模型研究[J]．物流科技，2023，46（22）：1-6，11.

[8] 劉善球，樊兵鵬.基于遺傳算法的快遞物流配送中心選址[J].河南工業大學學報，2021，35（5）：70-76.

[9] 于世鑫，徐文君，李安昌，等.基于免疫算法的石家莊地區物流中心選址研究[J].物流科技，2024，47（1）：26-28.

[10] "張亦弛，劉曉佳.基于自適應遺傳算法的生鮮產品冷鏈物流配送中心選址研究[J].物流科技，2023，46（23）：141-145.

[11] "黃濤，鄧斌，何棟，等.一種改進的自適應遺傳算法[J].計算機仿真，2024，41（3）：347-351.