基于改進免疫遺傳算法的鐵路空箱調運優(yōu)化

摘" 要：針對空箱調運問題，在傳統(tǒng)免疫遺傳算法（Immune Genetic Algorithm， IGA）基礎上，通過對Hamming距離計算方式優(yōu)化與調整，獲得抗體親和度與抗體濃度的精確度量，并據(jù)此設計了改進免疫遺傳算法（Improved Immune Genetic Algorithm， IIGA）。為驗證該算法的有效性和優(yōu)勢，以蘭州鐵路局下轄的各集裝箱辦理站實際運輸數(shù)據(jù)為例，分別將所提出的IIGA與傳統(tǒng)IGA、遺傳算法（Genetic Algorithm， GA）設計對比實驗。結果表明：在解決空箱調運問題時，相較于傳統(tǒng)IGA與GA，IIGA能夠在相對較短的時間內，以最少的迭代次數(shù)迅速收斂至最優(yōu)解。

" 關鍵詞：改進免疫遺傳算法；空箱調運；集裝箱；Hamming距離；親和度

" 中圖分類號：F253" " 文獻標志碼：A

DOI：10.13714/j.cnki.1002-3100.2025.03.028

Abstract： Addressing the issue of empty container repositioning， an Improved Immune Genetic Algorithm（IIGA）was developed based on the traditional Immune Genetic Algorithm（IGA）by optimizing and adjusting the calculation method for Hamming distance to achieve precise measurements of antibody affinity and antibody concentration. To validate the effectiveness and advantages of this algorithm， a comparative experiment was designed using actual transportation data from various container terminals under the jurisdiction of Lanzhou Railway Bureau， comparing the proposed IIGA with traditional IGA and Genetic Algorithm（GA）. The results indicated that， when solving the problem of empty container repositioning，IIGA was able to converge to the optimal solution more rapidly with the least number of iterations within a relatively shorter period of time compared to traditional IGA and GA.

Key words： Improved Immune Genetic Algorithm; empty container repositioning; container; Hamming distance; affinity

0" 引" 言

" 隨著鐵路需求的增長，集裝箱運輸作為一種高效、環(huán)保的運輸方式，在物流體系中扮演著越來越重要的角色。然而，在實際運營過程中，空箱調運問題一直是困擾鐵路集裝箱運輸效率提升的難題之一。空箱調運不僅涉及到運輸成本的控制，還關系到集裝箱資源的有效配置和物流服務的及時性。因此，如何科學、高效地解決空箱調運問題，對于提升鐵路集裝箱運輸?shù)恼w效益具有重要意義。

" 空箱調運問題一直以來是國內外學者研究的重點。孫浩[1]通過運用整數(shù)規(guī)劃方法優(yōu)化空箱海陸多式聯(lián)運調運成本，證明了模型有效可行。鄔開俊等[2]提出一種自適應變異粒子群算法（Adaptive Mutation Particle Swarm Algorithm）求解鐵路空車調配問題，通過調整變異概率和慣性權重因子優(yōu)化空車總走行距離。段剛等[3]針對鐵路集裝箱運輸?shù)目障湔{運問題，設計遺傳算法（Genetic Algorithm）并驗證其高效性與多最優(yōu)解獲取能力。Huang[4]從降低成本角度優(yōu)化空箱調運，運用線性規(guī)劃方法建立模型并舉例驗證，為單件低價商品問題提供新的定量分析方法。Meng et al.[5]提出結合集線式、多港掛靠及空箱調運的班輪服務網(wǎng)絡設計問題，并通過CPLEX求解混合整數(shù)線性規(guī)劃模型證明其成本節(jié)約潛力。石紅國等[6]提出基于運達時間約束的集裝箱空箱隨機機會模型，設計基于TOPSIS的限定參數(shù)區(qū)間搜索算法求解該模型。邢磊[7]針對可折疊集裝箱應用、合作協(xié)議下空箱調運及需求不確定性問題，分別構建優(yōu)化模型，設計混合遺傳算法（Hybrid Genetic Algorithm）進行求解，提供中歐班列海陸協(xié)同調運、多周期動態(tài)優(yōu)化及分布式魯棒優(yōu)化的解決方案。姜志永[8]針對兩種不同的特種箱空箱調運模型，分別設計限定范圍的帕累托最優(yōu)解搜索算法（Pareto Optimal Solution Search Algorithm）和遺傳算法求解。岳彥辰[9]對多周期內陸集裝箱調運與庫存優(yōu)化問題進行深入分析，并設計改進變鄰域搜索算法（Improved Variable Neighborhood Search Algorithm）進行求解。針對中歐班列的空箱管理問題，朱星龍等[10]全面考慮空箱獲取過程中的調運費、裝卸費、堆存費以及租賃費等相關因素，進而構建基于集裝箱共享的班列公司的動態(tài)空箱調租優(yōu)化模型，并使用Lingo軟件內置的分支定界法對模型進行精確求解；胡廣紅等[11]通過設計免疫遺傳算法（Immune Genetic Algorithm）進行優(yōu)化求解，結果顯示，相較于現(xiàn)行的空箱調運方案，采用集裝箱共享模式能夠顯著降低空箱調運的總費用。Xu et al.[12]提出結合自適應機制的強化學習框架，用于優(yōu)化海運物流中的空箱調運問題，通過動態(tài)調整獎勵函數(shù)權重提高了問題解決性能。錢力[13]構建以計劃周期內整個運輸網(wǎng)絡空箱調運總費用達到最小化為目標函數(shù)的鐵路集裝箱多時段空箱調運優(yōu)化模型，運用李雅普諾夫（Lyapunov）優(yōu)化方法簡化該模型，進而利用數(shù)學軟件進行求解。

