基于自適應大規模鄰域搜索算法的多等級引航員排班問題

蕭理陽，鄭航曉，孫 鵬，陳露嫻①

（1.上海大學，管理學院，上海 200444；2.天津大學，管理與經濟學部，天津 300072）

0 引言

船舶進出港是船舶航行中事故高發的環節[1]，大多數海港為了降低事故發生的概率，會安排引航員為船舶進出港環節提供引航服務。隨著船舶出入港的需求不斷增加，船舶入港作業時間更加緊湊，港口船舶調度難度加大。復雜的港口船舶流通現狀對引航員能力提出了更高要求，也使得制定引航員與船舶調度計劃的過程變得更加困難。

大多數國家對引航員分等級進行考核，給合格者授予引航證。在我國，引航員根據其能力水平被劃分為三個等級，只有通過考核的引航員才能被允許在特定水域進行引航服務。多等級引航員是排班過程中不可忽略的要素，依照交通運輸部海事局的《船舶引航管理規定》[2]，調度員需根據船舶大小、吃水以及運送物品種類等方面的不同，將不同難易程度的引航任務指派給相應級別的引航員?，F實情況下，培養一個經驗豐富的引航員往往需要十年以上[3]，大多數港口選擇從有經驗的船長中選拔和培訓引航員。鑒于引航員從業人數少、培養難度高的現狀，該行業目前仍存在巨大的人才缺口。另一方面，傳統調度方法主要以人工操作為主，隨著港口實際情況復雜化，人工排班造成的引航資源浪費和調度不合理現象也日益明顯。對于港口企業而言，合理的引航調度排班可以更高效地利用港口現有的引航員資源，大大降低港口的運營成本。因此，如何合理地制定引航員調度計劃提高引航調度的服務效率，成為當前港口企業亟待解決的問題。

現有與引航服務相關的研究文獻可以歸納為兩個方面：第一種從社會學的角度研究影響引航員工作效率的原因，如其疲勞度[4-6]、個人能力[7]、心理素質[8]、安全知識[9-10]和風險感知[11]等社會因素對引航工作的影響；另一種則是專注于構建引航員排班規則的模型，并根據排班模型設計相應算法[12]。Wu等[13]構建了一個考慮引航員換乘和航道容量限制的引航員排班問題模型，并開發了一種分支定價（Branch and price，B&P）算法來求解該問題。Gregory等[14]考慮了引航員工作排班不確定性的負面影響，在其模型中引入引航員最大連續工作時長和每周最大工作時長概念。Xiao[15]和譚哲一[16]則分別考慮了引航員疲勞度和船舶間的安全距離，并設計了一種兩階段變鄰域搜索（Variable Neighborhood Search，VNS）方法對其提出的模型求解。上述文獻雖然總結了引航員的稀缺性與差異性，但現有建模過程中通常假設引航員同質化，較少考慮引航員等級這一現實因素，并且多數模型作出引航員與任務數相等的假設也與實際的引航員人才稀缺現狀不符。同時，引航員排班問題已被Wu[13]證明為NP 難問題，對于該類問題，目前主流的精確式算法求解該問題難度較高且時間較長，現實應用價值較小。而相關啟發式算法，雖然沒法保證解的最優性，但是可以在有限時間內找到與已知最優解相接近的高質量解。

本文以多等級引航員排班問題作為研究對象，構建了一個包含引航員等級與引航員人數限制的混合整數規劃模型，并根據該問題的特點針對性設計了自適應大鄰域搜索算法（Adaptive Large Neighborhood Search，ALNS）進行求解。為了提高算法輸出解的精度與速度，在該算法中設計了領航任務開始時間判斷模塊和航道容量約束判斷模塊。為了檢驗該算法的性能，本文通過與CPLEX 商用求解器以及文獻中的兩階段VNS 算法在精度、效率等方面進行了充分比較。

本文的創新點主要有以下三點：（1）構建了考慮了引航員等級、時間窗、航道容量等因素的引航員排班問題整數規劃模型；（2）根據問題特征設計了ALNS算法，有較快的運行速度和較高的求解精度；（3）提出了相應的管理學啟示，可為引航站調度中心的引航員排班決策提供參考。

1 問題描述及模型

1.1 問題描述

