基于改進布谷鳥算法的集卡路徑優化

摘要：在集裝箱公路運輸中，合理規劃集卡路徑以提高運輸效率具有重要的現實意義。本文以最小化總運輸時間為目標，構建了集卡路徑優化問題的數學模型，并設計了改進布谷鳥算法進行求解。為了提升算法性能，本文根據問題的特點構造了局部搜索策略來改善布谷鳥算法的局部尋優能力。實驗結果表明，改進布谷鳥算法在優化性能上明顯優于標準的布谷鳥算法、差分進化算法和粒子群算法，因此是解決該類問題的有效算法，能為集裝箱公路運輸方案的規劃提供重要的決策支持。

關鍵詞：集卡路徑優化；改進布谷鳥算法；局部搜索策略

中圖分類號：TB"文獻標識碼：Adoi：10.19311/j.cnki.16723198.2025.01.081

0"引言

在世界經濟和國際貿易穩定增長的帶動下，交通運輸行業作為其衍生需求也實現了較快的發展。憑借高效、安全、便捷等優勢，集裝箱運輸已成為全球貨物運輸的主導方式。統計數據顯示，集裝箱運輸承擔了國際貿易約80%的貨物運輸量，成為連接各個經濟體的重要紐帶。在集裝箱運輸鏈中，集卡作為重要的運輸工具之一，承擔著貨物在碼頭與內陸運輸節點之間的短途運輸任務。集卡的配送和取貨效率直接關聯到集裝箱的集港和疏港效率，對整個物流體系的順暢運作至關重要。此外，由于高單位運輸成本，短距離集卡運輸成本占集裝箱總成本的30%以上。因此，如何通過科學合理規劃集卡的行駛路徑，有效降低運輸成本，并提升集裝箱的集散效率，成為當前集裝箱公路運輸領域亟待解決的關鍵問題之一。

針對集卡路徑優化問題，盡管學者們已經提出了各種求解算法，例如反應式禁忌算法、蟻群算法和粒子群算法等，但目前尚未有人采用布谷鳥算法來解決該問題。

鑒于此，本文選取以進口為主的港口作為研究背景，探討集卡運輸路徑規劃問題。首先，構建以最小化總運輸時間為目標的混合整數規劃模型；其次，在此基礎上，根據問題的特點設計布谷鳥算法求解策略；最后，通過實驗驗證算法的求解性能。

1"問題描述與模型構建

1.1"問題描述

在以進口為主的區域內，某集裝箱物流企業提供客戶點與港口之間的運輸服務。該企業有一個堆場，用于存放集卡和空集裝箱。集卡從堆場出發，在執行運輸任務過程中，可隨時訪問堆場提取或者存放空集裝箱，并最終返回堆場。假設所有集卡以及所有的集裝箱為同質的，集卡每次僅能搭載一個集裝箱。在該港口，運輸企業主要處理以下3類集裝箱運輸任務。

（1）進口滿載集裝箱（IF）：進口滿載集裝箱抵港后，運輸企業需派一輛集卡前往港口提取滿載集裝箱，然后將其運送至指定收貨方，卸貨后的空箱可運回堆場，或者運至出口客戶處用來封裝出口貨物或者運至港口作為出口的空集裝箱；

（2）出口滿載集裝箱（OF）：運輸企業需運送空箱至發貨方，發貨方裝箱后的滿箱需運至港口供出口；

（3）出口空載集裝箱（OE）：一定數量的空箱需運送至港口，這主要是由于貿易的不平衡，以進口為主的港口需將富余的空集裝箱通過出口運送至出口區域。

圖1"運輸任務示意圖

圖1通過圖示的方式清晰地展示了各種運輸任務的主要流程以及集卡狀態的變化。在流程示意圖中，方框內所代表的活動具有固定的起點和終點，是預先設定好的確定性活動；而方框外部涉及的前置條件和后續走向則是不確定的，這些是需要企業根據實際情況做出決策的活動。該問題的優化計劃是在給定的規劃期內（通常為1天），如何選擇最優的集卡運輸路線，使在滿足約束的條件下，完成全部運輸任務的總時間最小。

1.2"問題的網絡圖模型

