干擾約束下考慮分組作業(yè)面的岸橋AGV聯(lián)合調(diào)度

梁承姬，申 哲，張 悅

上海海事大學 物流科學與工程研究院 物流研究中心，上海 201306

1 引言

近年來，伴隨著全球貿(mào)易的進行，集裝箱貨運量也在不斷的增長。如今，自動化集裝箱碼頭已經(jīng)逐漸成為未來碼頭的一大發(fā)展趨勢，岸橋和AGV 作為自動化碼頭的重要設備，存在一些固有的干擾約束，易對設備的作業(yè)和調(diào)度產(chǎn)生限制或負面影響。岸橋依靠軌道進行移動，無法跨越作業(yè)，且為了作業(yè)安全，相鄰的岸橋之間還存在安全距離的約束；AGV有規(guī)定的、固定的行進路線，在多個AGV 共同運作情況下易出現(xiàn)堵塞干擾現(xiàn)象。因此，在干擾約束下，如何對岸橋和AGV進行合理的調(diào)度顯得尤為重要。

岸橋調(diào)度問題（QCSP）是在已知船舶岸橋服務數(shù)量的前提下，為了達成船舶在港時間最短的目標，在滿足相關(guān)的約束情況下，對岸橋的任務作業(yè)順序進行優(yōu)化。針對這一問題，Kasm等[1]在考慮單一船舶不可交叉和安全距離約束下，提出了一個新的精確且計算快速算法來解決岸橋調(diào)度問題。Liang 等[2]從岸橋的任務調(diào)度和數(shù)量配置兩個方面研究岸橋調(diào)度問題，通過分析兩個問題之間的關(guān)系，建立兩者之間的耦合關(guān)系并設計了一種循環(huán)迭代法來求解耦合模型。Si等[3]以最小化最大完工時間為目標研究了泊位分配問題和岸橋分配問題，并將泊位時間、岸橋、泊位變?yōu)榫匦卧u價塊，將整個問題轉(zhuǎn)化為新的三維矩形模型并與傳統(tǒng)建模方法和算法進行了比較。范志強[4]考慮到岸橋?qū)嶋H作業(yè)范圍的約束，無法全岸線移動，結(jié)合岸橋其他特有約束，構(gòu)建新的混合整數(shù)規(guī)劃模型，并設計算法來提高調(diào)度效率。張皓博[5]分析了岸橋作業(yè)與堆場任務均衡之間的關(guān)系，建立雙目標混合整數(shù)規(guī)劃模型，在最小化船舶在港時間的前提下，減少作業(yè)的不均衡量。Bierwirth 等[6]考慮了泊位分配，岸橋調(diào)度的綜合方法的模型的特征對文獻進行分類。確定了該領(lǐng)域的趨勢，討論并評估了模型和算法的優(yōu)劣。

AGV 是自動化碼頭的另一重要設備，它將岸線與堆場連接起來，負責集裝箱的運輸工作，良好的AGV調(diào)度與路徑優(yōu)化能夠有效減少運輸時間和成本。目前，碼頭多采用全岸線作業(yè)面調(diào)度模式，AGV 空閑就能被調(diào)用。在這一方面，呂品等[7]在總結(jié)大量集卡調(diào)度研究的基礎(chǔ)上，采用作業(yè)面調(diào)度模式建立同時對兩條船舶進行裝卸作業(yè)的集卡路徑優(yōu)化模型，驗證這一模式能夠有效提高集卡工作效率。王軍等[8]為了避免集卡大量的空載導致資源浪費效率低下，考慮了集卡運輸路徑中各部分的工作時間，建立作業(yè)面模式下的集卡動態(tài)調(diào)度模型，規(guī)劃最優(yōu)運輸路徑，提高裝卸效率。仲美穌等[9]結(jié)合道路交通理論，為避免大量的AGV 在碼頭行駛時產(chǎn)生交叉堵塞，提出交通虛擬環(huán)島策略，并設計仿真模型證明其優(yōu)化能力。丁榮濤[10]引入基于時間窗的沖突反饋機制，設計基于能力約束判斷的資源協(xié)作模型，解決吊裝作業(yè)溢出問題。為避免局部收斂，模型應用了改進的量子遺傳進化算法進行求解。