本文所研究的問題僅考慮一個引航站調度中心，調度中心中有數量限制的高、中、低三類不同等級的引航員。調度中心會根據港口管理局提供的船舶進出信息，在考慮航道和引航員相關信息后生成一個引航員調度計劃。如圖1所示，當船到達港口時，調度中心需要安排引航員對其進行進港引航服務；同樣，當船即將離開港口時，也需要安排引航員對其進行離崗引航服務。在該問題中，假設每艘船必須有引航員對其進行引航服務，而在實際情況中部分引航任務難度較高，只有經驗豐富的引航員才能勝任，所以把船的引航任務假設為三個難度等級（見表1），只有能力與之匹配或更好的引航員才能被安排該類船的引航任務，如圖2所示。

表1 任務難度及對引航員等級要求Tab.1 Task difficulty and requirements for pilot levels

圖1 引航示意圖Fig.1 Schematic of pilot scheduling

圖2 引航員排班計劃Fig.2 Pilot scheduling plan

同時，假設所有引航員初始都在位于靠近泊位的引航員調度中心待命，等到有任務安排之后乘坐交通工具到達目標點，換乘工具有直升機和快艇兩種。引航員在完成單次引航任務后，可以原地休息等待下一任務或返回調度中心結束當天任務。為了防止出現引航員工作時間過長導致其因為疲勞而增大事故發生概率，規定引航員每天的工作時間不能超過工作時間上限Hˉ。

1.2 參數及變量

為了對模型進行更好的描述，模型中的參數和變量如下：

1.2.1 參數

Ν：所有任務集合，與任務集合相關參數下標均為i,j。

Νh：進港任務集合，Ν0為進港任務集合，Ν1為出港任務集合。

Νleνel：進港任務集合，leνel∈{0,1,2}。

Λ：任務類型，Λ={0,1}，0為進港任務，1為出港任務，下標為h。

L：任務等級集合，L={0,1,2}，0為高難度任務，1為中等難度任務，2為普通任務，下標為level。

qip：若引航員p滿足服務任務i要求時為1，其他情況為0。

Ρ：可調度引航員集合，Ρ={1,2,…,|Ρ|}，每個引航員在一次排班中最多安排一個任務周期，下標為p。

Θ：引航員運輸工具類型，Θ={0,1}，下標為k。

EF：規劃范圍內任務最晚結束時間。

T：在規劃范圍內的時間點集合，T={1,2,…,|EF|}，下標為t,t1,t2。

C：任務i的單位延遲成本。

C：一位leνel級別的引航員的班期成本。

C3：為一項任務提供引航服務的費用。

C：通過k型換乘工具換乘的單位成本。

C5：被服務船只的懲罰成本。

Ei：任務i的最早允許開始時間。

Di：服務于任務i所需的時間。

Οk：運輸工具k的運輸時間。

M：一個足夠大的常數。

Βij：引航員在完成任務i后若立即執行任務j時需要換乘為1，其他情況為0。

1.2.2 變量

yit：如果任務i的開始服務時間為t時為1，其他情況為0。

ni：i任務未被安排服務時為1，其他情況為0。

1.3 數學模型

根據1.1 節問題描述，本文建立的模型以引航作業總成本最小為目標，構建模型如下：

1.3.1 決策變量

目標函數（1）為最小化引航作業總成本F，包括任務延遲成本（第一項）、引航調度成本（第二項）、引航成本（第三項）、引航員換乘工具成本（第四項）和未服務任務懲罰成本（第五項）。

1.3.2 約束條件

其中，約束（2）表示每個引航員班次最多分配一個開始時間。如果沒有分配任何開始時間的引航員班次，則引航員班次為空。約束（3）表示每個引航員輪班最多有一個啟動任務。約束（4）確保每個任務點都有安排。約束（5）為每個任務都被標記為安排或未被排班狀態。約束（6）確保每個任務必須由符合其要求的引航員執行。約束（7）為每個任務分配一個開始時間。約束（8）表示引航員排班中第一項任務的開始時間不早于引航員輪班的開始時間，并且在引航員到達相應船舶的位置之前，第一項任務不能開始。約束（9）規定了在同一引航員輪班中連續執行的兩項任務的開始時間之間的關系。約束（10）指定引航員輪班中最后一項任務的開始時間與引航員返回基地的時間之間的關系，并且確保每個引航員輪班的長度不超過每次工作時長上限。約束（11）為每個任務設置了一個時間窗口。約束（12）確保在引航員需要連續執行兩個相同類型的任務時，使用換乘工具通過通道運輸引航員。約束（13）對同時在航道航行的進港船只和離港船只的數量施加了上限。約束（14）～（18）定義了決策變量為0-1變量。