為了方便建模，本文借鑒文獻[5]的方法，通過把每個運輸任務表示為一個節點，將問題抽象為一個有向網絡圖G={V，A}，其中："V={0}∪VN，節點“0”為出發/返回頂點，VN為運輸任務節點的集合，A={（i，j）|i，j∈V}為連接兩個節點的弧集合。

定義1"出發/返回節點

出發/返回節點用來表示集卡最初從堆場出發以及最終返回堆場，標記為0節點。

定義2"運輸任務節點

該類節點用來表示三類運輸任務中需要完成的確定性活動。表1給出了表征各類型運輸任務的節點所關聯的活動。該類節點的屬性為執行各自所關聯的活動需消耗的時間Ti。

定義3"節點的連接弧

弧表示集卡從一個節點到另一個節點的路徑。不同類型節點之間的連接弧指代不同的活動。表2列出了不同連接弧所代表的活動。弧的屬性（或稱為權重）是集卡執行弧上活動所必須的時間消耗Tij。

由上述內容可知，原問題可轉化為：在有向圖上尋找總作業時間最少的若干條路徑，每條路徑從出發/返回節點出發，途經若干個任務節點，最后返回出發/返回節點；每個任務節點被訪問且只被訪問一次。因此，原問題最終轉化為等價的車輛路徑規劃問題。

1.3"問題的數學模型

數學模型涉及的參數包括：Ti為節點i的時間消耗；Tij為弧ij的時間消耗；Tmax為集卡的最大工作時長；M為一個足夠大的常數。數學模型涉及的變量包括：xij為0-1變量，表示集卡經過弧ij；yi為連續型變量，表示集卡訪問節點i的時間。基于這些參數和變量，可構建問題如下的數學模型。

Min∑i∈VNyi+Ti+Ti0）xi0（1）

s.t.∑j∈Vxij=1，i∈VN（2）

∑j∈Vxji=∑j∈Vxij，i∈VN（3）

yi+Ti+Tij≤yj+（1－xij）M，i，j∈VN（4）

yi+Ti+Ti0xi0≤Tmax，i∈VN（5）

xij∈{0，1}，yi≥0，i，j∈V（6）

目標函數（1）表示最小化集卡總的運輸完成時間，即返回堆場的時間總和；約束（2）表示所有任務節點都要被訪問，即需要完成所有的運輸任務；約束（3）為路徑的流平衡約束，集卡訪問一個節點后必須離開該節點；約束（4）為時序約束，集卡節點i訪問之后才能訪問節點j；約束（5）為最長工作時限約束；約束（6）給出了變量的取值范圍。

2"改進布谷鳥算法設計

由于集卡優化問題屬于NP-Hard問題，不存在多項式時間算法，為了適應現實大規模優化問題的需求，本文設計改進的布谷鳥算法對該類問題進行求解。布谷鳥算法是模擬布谷鳥借窩產卵的繁衍習性有效地求解最優化問題的全局優化算法。該算法將整個搜索空間視為可行域；將鳥窩或者卵視為候選解；將宿主鳥窩的優劣來代表問題解的適應度；將最好鳥窩或卵的位置視為最優解；將布谷鳥搜尋和選擇鳥巢的過程視為尋找問題最優解的過程，建立虛擬布谷鳥與解集的對應關系，然后通過產生候選種群、擇優選擇和隨機遷移三個操作模擬自然界中布谷鳥的尋窩過程，實現對全局最優解的搜尋。該算法具有原理簡單、參數設置少和全局收斂性能好的優點，被應用于求解各類組合優化問題。鑒于此，本文將布谷鳥算法拓展用于解決集卡優化問題。同時，為了提升算法的性能，本文引入局部搜索策略增強布谷鳥算法的局部搜索能力，以期找到更優的近似解。本文設計的算法細節如下。

2.1"編碼與解碼

本文算法中的個體編碼采用浮點數編碼，"即用（r1，r2，r3，…，ri，…，rn）"表示一個個體，"其中每一維的ri代表在安排訪問順序時節點i的優先級，ri取值范圍為[0，"1]。該種編碼方式的個體中沒有作為子路徑的分隔符，因而無須事先估計所需要的集卡數量。

