基于混合啟發(fā)式算法的集裝箱貨輪裝配策略研究

秦媛媛 （江蘇財經(jīng)職業(yè)技術(shù)學(xué)院 智能工程技術(shù)學(xué)院，江蘇 淮安 223003）

0 引 言

當(dāng)今世界70%以上的價值貿(mào)易是通過海運進行的。由于大量的一般貨物是由集裝箱運輸，而為了滿足具有競爭力的航運公司選擇服務(wù)的實際需求，甚至有更大的集裝箱船。此外，班輪航運網(wǎng)絡(luò)可能包括幾十個船舶航線和港口，這取決于船隊的能力。由于海上運輸需求的不斷增加，港口活動和航線不能再被視為獨立于海運之外。盡管如此，近年來關(guān)于海運的管理科學(xué)文獻主要集中在海運碼頭進出口集裝箱流動中所需的優(yōu)化技術(shù)或航運的改善服務(wù)。然而，許多研究者也都認(rèn)識到，裝卸作業(yè)和配載規(guī)劃對碼頭的效率和班輪航運選擇有很大的影響。最近的許多論文開始致力于對集裝箱船配載方案加以優(yōu)化的研究。

事實上，配載規(guī)劃是由航運線路協(xié)調(diào)器和碼頭規(guī)劃器決定的。在計劃層面上，控制中心對船舶的整個行程有一個視圖，匯總信息以作出決策，航運線路協(xié)調(diào)器接收o-d運輸需求并驗證是否可以接受運輸需求。然后，航運線路協(xié)調(diào)器為船舶航行的港口定義一個配載計劃，并在收到和接受對該船舶的需求時及時更新該計劃。在船抵達港口之前，船長必須給出一份可行的計劃，根據(jù)目的地、類型、大小和裝載重量不同的集裝箱做出一般指示。航運線路協(xié)調(diào)器表明集裝箱是船舶的一部分。

碼頭規(guī)劃器能夠在運營層面作出更為詳細(xì)的決策。裝卸工作是在收到船長的裝卸指示后開始的。具體來說，碼頭規(guī)劃器必須按照從航運線路協(xié)調(diào)器收到的裝載前指示，為每個要裝上船的集裝箱定義確切的位置。然后，碼頭采用的詳細(xì)積載計劃被傳達給航運線路協(xié)調(diào)器，航運線路協(xié)調(diào)器更新船舶當(dāng)前的貨物，并開始新的規(guī)劃階段，將新的貨物與航線船舶上相繼港口的運輸需求結(jié)合起來。在船舶抵達港口之前(即航運線路協(xié)調(diào)器發(fā)送到碼頭的積載計劃)，需要將船舶貨物組成與船舶離港后的實際貨物(即the碼頭規(guī)劃器定義的積載計劃)合并起來，這是由于兩個計劃的詳細(xì)程度不同。事實上，由航運線路協(xié)調(diào)器給出了碼頭的一般指令，而碼頭規(guī)劃器定義了每個集裝箱裝船的確切位置。例如，一旦航運線路協(xié)調(diào)器確定“10個A1-10類集裝箱、標(biāo)準(zhǔn)、輕量級、目的港AI必須裝入10號艙”，碼頭規(guī)劃器就決定在10號艙裝入10個A1類集裝箱的每個集裝箱的行和層索引。

積載計劃的研究從單一港口問題開始，即主艙規(guī)劃問題。王崇等人最近的一項研究試圖將堆場管理納入到主港灣平面圖問題當(dāng)中。在對于多港口主港灣平面圖問題的研究中，大多數(shù)論文通常會提出分解方法，提出一種生成多港口航程集裝箱船配載計劃的方法，并將決策過程分解為兩個規(guī)劃子過程：戰(zhàn)略和戰(zhàn)術(shù)。楊欣宇等人提出了一個包括主穩(wěn)定性和應(yīng)力矩計算的壓載艙線性模型，用于處理可變位移。張曉林等人考慮到集裝箱船的艙口和不規(guī)則龍骨，提出了求解多港口主港灣平面圖問題的兩個混合整數(shù)規(guī)劃模型。本文在一個新的解決方案的基礎(chǔ)上提出的混合整數(shù)規(guī)劃模型。這項工作為多港口提出并評估了一種新的混合整數(shù)規(guī)劃啟發(fā)式方法，該方法利用了放松和修復(fù)原理，以迭代的方式解決了混合整數(shù)規(guī)劃模型的松弛問題，逐步修復(fù)了二進制變量的子集，詳細(xì)介紹了一個實驗活動，以顯示所提出的方法的能力，包括在一個有效的工具確定配載計劃的供應(yīng)鏈。本文結(jié)構(gòu)組織如下：正在研究的問題在第1節(jié)中詳細(xì)介紹。對問題的基本混合整數(shù)規(guī)劃模型進行簡短的提示之后，第5部分給出提議混合整數(shù)規(guī)劃啟發(fā)式的主要步驟。假設(shè)結(jié)果在第7部分給出，而第5部分得出了工作的主要結(jié)論和概要。