2 自適應大鄰域搜索算法

上述模型所描述的多等級引航員排班問題屬于NP 難問題，精確算法和CPLEX 等優化求解器難以在可接受的時間內求解該問題的中大規模實例。而ALNS 算法可以在較短時間內求解大規模實例，所以文章選擇采用改進版的ALNS算法進行求解。

ALNS算法（見圖3）為運用破壞算子和修復算子對解空間進行搜索的自適應大鄰域搜索算法，最早由Ropke[17]在大規模鄰域搜索算法（Large Neighborhood Search，LNS）的基礎上提出，最初是用以求解帶時間窗的取送貨車輛路徑問題。該算法在搜索過程中根據算子對解的改進情況自適應地選擇搜索算子，對解的改進較好的算子在后續迭代中有更大的概率再次被選擇來搜索解，以達到對解空間的高效搜索進而提高算法的性能。另外，為了跳出局部最優解，該算法還使用了模擬退火新解接受準則。在改進的算法中，設計了算子之間相互交互的功能（見圖4）。同時考慮到引航員等級約束，算法中針對性設計了引航員降級破壞算子。

圖3 ALNS算法流程圖Fig.3 ALNS algorithm flowchart

圖4 算子選擇與使用Fig.4 Operator selection and use

考慮到問題的復雜性，本文參考石敏涵[18]方案在設計算法的過程中將算法分為兩層：外層通過構建ALNS 算法生成排班順序方案（算法1），包括生成初始解、選擇破壞算子與修復算子的輪盤賭算法以及模擬退火迭代算法。內層則是通過外層的排班方案，計算該排班順序下的模型最佳被服務時間以及計算最小成本。

算法1：ALNS基本邏輯

2.1 內層程序

內層程序主要為引航總成本計算程序（算法2）。通過排班順序只能確定引航調度成本、引航成本、未服務任務懲罰成本等較為固定的成本值，而計算任務的延誤成本和引航員換乘工具成本則需要配合任務的具體開始時間數據。因此，內層程序考慮時間窗約束、引航員工作時長、換乘工具比較、航道容量約束等因素，生成具體開始時間starts_p。然后根據排班順序結合任務開始時間計算任務總加權成本，輔助判斷此次排班的質量。

算法2：內層算法

2.2 生成初始解

在ALNS 的算法中，初始解的質量十分重要[19]。本模塊主要用貪婪算法[20]計算出模型的一個初始排班順序。該環節通過內部算法輔助，逐一嘗試把每個任務點插入到排班的所有可插入位置中并計算出每一次插入時當前的加權總成本，記住其中排班成本最小的一次作為該點的最優插入位置進行插入。當所有任務被確認插入成功后，記錄當前加權總成本與排班順序為當前解和當前最優解，供后續程序進行破壞和修復。

2.3 破壞算子

破壞算子通過刪除路線上一定數量的節點，得到一條新的排班順序。在這個過程中原有的路線會因為破壞算子刪除的部分節點而發生變化。選擇刪除的邏輯主要有四種：隨機破壞、貪婪破壞、延誤點最長點破壞、降級破壞。被破壞的節點將被記錄在pool 中，供修復算子進行修復操作時使用。前三種算子均為刪除隨機任務數，其中為了增加破壞算子的隨機性使得能夠探索更大的鄰域，破壞算子之間允許組合使用，但是刪除任務點的總數不能超過設定刪除數量上限（R_max）。

2.3.1 隨機破壞

隨機破壞是從排班中隨機破壞R_random 個引航員排班中的任務點，該算子運行速度快，但隨機性強破壞效果較差。

2.3.2 貪婪破壞

貪婪破壞是執行R_random 次破壞任務，每一次破壞前嘗試破壞所有可破壞任務點，并從中選出破壞時對總成本影響最大的一個任務點進行破壞，該算子運行速度最慢，但破壞效果最好。

2.3.3 延誤點最長點破壞