關(guān)于設備的協(xié)調(diào)調(diào)度，近年來也有一些研究。Tang等[11]就集裝箱碼頭岸橋和集卡的聯(lián)合調(diào)度問題，對于僅有進口箱的單向流動問題，集卡在不運行出口箱的情況下返回碼頭，以最小化完工時間為目標制定混合整數(shù)規(guī)劃模型。然后開發(fā)了一種改進的粒子群優(yōu)化算法（PSO）來解決這個問題。Vahdani等[12]整合了岸橋分配與內(nèi)集卡共享，通過將內(nèi)集卡分享到不同的碼頭岸線，來實現(xiàn)碼頭工作量與內(nèi)集卡之間的平衡，建立雙目標模型，在最小化運營成本的前提下，降低碼頭最大溢出工作量。He等[13]討論了集成岸橋調(diào)度，集卡調(diào)度和場橋調(diào)度的問題。建立混合整數(shù)規(guī)劃模型，并開發(fā)了一種基于仿真的集成優(yōu)化方法來解決該問題。Chen 等[14]提出了一個考慮堆場、集卡、場橋的整數(shù)規(guī)劃模型。目標是最小化所有卸載操作已完成且所有容器已堆疊在存儲塊中的時間。并開發(fā)了局部序列切割（LSC）方法來解決該問題。Narges等[15]開發(fā)了一種混合整數(shù)規(guī)劃模型，用于聯(lián)合調(diào)度岸橋和集卡。并開發(fā)了遺傳算法與貪婪算法相結(jié)合的算法來解決這一問題。

從上述的研究中不難發(fā)現(xiàn)，AGV 調(diào)度基本采用全岸線作業(yè)面或作業(yè)線的模式。作業(yè)線模式空載率高，效率低下，全岸線作業(yè)面模式下AGV 會出現(xiàn)更多的交叉堵塞。而在聯(lián)合調(diào)度中則主要針對岸橋進行忽略AGV的優(yōu)化。為此，本文將從岸橋與AGV 協(xié)調(diào)調(diào)度角度出發(fā)，動態(tài)調(diào)度岸橋。針對岸橋任務變化，本文提出分組作業(yè)面這一新的調(diào)度模式對AGV 進行調(diào)度，以達到全岸線多設備的快速聯(lián)動，從而得到最佳的岸橋AGV 聯(lián)合調(diào)度方案。

2 問題描述

岸橋和AGV是自動化集裝箱碼頭海側(cè)作業(yè)的重要設備。傳統(tǒng)的作業(yè)模式中岸橋的服務遵循單船服務，即岸橋在結(jié)束當前船只所有任務后，根據(jù)調(diào)度計劃的指示為下一艘船只服務或者進入閑置等待狀態(tài)。這一調(diào)度模式下，岸橋的作業(yè)能力會因船只任務量的不均衡被限制。AGV則是遵循全岸線作業(yè)面調(diào)度。在碼頭整個岸線長度范圍內(nèi)，目標箱出現(xiàn)時就調(diào)度空閑AGV，不考慮兩者之間的距離問題。相較于AGV只服務于一個岸橋的作業(yè)線調(diào)度，作業(yè)面調(diào)度減少了大量的AGV 空載時間，提高了AGV的運輸效率。但是由于AGV是固定路線工作，全岸線長度范圍、多AGV的調(diào)度易造成行進路線上更多的堵塞等待現(xiàn)象。

針對上述問題，本文從整體出發(fā)，以貝位為基礎(chǔ)將集裝箱碼頭岸線劃分為若干個長度相同的單位。船舶入港后岸橋按照船舶占據(jù)的貝位進行工作（不足一個貝位的按照一個貝位計算）。對岸橋和AGV 進行聯(lián)合調(diào)度，改進兩種設備的作業(yè)方式并通過岸橋作業(yè)時刻表將兩者聯(lián)系起來。