" 本文基于免疫遺傳算法的核心原理，通過對Hamming距離計算公式進行優(yōu)化調整，提出改進免疫遺傳算法（Improved Immune Genetic Algorithm， IIGA）。為驗證該算法的性能，將其與傳統(tǒng)免疫遺傳算法及遺傳算法進行對比。結果表明，IIGA在求解效率方面實現(xiàn)了顯著提升。

1" 鐵路集裝箱空箱調運數(shù)學模型

" 空箱調運問題通常涉及解決如何以最有效或最低成本的方式將空箱從供應站調配到需求站的問題。設n為空箱供應站數(shù)量，A=a，a，…，a表示空箱供應站集合，c為供應站a可供應的空箱數(shù)量，其中i∈1，n；m為空箱需求站數(shù)量，B

=b，b，…，b為空箱需求站集合，則d表示需求站b所需空箱數(shù)量，其中j∈1，m。供應站a到需求站b的運輸距離用d表示，x是決策變量，表示從供應站a到需求站b調運空箱數(shù)。建立滿足以上要求的數(shù)學模型：

minZ=xd" " " " " " " " " " " " " " " " " " " " " " （1）

subject to：

x=c， i=1，2，…，n" " " " " " " " " " " " " " " " " " " " " " （2）

x=d， j=1，2，…，m" " " " " " " " " " " " " " " " " " " " " "（3）

x∈0，1，2，…" " " " " " " " " " " " " " " " " " " " " " "（4）

其中：式（1）為目標函數(shù)，旨在最小化整體運輸費用；式（2）表示供應站a供應給各需求站的空箱數(shù)量之和恰好等于其供應量c；式（3）確保對于每個需求站b，從所有供應站a供應的空箱總數(shù)恰好滿足其需求量d；式（4）為變量非負整數(shù)約束。

2" IIGA算法設計

2.1" 染色體編碼

" 采用矩陣整數(shù)編碼，以X表示一個染色體：

X=" " " " " " " " " " " " " " " " " " " " " " "（5）

式中：x為染色體基因，x∈0，1，2，…， i=1，2，…，n且j=1，2，…，m。

2.2" 親和度計算算子

親和度通常用來描述抗體與抗原之間的結合強度。在優(yōu)化問題中，通常可以對函數(shù)值進行簡單處理（如取倒數(shù)等）作為親和度評價。此外，親和度也能夠通過更復雜的度量方式計算，例如Euclidean距離和Hamming距離，詳見式（6）和式（7）。

H=" " " " " " " " " " " " " " " " " " " " " （6）

H=？鄣" " " " " " " " " " " " " " " " " " " " " " " "（7）

？鄣=" " " " " " " " " " " " " " " " " " " " " " （8）

式中：H表示抗體間結合強度；w和w分別表示抗體i的第k位和抗體j的第k位；L表示抗體編碼長度。