由于該編碼方式沒有顯式地表達問題的解，即集卡的路徑方案，所以需要構造解碼算子來將個體轉換為可行的集卡行駛路徑。解碼時，第一步先根據優先值對節點進行排序，以表3為例，節點4的優先值最大，因此節點4排序第一，節點5優先值排第二，因此節點5排第二，同理對其他節點進行排序，最終可得到節點排序序列{4-5-3-1-2}。第二步則將第一步得到的排序序列進行分割，得到多條集卡訪問路徑。具體地，首先初始化一條從代表堆場開始的路徑{0→}，然后將節點序列中最左端未訪問的節點加入到該路徑中，例如{0→4}，重復上述步驟，直至工作時限約束導致不能再往該路徑添加節點，形成一條完整的集卡路徑，例如，例如{0→4→5→3→0}。然后，重新初始化一條新的路徑，繼續依次向路徑中添加未訪問的節點，直至所有的節點都被訪問。例如，個體{0.2，"0.1，"0.3，0.5，0.4}，經解碼后，轉化為兩條集卡路徑，路線1：{0→4→5→3→0};路線2：{0→1→2→0}。

2.2"種群初始化

因為個體采用浮點數編碼，所以本文按照公式（7）隨機生成NP個個體Xti（i=1，2，3，…，NP），作為布谷鳥算法的初始種群。

Xti=rand（1，|VN|）（7）

其中，rand（1，|VN|）表示隨機生成1行|VN|列的（0，1）范圍內的隨機數。

2.3"產生候選種群

算法按照位置更新公式（8）產生候選種群：

Yt+1i=Xti+αL（λ）（8）

其中，Yt+1i表示第t+1代鳥窩的候選位置，Xti表示第t代第i個鳥窩的位置；α為控制步長，可根據求解問題設定；為點對點乘法；L（λ）為Levy飛行的隨機搜索路徑。

2.4"擇優選擇

標準布谷鳥算法的選擇算子是將父體與其候選子代一對一地比較適應度，適應度高的個體將保留到下一代。具體規則如下：

Xt+1i=Yt+1i，iffYt+1i）gt;fXti）Xti，其他（9）

擇優選擇操作是采用的貪婪策略進行選擇，它能夠跟蹤進化過程搜尋到的最優解，不但能防止迭代過程退化現象的發生，而且能夠加快收斂速度，是一種非常可取的選擇策略。在布谷鳥算法中，個體各自獨立地通過Levy飛行產生子代的操作能夠避免算法早熟現象。

2.5"隨機遷移

在隨機遷移算子探尋到的新鳥窩后需執行擇優選擇算子，保留相對較好的鳥窩。隨機遷移算子既能淘汰種群中的劣勢個體，又可以增加種群的多樣性。

2.6"局部搜索策略

局部搜索是解決組合優化問題時非常有效的技術，其核心在于通過探索當前解的鄰域環境來尋找潛在的更優解。在集裝箱運輸路徑規劃問題中，集卡運輸任務表現出一種特定的模式：釋放一個空箱的IF任務和需要一個空箱的OF或OE型任務交替被執行，這樣可以避免多次連續執行IF、OF或OE任務，從而節省了頻繁往返堆場進行空箱存取的時間。基于這一規律，本文算法設計了兩種局部搜索方法，以便更有效地尋找最優運輸路徑。

（1）交換法。選擇兩個相同類型的節點（即兩個IF節點，或兩個OF/OE節點），并嘗試交換它們在序列中的位置。通過重新排列這些節點生成了一個新的序列，并計算該序列的最短完成時間。如果新序列的目標函數更優，則交換成功，并用新序列替換原始序列。

（2）逆轉法。選擇兩個相同類型的節點（IF或OF/OE），然后逆轉這兩個節點之間所有節點的順序。逆序排列生成一個新的序列，同樣計算該序列下的最短完成時間。如果逆轉后的序列具有更優的目標函數值，則逆轉成功，并將新序列替代原序列。

2.7"算法流程

本文設計的求解集卡路徑優化問題的改進布谷鳥算法流程描述如下：

步驟1：設置參數和種群初始化。設置種群規模Pop；控制步長α；發現概率Pa；設置終止條件，一般為最大進化代數Iter；然后根據問題的屬性初始化種群；

步驟2：判斷是否達到終止條件。若達到設定的迭代次數，則算法結束輸出最優解，否則轉步驟3；