延誤點最長點破壞比較每個任務的實際開始時間與最早開始時間，記錄其中差值最大的R_random個點進行破壞。

2.3.4 降級破壞

將中高等級引航員換為低一等級引航員，并對新引航排班中不符合條件的引航員進行刪除。該算子可以幫助跳出只有部分高等級引航員參與的排班循環。

2.3.5 破壞算子組合使用

為了探索更多的領域，防止陷入局部最優解后循環相同或相似的破壞與修復程序，破壞算子需要有更高的隨機性。算法設計在破壞算子的選擇過程中貪婪破壞算子可以與隨機破壞、延誤點最長點破壞、降級破壞算子在一次破壞程序中共同被調用，通過多種算子之間的組合使用，可以很好地提高其他破壞算子的隨機性。

2.4 修復算子

本模塊通過重新插入被破壞算子刪除的節點生成一個新的排班。Ropke 在大鄰域搜索算法中提出了貪婪修復、隨機修復和最大后悔值修復三種修復方式。在多數情況下貪婪修復和最大后悔值修復的效果好于隨機修復，但是容易出現陷入局部最優解情況。所以為了提升算法的效率，修復的邏輯主要有四種：隨機修復、貪婪修復、最大后悔值修復、修復算子組合使用。

2.4.1 隨機修復

隨機選擇pool 中的部分任務點，選擇排班內的某一符合插入條件的節點序列進行插入，并生成任務開始時間。隨機修復算子隨機性相當強，小規模地使用隨機修復算子能夠幫助算法很快地跳出原有的局部最優解。但也正是因為其隨機性相當的強，導致其單獨使用生成的解質量整體較差，并隨著其修復點數增加解質量進一步惡化。

2.4.2 貪婪修復

貪婪修復即嘗試對待插入的點在每一條排班的每一個序列點進行插入并重新計劃開始時間，比較每一次插入對新排班帶來的變化，選出其中變化最小的作為插入點。貪婪修復是多次比較生成解的修復方式，因為修復原理是以每個點的最優插入位置為目標，修復所產生的解的質量也是最高的。但因為固化的按順序比較選取最優的算法流程，容易陷入局部最優解。同時，貪婪修復算法將那些對整體成本影響大的任務靠后插入，使得其插入過程中選擇變得更小，這些任務點很可能有苛刻的要求需要被優先考慮。

2.4.3 最大后悔值修復

計算被移除任務點插回到已分配排班序列中的次優位置時其目標函數值與最優位置的目標函數值的差之和，然后選擇差之和最大的需求節點及其最優位置。最大后悔值修復有著較好修復效率，相比于貪婪算子也能兼顧到對整體成本影響大的任務，但頻繁使用也容易陷入局部最優解循環。

2.4.4 修復算子組合使用

單獨使用隨機修復算子效率較差，在修復算子的輪盤賭算法中若是選擇了隨機修復算子則有概率與貪婪修復和最大后悔值修復同時使用，考慮到隨機修復算子隨機性相當強，與貪婪修復和最大后悔值修復可以擴大其修復領域，從而幫助算法更好地跳出局部最優解循環，同時也保證了算法效率。

2.5 自適應機制

本章使用Pisinger 等[21]提出的輪盤賭輪選擇程序來確定路由和節點選擇方法。在一開始，每個破壞或修復算子的選擇方法被分配相同的概率，然后，基于評分系統進行γ次主迭代后，動態更新每種方法的概率。由于不同算子得出的解質量有一定的差距，通過對解的優劣判斷可以有效分析算子的使用效率，更多的使用高質量算子可以進一步提升算法效率[22]。因此本文針對性地設立了評分系統，規則如下：（1）如果在應用一種選擇方法后獲得了一個新的整體最佳解，則在該方法中添加ν1分；（2）如果當前的解較上一解得到改進，則增加ν2分；（3）如果該解決方案比當前的解決方案差，但根據接受標準被接受，則給該方法加ν3分。

評分系統被應用于算子選擇的過程中，算子的評分越高就代表其效果越好，被選中的概率也就越高。假設s種算子權重為ωi(i=1,…,s)，得分為πi，選擇算法的次數為?i次，ρ為0 到1 之間的系數，則可計算算子的被選擇概率為：

2.6 迭代算法