1 船舶的結(jié)構(gòu)特點

航線(按要訪問的港口的循環(huán)順序描述)和當(dāng)前貨物的問題在于為一組不同尺寸、類型和重量的特定集裝箱以及根據(jù)裝載港和目的港的具體要求確定裝載計劃，以便所有集裝箱都能裝上船，同時滿足結(jié)構(gòu)和操作限制，并將船舶在港口進行裝卸作業(yè)的時間降至最低。

在更詳細(xì)的定義中，多港口主港灣平面圖問題考慮了以下因素:

一艘具有特定結(jié)構(gòu)的船舶，其擁有的屬性分別為港灣、行、層和艙口的集合，即i、j、k和h(見圖1)。

圖1 集裝箱船的結(jié)構(gòu)

的承載能力，即分別對應(yīng)于艙內(nèi)下的艙口位置(艙口位置)和甲板上上的艙口位置(甲板艙口位置)可用的數(shù)量，詳細(xì)說明冷凍箱和開放式頂部容器的裝載能力；關(guān)于船舶穩(wěn)定性的一些要求，以最大交叉平衡公差1和最大水平平衡公差1表示；船舶循環(huán)航線所包括的港口組和船舶考慮行程中的船舶組；運輸節(jié)點的要求，以大小為、類型為、重量等級為的集裝箱數(shù)量表示，以便在目的港裝運。

然后，多港口主港灣平面圖問題包括如何將每組集裝箱分配到船舶艙口上方/下方的位置。組是一組同質(zhì)的集裝箱，涉及尺寸(10或70集裝箱)、類型、重量級和裝貨港()和卸貨港()。確定集裝箱分配的主要目標(biāo)是滿足貨運需求，同時滿足船舶裝載不同類型的集裝箱的能力，并盡量減少船舶在港口進行裝卸作業(yè)所花費的時間。通過減少每個港口并行工作的起重機的重新把手(即非生產(chǎn)性運動)的數(shù)量和裝卸作業(yè)之間的不平衡，可以使得船舶停留在港口時間最短。后一個目標(biāo)是合理的事實，一個港口的時間取決于所需的時間起重機執(zhí)行最大數(shù)量的裝卸作業(yè)。為此，假定在p港口平行服務(wù)于船舶的碼頭起重機的集合類型和在c港口服務(wù)于艙口的子集是已知的。

主要的決定，表示的變量報告如下所定義的模型中提出的氨水等。以及它們受到的主要限制如下：在船舶的艙/甲板艙口的位置分配給定組的集裝箱數(shù)量(具有固定的大小、類型、重量等級、起點港和目的港)，由整數(shù)變量表示，以滿足每組集裝箱的運輸需求。集裝箱到艙口位置的分配必須遵守船舶結(jié)構(gòu)的容量條件，容量條件指裝載在船上的所有集裝箱，但也包括不同類型的集裝箱(標(biāo)準(zhǔn)集裝箱、敞口集裝箱和冷藏集裝箱)。此外，穩(wěn)定性條件也必須通過指派得到重視，特別是水平和交叉平衡必須得到滿足。在貨艙/甲板的艙口位置到目的地d的港口p的指派，由二元變量表示。這個指派在每個港口執(zhí)行，它可以隨著旅程的變化而改變，但在每個港口，只有具有相同目的地的集裝箱才能裝載到每個艙口相同的位置。