岸橋調(diào)度方面，對岸橋進行動態(tài)調(diào)度。岸橋可以根據(jù)船舶任務量在執(zhí)行完當前任務中途停止作業(yè)并更換作業(yè)船舶，使岸橋作業(yè)量趨近平衡，提高整體作業(yè)效率，減少岸橋最大完工時間。

AGV 調(diào)度方面，本文提出一種分組作業(yè)面的調(diào)度形式。將全岸線分為多個小的作業(yè)面，并劃分AGV 所屬的作業(yè)面。AGV在這個小的作業(yè)面中依舊遵循作業(yè)面作業(yè)的規(guī)則，即空閑就調(diào)用，但AGV的移動范圍僅限于該作業(yè)面。這一新的調(diào)度模式，旨在盡可能減少AGV 路徑交叉堵塞時間與長距離跑動次數(shù)的前提下，最小化AGV的最大作業(yè)時間。具體形式如圖1所示。

圖1 分組作業(yè)面示意圖

3 模型建立

本文研究岸橋與AGV 的聯(lián)合調(diào)度問題。首先，以貝位為單位將岸線劃分若干個區(qū)域。其次，在船舶靠泊位置，時間和集裝箱量已知的情況下，對碼頭岸橋進行動態(tài)調(diào)度。最后，依據(jù)岸線長度將AGV 作業(yè)面分組劃分為多個小作業(yè)面，再根據(jù)岸橋調(diào)度計劃表對AGV 進行作業(yè)面調(diào)度。

3.1 模型假設

（1）岸橋在同一軌道上行進作業(yè)，不可交叉，即不可跨越作業(yè)；

（2）相鄰的兩個岸橋之間存在安全距離，安全距離為G；

（3）岸橋移動速度恒定，作業(yè)效率相同；

（4）岸橋初始作業(yè)時刻已知，初始位置已知；

（5）一個岸橋同一時刻只能處理一個任務，一個任務只能由一個岸橋完成；

（6）AGV只能在規(guī)定的范圍內(nèi)進行作業(yè)，即不可跨作業(yè)面作業(yè)；

（7）任務出現(xiàn)時，分派給作業(yè)面內(nèi)空閑AGV；

（8）AGV移動速度恒定；

（9）一個AGV同一時刻只能處理一個集裝箱，一個集裝箱只能由一個AGV完成；

（10）只考慮卸船作業(yè)；

（11）不考慮突發(fā)情況。

3.2 符號說明

（1）參數(shù)定義

B：表示貝位集合，編號為{1…i,j},i,j∈B；

Q：表示岸橋集合，編號為{1…k},k∈Q；

U：表示AGV集合，編號為 {1…u},u∈U；

S：表示堆存區(qū)塊集合，編號為{1…s},s∈S；

C：表示集裝箱集合，編號從左到右依次為{1…m,n},m,n∈C；

Pi：岸橋處理任務貝位i的任務時間；

Rm：表示集裝箱m對應的堆存區(qū)塊，Rm∈S；

li：表示貝位i有岸橋任務需要處理；

：表示岸橋k的初始位置；

：表示岸橋k完成分配任務后的終止貝位；

：表示AGVu從初始位置到集裝箱m位置的距離；

：表示AGVu完成分配任務后從堆存區(qū)塊s到終止位置的距離；

：表示集裝箱m從自身所在貝位到堆存區(qū)塊Rm的距離；

λ：表示岸橋單位移動時間，即移動一個貝位所需時間；

：表示岸橋k從初始貝位移動到第一個任務貝位i的時間；

：表示岸橋k從最后任務貝位移動到終止位置的時間，理論上應該為0；

G：表示相鄰岸橋k與k+1 之間的安全距離，通常為1個貝位；

v：表示AGV單位移動時間；

：表示AGVu從初始位置到做第一個集裝箱m的時間；

：表示AGVu做完最后一個集裝箱m移動到終止位置的時間；

