考慮路徑?jīng)_突的AGV配置與調(diào)度優(yōu)化

范厚明， 岳麗君， 李 蕩， 馬夢知

(大連海事大學 交通運輸工程學院,遼寧 大連 116026)

0 引言

隨著船舶大型化的發(fā)展，近年來自動化集裝箱碼頭進入新一輪的快速發(fā)展時期。班輪等集裝箱船對靠港裝卸時間要求嚴格，即在規(guī)定的時間內(nèi)碼頭需要完成對靠港船舶的裝卸作業(yè)，所以保證每艘船在規(guī)定的時間內(nèi)完成集裝箱的裝卸作業(yè)是碼頭重要的目標。集裝箱船的裝卸過程如圖1所示，包括三個階段：卸船階段、裝卸同步階段、裝船階段。在卸船階段，所有岸橋進行卸船作業(yè)，AGV在岸橋下接收進口集裝箱并送箱到達指定進口箱區(qū)，交付該集裝箱后空載行駛到作業(yè)下一集裝箱的岸橋下。在裝卸同步階段，部分岸橋裝船、部分岸橋卸船，AGV在卸船岸橋下接收進口箱并送到指定箱區(qū)后，可以前往出口箱區(qū)提取裝船集裝箱并載箱到達指定的裝船岸橋下，也可以前往卸船岸橋下作業(yè)下一卸船集裝箱。在裝船階段，所有岸橋進行裝船作業(yè)，AGV在出口箱區(qū)取箱送至裝船岸橋。

AGV作為水平運輸工具，往來于船邊和堆場之間，服務于岸橋和場橋。若AGV載箱/空駛到達岸橋或場橋下的時刻，晚于岸橋或場橋相應的計劃放/提箱時刻，則會導致作業(yè)時間發(fā)生延誤，進而可能無法在要求的時間內(nèi)完成裝卸作業(yè)。

為減少場橋延誤，大多數(shù)自動化集裝箱碼頭在箱區(qū)內(nèi)設立緩沖支架。如圖1所示，AGV在卸船岸橋下接收進口集裝箱后，沿卸船路線前往堆場送箱，當送箱AGV到達進口箱區(qū)的時間早于場橋計劃作業(yè)時間，若緩沖支架全被占用，即緩沖空間已滿，則AGV在場橋下等待；若緩沖空間未滿，AGV將進口箱放置到緩沖支架上后繼續(xù)作業(yè)下一集裝箱。對于出口集裝箱，若取箱AGV到達出口箱區(qū)的時間晚于場橋計劃作業(yè)時間，場橋?qū)⒓b箱放置在緩沖支架上，AGV到達后在緩沖支架上取箱后，沿裝船路線前往岸橋下送箱。緩沖支架的設置減少了場橋延誤。為減少岸橋延誤，大多數(shù)碼頭選擇增加AGV的配置數(shù)量。AGV數(shù)量增加一方面增加了AGV的等待時間，導致AGV的利用率降低；另一方面增大了發(fā)生路徑?jīng)_突概率，導致AGV到達岸橋下的時間不確定，不一定能有效保證完工時間。

因此，考慮路徑?jīng)_突條件下，優(yōu)化AGV的配置及調(diào)度以滿足船舶的裝卸時間要求是迫切需要解決的問題。

圖1 裝卸過程中AGV運行流程圖

