船舶組合分段堆場調度方法

孟令通， 蔣祖華， 陶寧蓉， 劉建峰， 李柏鶴

(1. 上海交通大學 機械與動力工程學院， 上海 200240； 2. 上海海洋大學 工程學院， 上海 201306；3. 上海外高橋造船有限公司， 上海 200137)

在現代造船行業中，船舶建造以分段作為基本生產單元.分段在建造車間脫胎后，需經過預舾裝、舾裝、涂裝、總組等工藝流程，再到船塢進行搭載并最終合攏成整船.為了協調各工藝流程的工作節拍，船廠中劃分了若干堆場用于在生產流通過程中臨時存放分段.堆場中的調度作業是靠平板車完成的，為了減少平板車的運輸耗油量、提高堆場的調度作業效率，優化堆場調度方法至關重要[1].

利用現有的堆場布局方式及調度方法，只能解決單一規格分段的調度問題.在多規格分段堆場的堆位布局和堆場調度中，通常以犧牲空間資源利用率來達到簡化調度作業的目的.由于經驗型堆場布局過多，容易導致調度作業效率下降、空間利用率過低等問題.實際上，許多分段工藝具有相似性，只要組合分段的堆置時間相近且形狀互補，就能夠堆置在同一堆位中.設計針對組合分段的堆場調度方法，可以有效地增加堆場的空間利用率、提高船舶的生產效率，同時降低堆場的調度成本.

分段堆場調度問題是一種考慮時間及空間約束的調度問題.該問題的核心是優化船舶分段在堆場中的堆位分配、進出堆場路徑及任務執行順序，并最終達到分段存取物流成本最小化的目標[2].文獻[3]分析了分段堆場調度問題的物流成本，將阻擋分段的移動作為非增值運輸，提出了分段堆位選擇策略和阻擋分段移動策略，并在此基礎上研究了分段移動次序和堆場布局對調度結果的影響.文獻[4]重新定義了分段堆場調度問題，將堆場劃分為若干個堆位，分段與堆位之間一一對應，則分段堆場調度問題可以轉化為堆場中的堆位選擇問題.文獻[5]將任務執行順序作為堆場調度的優化目標之一，提出啟發式堆位分配策略，并通過禁忌搜索算法進行求解，提高了分段在堆場內的周轉效率.但是，上述研究均假設運輸路徑為直線，且阻擋分段在移動后要放回原堆位，這種調度方式的分段移動條件較為苛刻，增加了分段的重復運輸，僅適用于場地規模較小的堆場.為了解決這些問題，文獻[6]將分段移動度作為優化目標，通過最短路徑算法求解分段運輸的直角折線路徑，減少了調度過程中阻擋分段的移動.文獻[7]將運輸分段的平板車數量作為優化目標，構建分段搬運兩階段優化模型,通過遺傳算法求解運輸路徑，降低了平板車數量.文獻[8]考慮了分段調度過程中的隨機擾動，并利用改進遺傳算法進行求解.文獻[9]針對隨機進場的分段，提出用反向傳播神經網絡來預測一個周期內進出場的分段數量，并研究建立了以分段移動度最小為目標的優化模型.文獻[2]考慮了分段進場時間窗，提出了5種阻擋分段移動策略，利用多鏈DNA遺傳算法進行求解，并驗證了其收斂性.上述研究從不同角度對分段在堆場內的運輸進行了優化，雖然將運輸路線由單一的直線變為折線，但降低堆場調度成本的關鍵在于減少阻擋分段的移動數量.

除了堆場布局和運輸路線外，堆場分段形狀對堆場調度問題也有著重要影響.文獻[10]將船體分段在場地上的加工抽象成凸多邊形在矩形平面上的二維空間布局問題，應用可配置空間的概念定義可放置空間集，縮小了空間布局的搜索空間.文獻[11]基于分段形狀和投影交叉分析，研究梯形分段的空間約束，構建時空利用率模型對分段進行調度，提高了堆場利用率.文獻[12]針對帶有進場時間窗的不規則分段在堆場中的調度，采用遺傳算法和最大平均空閑矩形的空間定位策略對分段的進出場順序、位置和方向進行了優化，同時考慮了不規則分段的擺放角度對場地利用率的影響，解決了不規則分段的動態場地堆放問題.但是，上述研究并沒有劃分堆場，僅適用于分段數量較少的情況，且大多采用吊裝設備直接運輸到位，并不適用于平面運輸.