Xk：表示岸橋k的完工時間；

Zu：表示AGVu的完工時間；

Di：表示貝位i的完工時間；

θm：表示集裝箱m的完工時間；

W：表示岸橋處理任務的最大完工時間；

L：表示AGV的總等待時間；

H：表示AGV處理集裝箱的最大完工時間；

M：表示一個足夠大的數(shù)；

α1：表示任務最大完工時間的權(quán)重；

α2：表示AGV總等待時間的權(quán)重；

α3：表示AGV最大完工時間的權(quán)重。

（2）決策變量定義

xik：若岸橋k分配給貝位i則為1，否則為0；

：若岸橋k執(zhí)行完任務貝位i后執(zhí)行任務貝位j則為1，否則為0；

：若岸橋k在t時刻時分配給貝位i則為1，否則為0；

yij：若任務貝位i的完成時間早于任務貝位j的開始時間則為1，否則為0；

zmu：若AGVu分配給集裝箱m則為1，否則為0；

：若AGVu運輸完集裝箱m后運輸集裝箱n則為1，否則為0；

qmu：若AGVu和集裝箱m在同一作業(yè)面則為1，否則為0。

3.3 目標函數(shù)與約束條件

集裝箱碼頭作業(yè)需要各設備之間相互協(xié)調(diào)，在初始的聯(lián)合調(diào)度方案中需要進行多設備的調(diào)整，本文對各個目標設置相應的權(quán)重進行計算。

約束條件為：

式（1）表示最小化岸橋最大完工時間和AGV 完工時間以及AGV等待時間；式（2）表示岸橋任務的最大完工時間為W；式（3）表示AGV 的總等待時間L；式（4）表示AGV 的最大完工時間為H；式（5）表示單個任務只能由一臺岸橋完成；式（6）和式（7）分別說明每個岸橋的初始任務和最終任務有且只有一個；式（8）表示單個集裝箱只能由一個AGV運輸；式（9）和式（10）分別說明每個AGV的初始任務集裝箱和最終任務集裝箱有且只有一個；式（11）表示AGV 只能運輸它作業(yè)面內(nèi)的集裝箱；式（12）表示兩設備的作業(yè)順序，集裝箱岸橋完工時間小于AGV 開始作業(yè)時間；式（13）定義了任務的優(yōu)先級，即任務i要先于任務j處理；式（14）表示任務j的完成時間，不小于緊前任務i的完成時間、任務j的處理時間以及岸橋在i,j貝位的移動時間之和；式（15）說明由于沖突的存在，部分任務無法同時處理；式（16）定義了岸橋作業(yè)時不能產(chǎn)生干涉；式（17）表示岸橋的初始任務完成時間，不小于岸橋從初始位置移動到任務貝位的時間與初始任務的處理時間之和；式（18）表示岸橋的最終完成時間等于最終任務的完成時間加上從該位置移動到最終位置的時間；式（19）表示集裝箱n的完成時間，不小于集裝箱m的完成時間與從集裝箱m出發(fā)處理n的時間之和；式（20）表示AGV 的初始任務完成時間大于AGV從初始位置移動到集裝箱位置的時間與運輸時間的總和；式（21）表示AGV 的最終完成時間等于最終集裝箱的完成時間加上從該位置移動到最終位置的時間；式（22）與式（23）定義了xik和的關(guān)系；式（24）與式（25）定義了zmu和的關(guān)系；式（26）確定岸橋在依次作業(yè)過程中，相鄰岸橋間保持G個貝位的安全距離；式（27）說明了三個權(quán)重之間的關(guān)系；式（28）和式（29）確保了決策變量為0-1變量以及模型中的變量均大于0。

4 算法設計

上述模型中的聯(lián)合調(diào)度問題是一個NP-hard 問題，問題規(guī)模愈大，計算的復雜程度就成倍地增長。遺傳算法由于其通用性，魯棒性強，能進行廣泛的并行處理等特點，在求解此類NP-hard 問題上有較為明顯的優(yōu)勢。由于本文將對岸橋和AGV 進行聯(lián)合調(diào)度，因此將設計改進的遺傳算法對問題進行求解。