針對船舶裝卸作業(yè)優(yōu)化問題，韓少龍等[1]利用集裝箱港口仿真軟件Flexsim-CT建立了包括泊位、岸橋、集卡、場橋和堆場資源在內(nèi)的集裝箱港口裝卸作業(yè)仿真模型，分析了作業(yè)面、作業(yè)線和同步裝卸三種調(diào)度模式對船舶裝卸作業(yè)時間和裝卸設備作業(yè)效率的影響。Zeng等[2]以最小化船舶完工時間為目標，分別構(gòu)建了全場調(diào)度模式和同船調(diào)度模式下的調(diào)度優(yōu)化模型，并設計了兩階段禁忌搜索算法和Q學習算法來求解這兩種模型，最后證明同船調(diào)度模式可以減少水平運輸工具的空駛時間，提高水平運輸工具的利用率。Kim等[3]研究了在確定和隨機環(huán)境下裝卸設備的集成調(diào)度問題，以最小化船舶完工時間為目標，將AGV同步分配給岸橋。陶莎等[4]提出了協(xié)調(diào)岸橋、集卡和場橋作業(yè)時間的三級裝卸搬運分時協(xié)調(diào)策略，采用統(tǒng)計學中有序樣本聚類的最優(yōu)分割法將整體作業(yè)時間分為幾個階段，分別求最優(yōu)解。Homayouni等[5]和Luo等[6]分別研究了岸橋和場橋與AGV的協(xié)同調(diào)度優(yōu)化，均以最小化最大完工時間為目標，構(gòu)建了混合整數(shù)規(guī)劃模型，應用模擬退火算法對模型求解。Lim等[7]通過為岸橋配置不同數(shù)量的內(nèi)集卡，來控制岸橋的作業(yè)效率。證明了幾種不確定環(huán)境下，該調(diào)度方式可以自動恢復岸橋作業(yè)效率、保障船舶裝卸時間。常祎妹等[8]討論了設備作業(yè)效率不確定時，集裝箱碼頭各設備的集成調(diào)度問題，建立了車船裝卸作業(yè)集成調(diào)度模型并設計了改進的多層遺傳算法求解模型。Azevedo等[9]聯(lián)合考慮船舶配積載計劃和岸橋調(diào)度問題，研究制定了一系列船舶箱位分配和岸橋調(diào)度規(guī)則，模擬集裝箱裝卸順序和岸橋調(diào)度規(guī)則的組合，采用遺傳算法求解船舶的總裝卸時間，比較所有組合的效率。Yang等[10]研究了自動化集裝箱碼頭中岸橋、AGV和場橋的集成調(diào)度問題，以最小化完工時間為目標構(gòu)建了雙層模型，設計了基于堵塞預防規(guī)則的雙層遺傳算法求解模型。

針對自動化集裝箱碼頭AGV配置與調(diào)度問題，Zhang等[11]提出了三種AGV調(diào)度模型并改進了貪婪算法求解；韓曉龍等[12]利用仿真軟件分析了不同的AGV調(diào)度策略及AGV配置數(shù)量對集裝箱港口裝卸效率的影響；Nishi等[13]同時考慮了AGV的調(diào)度和路徑規(guī)劃問題，構(gòu)建雙層混合整數(shù)規(guī)劃模型并利用拉格朗日松弛算法進行求解；Kim等[14]研究了多目標的自動化集裝箱碼頭AGV調(diào)度，采用改進的進化算法對問題仿真模擬，得出AGV的配置和調(diào)度方案。Choe等[15]提出了OnPL(online preference learning)算法，通過更新偏好函數(shù)實時動態(tài)調(diào)整AGV的調(diào)度方案。Wang等[16]研究了同時裝卸船模式下AGV調(diào)度和堆存位置分配問題，采用樹結(jié)構(gòu)表示解空間以增強鄰域解搜索能力。魯渤等[17]建立了ALV調(diào)度與堆場位置分配集成優(yōu)化模型，設計了基于遺傳的啟發(fā)式算法對模型求解，得到了最小化最大完工時間的調(diào)度方案。Roy等[18]基于交通流的閉合排隊網(wǎng)絡模型研究了AGV配置的數(shù)量和AGV擁堵對碼頭吞吐量的影響。張素云等[19]研究了AGV可能發(fā)生的路徑?jīng)_突問題，采用位向量交集運算法檢測路徑?jīng)_突發(fā)生概率，通過仿真實驗比較了速度控制策略在AGV路徑?jīng)_突問題中的可行性及有效性。

綜上，通過梳理現(xiàn)有文獻發(fā)現(xiàn)：(1)在船舶裝卸作業(yè)優(yōu)化方面，已有文獻多為集裝箱裝卸設備間的調(diào)度協(xié)同優(yōu)化，以使得裝卸完工時間最小，沒有考慮班輪對裝卸時間的要求，實際完工時間過短或過長都會對碼頭造成損失；(2)在自動化集裝箱碼頭AGV的配置與調(diào)度優(yōu)化的研究中，主要優(yōu)化AGV的配置數(shù)量和調(diào)度模式，忽略了AGV在運輸過程中，因路徑?jīng)_突造成的實際交箱時間的不確定性對船舶裝卸完工時間的影響；(3)現(xiàn)有文獻很少考慮AGV利用率問題，在實際運營環(huán)境中，碼頭的AGV資源有限且有較高的運行成本和閑置成本，在保證船舶裝卸時間要求的基礎上提高AGV的利用率，即調(diào)度過程中最小化AGV的空載和等待時間，可以增加碼頭運營方的效益。