步驟3：產生候選種群操作。按照公式（8）生成子代；

步驟4：執行擇優選擇算子。按照公式（9）采取一對一的選擇策略，從父體和子體中選擇更優的個體作為下一代的父體；

步驟5：執行隨機遷移算子。從步驟4更新后的種群中按照概率Pa進行變異；

步驟6：對當前最優解執行局部搜索策略，然后轉步驟2。

3"算法驗證與分析

3.1"實驗設置

由于集卡路徑優化問題目前沒有基準問題測試庫，因此本文通過隨機生成測試案例來驗證算法的有效性。具體生產規則如下，運輸企業的服務區域假定為邊長為3小時行程的正方形區域，港口、堆場和客戶地點在該區域內隨機生成；兩點的歐幾里得距離作為兩點間的集卡行駛時程；裝貨/卸貨的時間設為0.5小時；集卡的每天工作時長設為10小時。鑒于本文以進口港口為背景，故每一個測試算例中各類型運輸任務數生成規則為：IF型、OE和OF型任務分別各占總運輸任務數的50%、25%和25%。

為了驗證算法的有效性，本文將改進的布谷鳥算法（ICS）和標準的布谷鳥算法（CS）、粒子群算法（PSO）和差分進化算法（DE）進行比較。差分進化算法參數設置如下：種群規模Pop=30；縮放因子F=0.4；交叉概率CR=0.75。粒子群算法中種群規模Pop=30；學習因子c1=c2=0.1；慣性權重w取值區間為[0.9，0.4]，并采用直線遞減的方式調整取值。改進布谷鳥算法和基本布谷鳥算法的種群規模Pop=30；控制步長α=0.1；發現概率Pa=0.25。為了公平比較，所有算法的迭代終止條件都是迭代N*200次結束，其中N為問題的任務規模。

測試案例的運輸任務規模設為［20，"40，"60，"100］，總共4組，每組包括5個不同的測試算例。對每個算例，每種算法各運行10次，統計找到的最優解Obj和每次耗費的平均時間CPU，單位為秒。

本實驗硬件環境為Intel"Core"i3"2.3GHZ的CPU，內存為4GB"DDR3；軟件環境為Windows"10操作系統和MATLAB"2021a的編程平臺。

3.2"實驗結果分析

通過表4呈現的結果可知，布谷鳥算法和基本的布谷鳥算法的求解結果明顯優于差分進化算法和粒子群算法。這一現象的原因在于，布谷鳥算法的個體各自獨立地通過Levy飛行產生子代，這種方式能夠避免出現差分進化算法中種群間合作方式產生子代再結合擇優選擇引起的算法早熟現象。此外，通過對比改進的布谷鳥算法和基本的布谷鳥算法求解可知，改進的布谷鳥算法的質量明顯高于基本的布谷鳥算法，由此可知，引入的局部搜索策略能有效提高算法的局部尋優能力，從而提高算法的求解質量，獲得更好的最優解。

圖2以算例60-1為例，對比了本文算法、標準布谷鳥算法、粒子群算法和差分進化算法的迭代進程。從圖2可以看出，本文算法能有效避免過早出現的早熟現象，搜索到更優的解。由此可知，本文算法是求解該類問題的有效算法。

參考文獻

［1］Zhang"R.，Yun"W"Y，Moon"I.A"reactive"tabu"search"algorithm"for"the"multi-depot"container"truck"transportation"problem.Transportation"Research"Part"E：Logistics"and"Transportation"Review"[J].2009，45（6）：904914.

[2]張瑞友，張輝，黃敏，等.以低碳為目標的集裝箱拖車運輸問題及其時間窗離散化算法[J].控制與決策，2016，31（4）：717722.

[3]靳志宏，黃穎，張佳藝，等.甩箱模式下考慮多箱型任務組合的集卡調度優化[J].交通運輸系統工程與信息，2022，22（5）：243251.

[4]李琦，魏玉光.帶時間窗的中心站多車程集卡調度優化研究[J].交通運輸系統工程與信息，2024，24（1）：272281.

[5]張瑞友，汪定偉，尹原永，等.集裝箱卡車運輸問題的基于圖的建模方法.系統工程理論與實踐，2011，Vol.31（8）：15391545.