梁承姬，申 哲，張 悅

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

1 引言

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

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

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

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

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

2 問(wèn)題描述

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

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

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

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

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

3 模型建立

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

3.1 模型假設(shè)

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

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

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

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

（5）一個(gè)岸橋同一時(shí)刻只能處理一個(gè)任務(wù)，一個(gè)任務(wù)只能由一個(gè)岸橋完成；

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

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

（8）AGV移動(dòng)速度恒定；

（9）一個(gè)AGV同一時(shí)刻只能處理一個(gè)集裝箱，一個(gè)集裝箱只能由一個(gè)AGV完成；

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

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

3.2 符號(hào)說(shuō)明

（1）參數(shù)定義

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

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

U：表示AGV集合，編號(hào)為 {1…u},u∈U；

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

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

Pi：岸橋處理任務(wù)貝位i的任務(wù)時(shí)間；

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

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

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

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

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

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

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

λ：表示岸橋單位移動(dòng)時(shí)間，即移動(dòng)一個(gè)貝位所需時(shí)間；

：表示岸橋k從初始貝位移動(dòng)到第一個(gè)任務(wù)貝位i的時(shí)間；

：表示岸橋k從最后任務(wù)貝位移動(dòng)到終止位置的時(shí)間，理論上應(yīng)該為0；

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

v：表示AGV單位移動(dòng)時(shí)間；

：表示AGVu從初始位置到做第一個(gè)集裝箱m的時(shí)間；

：表示AGVu做完最后一個(gè)集裝箱m移動(dòng)到終止位置的時(shí)間；

Xk：表示岸橋k的完工時(shí)間；

Zu：表示AGVu的完工時(shí)間；

Di：表示貝位i的完工時(shí)間；

θm：表示集裝箱m的完工時(shí)間；

W：表示岸橋處理任務(wù)的最大完工時(shí)間；

L：表示AGV的總等待時(shí)間；

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

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

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

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

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

（2）決策變量定義

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

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

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

yij：若任務(wù)貝位i的完成時(shí)間早于任務(wù)貝位j的開(kāi)始時(shí)間則為1，否則為0；

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

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

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

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

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

約束條件為：

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

4 算法設(shè)計(jì)

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

4.1 染色體編碼

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

圖2 岸橋染色體示例

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

圖3 AGV染色體示例

4.2 適應(yīng)度函數(shù)設(shè)置

4.2.1 岸橋干擾約束

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

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

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

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

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

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

4.2.2 AGV干擾約束

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

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

（2）AGV 在處理任務(wù)中途與另外的AGV 路線(xiàn)交叉，堵塞等待。

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

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

4.3 遺傳操作

4.3.1 岸橋部分遺傳操作

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

因?yàn)槿旧w設(shè)計(jì)的特殊性，本文選取染色體基因值分類(lèi)的交叉策略，具體操作如下：

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

圖4 岸橋交叉示例

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

如圖5所示，變異前第一行和第二行黃色的基因值為選中的需變異的值，變異后藍(lán)色的基因值為進(jìn)行變異并修復(fù)后的基因值。

圖5 岸橋變異示例

4.3.2 AGV部分遺傳操作

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

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

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

圖6 AGV交叉示例

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

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

圖7 AGV變異示例

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

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

本文通過(guò)設(shè)計(jì)不同情況與規(guī)模的算例，驗(yàn)證本文所提出的模型與算法的可行性。算例中岸橋卸一個(gè)集裝箱所需時(shí)間2 min，AGV 裝卸車(chē)時(shí)間2 min，空載與滿(mǎn)載速度恒定為24 km/h，岸線(xiàn)總長(zhǎng)度2 000 m，每個(gè)貝位之間距離50 m，岸線(xiàn)到堆場(chǎng)距離600 m，相鄰的岸橋之間存在1 個(gè)貝位的安全距離，AGV 與岸橋的初始位置給定，貝位數(shù)量40，卸船箱生成貝位隨機(jī)，設(shè)置權(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。實(shí)驗(yàn)在 Intel?CoreTMi7 的處理器，內(nèi)存 8 GB 的PC上進(jìn)行，使用Matlab2018a編寫(xiě)實(shí)現(xiàn)。

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

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

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

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

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

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

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

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

表2 AGV空閑時(shí)間與阻塞時(shí)間對(duì)比

6 結(jié)論

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