4.1 染色體編碼

本文岸橋部分采用矩陣式編碼，染色體第一行代表每個貝位的任務各自分配給的岸橋；第二行開始則代表每個貝位集裝箱的作業(yè)順序，染色體長度與貝位最大集裝箱量相等。這其中第一行每一列代表一個貝位直至貝位分配完畢，0代表該貝位無任務，不需要分配岸橋或者超出貝位上限不予處理；第二行開始，每一行的非零數(shù)總和分別和各個貝位的集裝箱量相等。圖2為有3個岸橋，10 個貝位的染色體編碼，其中第一行為AGV 調(diào)度，第二行為第一個貝位任務順序，后續(xù)貝位與該貝位規(guī)則相同。

圖2 岸橋染色體示例

本文AGV 部分染色體采用分段式編碼。如圖3 所示，黃色部分為第一段，表示按照貝位將全岸線分成多個作業(yè)面，數(shù)字為作業(yè)面右邊界，即1到4貝位為第一個作業(yè)面，5 到10 貝位為第二個作業(yè)面；藍色部分為第二段，表示每一個AGV 所屬的作業(yè)面，小數(shù)點前為AGV編號，小數(shù)點后為該AGV所屬作業(yè)面；橙色部分為第三段，表示每個集裝箱分配的AGV，每個貝位以0隔開，小數(shù)點前為集裝箱編號，小數(shù)點后為AGV編號。

圖3 AGV染色體示例

4.2 適應度函數(shù)設置

4.2.1 岸橋干擾約束

通過GA中的目標函數(shù)確定每個岸橋的初始位置，每個集裝箱的岸橋作業(yè)起始和結(jié)束時間以及每個岸橋工作的位置，并存儲在矩陣數(shù)據(jù)結(jié)構(gòu)中。每次岸橋需要開始處理與岸橋當前貝位不同的貝位的新任務時，它將檢查相鄰貝位（在新任務貝位的左側(cè)和右側(cè)）的任務是否有其他岸橋占用。如果因為不同岸橋執(zhí)行任務干擾其移動，則檢查這些任務的完成時間。如果這些任務沒有完成，那么目前的岸橋需要等待；否則，它可以繼續(xù)移動到下一個任務的貝位并開始卸載或裝載作業(yè)。

根據(jù)岸橋的當前貝位，下一步將要執(zhí)行的任務的貝位和其他岸橋的當前所在貝位，按照干擾情況的不同可將岸橋狀態(tài)分為以下四種：

（1）岸橋前往其任務貝位并處理該任務。

（2）岸橋需要等待，避免與另一臺岸橋發(fā)生碰撞，然后運行到其下一個任務位置。

（3）岸橋保持閑置狀態(tài)，并將停留在當前位置。

（4）岸橋保持閑置狀態(tài)，但需要移動以避免與相鄰的岸橋發(fā)生碰撞。

4.2.2 AGV干擾約束

同樣的，通過GA中的目標函數(shù)確定每個AGV的初始位置。根據(jù)岸橋任務計劃表，計算每個集裝箱的AGV作業(yè)起始、結(jié)束時間以及每次任務AGV移動距離，并存儲在矩陣數(shù)據(jù)結(jié)構(gòu)中。AGV 的約束相對簡單，可將其狀態(tài)分為以下四種情況：

（1）任務貝位在AGV 作業(yè)面內(nèi)，AGV 前往其任務貝位并處理該任務。

（2）AGV 在處理任務中途與另外的AGV 路線交叉，堵塞等待。

（3）AGV處于空閑狀態(tài)等待下一個任務。

（4）任務貝位在AGV作業(yè)面外，放棄任務保持空閑狀態(tài)等待下一任務。

4.3 遺傳操作

4.3.1 岸橋部分遺傳操作

岸橋本文采用輪盤賭的選擇策略，在盡可能保留高適應度值染色體的前提下，有效地提高種群的多樣性。