" 針對空箱調運問題，對原有的式（8）進行優(yōu)化調整得到式（9），然后通過Hamming公式計算抗體間的親和度A。

？鄣=" " " " " " " " " " " " " " " （9）

A=" " " " " " " " " " " " " " " " " " " " " " " "（10）

2.3" 濃度計算算子

抗體濃度反應種群多樣性。當抗體濃度過高時，意味著種群中存在大量相似個體，這種高度同質性不利于全局搜索。因此，有必要對這些高濃度的抗體實施適當?shù)囊种拼胧源龠M種群的多樣性和探索能力。相反，對于那些濃度較低的抗體，則應當給予適當?shù)拇龠M和激勵，以增強其在搜索過程中的活躍度和貢獻度。這樣的策略有助于平衡種群的多樣性和搜索效率，從而提升整體性能。抗體i的濃度CON計算公式為：

CON=S" " " " " " " " " " " " " " " " " " " " " " （11）

S=" " " " " " " " " " " " " " " " " " " " " （12）

其中：N為種群規(guī)模大小；S為抗體間相似度；λ為相似度閾值，一般取0lt;λlt;1。

2.4" 繁殖概率計算算子

抗體i的繁殖概率P通常需要綜合考慮抗體適應度概率P與抗體濃度概率P。通常而言，具有高親和度且濃度較低的抗體更容易被選擇，以此確保后代種群的多樣性得以保持。抗體繁殖概率計算公式為：

P=αP+1-αP" " " " " " " " " " " " " " " " " " " " " "（13）

P=" " " " " " " " " " " " " " " " " " " " " " " （14）

P=" " " " " " " " " " " " " " " " " " （15）

其中：0lt;αlt;1為親和系數(shù)；f為抗體i的適應度值；0lt;ξlt;1為濃度閾值；0lt;tlt;N為濃度大于閾值的染色體數(shù)量。

2.5" 選擇、交叉和變異算子

首先，按照個體繁殖概率，執(zhí)行輪盤賭選擇。

其次，隨機選取兩個父代染色體X和X，并生成一個隨機數(shù)r∈0，1，若該隨機數(shù)滿足交叉概率條件，則依據(jù)參考文獻[3]的方式生成子代染色體。這一過程將持續(xù)進行，直至種群中的所有父代染色體均被遍歷完畢。其中X=x和X=x表示父代染色體，X=x和X=x表示生成的子代染色體。首先，令：

x=αx+1-γx" " " " " " " " " " " " " " " " " " " " "（16）

x=αx+1-γx" " " " " " " " " " " " " " " " " " " " "（17）

其中：0lt;γ≤0.5為交叉參數(shù)，x為maxy∈Z∪0|y≤x。再令：

x=max0， minαx+1-γx-x， αx+1-γx-x" " " " " " " " "（18）

x=max0， minαx+1-γx-x， αx+1-γx-x" " " " " " " " "（19）

其中：i=1，2，…，n且j=1，2，…，m，i和j不同時為1。當i=1，j≥2時，式（18）和式（19）中的最小值取第1項；反之，當j=1，i≥2時，兩式中的最小值取第2項。以上計算方式能夠保證調運量非負，且每行的調運量之和不會超過供應量，每列的調運量之和不會超過需求量，但供需平衡的條件不一定滿足，因此，需要對調運量進行以下調整。以染色體X為例，令：

δ=minc-x， d-x" " " " " " " " " " " " " " " " " " （20）

然后令：x=δ+x更新x，遍歷i和j，直至所有調運量都滿足供需平衡條件。

" 最后，基于矩陣閉合回路法設計變異算子，對于某染色體X，挑選矩陣中不同行不同列的非零元素X和X，取：

Δ=minX，X" " " " " " " " " " " " " " " " " " " " " " （21）

然后根據(jù)以下方式執(zhí)行變異操作。

X=X-Δ" " " " " " " " " " " " " " " " " " " " " " "（22）

X=X-Δ" " " " " " " " " " " " " " " " " " " " " " "（23）

X=X+Δ" " " " " " " " " " " " " " " " " " " " " " "（24）

X=X+Δ" " " " " " " " " " " " " " " " " " " " " " "（25）

2.6" 記憶庫及終止準則