本文在已有研究的基礎上，針對集裝箱船裝卸時間要求，考慮AGV運輸過程中因路徑?jīng)_突導致交箱時間的不確定性，以最小化最大完工時間和最小化AGV的空載和等待時間為目標構(gòu)建AGV調(diào)度優(yōu)化模型，并設計改進NSGA-Ⅱ算法對模型進行求解，最后通過算例分析驗證了本文所提調(diào)度優(yōu)化方案的有效性。

1 問題描述

船舶裝卸過程中，AGV在岸橋與場橋之間運輸集裝箱。岸橋作業(yè)的理想狀態(tài)為岸橋不等待AGV，即AGV在岸橋下隨時待命，以使完工時間最小化；AGV運輸?shù)睦硐霠顟B(tài)為到達岸橋或場橋后可以立刻取/交集裝箱，AGV在岸橋和場橋下的等待時間及空駛時間最短。因此，必須綜合考慮岸橋和AGV的目標進行協(xié)同優(yōu)化，單一優(yōu)化某個目標使其達到理想狀態(tài)并不滿足碼頭實際作業(yè)的要求。要保證岸橋在要求完工時間內(nèi)完工且AGV空載和等待時間最小，則需要解決以下三個問題：(1)AGV配置數(shù)量。配置數(shù)量過少時，AGV不能及時到達導致岸橋等待，岸橋不能按計劃作業(yè)又會產(chǎn)生后續(xù)的AGV等待，總裝卸完工時間較長，AGV利用率低；數(shù)量較多時產(chǎn)生多輛AGV在岸橋/場橋下等待的現(xiàn)象，AGV的空載和等待時間較長；(2)AGV調(diào)度方案。調(diào)度方案追求的是在給定AGV數(shù)量下，確保岸橋完工時間最小化和AGV的空載及等待時間最小化；(3)運輸過程中的多輛AGV間的路徑?jīng)_突。如圖2所示，多輛AGV同時到達一個路徑節(jié)點產(chǎn)生的交叉沖突，多輛AGV同向而行產(chǎn)生的等待沖突，會影響AGV的實際到達時間。

圖2 AGV之間路徑?jīng)_突示意圖

在實際作業(yè)過程中，路徑?jīng)_突會增加AGV的運輸時間，若AGV的實際到達時間早于岸橋開始作業(yè)時間，則AGV在沖突點的額外作業(yè)時間不會影響岸橋作業(yè)，否則導致岸橋等待，如圖3所示，岸橋?qū)嶋H開始作業(yè)集裝箱2的時刻晚于計劃開始作業(yè)時刻，最終導致集裝箱實際裝卸完工時間晚于裝卸時間要求。定義該部分為延誤時間DT，即岸橋的延誤時間=實際完工時間-裝卸作業(yè)要求時間。

圖3 岸橋作業(yè)示意圖

在船舶裝卸作業(yè)要求時間內(nèi)預留一段緩沖時間，有利于最終的實際完工時間早于要求完工時間。AGV因路徑?jīng)_突導致的岸橋延誤時間很難有一個明確的、固定的值。為了衡量其對AGV調(diào)度方案的影響，以設置合理的緩沖時間，采用多AGV系統(tǒng)下沖突點等待的調(diào)度策略，利用愛爾朗分布模擬實際作業(yè)過程中AGV經(jīng)過沖突點的額外作業(yè)時間，則在一次送/取箱過程中，AGV經(jīng)過m個沖突點時額外作業(yè)時間為：

(1)

式(1)中m為AGV經(jīng)過的沖突點的總個數(shù)；θ為AGV在沖突點的平均等待時間。總的AGV額外作業(yè)時間服從均值為mθ的愛爾朗分布。假設n個集裝箱在運輸過程中，發(fā)生沖突的概率為β，預設緩沖時間為：

t0=β×n×m×θ

(2)