在p口處，重新安排可能發(fā)生在艙口h上方甲板上的位置，用于裝載集裝箱前往p口并存放在艙口h下方的貨艙中，用于裝載集裝箱在艙口h下方貨艙的自由位置偏離p口(見圖1)。在p端口過艙口h要執(zhí)行的重新處理操作的數(shù)量等于船舶抵達p端口時裝載在甲板艙位置h而不是運往p的集裝箱的數(shù)量，即裝載在起點和目的地的集裝箱的數(shù)量。通過二元輔助變量和在甲板艙口位置h上，每個港口p處執(zhí)行的重新處理的確切數(shù)目h，來模擬在甲板艙口位置h中執(zhí)行重新處理的需要，由整數(shù)變量。如前所述，第二個目標(biāo)使船舶在港口花費的時間最小化，這與工作起重機的平衡有關(guān)。因此，通過變量計算每個港口每臺起重機的裝卸作業(yè)總次數(shù)；再通過變量計算每個港口的每臺起重機c的裝卸作業(yè)次數(shù)之間的絕對差；通過最大變量表示每個港口每對起重機的裝卸作業(yè)次數(shù)之間的最大差異，表明船舶前方最大起重機的作業(yè)不平衡。

圖2 卸貨裝貨示意圖

2 模型假設(shè)和求解

本節(jié)描述了求解多港口主港灣平面圖問題的兩級漸進隨機固定程序，該程序基于張曉林等人提出的混合整數(shù)規(guī)劃模型而提出，其變量和主約束已在前一節(jié)中簡要描述。以作為多港口主港灣平面圖問題的混合整數(shù)規(guī)劃模型。其運作方式類似于放松和修復(fù)啟發(fā)式。尤其是多港口主港灣平面圖問題的特點是兩種主要類型的決策：由二進制變量建模的目的地位置分配，以及由整數(shù)變量建模的容器位置分配，其值取決于其中一個變量。因此，把變量看作最重要的變量，然后在第一步中，通過最優(yōu)解決一個顯然更簡單的混合整數(shù)規(guī)劃問題來確定它們的值，這個問題中所有的變量都是線性松弛的。然后，啟發(fā)式繼續(xù)嘗試尋找一個可行的解決方案，通過解決原來的問題，所有的位置決定，對應(yīng)的變量是固定在第一步得到的值。然而，第二步可能仍然是相當(dāng)耗時的，所以它被劃分為一個簡單的步驟序列，遵循一種潛水和固定的策略:因為，正如觀察到的一樣，對于多港口主港灣平面圖問題許多變量假設(shè)整數(shù)值在第一步的解決方案，這些變量暫時固定在以下步驟。一般而言，這種固定匯率制度不能有可行的解決方案，或產(chǎn)生的解決方案不夠理想，即與第一步所得的下限之間的差距過大。當(dāng)這種情況發(fā)生時，變量修正被認(rèn)為是約束性過大的，并且對于隨機選擇的一個變量子集它在被逐漸移除。這種策略導(dǎo)致要解決一系列越來越難的混合整數(shù)規(guī)劃問題，這些問題要么在一個可行且足夠好的解決方案時終止。

首先求解模型的部分線性松弛(多港口)，以求得初始解和在尋找整數(shù)可行解過程中利用的某些解。部分松弛是通過線性松弛變量來獲得，這兩個變量分別定義了給定集裝箱的集裝箱數(shù)量，分別用于存放和確定甲板艙口位置。注意，在鏈接到模型中，變量是線性松弛的。注意，由于這種松弛，如果某個變量假定非整數(shù)值，多港口的解可能不是的可行解。另一方面，在多港口的解中，其數(shù)目(通常很大)假定為整數(shù)值。然后，該啟發(fā)式算法對模型的解進行迭代，其整數(shù)變量部分固定于求解多港口的整數(shù)值，每次迭代時，所有的二進制變量都固定于求解多港口的值，以及在解中值為整數(shù)的變量子集給定百分比百分位數(shù)。將值初始化為100%，并在迭代過程中降低。

這個過程被稱為“漸進隨機固定”，在迭代過程中，它試圖解決模型固定了一個隨機選擇的整數(shù)變量子集，其基數(shù)逐漸減少。此外，在求解給定前綴的模型之前，考慮與所找到的第一個整數(shù)解相關(guān)的下界，對獲得優(yōu)質(zhì)解的可能性進行評估。采用星期天條件，最長時間限制為5 600秒，或滿足給定的容忍值。請注意，如果找到一個高質(zhì)量的解決方案變得太困難，即當(dāng)其逼近零時，公差值增加，因此放松了一個終止條件。然而，如果考慮的實例是可行的，啟發(fā)式返回的最終解決方案總是模型m的可行解決方案，因此是多港口主港灣平面圖問題的可行解決方案。