" 記憶細胞的主要功能是將表現(xiàn)優(yōu)異的抗體后代儲存于記憶庫中，以便將來能夠迅速響應相同的抗原挑戰(zhàn)；設定最大迭代次數(shù)作為算法終止準則。

2.7" 算法流程

" 免疫遺傳算法基本流程如圖1所示。

（1）參數(shù)及種群初始化。輸入各供應地的空箱供給量、需求地的空箱需求量及距離矩陣等基礎數(shù)據(jù)。初始化算法關鍵參數(shù)，包括種群規(guī)模、記憶庫容量、交叉概率、變異概率、親和系數(shù)、相似度閾值、濃度閾值等。采用整數(shù)編碼的方式初始化抗體群，隨機生成滿足供需平衡條件的初始抗體群。

" （2）抗體適應度、親和度及濃度評價。

" （3）生成免疫記憶細胞，更新記憶庫。

" （4）記錄當前最佳個體適應度和種群平均適應度，更新全局最優(yōu)解。

" （5）計算抗體繁殖概率。根據(jù)式（14）和式（15）分別計算抗體適應度概率P與抗體濃度概率P，進而通過式（13）得出抗體的繁殖概率P，為后續(xù)的選擇操作提供依據(jù)。

（6）執(zhí)行進化操作。根據(jù)抗體的繁殖概率執(zhí)行選擇操作，然后通過交叉和變異操作生成新的抗體群。同時，在生成新抗體群的過程中，加入記憶庫細胞以加速算法的收斂速度。

" （7）判斷終止條件。檢查算法是否滿足預設的終止準則。若滿足，則結束循環(huán)，輸出最終優(yōu)化結果；否則，返回步驟（2）繼續(xù)迭代。

3" 算例分析

實驗在CPU處理器為i5-12500H，主頻2.50 GHz，內存16.0GB以及64位Windows11操作系統(tǒng)中，借助MATLAB R2022a軟件執(zhí)行。參考段剛等[3]的算例，選取甘谷、金昌、嘉峪關、青銅峽和張掖5個空箱供應站，以及白銀、定西、低窩鋪、惠農、蘭州北、隴西、石嘴山、銀川和天水9個空箱需求站。由于總空箱需求量（554TEU）大于總空箱供應量（334TEU），需增加一個虛擬供應站，其供應量為210TEU。各集裝箱辦理站間運輸距離及供需量見表1。本實驗所涉及的相關參數(shù)及具體配置已詳細于表2中列出。

通過20次對比實驗，評估IIGA、IGA及GA在解決空箱調運問題時的效率。確保在每次實驗中算法都能夠成功收斂至最優(yōu)解（具體最優(yōu)解見表3，對應最小適應度值為141 913），以此作為評估的前提和基礎。表4記錄了不同算法所需的迭代次數(shù)與仿真耗時數(shù)據(jù)。由表4可知：IIGA表現(xiàn)出了最快的收斂速度，其迭代次數(shù)顯著低于其他兩種算法，同時仿真耗時也相對較短；IGA的收斂速度介于IIGA和GA之間，仿真耗時相對較長；盡管GA在仿真耗時方面與IIGA具有較強的競爭力，但其收斂速度卻明顯滯后。

圖2描繪了某次實驗不同算法的收斂情況。結合圖2可知，IIGA在僅迭代了120次就迅速達到了最優(yōu)解，而IGA則需要迭代1 417次才能觸及這一目標，而GA的收斂過程更為漫長，迭代超過4 000次后才逐漸逼近并最終出現(xiàn)最優(yōu)解。這一對比證實IIGA在收斂性能方面具有顯著優(yōu)勢。

4" 結束語

對于空箱調運問題，針對傳統(tǒng)IGA在求解效率與性能方面的不足，提出基于Hamming距離計算公式優(yōu)化調整的IIGA。通過對蘭州鐵路局下轄的各集裝箱辦理站實際運輸數(shù)據(jù)進行實驗，并與傳統(tǒng)IGA及GA進行對比分析，得出以下結論：（1）通過對Hamming距離計算公式的優(yōu)化調整，IIGA在抗體親和度與抗體濃度的度量上實現(xiàn)了更為精確的計算，進而提升了算法在全局搜索與局部優(yōu)化之間的平衡能力。這種優(yōu)化使其在求解空箱調運問題時能夠表現(xiàn)出更強的適應性。（2）相較于IGA和GA，IIGA在求解鐵路空箱調運問題時展現(xiàn)出更為顯著的效率與性能。具體而言，IIGA能夠在較少的迭代次數(shù)內迅速達到最優(yōu)解，從而有效降低計算成本和時間消耗。（3）實驗結果表明，IIGA算法在仿真耗時方面也具有一定的優(yōu)勢。盡管在某些情況下，GA的仿真耗時可能較短，但其收斂速度較慢。相比之下，IIGA算法在保持較快收斂速度的同時，也實現(xiàn)了相對較短的仿真耗時，從而在實際應用中更具競爭力。