目前，船舶的分段堆場調度研究中大部分針對的是單一規格、堆位固定且只能容納1個分段的情況，進場分段堆位分配多數采用隨機分配的方式，阻擋分段的移動策略大多采用放回式策略.然而，這些研究并沒有分析堆場四周道路通行情況對分段運輸效率的影響.

針對上述問題，本文提出一種組合分段堆場調度模型，以及進場分段堆位分配策略和阻擋分段移動策略；基于運輸方向的深度優先搜索算法得到分段任務執行時的路徑，并設計遺傳算法與禁忌搜索相結合的混合式算法求解任務分段的執行順序；最后，討論了堆場四周道路通行能力對運輸效率的影響，對比分析了場地規模、調度周期、堆場占用率等不同因素對調度結果的影響.

1 問題建模

1.1 問題描述

針對多規格梯形分段，在由W×H個矩形堆位組成的四面通行堆場中，每個堆位可以堆置1個大型分段或2個小型分段.堆置多個分段時，各分段之間存在相互干涉,會影響分段進出堆場的方向.分段移動有以下3種類型：① 將分段存放于堆場的空堆位或組合堆位；② 從堆場中取出分段；③ 將阻擋分段移動至其他空堆位或組合堆位.

給定一組多規格分段進出堆場的任務，分段進出堆場時可能會有阻擋分段在其移動路線上，進而導致產生分段的無效移動.因此，通過規劃進出場分段移動路線、進場分段堆位、阻擋分段堆位及分段任務的執行順序能夠使調度周期內阻擋分段的數量最小.為了保證調度的準時性，分段任務需滿足進出堆場的設定日期.

多規格分段堆場內的調度應遵循如下規則：

(1) 組合分段在堆場中的堆置不可堆疊，且不可超出堆位范圍，在堆位完全清空前禁止平板車的運輸及通行.

(2) 堆場四周環繞道路，任務分段可以從上下左右4個方向進出堆場.

(3) 進場分段至少在堆場中存放1天，若是分段當天進當天出，則將其視為直接進入下一工藝階段.

(4) 進場分段和阻擋分段按照策略進行移動，進場分段進場時允許產生阻擋分段，但阻擋分段在位置再次分配時不允許再次產生阻擋.

(5) 分段移動時遇到阻擋分段時的成本遠大于無阻擋時的成本，故最短距離指路徑上的阻擋分段最少.

(6) 一個堆位需通過文獻[13]中的內外接多邊形方法，依據分段的尺寸形狀判斷其能否組合堆置.若能，則為組合堆位，并得到組合內分段移動時相互干涉的方向.

1.2 數學模型

一個4×5規格的組合分段堆場，其四周均為道路，可供載有分段的平板車進出.該堆場第5天的狀態如圖1所示，75和56分別表示該堆位有7號和5號2個分段，其計劃出場時間分別是第5天和第6天.當7號分段移出堆場時，其較短路徑有實線和虛線2條，由于組合分段存在干涉，向右或向下移動時組合分段會產生阻擋，即在選擇虛線路徑時要移動27號和5號2個分段，阻擋分段數量為2；而實線路徑僅需移動9號分段，阻擋分段數量為1，因此選擇實線作為最短調度路線.

圖1 組合分段堆場實例Fig.1 Sketch of combined block storage yard

決策變量：

目標函數：

(1)

(2)

(3)

dRi,j∈di,j

(4)

(5)

(6)

bi,j≤bi,j′

(7)

目標函數求解的是當前周期內分段調度任務產生的阻擋分段最小值.前半部分是進場分段(sb)任務的阻擋分段數量，其中t+1表示分段i至少在堆場中停留1天；后半部分是出場分段(rb)任務的阻擋分段數量，其中t-1表示分段在出場之前堆位不變.阻擋分段在移動后會重新分配堆位.