因為卸船階段、裝卸同步階段和裝船階段的裝卸設備作業(yè)特點不同，且各階段具有機動時間的傳遞性，為保證船舶裝卸時間要求的同時提高AGV利用率，解決存在路徑?jīng)_突時AGV配置與調(diào)度優(yōu)化問題，本文采用分階段調(diào)度策略，將裝卸時間要求分三個階段，即卸船階段時間要求、裝卸同步階段時間要求和裝船階段時間要求。在各個階段內(nèi)分別考慮AGV的配置與調(diào)度方案對船舶裝卸時間的影響，建立以最小化最大完工時間和最小化AGV空載等待時間為雙目標的調(diào)度優(yōu)化模型。配置的AGV數(shù)量不同，模型的非支配最優(yōu)解不同，將不同AGV數(shù)量下模型的非支配解放入調(diào)度方案集合中。根據(jù)本階段的實際完工時間，從最優(yōu)解集中選擇下一階段滿足裝卸時間要求且AGV利用率最高的配置與調(diào)度方案。

2 模型建立

2.1 前提假設

研究基于以下假設：

(1)待作業(yè)集裝箱位置信息及裝卸順序已知，AGV運輸起點為出口箱所屬堆場和作業(yè)進口箱的卸船岸橋，終點為存儲進口箱的堆場和作業(yè)出口箱的裝船岸橋；

(2)所有待作業(yè)集裝箱箱型一致最終所有的進口箱運送到指定堆場，所有出口箱運送到船上指定箱位；

(3)堆場按進口箱區(qū)和出口箱區(qū)分類，每個箱區(qū)有且只有一臺場橋作業(yè)；

(4)只有在前一集裝箱作業(yè)完成后才能作業(yè)后一集裝箱，即岸橋、場橋和AGV均不能同時作業(yè)兩個集裝箱。

2.2 符號說明

(1)輸入變量

n=1,2,…,N,N為待裝卸集裝箱總量，其中N+表示待裝船集裝箱總量，N-表示待卸船集裝箱總量；k=1,2,…,K,K為裝卸船岸橋配置數(shù)量；c=12,…,C,C為場橋數(shù)量；v=1,2,…,V，V為AGV配置數(shù)量；b=1,2,…,B，B為船舶總貝位數(shù)；P為緩沖容量，即每個箱區(qū)的緩沖支架上可以同時放置集裝箱的數(shù)量；τ1和τ2分別為岸橋、場橋完成一個集裝箱裝卸作業(yè)的平均時間；σ為岸橋移動一個貝位的時間；eik為第i個集裝箱在岸橋k下的計劃開始作業(yè)時間，即岸橋k計劃從AGV上提起待裝船集裝箱i的時刻，或岸橋k計劃放下待卸船集裝箱i到AGV的時刻；TF為每個階段要求的裝卸完工時間。

(2)中間變量

Nk為岸橋k作業(yè)集裝箱的總數(shù)量；Eik為AGV無路徑?jīng)_突時岸橋k實際開始作業(yè)集裝箱i的時間；Emax為最大實際完工時間，是AGV無路徑?jīng)_突時岸橋提起最后一個待裝船集裝箱或放下最后一個待卸船集裝箱的時刻；wikv為運載集裝箱i的第v輛AGV在岸橋k下的等待時間；tiv為第v輛AGV運載集裝箱時的行駛時間；tijv為第v輛AGV交付集裝箱i后前往下一個集裝箱j所在位置的空駛時間；[ETic,LTic]為場橋c下AGV可放/提集裝箱的時間窗；wicv為運載集裝箱i的第v輛AGV在場橋c下的等待時間；τij為岸橋k提取/放下集裝箱i后作業(yè)集裝箱j所用的時間；tab為岸橋k由貝位a移動到貝位b所需要的時間；ubk為岸橋k開始作業(yè)貝位b的時刻；div為第v輛AGV開始作業(yè)集裝箱i的時刻，tiv為第v輛AGV將集裝箱i運輸?shù)侥康牡厮玫臅r間，即運輸待裝船集裝箱到作業(yè)岸橋下或運輸待卸船集裝箱到堆存箱區(qū)。Fvc為第v輛AGV已經(jīng)送箱到箱區(qū)c或已從箱區(qū)c取箱的數(shù)量；Sic為場橋c開始作業(yè)集裝箱i的時刻；Hc為場橋c已裝卸集裝箱的數(shù)量。