" 綜上所述，IIGA為空箱調運問題的優(yōu)化提供了一種更為有效的算法選擇。該算法不僅提高了求解效率與性能，還為鐵路集裝箱運輸?shù)恼w效益提升提供了有力支持。未來將進一步研究該算法在更大規(guī)模空箱調運問題中的應用效果，并探索與其他優(yōu)化算法的結合使用，以期獲得更加高效的求解性能。

參考文獻：

[1] 孫浩. 海陸多式聯(lián)運空箱調運模型研究[J]. 武漢理工大學學報（交通科學與工程版），2010，34（3）：533-536，541.

[2] 鄔開俊，魯懷偉，王鐵君. 基于自適應變異粒子群算法的鐵路空車調配[J]. 蘭州理工大學學報，2011，37（2）：102-105.

[3] 段剛，張慧，陳莉，等. 鐵路集裝箱空箱調運問題的遺傳算法[J]. 鐵道科學與工程學報，2011，8（3）：110-115.

[4]" HUANG CHUNHUI. The optimization of empty shipping container reposition based on the network simplex method[C] // International Conference on Management and Service Science， 2011.

[5]" MENG QIANG， SHUAIAN WANG. Liner shipping service network design with empty container repositioning[J]. Transportation Research Part E： Logistics and Transportation Review， 2011，47（5）：695-708.

[6] 石紅國，高明瑤. 帶時間窗約束的集裝箱空箱調運隨機機會約束模型研究[J]. 鐵道運輸與經(jīng)濟，2020，42（2）：87-92.

[7] 邢磊. 中歐班列空箱調運優(yōu)化研究[D]. 大連：大連海事大學，2021.

[8] 姜志永. 不確定環(huán)境下鐵路特種箱空箱調運優(yōu)化[D]. 大連：大連海事大學，2022.

[9] 岳彥辰. 多周期內陸集裝箱調運與庫存優(yōu)化研究[D]. 北京：北京交通大學，2023.

[10] 朱星龍，湯銀英，陳思. 基于集裝箱共享的中歐班列空箱調租優(yōu)化[J]. 鐵道科學與工程學報，2020，17（6）：1571-1577.

[11] 胡廣紅，湯銀英，李鱗睿，等. 考慮集裝箱共享的中歐班列空箱調運研究[J/OL]. 鐵道運輸與經(jīng)濟，1-10（2024-10-20）[2024-12-26]. http：//kns.cnki.net/kcms/detail/11.1949.U.20240825.1729.004.html.

[12]" XU XIAOFENG， XINRU HUANG， LIANJU WANG. Empty container repositioning problem using a reinforcement learning framework with multi-weight adaptive reward function[J]. Maritime Policy amp; Management， 2024，2024：1-22.

[13] 錢力. 基于李雅普諾夫優(yōu)化的鐵路集裝箱貨運站間空箱協(xié)同調運研究[J]. 鐵道貨運，2024，42（5）：46-52.

收稿日期：2024-10-28

基金項目：國家自然科學基金項目（62262037）；甘肅省科技廳軟科學項目（23JRZA360）；中國鐵路蘭州局集團有限公司科技項目（LZJKY2024012-1）

作者簡介：繆莉盼（1999—），女，甘肅慶陽人，蘭州交通大學交通運輸學院碩士研究生，研究方向：鐵路集裝箱空箱調運；

向萬里（1978—），本文通信作者，男，湖南永順人，蘭州交通大學交通運輸學院，教授，博士生導師，研究方向：交通運輸規(guī)劃與管理。

引文格式：繆莉盼，張宇峰，水源，等. 基于改進免疫遺傳算法的鐵路空箱調運優(yōu)化[J]. 物流科技，2025，48（3）：121-125.