因為染色體設計的特殊性，本文選取染色體基因值分類的交叉策略，具體操作如下：

對第一行岸橋分配策略在排除無任務貝位的情況下進行多點交叉；對第二行開始的集裝箱作業(yè)順序隨機選擇行，在排除多余的0點后，進行雙點交叉，最后對其進行修復。如圖4 所示，父代1 和父代2 第一行和第二行黃色的基因值為交叉操作選定的位置；列出的子代1藍色的基因值為進行交叉并修復后的值。

圖4 岸橋交叉示例

變異則是統(tǒng)一使用逆轉(zhuǎn)變異的方式，即隨機選擇第i行的兩個基因值，將這兩個值互換位置。

如圖5所示，變異前第一行和第二行黃色的基因值為選中的需變異的值，變異后藍色的基因值為進行變異并修復后的基因值。

圖5 岸橋變異示例

4.3.2 AGV部分遺傳操作

AGV部分的選擇操作，本文采用精英保留策略，保留高適應度值的染色體，提高算法的收斂性。對不同的保留值進行測試后，發(fā)現(xiàn)在保留50%時，染色體能夠在保持一定的種群多樣性的基礎(chǔ)上，有效地提高算法整體的收斂性。因此本文后續(xù)實驗采用50%的精英保留策略。

交叉操作，由于第二段AGV 作業(yè)面歸屬與第一段作業(yè)面設置關(guān)聯(lián)性較大，因此本文只對第一段與第三段進行交叉操作。

第一段作業(yè)面分組規(guī)劃，本文進行單點交叉；第三段AGV作業(yè)分配，本文采用多點交叉的方式，最后對其進行修復。圖6 為AGV 染色體交叉示例，各顏色意義與圖4類似。

圖6 AGV交叉示例

變異相較于交叉操作，作用范圍更小，只針對AGV作業(yè)分配進行交叉操作。變異的方式與岸橋相似，采用逆轉(zhuǎn)變異法，隨機選擇貝位，將其染色體值的小數(shù)點部分進行交換，具體操作如圖7所示，各顏色意義與圖5類似。

4.4 結(jié)束規(guī)則

圖7 AGV變異示例

該遺傳算法以適應度值為衡量指標，對種群進行優(yōu)化，當達到最大迭代次數(shù)后停止算法，輸出最優(yōu)解。

5 算例與結(jié)果分析

本文通過設計不同情況與規(guī)模的算例，驗證本文所提出的模型與算法的可行性。算例中岸橋卸一個集裝箱所需時間2 min，AGV 裝卸車時間2 min，空載與滿載速度恒定為24 km/h，岸線總長度2 000 m，每個貝位之間距離50 m，岸線到堆場距離600 m，相鄰的岸橋之間存在1 個貝位的安全距離，AGV 與岸橋的初始位置給定，貝位數(shù)量40，卸船箱生成貝位隨機，設置權(quán)重α1=0.4,α2=0.3，α3=0.3。

遺傳算法的參數(shù)，岸橋部分：交叉概率0.8，變異概率0.1，種群大小50，最大迭代次數(shù)300；AGV部分：交叉概率0.9，變異概率0.15，種群大小100，最大迭代次數(shù)200。實驗在 Intel?CoreTMi7 的處理器，內(nèi)存 8 GB 的PC上進行，使用Matlab2018a編寫實現(xiàn)。

通過選取12個不同規(guī)模的算例對本文的模型及算法進行驗證，由于遺傳算法的特性，每一個算例由算法運行10 次得到平均值，并與傳統(tǒng)調(diào)度方法求得的解進行對比，計算出優(yōu)化效果，計算公式為：