注意，在每次迭代中，要評估當(dāng)前部分固定的模型多港口f是否可探索，即是否值得求解。這是通過檢查與多港口f的第一個解相關(guān)的下界與多港口r解的目標(biāo)值之間的絕對差是否小于給定的公差來完成的。當(dāng)有跡象表明生產(chǎn)的溶液質(zhì)量不能滿足終止條件時，引入這樣的測試來加速停止部分固定模型的溶液的計算。在這種情況下，百分比被降低，整個評估過程被重復(fù)。第八個步驟實現(xiàn)終止條件；具體來說，如果下列三個條件中的一個成功，則停止：

得到的解決方案的兩個方案質(zhì)量相當(dāng)，即目標(biāo)函數(shù)值在來自其的公差范圍內(nèi)；在解決可探索的多港口的最大迭代次數(shù)之后，終止條件()被放松，新的放松的終止條件包括驗證下限是否在下限值的公差范圍內(nèi)；整數(shù)變量修正的百分比為零；這表明在模型多港口中，最后只有二進制變量是固定的。由于要固定的變量是隨機選擇的，因此步驟9的作用是允許一定數(shù)量的嘗試，然后在每當(dāng)為這樣的百分比生成可探索的多港口時減少。最后，如果將最小正閾值設(shè)置為，則步驟10將其重置為1.0，并且在降低到以下時增加公差值。

計算結(jié)果上一節(jié)描述的混合啟發(fā)式中實現(xiàn)，使用混合整數(shù)規(guī)劃求解器cplex11.5。所有的測試都運行在一臺1.7GHz的IntelCore1Twoe6 600計算機上，7gb內(nèi)存。計算測試基于多港口主港灣平面圖問題的隨機生成實例，這些實例代表了真實場景。三艘容量分別為7 800、10 000和18 051標(biāo)準(zhǔn)桿的集裝箱船進行這些測試。每艘集裝箱船都有一定的容量來裝載冷藏集裝箱和開口集裝箱。這些容量范圍從800至1 680的冷藏集裝箱和從1 560至1 576的開放式頂部集裝箱。集裝箱最常見的三種重量級:輕型、中型和重型。每個級別的重量限制對10和70集裝箱是不同的，包括10集裝箱，分別達到7噸、17噸和11噸，70集裝箱，分別達到10噸、20噸和50噸。

每艘船行駛在一條有6個港口的圓形航線上，運輸需求是隨機產(chǎn)生的，對于航線上的每一個原產(chǎn)地以及對于航線上連續(xù)三個港口的標(biāo)準(zhǔn)、冷藏和開放頂部集裝箱都有積極的需求。例如，在規(guī)劃5號港口的配載時，船上的貨物來自于在1、5和7號港口進行的裝載作業(yè)。在5號港口，卸貨作業(yè)完成后，裝貨過程涉及裝往6號、1號、7號港口的集裝箱，其中1號和7號港口表示船舶在第二回合期間到達的1號和7號港口。每艘集裝箱船產(chǎn)生四個實例，每個實例與其他實例不同，以滿足運輸需求。無論如何，所有實例都是以這種方式產(chǎn)生的，以強調(diào)啟發(fā)式方法在短時間內(nèi)擁有獲得可行和有效解決方案的能力。表1就每艘被考慮的船舶(即小型船舶、中型船舶和大型船舶)報告占用船舶的百分比水平離開所考慮航線的港口時，船舶所需容量的百分比與每個端口的裝載需求相關(guān)聯(lián)。請注意，船舶的占用水平是以船上的載重量與船舶載重量的比率來計算的。這兩個參數(shù)給出了實例求解難度的一個概念：給定一定比例的船舶所需容量，船舶的占用率越高，實例求解的難度越大。

表1 所考慮的集裝箱船的平均占用特征

在生成的例子中，在每個港口裝載的貨物需要占船舶容量的75%。每個港口裝載的集裝箱有75%是10英尺集裝箱。此外，平均80%的貨物與標(biāo)準(zhǔn)貨柜有關(guān)，10%為冷藏貨物，10%為敞口貨柜，平均入住率超過85%。模型適用于所考慮的情況有一些變量，從最小的船舶的95 511到最大的船舶的159 501，以及相應(yīng)的一些約束，從16 708到71 618。