本文使用了模擬退火算法的原理。首先設置一個最大迭代值Iter_max和最大迭代時間T_max。將生成的初始解導入后，利用輪盤賭算法選擇出即將使用的破壞算子和操作算子初始排班進行振動操作。在這個過程中，如果新生成的解優于當前解，則對其新生成的解進行記錄。如果該解優于已記錄最優解，則將該解記錄為最優解，否則按照模擬退火準則處理。當迭代次數或迭代時間達到最大值之后，停止迭代，輸出當前的最優值和算子使用情況。

3 算例分析

為了檢驗問題模型和算法的有效性，并對影響排班成本的部分要素進行分析，文章做了以下兩個部分的實驗：

（1）對比大、中、小規模算例的改進版ALNS算法、CPLEX算法以及兩階段VNS算法結果。

（2）分析模型中關鍵參數對于系統運行總成本的影響，并總結算例結果進行分析，對多等級引航員排班問題提出管理啟示。

3.1 算法有效性驗證

在本節中，本文對多組數據進行計算實驗，以驗證本文所提出的改進版ALNS 模型和求解方法的適用性和有效性。本文數據基于對廈門港等多地的調研結果。文中假設以24 h 為一個調度周期單位，假定5 min 為一個基礎時間單元。調度中心每天的最長工作時間為12 h及144個時間單元，而單個引航員每次最長工作時間為36時間單元?？紤]到實際引航員人才較為緊缺，港口無法做到引航員數量充沛的理想情況，因此假設引航員調度中心常駐引航員數量為任務數量的一半。本文多等級引航員則參考廈門港引航站引航一科引航員比例，其中高等級引航員為9人，一、二級引航員為11 人，三級引航員和見習引航員為5 人，故本文將引航員高、中、低級比例確定為3∶5∶2，任務難度則參照上文表1 標準進行劃分。進出港航道的初始容量均假設為同時可供兩艘船并排航行。根據上述的數據進行不同引航員和船舶規模下的實驗，本文總共測試12 組數據，用n_p_i命名不同的算例，n表示船舶的數量，p表示引航員的數量，i則表示該規模算例的索引，以此規則生成10、20、30、40和50 個任務算例，本文所用實驗平臺的CPU 為AMD 銳龍R5 5600H3.30 GHz，內存為16 GB，采用Windows11 64位處理系統，代碼使用Java IDEA實現，所用CPLEX 求解器版本為12.6.1。實驗結果如表2所示。

表2 兩階段VNS、改進版ALNS與CPLEX算法比較Tab.2 Comparison of two-stage VNS,improved ALNS and CPLEX algorithms

從目標結果的數值來看，10 個任務的小規模算例三種算法都得到了最優解，保證了在中小規模算例時解的質量。在求解方面，CPLEX 的求解所用時間明顯多于兩個啟發式算法。而在任務船達到了20 艘以上的時候，CPLEX 均無法在三個小時內解出目標值，對于日進出船舶數量多、時效要求高的港口而言，CPLEX的實用性較差。

改進后的ALNS 算法和VNS 兩階段算法均可以在較短時間內獲得一個可行解。相較兩階段VNS 算法，改進后的ALNS 算法平均總成本下降了52.68%。兩階段的VNS 算法雖然整體上求解時間更短，但是其在中、大規模的算例中難以保證解的質量，甚至在50 個以上任務規模的案例中多次出現了大規模任務點排班失敗情況。

由此可見，改進版ALNS在規定時間可以保持較好的求解效率和精度，在解決的實際問題時，該算法總體上優于CPLEX算法和兩階段VNS算法。

3.2 關鍵參數敏感性分析

在實際情況中任務調度中心并無法修改任務船的實際需求，只能通過改變調度中心引航員的數量或擴寬航道等方式來對效率進行提升。同樣對于決策者而言，增加或減少雇傭引航員的數量與航道是否需要擴容都是其在港口規劃決策時所面臨的選擇難題。為了分析模型中港口實際過程中的關鍵參數對于最終結果的影響，本文嘗試改變引航員數量、引航員各等級比例與航道容量等參數，并通過數據對比探究其對結果的影響。

3.2.1 引航員數量變化