在給定集裝箱數(shù)量(N1)、岸橋數(shù)量(N2)、AGV數(shù)量(N3)后，表1的計算結(jié)果表明本文提出的岸橋與AGV聯(lián)合調(diào)度方案，隨著算例規(guī)模的增大，優(yōu)化效果先增后降。在算例1 中，本文提出的岸橋AGV 聯(lián)合調(diào)度模式效果劣于傳統(tǒng)調(diào)度。出現(xiàn)這種計算結(jié)果是由于在小規(guī)模算例中，集裝箱任務數(shù)量較少，岸橋動態(tài)調(diào)度優(yōu)勢不明顯并且AGV 空閑時間長，而分組作業(yè)面調(diào)度下空閑AGV無法跨作業(yè)面作業(yè)，導致AGV等待時間大于傳統(tǒng)調(diào)度，總體效果會不如傳統(tǒng)調(diào)度。隨著算例規(guī)模的增大，岸橋動態(tài)調(diào)度和AGV 分組作業(yè)面調(diào)度的優(yōu)勢開始逐漸展現(xiàn)，到算例8 時，新式調(diào)度的優(yōu)化效果達到峰值16%。當算例規(guī)模繼續(xù)擴大，即集裝箱數(shù)量大于200，岸橋數(shù)量大于4，AGV數(shù)量大于18時，即便將AGV作業(yè)面進行了分組劃分，但同一作業(yè)面中任務數(shù)量與AGV 數(shù)量也較多，AGV堵塞等待時間會有較為顯著的增加，因此聯(lián)合調(diào)度方案的優(yōu)化效果會有略微降低，但即便如此本文提出的協(xié)調(diào)調(diào)度相較于傳統(tǒng)調(diào)度優(yōu)化效果仍在13%以上。

表1 不同規(guī)模算例計算結(jié)果

對單設備進行對比。本文提出的岸橋動態(tài)調(diào)度方案，岸橋能夠中途更換作業(yè)船只，作業(yè)均衡性相較于傳統(tǒng)調(diào)度有顯著提升，因此從表1的計算結(jié)果可以明顯發(fā)現(xiàn)在不同規(guī)模算例中岸橋完工時間均低于傳統(tǒng)調(diào)度方案，并且隨著算例規(guī)模的不斷增大，岸橋動態(tài)調(diào)度的優(yōu)勢也在不斷地增大；另一方面，在算例規(guī)模較小的時候，由于之前提到的原因，本文提出的AGV 分組作業(yè)面作業(yè)并沒有優(yōu)勢，但隨著算例的規(guī)模增大，AGV的等待時間相較于傳統(tǒng)調(diào)度方案有明顯優(yōu)勢，并且長距離運輸導致AGV 作業(yè)時間傳統(tǒng)調(diào)度也會高于分組作業(yè)面，從而總完工時間高于分組作業(yè)面調(diào)度方案。

將AGV 等待時間細分為AGV 空閑等待時間與AGV堵塞等待時間進行進一步的數(shù)值分析。并將全岸線作業(yè)面調(diào)度與分組作業(yè)面調(diào)度進行計算對比，計算公式為：

作業(yè)面調(diào)度遵循空閑就調(diào)用的原則，能夠極大程度地減少AGV空閑等待時間，但在實際碼頭操作中，這一原則會使得AGV出現(xiàn)超遠距離運輸。分組作業(yè)面調(diào)度模式就是企圖在盡可能減少遠距離運輸現(xiàn)象的基礎(chǔ)上，提高AGV 的調(diào)用頻次。如表2 顯示，在所有算例規(guī)模中，對比AGV空閑等待時間，全岸線作業(yè)面調(diào)度要小于分組作業(yè)面調(diào)度。這是由于全岸線調(diào)度是單個作業(yè)面的調(diào)度而分組作業(yè)面則是多個作業(yè)面，AGV 無法跨作業(yè)面遠距離運輸，空閑等待時間相對較長。在AGV 阻塞等待時間方面，由于AGV 在碼頭行進有著固定的路線，長距離運輸意味著更加復雜的線路與更加多的交叉點，而多個AGV 之間更多的交叉點意味著更多的阻塞等待。因此，從表2 可以看出，隨著算例規(guī)模的不斷擴大，全岸線作業(yè)面調(diào)度與分組作業(yè)面調(diào)度的AGV 阻塞等待時間之間的差距也在不斷增大。