采用遺傳算法與禁忌搜索相結合的混合式算法求解上述問題，并利用深度優先搜索算法逐一求出任務分段進出堆場時的最短路徑.式(2)保證了每個分段只執行1次進場或出場任務；式(3)表示在堆場中同一個堆位上至多可以堆置2個小型分段；式(4)表示由于分段之間的相互干涉影響了分段進出堆場時的移動方向，所以任務分段最短路徑方向要與分段允許進出堆位的方向一致，若兩者不同，則會增加阻擋分段數量；式(5)保證了進場分段要在其規定進場時間內進入堆場；式(6)保證了出場分段要在其規定出場時間內移出堆場；式(7)保證了任務分段經由阻擋最少的路徑進出堆場.

2 模型求解

2.1 求解組合分段最短移動路線

在組合堆場中，相互組合的分段在運輸時可能會限制彼此的移動方向，此時將堆位作為節點處理會使得求解過程過于繁瑣.利用深度優先搜索算法，遍歷任務分段行進方向上的所有路線，即可找到進場分段進入某堆位或出場分段從某堆位運輸到堆場邊緣的最短路線，其詳細步驟如下.

步驟1確定分段的初始堆位，設最小阻擋分段數量bm=+∞，當前阻擋分段數量b=0.選取分段允許的移動方向作為初始移動方向d.若選擇的方向被組合分段阻擋，則b=b+1.

步驟2選擇當前堆位的分段移動方向，注意不能與初始移動方向或已選擇的移動方向相反，記該方向為d′.

步驟3判斷移動方向上的堆位是否堆有分段，若有，則b=b+z(z為堆位上的阻擋分段數量)，并記錄該堆位.

步驟4判斷堆位是否位于堆場邊界.

(1) 若是邊緣堆位，則得到阻擋分段數量b.如果b

(2) 若不是邊緣堆位，則返回步驟2.

步驟5選擇當前堆位的前驅堆位改變移動方向并修正b值，執行步驟3，直至將初始堆位移動方向遍歷完畢，執行下一步驟.

步驟6返回最短路徑堆位編號及bm.

2.2 組合分段堆位分配策略

分段任務分為進場分段任務和出場分段任務，這些任務在執行過程中可能會產生阻擋分段.為了減少進場分段和阻擋分段對后續分段任務造成的影響，采用非放回式分段移動方法(即在阻擋分段讓路后重新分配堆位)，通過進場分段堆位分配策略和阻擋分段移動策略，選擇進場分段對堆場影響指標最小的位置堆置分段，進而減少阻擋分段的數量.

任務分段的堆位對堆場的影響分為兩種：① 可能阻擋出場分段的移動；② 可能阻擋進場分段進入空堆位或組合堆位.由于每個堆置于堆場的分段或空堆位都有當前進出堆場的最短路徑，在空堆位或組合堆位上堆置新的分段可能會使阻擋分段有所增加，所以通過計算進場分段對堆場已有分段移出堆場的影響指標α和分段移入空堆位的影響指標β，在候選堆位集合中選擇任務分段i的堆位.

圖2所示為分段在堆場中的布局示意圖和影響系數矩陣，標紅部分分別是進場分段(左)和預計產生的阻擋分段數量(右).由于影響分段出場的只能是出場時間較晚的分段，所以在預計某分段移出堆場的阻擋時可以忽略出場時間較早或同時出堆場的分段.例如，在圖2的案例3中，進場8號分段允許與25號分段組合堆置，雖然進場分段可能會限制25號分段的出場移動方向，然而25號上方的分段出場時間較早，因此，該組合堆置并不會增加25號分段的出場難度，即可以計算得出α=0.

圖2 進場分段堆位選擇策略示意圖Fig.2 Illustration of selecting location for the incoming block

進場分段堆置于堆位k對堆場的影響指標Vk=α+β.然而，通過這種方式計算得到分段進場對整個堆場的影響時，可能會出現權重相同的情況.為了避免出現這種情況，在符合組合堆置要求的堆位中，應首先選取移動時間相近的堆位，或通過文獻[3]中的方式選取堆位編號較大的堆位進行組合堆置.需要注意的是在選擇過程中仍需考慮進場分段進入堆場不同堆位后產生的阻擋分段數量.