(3)決策變量

征稿內(nèi)容： 自然災害(特別是地質(zhì)災害)與人為災害防治，生態(tài)環(huán)境、資源環(huán)境和地質(zhì)環(huán)境保護，水文地質(zhì)與工程地質(zhì)，巖土工程與工程勘察，與本學科有關的邊緣和交叉學科等方面的優(yōu)秀論文，最新科技成果，新理論、新方法、新技術研討，及工程技術經(jīng)驗總結(jié)，新成就、新動向方面的綜述、述評，新書刊、新設備評介等。

2.3 優(yōu)化模型

本文采用分階段調(diào)度策略，將整個裝卸作業(yè)分為三個階段，在每個階段內(nèi)建立AGV的調(diào)度優(yōu)化模型，如下：

調(diào)度優(yōu)化目標：

(3)

(4)

約束條件：

(5)

(6)

(7)

(8)

ejk=max(Eik+τij,ejk),i,j∈N

(9)

Eik=max(div+tiv,eik),?i∈N+

(10)

(11)

ubk≥uak+tab

(12)

Emax≤TF-t0

(13)

(14)

Sic+τ2≤ETic,?i∈N+

(15)

ETic≤Sic, ?i∈N-

(16)

wikv=max{eik-div-tiv,0},?i∈N+

(17)

wikv=max{eik-div,0},?i∈N-

(18)

wicv=max{ETic-div,0},?i∈N+

(19)

wicv=max{ETic-div-tiv,0},?i∈N-

(20)

div+tiv+wikv+tijv+wjcv≤djv,?i∈N+,j∈N+

(21)

div+tiv+wikv+tijv+wjkv≤djv,?i∈N+,j∈N-

(22)

div+tiv+wicv+tijv+wjcv≤djv,?i∈N-,j∈N+

(23)

div+tiv+wicv+tijv+wjkv≤djv,?i∈N-,j∈N-

(24)

(25)

xiv,yik,zic,xijv∈{0,1},?i,j∈N

(26)

div≥0, ?i∈N

(27)

式(3)和式(4)為目標函數(shù)，其中f1表示最小化最大完工時間，f2表示最小化所有AGV的空載時間、場橋下等待時間和岸橋下等待時間之和；式(5)和式(6)表示一個集裝箱由且僅由一輛AGV運輸；式(7)和式(8)分別表示一個集裝箱由一臺岸橋或場橋作業(yè)；式(9)表示更新后的岸橋計劃作業(yè)時間；式(10)和式(11)分別表示作業(yè)裝船集裝箱或卸船集裝箱的岸橋的實際作業(yè)時間；式(12)表示岸橋由當前貝位移動到下一貝位后開始作業(yè)時間；式(13)表示每個階段的船舶裝卸要求約束；式(14)表示每個箱區(qū)的緩存容量約束；式(15)和式(16)分別表示作業(yè)待裝船集裝箱或待卸船集裝箱的岸橋開始作業(yè)的時間約束；式(17)和式(18)分別表示AGV交付裝船集裝箱或提取卸船集裝箱時在岸橋下的等待時間；式(19)和(20)分別表示AGV提取裝船集裝箱或交付卸船集裝箱在場橋下的等待時間；式(21)和式(22)分別表示AGV在送完裝船集裝箱后，作業(yè)下一個裝船集裝箱或卸船集裝箱的時間約束；式(23)和式(24)分別表示AGV在送完卸船集裝箱后，作業(yè)下一個裝船集裝箱箱或卸船集裝箱的時間約束；式(25)表示本階段AGV的利用率；式(26)和式(27)分別表示變量的類型和取值范圍。

3 模型求解

3.1 算法設計

本文研究的AGV配置與調(diào)度優(yōu)化問題屬于NP-hard問題，很難獲得精確地最優(yōu)解，又因為所建立的混合整數(shù)規(guī)劃模型需要優(yōu)化兩個目標，NSGA-Ⅱ算法[20]具有全局優(yōu)化性能，在多目標優(yōu)化中有較為廣泛的應用，因此，本文結(jié)合具體問題對NSGAⅠ算法進行了改進，詳細求解步驟如下：

(1)個體編碼和解碼