然而，在集裝箱數(shù)量大于75，岸橋數(shù)量大于3，AGV數(shù)量大于10 的情況下，分組作業(yè)面調(diào)度模式的總等待時間才開始低于全岸線作業(yè)面調(diào)度模式。在算例規(guī)模較小時，分組作業(yè)面調(diào)度難以體現(xiàn)它的優(yōu)勢。由于集裝箱數(shù)量與AGV 數(shù)量過少，在作業(yè)過程中很少會發(fā)生阻塞等待的情況，而分組作業(yè)面限制了AGV的作業(yè)范圍，增加了空閑等待時間。在多方面作用下，會產(chǎn)生類似算例1、2無優(yōu)化效果的情況。

在算例規(guī)模較大時，集裝箱任務量大，分組作業(yè)面調(diào)度中AGV 即使無法跨作業(yè)面作業(yè)，單個作業(yè)面內(nèi)大量的任務也減少了AGV 空閑等待時間。同時，單個作業(yè)面內(nèi)大量的任務也會增加AGV的阻塞等待時間。因此，從表2 的后三個大規(guī)模算例可以看出，兩種調(diào)度模式下AGV 空閑等待時間產(chǎn)生趨近的現(xiàn)象；分組作業(yè)面調(diào)度的AGV阻塞等待時間雖然仍遠小于全岸線作業(yè)面調(diào)度，但是也開始驟增。由于這些原因，分組作業(yè)面對比全岸線作業(yè)面會在算例8 時優(yōu)化效果達到峰值51.9%，而在集裝箱數(shù)量大于200，岸橋數(shù)量大于4，AGV數(shù)量大于18 的情況下，優(yōu)化效果下降，但由于在AGV阻塞等待時間上的巨大優(yōu)勢，分組作業(yè)面調(diào)度模式的優(yōu)化效果仍然在47%以上。

表2 AGV空閑時間與阻塞時間對比

6 結(jié)論

本文對自動化碼頭的岸橋與AGV聯(lián)合調(diào)度問題進行了研究。考慮岸橋作業(yè)中安全距離、不可交叉等約束，AGV 作業(yè)中路徑交叉堵塞等約束，以減少岸橋等待、AGV等待以及最小化岸橋和AGV最大完工時間為目標，建立混合整數(shù)規(guī)劃模型，同時設計嵌套式的遺傳算法進行求解。結(jié)果表明，相較于傳統(tǒng)調(diào)度模式，在非小規(guī)模算例中，本文提出的新的聯(lián)合調(diào)度方案在岸橋完工時間、AGV 完工時間和等待時間上都有較為明顯的減少。在岸橋調(diào)度方面，動態(tài)調(diào)度方案由于作業(yè)均衡性的提升，相較傳統(tǒng)方案有著明顯的優(yōu)勢。在AGV 阻塞等待方面，很好地展示了分組作業(yè)面的優(yōu)勢，減少長距離運輸帶來的堵塞。該模型能更加有效地優(yōu)化岸橋與AGV 調(diào)度問題。本文通過算例驗證了研究方案，可以為岸橋AGV 的調(diào)度提供科學合理的方案和決策依據(jù)。同時，本文也存在一些不足，隨著問題規(guī)模的增大，優(yōu)化的效果先增后降。在大規(guī)模算例中由于單個作業(yè)面中AGV與任務數(shù)量的增加，阻塞等待時間驟增，優(yōu)化效果會受到負面影響，在算例規(guī)模不斷增大的情況下，本文提出的聯(lián)合調(diào)度方案能否保持優(yōu)化效果未進行驗證。考慮到大規(guī)模算例中AGV 阻塞時間驟增的現(xiàn)象，在后續(xù)的研究中，將在基于優(yōu)化岸橋AGV 聯(lián)合調(diào)度的基礎(chǔ)上，設計分組作業(yè)面中單個作業(yè)面AGV 數(shù)量配置優(yōu)化的研究。