2.2.2阻擋分段移動策略 阻擋分段的運輸需在任務分段執行前完成.阻擋分段的堆位重新分配策略與進場分段堆位分配策略類似，但在位置再分配時不允許再次產生阻擋分段，其具體步驟如下.

步驟1獲取任務分段執行時的阻擋分段.

2.3 混合算法設計

在堆場調度時，組合分段的堆位選擇由啟發式算法確定，進出堆場路線由組合干涉與深度優先搜索算法產生，因此優化任務分段執行序列才是堆場內調度問題的核心.遺傳算法有并行搜索能力，在一定程度上能保留歷史信息，適合求解大規模的全局優化問題，但其局部搜索能力差，變異概率小，引入新染色體機會少，所以采用綜合了大范圍搜索的遺傳算法與局部搜索的禁忌算法的混合算法求解分段任務執行序列.

2.3.1遺傳算法設計 初始種群由周期內的任務分段按照各分段的執行日期隨機產生，每條染色體代表1種任務執行序列.染色體上的每個基因記錄了任務分段的執行信息，包括進場分段的位置分配、路徑的選擇和阻擋分段的移動.進場任務用S表示，出場任務用R表示.

根據任務執行序列，計算每條染色體產生的阻擋分段數量，具體步驟：① 取堆場初始的占用狀態；② 按照堆位分配策略選擇進場分段堆位，利用深度優先搜索選擇分段進出堆場的路徑，得到任務執行過程中的阻擋分段數量；③ 用阻擋分段移動策略處理阻擋分段；④ 更新堆場狀態，執行下一個任務.由此得到目標函數F，遺傳算法的適應度f*=M-F，M為足夠大的整數.為了提高算法的收斂速度，采用比例復制和輪盤賭的方法選取染色體.其中：比例復制為將適應度靠前的個體直接復制到下一代；輪盤賭為根據個體適應度計算出的概率決定是否復制到下一代.下一代的其余個體由單點交叉(見圖3(a))和交換變異(見圖3(b))產生.由于交換后的序列往往存在任務重復、任務遺漏、時間交錯等問題，所以在染色體交叉后需要進行基因修復，以保證任務分段的執行時間不會發生變化.新一代種群由比例復制、輪盤賭、單點交叉及交換變異產生，其占比分別為PE,PR,PC,PM.

2.3.2禁忌搜索設計 對每一代種群中適應度值最大的個體進行禁忌搜索.禁忌搜索是組合堆場調度過程的局部最優搜索.其鄰域搜索過程如圖4所示，解的鄰域空間通過以下步驟獲取：① 選擇當前種群中適應度值最大的個體；② 選擇周期內的某一天將任務分段插入當天其他的堆位執行；③ 檢測搜索結果的可行性，保證堆場不會被分段堆滿.將鄰域操作的檢測結果記錄于禁忌表中，以避免循環操作.

圖3 染色體交叉變異Fig.3 Crossover and mutation for chromosomes

圖4 鄰域搜索Fig.4 Neighborhood search

每個任務用(t,x1,x2)表示，其中：x1表示隨機選擇調整位置的任務；x2表示任務x1將要插入的位置.禁忌表的長度表示在迭代過程中不能選擇禁忌對象的步數.迭代系數有2個：Iter代表總迭代次數；NIter代表計算結果沒有提升的迭代次數.

2.3.3混合算法的流程

步驟1設定初始參數，包括最大迭代次數N，種群規模Z，子代生成比例PE、PR、PC、PM，禁忌搜索最大迭代次數MaxIter，和最大無效迭代次數NonIter.

步驟2按照周期內的日期順序，對任務序列進行編碼，當前迭代次數n=0.

步驟4計算個體適應度

其中適應度最高的個體為xbest，其任務序列為seq，設最優適應度F*=f*(xbest).

步驟5對于任務序列seq，禁忌表TL=?，Iter=NIter=0.

步驟6隨機生成seq的鄰域變換(t,x1,x2)，產生鄰域集合S(seq).

步驟8Iter=Iter+1，NIter=NIter+1，若 Iter>MaxIter或NIter>NonIter，則執行步驟9；否則返回步驟6.