原模型設定引航員總數為任務數量的50%（Ρ=|Ν|×0.5）。為探究引航員數量變化對結果的影響，下面通過假設引航員與任務數相等（Ρ=|Ν|）和引航員總數為任務數量的30%（Ρ=|Ν|×0.3）分別模擬引航員數量完全充足和引航員緊缺兩種情況，并與原數據結果進行對比，結果見表3。通過對比可知在引航員數量充足的情況下，引航排班將會有更多選擇，解的質量也能有小幅度的提升。但當引航員人數過少時，不僅時間延遲成本會受影響，還會涌現出大批的任務排不上班的情況，大大增加港口的運營成本。

表3 引航員數量變化結果對比Tab.3 Comparison results of pilot number change

3.2.2 引航員比例變化

下面將高、中、低級引航員的比例由3∶5∶2 改為2∶3∶5和4∶4∶2。

改變高、中、低級引航員比例的目標值對比結果見表4。高等級的引航員數量不足，往往會導致部分情況下任務的時間延遲增加，從而增大港口每天的運營成本。而在各等級領航員數量約為總任務數量一半的時候，在此基礎上增加高級引航員比例，并不能對港口產生很多的正收益，在特殊情況下反而會使高等級引航員更多地參與到低難度的任務中，從而造成資源的浪費。從表中的整體情況上來看，高等級的引航員人數越多，每日排班的總成本就越低。

表4 引航員數量比例變化結果對比Tab.4 Results of pilot quantity proportion change

3.2.3 航道容量變化

進、出航道由2+2（進港航道允許最多同時航行2 艘船，出港航道允許最多同時航行2 艘船，下同）改為1+1 和3+3。改變航道容量后的目標值對比結果見表5。從表中的數據可以發現，總體上航道容量越大則其解越優。而在當天任務量比較多的情況下，航道少的港口往往會因為航道擁擠無法當天完成引航任務，為港口造成較大的延誤損失。而在中小規模任務的情況下航道規模的影響并不是那么明顯。如表5中，當每日任務數量達到40 個的時候，航道1+1 便出現了任務當天無法完成的情況。同樣，當每日任務數量達到60個時，航道2+2條件也難以滿足實際任務的需求。

表5 航道容量變化結果對比Tab.5 Comparison results of channel capacity change

綜上，通過對算例結果的分析，可以得出以下結論及系統運營管理建議：

（1）若每日的任務量在一個合理的范圍內，擴寬航道并不會對每日的成本造成較大的影響。相比于擴寬航道的成本，多數情況下港口擴寬航道帶來的收益并不明顯。而在排班任務密度過高或排班需求增速很快的情況下，適當的拓寬港口的進出航道容量，可以緩解港口每日服務船舶過多或者港口服務需求增長過快帶來的壓力。

（2）在一定范圍內，能力高的引航員能夠給港口帶來更多的收益，鑒于社會上目前高水平引航員欠缺的實際情況，港口企業需要注重吸引和培養人才，保證其引航排班時可調度引航員比例在一個合理的范圍內。而在引航員的數量達到一定規模后，增大中低等級引航員比例并不會對總成本造成大的影響，港口在吸收經驗豐富的社會船員的同時也需要重視經驗不足但是潛力巨大的年輕人才的培養和儲備。

4 結論與展望

本文對港口的引航員排班問題進行了研究，考慮了時間窗、航道容量等因素，以時間延遲成本、引航員出工成本、引航員換乘成本、單次服務成本以及當日未服務船的懲罰成本的總加權成本最小為目標。通過優化模型構建與算法設計，給出了一個調度周期內引航員排班方案。本文在ALNS 算法中加入了不同算子之間相互配合的功能，在增大探索鄰域范圍的同時更高頻繁利用了其中效果較好的算子，從而增大找到最優解的概率。與CPLEX 相比，文中所改進的ALNS方法，能大幅度降低運行時間，并且在中小規模的實踐中可以證明其解的精度有一定的保證，使得該模型在現實中能有較好的應用價值。

在未來的研究中，本文會進一步探索該模型的實用性。例如考慮船舶進出港口時間的不確定性對引航員排班帶來的影響或是考慮船舶靠岸作業情況構建一個完整的船舶進出港口周期模型。此外，考慮模型的復雜性特點，在未來的算法設計中可以融入變鄰域搜索算法等其他算法的思想，提高解的精度。