本文研究內(nèi)容屬于實際調(diào)度優(yōu)化問題，采用實數(shù)矩陣編碼的方式更易于理解。設計一個三行n列的染色體，染色體長度代表待裝卸的集裝箱總量，染色體第一至三行的基因值分別為集裝箱作業(yè)序號、岸橋序號、場橋序號。以10個待裝卸的集裝箱，3輛AGV為例。如圖4所示，首先對待裝卸的集裝箱按其岸橋計劃作業(yè)時間的先后順序進行編號，岸橋計劃作業(yè)時間較早的集裝箱作業(yè)序號小；岸橋序號表示，裝/卸相應集裝箱的岸橋的編號，由進口集裝箱所在船舶貝位和出口集裝箱的目標貝位決定；場橋序號表示作業(yè)相應集裝箱的場橋的編號，由集裝箱在堆場中的位置決定；集裝箱箱號與作業(yè)序號、岸橋序號、場橋序號一一對應。

(2)初始種群生成

隨機生成初始種群，根據(jù)可利用的AGV數(shù)量生成隨機切斷點，兩斷點間的染色體分配相同的AGV序號，AGV序號表示運載相應集裝箱的AGV的編號，如圖4所示。

圖4 染色體

(3)非支配排序與精英保留策略

對候選池中個體，依據(jù)公式(3)和(4)計算兩個目標函數(shù)值，兩目標值不能同時小于其他個體的所有個體組成非支配前沿，非支配前沿中個體視為精英個體，直接進入下一代。若非支配前沿個體數(shù)量小于種群規(guī)模，則計算下一前沿面中個體的擁擠度。個體的擁擠度設定為與相鄰個體相應目標值的差，均一化處理后得到每個個體的擁擠度，保留擁擠度值較大的個體進入下一代。

(4)交叉

采用部分匹配交叉(PMX，Partial Mapped Crossover)的交叉方式對兩個父代個體進行交叉操作生成同等規(guī)模的兩類子代。具體操作過程如圖5所示。

圖5 染色體交叉

從所有個體的第一行(即集裝箱的作業(yè)序列)中，隨機選擇兩個用來交叉的父代個體，然后再隨機選擇兩個交叉點位置，置換兩交叉點之間的染色體片段，剩余部分按順序排列，形成兩個子代染色體。子代染色體中，每輛AGV作業(yè)量與父代相同，作業(yè)的集裝箱序號發(fā)生改變。父代個體和子代個體均進入候選池中。

(5)變異

采用均勻變異算子(Uniform Mutation)的方式，變異作業(yè)序列對應的AGV序號。在[0,V]內(nèi)，產(chǎn)生均勻分布的隨機數(shù)，以一定的概率來替換父代染色體對應的原有AGV序號，最終產(chǎn)生新的AGV分配方式，如圖6所示。

圖6 染色體變異

(6)終止條件設置

若算法的迭代次數(shù)達到預先設置的最大次數(shù)，則輸出結(jié)果，否則返回到步驟(3)。

3.2 算法性能評價指標

采用NSGA Ⅰ算法對模型求解，得到一組非劣解集形成的近似Pareto前沿，通過計算非劣解集的收斂性和分布性可判斷解的優(yōu)劣[21]，結(jié)合現(xiàn)有研究和集裝箱碼頭調(diào)度問題的特性，采用收斂度和分布性評價本文算法性能：

(1)收斂度

收斂度可以反映非劣解集與真實 Pareto前沿之間的逼近程度。隨著待裝卸集裝箱數(shù)量的增加，問題復雜度增大，真實的Pareto前沿無法獲取。因此本文用函數(shù)的最小值代替模型最優(yōu)解。考慮理想狀態(tài)下，若AGV在岸橋和場橋下不等待，由公式(4)～(8)和(21)～(22)可解得f1的最小值o1；若岸橋不延誤，由公式(3)、(5)～(12)可解得f2的最小值o2。計算第G代收斂度值時，首先計算非劣解中各點到(o1,o2)的歐幾里得距離：

(28)

然后將第G代解集中各點歐幾里得距離均值除以初始解中對應的距離均值，可得收斂度γ，γ越小表明算法性能越好。

(2)分布性

分布性可以體現(xiàn)非劣解集中個體在前沿面分布的均勻程度。通過近似Pareto前沿中每個個體到與其最近的個體的距離求分布性Δ：