步驟9將所有個體按照適應度值由大到小排列，直接保留比例為PE的精英個體，利用輪盤賭選擇比例為PR的個體.

步驟10隨機選取父代中的2條染色體進行單點交叉，產生比例為PC的子代.

步驟11隨機選取父代中的2條染色體進行交換變異，產生比例為PM的子代.

步驟12若n

步驟13停止運算，輸出xbest和任務序列seq.

3 算例分析

3.1 實例驗證

表1 3種調度方法的結果對比Tab.1 Comparisons of three scheduling strategies

由表1可知：M2和M3中組合分段堆場處理的任務分段數量更多；M2的目標函數值較高，但阻擋分段的比例優于M1，說明進場分段及阻擋分段移動策略較文獻[4]中的方法更好，在一定程度上減少了阻擋分段的產生；M3的調度結果明顯優于M2，說明任務執行序列對調度結果的影響十分顯著，任務執行周期內進入堆場的分段會對后續分段的調度產生很大的干擾，而通過混合算法可以從一定程度上減少分段的再次阻擋，從而提高堆場的調度效率，減少阻擋分段數量.此外，堆場布局和堆場平均占用率也對調度結果有著一定的影響.隨著堆場與道路間通道的減少(3×20、4×15、5×12、6×10的堆場，通道數量依次為46, 38, 34, 32)，F及r隨之增加；隨著μ的增大，即堆置的分段越來越密集，F及r隨之增加；隨著調度周期長短的變化，F及r并無直接的變化關系.由此可得，堆場布局以及堆位平均占用率是影響堆場調度成本的兩大因素，通過啟發式策略分配堆位和混合算法能有效地降低阻擋分段的數量.

3.2 調度結果分析

圖5 通行能力及堆場平均占用率對調度結果的影響Fig.5 Influence of capacity and workload on different scheduling strategies

由圖5(a)可知： 堆場布局為3×20的堆場在所有通行情況中，r都是最小的；當堆場四周為三面通行或兩面通行時，r較為固定(約為20%)，說明堆場布局對調度結果的影響較小；當堆場為四面通行或單面通行時，r浮動較大，變化范圍超過10%，說明在這2種條件下， 堆場布局對調度結果的影響十分顯著.由圖5(b)可知：當μ相同(即任務數量相同)時，F隨堆場布局由“扁平”到“均勻”逐漸增大；當μ逐漸增加，堆場布局為3×20的堆場F值的增幅明顯小于堆場布局為6×10的堆場，說明越“均勻”的堆場，場地復雜度越高，各分段之間更容易產生空間上的干涉.

4 結論

針對船舶分段堆場調度過程中經驗型堆場布局過多、作業效率低下、空間利用率過低等問題，提出一種組合分段堆場調度模型，有效地增加了堆場處理任務分段的能力.同時，通過對比堆位分配策略與傳統策略以及混合算法優化前后的分析結果，證明了該調度分配策略與混合算法的有效性，獲得的主要結論如下：

(1) 構建組合分段堆場調度模型，考慮單一堆位堆置組合分段的情況和堆位內分段之間的干涉，并與深度優先搜索相結合，規劃任務分段堆場內的移動路線，減少了分段的無效移動，提高了堆場的利用率.

(2) 考慮任務分段分別對出場分段移動和進場分段進入空堆位的影響，提出進場分段堆位分配策略及阻擋分段移動策略，相比原有的隨機分配進場分段堆位方式，阻擋分段數量明顯減少.

(3) 考慮任務分段執行順序，以阻擋分段最少為優化目標，通過混合算法求解得出進場任務堆位、阻擋分段堆位、進出場任務移動路線以及任務分段執行序列，進一步減少了阻擋分段的數量，相比遺傳算法，從一定程度上避免了陷入局部最優解.

由于船廠的條件限制，所提方法僅利用模擬數據進行驗證，并未使用船廠的實際生產數據，對實際生產中可能遇到的問題還需進一步研究.另外，本文僅針對矩形堆場和2種規格的梯形分段進行調度，對于形狀不規則堆場或任意規格分段的調度方法，還需進一步深入研究.