為了評估所提出的啟發(fā)式算法的有效性，將1和1參數(shù)與穩(wěn)定性條件相關(guān)，分別固定在不同的和更強的數(shù)值上，范圍從船舶總重量的0.1%到0.01%。更準(zhǔn)確地說，在定義配載計劃時，穩(wěn)定性十分很重要；在目前的研究中，穩(wěn)定性條件對應(yīng)船舶離開其航線每個港口時在船上貨物上計算的水平和交叉平衡。固定在總重量的0.01%的穩(wěn)定性值可以被視為一個相當(dāng)不現(xiàn)實的情況，例如，最大船允許的最大穩(wěn)定性公差對應(yīng)于一個10英尺或70英尺的重型集裝箱，兩個10英尺或一個70英尺輕型集裝箱。然而，這種限制性的公差值僅僅是為了強調(diào)擬議的混合整數(shù)規(guī)劃的啟發(fā)式能力。

所執(zhí)行的測試比較了其啟發(fā)式和混合整數(shù)規(guī)劃求解器所產(chǎn)生的啟發(fā)式的性能。這兩種方法的最大時間限制是固定值5 600秒。目標(biāo)函數(shù)中的權(quán)重以這種方式確定，比以考慮重新處理起重機不平衡更不理想的十倍。啟發(fā)式的公差相當(dāng)于接受一個絕對最優(yōu)間隙等于1的解決方案作為最優(yōu)解(即，一次操作的最大起重機不平衡)。表1列出了由其得到的結(jié)果，顯示了三種類型的集裝箱船和不同穩(wěn)定公差(1-1)的整體目標(biāo)函數(shù)()、重新處理的數(shù)量()、最大起重機操作不平衡()和計算時間()的值。表1的每一行報告了四個已解決實例的平均值。特別是部分放松（多港口）和部分固定（多港口）模型產(chǎn)生的解決方案，以及其()的總計算時間。

與混合整數(shù)規(guī)劃的比較可以通過觀察表1中的最后一列來完成，該列報告了由其獲得的時間，相對于混合整數(shù)規(guī)劃solver所需的時間的百分比偏差，以產(chǎn)生完全相同的結(jié)果。時間列中顯示破折號的單元格，表示混合整數(shù)規(guī)劃求解器在計算一小時內(nèi)無法找到可行解的實例。在灰數(shù)的情況下(相同的實例的情況)，數(shù)據(jù)是在5 600秒的時間限制內(nèi)由模型解決的那些實例的平均值(即7個實例中的5個)。可以觀察到其高計算性能，它能夠找到所有情況下的最優(yōu)解(由于最終下界嚴(yán)格大于零，因此對于那些沒有被混合整數(shù)規(guī)劃解算器解決的情況也可以證明最優(yōu)性)。對于所有和實例，其需要的計算時間小于170秒，而實例的平均時間為1 571秒，結(jié)果表明更難求解，但是啟發(fā)式所需的總體時間561秒是可以接受的，除了較難的7種情況外，它可以降低到161秒。表2報告了在5 600秒的時間限制內(nèi)求解模型所獲得的結(jié)果。對于三種類型的集裝箱船和兩個不同的穩(wěn)定性公差值(1-1=0.100%和0.050%)，如表1所示，整體目標(biāo)函數(shù)()的值、重新處理的數(shù)量()、最大起重機操作不平衡()和計算時間()。

表2 啟發(fā)式程序得到的結(jié)果

3 結(jié) 語

多港口主港灣規(guī)劃問題(多港口主港灣平面圖問題)是海運物流中一個非常關(guān)鍵的優(yōu)化問題，尤其是對于海運碼頭和港口作業(yè)的效率而言。多港口主港灣平面圖問題涉及兩個決策者，即船舶協(xié)調(diào)員和終端規(guī)劃員，他們有不同的觀點和信息，都能夠快速和良好地解決方案。為了支持這些決策過程，文章提出了一種混合整數(shù)規(guī)劃啟發(fā)式方法，目的是確定集裝箱船循環(huán)航線的配載計劃，即不同類型、大小和目的地的集裝箱必須裝船運往目的地。以船舶的最小停泊時間為目標(biāo)函數(shù)，并考慮了船舶和航線所涉及碼頭的結(jié)構(gòu)和操作約束。該啟發(fā)式算法依賴于文獻中最近提出的一個非常有效的混合整數(shù)規(guī)劃模型，可以在非常短的計算時間內(nèi)得到18000艘集裝箱船的可行解。在已有計算結(jié)果的基礎(chǔ)上，我們相信在一個合適的工具中實現(xiàn)這種混合整數(shù)規(guī)劃啟發(fā)式可以真正有效地支持和改進配載計劃的定義。