(29)

(3)運行時間

算法的復雜度直接影響算法的運行時間，程序計算時間AT越小，算法性能越好。

4 算例分析

4.1 算例比較

為了評價在優(yōu)化集裝箱碼頭AGV調(diào)度問題中所提出的算法的性能，參考文獻[22]中目標函數(shù)和數(shù)據(jù)，最小化AGV空載時間與岸橋延誤時間和場橋運行時間的總和，其中三個目標函數(shù)的比例分別為0.1、0.8和0.1。運行程序20次，對比所得目標函數(shù)值。表1中列舉了文獻[22]和本文算法的計算結(jié)果，Optimal、Best、Average分別表示最優(yōu)解、啟發(fā)式算法所求解的最優(yōu)值、平均值，AT表示算法運行時間，Dev表示最優(yōu)值與最優(yōu)解間的偏差。

表1 小規(guī)模算例結(jié)果對比

由表1知，當問題規(guī)模擴大到16個集裝箱時，CPLEX已經(jīng)無法在有限時間內(nèi)求得精確解，而本文提出的算法，卻可以在很短的時間內(nèi)，求得近似最優(yōu)解，并且本文提出的算法所求得的函數(shù)值與CPLEX求得的精確解之間的平均誤差僅為3.08%，故本文算法可用于求解集裝箱碼頭AGV調(diào)度問題。

4.2 實例分析

本文以青島某自動化碼頭車道布局圖及水平交通規(guī)則[23]為研究背景，待裝卸船舶到達泊位后，設有2臺岸橋同時作業(yè)。將整個集裝箱碼頭分為8個作業(yè)點，其中1～2為岸橋作業(yè)點，3～5為進口箱區(qū)場橋的作業(yè)點，6～8為出口箱區(qū)場橋的作業(yè)點。AGV空載速度為5m/s，重載速度為3.5m/s，岸橋和場橋的平均單箱作業(yè)時間分別為：120s和180s。岸橋沿船舶方向移動一個貝位所需時間為300s，場橋下緩沖支架最多可同時放置4個集裝箱。隨機生成船上每個貝位(共有12個貝位)中待裝、卸集裝箱數(shù)量，如圖7所示。待卸船集裝箱在堆場的目標箱區(qū)和待裝船集裝箱現(xiàn)堆存箱區(qū)已知，如表2所示。

圖7 待裝卸集裝箱堆存位置

表2 進出口箱區(qū)場橋作業(yè)集裝箱數(shù)量

所有集裝箱要求24h內(nèi)完成裝卸作業(yè)，分配裝船、裝卸同步和卸船三個階段中的岸橋作業(yè)量和裝卸時間要求如表3所示。采用愛爾朗分布模擬實際作業(yè)中因路徑?jīng)_突產(chǎn)生的額外作業(yè)時間，AGV在沖突點的平均等待時間θ=2.5，AGV一次運輸過程中經(jīng)過沖突點的個數(shù)m=2，AGV發(fā)生沖突的概率β=0.2。

表3 各階段作業(yè)集裝箱量和裝卸時間要求

(1)計算結(jié)果

采用matlab 2016b編寫算法，設置種群大小為100，最大迭代次數(shù)為1000。對配置不同數(shù)量AGV時上述實例中三個階段的調(diào)度模型求解10次，將10次的運算結(jié)果放入最優(yōu)解集中，從中選出種群規(guī)模大小、分布均勻的非支配解。在每階段非支配解集中選擇滿足裝卸時間要求且AGV利用率最高的調(diào)度方案，AGV空載和等待時間、岸橋完工時間、AGV利用率、算法收斂度和分布性以及運算時間的結(jié)果見表4。

表4 配置不同數(shù)量AGV時的最優(yōu)調(diào)度結(jié)果和算法性能

卸船階段計劃兩臺岸橋共卸載393個集裝箱，計劃完工時間為27720s，預設緩沖時間為393s；由表3可知，配置6輛AGV時利用率最高。采用愛爾朗分布模擬實際運輸過程，所得路徑?jīng)_突造成岸橋等待作業(yè)時間為248s，完工時間為27565s，可比計劃完工時間提前155s。裝卸同步階段計劃岸橋1卸載240個集裝箱，岸橋2裝載247個集裝箱，預設緩沖時間為487s；配置4輛AGV，模擬實際運輸過程得路徑?jīng)_突造成岸橋等待作業(yè)時間為412s，完工時間為32947s，可比計劃完工時間提前547s。裝船階段計劃裝載363個集裝箱，預設緩沖時間為363s；配置6輛AGV，模擬實際運輸過程得路徑?jīng)_突造成岸橋等待作業(yè)時間為207s，完工時間為26418s，可比計劃完工時間提前138s。在考慮路徑?jīng)_突時，整個裝卸過程實際完工時間為85560s，比船舶裝卸要求完工時間提前了840s。該配置下相應的AGV的調(diào)度方案如圖8所示：

圖8 AGV配置與調(diào)度方案

(2)與現(xiàn)有調(diào)度方案對比分析

為了進一步驗證本文所提的雙目標調(diào)度優(yōu)化方案的有效性，將本文與單一目標最優(yōu)時的調(diào)度優(yōu)化方案對比，即分別以最小化AGV空載和等待時間為目標(方案一)和最小化最大完工時間為目標(方案二[6])，對上述算例進行數(shù)值實驗，計算不考慮路徑?jīng)_突時最優(yōu)配置下各個階段AGV的空載和等待時間、實際完工時間、延誤時間、AGV的利用率。實驗結(jié)果如表5所示。

對比三種調(diào)度優(yōu)化方案發(fā)現(xiàn)，采用方案一時，三個階段延誤時間之和為15302s，最高AGV利用率可達到53.8%，表明以最小化AGV空載和等待時間為調(diào)度目標，雖然有較高的AGV利用率，但不能在要求的時間內(nèi)完成裝卸船作業(yè)，不符合實際碼頭作業(yè)要求；采用方案二時船舶可提前4102s完成集裝箱裝卸作業(yè)，最高AGV利用率僅為16.4%；采用本文方案時船舶可提前156s完成裝卸作業(yè)，且最高AGV利用率為37.2%，AGV空載和等待時間相較于方案二減少了162505s，滿足實際作業(yè)要求的同時提高了AGV的利用率。對比結(jié)果說明本文研究在保證船舶裝卸時間和提高AGV的利用率方面具有優(yōu)勢。

表5 不考慮路徑?jīng)_突時不同優(yōu)化目標調(diào)度結(jié)果

(3)魯棒性分析

忽略AGV運輸過程中的路徑?jīng)_突，將會影響調(diào)度方案的魯棒性，可能導致船舶裝卸作業(yè)的延遲。為了驗證存在AGV路徑?jīng)_突時本文模型和調(diào)度策略的有效性，保持其他參數(shù)不變，改變沖突發(fā)生概率β和沖突點個數(shù)m的值，最終的實際完工時間和AGV的利用率如圖9和圖10所示。

圖9 不同β和值對實際完工時間的影響

圖10 不同β和值對AGV利用率的影響

從圖9中看出，在發(fā)生沖突概率不同、沖突點個數(shù)不同的情況下，本文所提的分階段調(diào)度策略均可以保證在船舶裝卸時間的要求內(nèi)完成裝卸作業(yè)。從圖10中看出β和m發(fā)生變化時，AGV的利用率會降低，但整體利用率仍高于方案二。本文所提模型和調(diào)度策略更符合自動化集裝箱碼頭的實際要求。

5 結(jié)論

本文在對自動化集裝箱碼頭AGV配置與調(diào)度問題的研究中，考慮了靠港船舶裝卸時間要求的約束和AGV運輸中路徑?jīng)_突對岸橋作業(yè)時間的影響，建立了AGV調(diào)度優(yōu)化的多目標模型，并改進了NSGA-Ⅱ算法對其求解，算例分析結(jié)果表明：本文所提出的AGV配置與調(diào)度方案可以確保船舶在要求完工時間內(nèi)結(jié)束裝卸作業(yè)，同時提高了AGV利用率。但本文還存在一些不足，沒有考慮集裝箱在船舶和堆場位置分配，而實際操作中，集裝箱的堆存位置會影響AGV的送取箱時間，進而影響船舶的裝卸作業(yè)時間。因此，綜合考慮集裝箱堆存位置約束和船舶裝卸時間要求，優(yōu)化AGV的配置與調(diào)度方案將作為未來的研究方向。