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

范厚明， 岳麗君， 李 蕩， 馬夢(mèng)知

(大連海事大學(xué) 交通運(yùn)輸工程學(xué)院,遼寧 大連 116026)

0 引言

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

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

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

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

圖1 裝卸過程中AGV運(yùn)行流程圖

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

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

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

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

1 問題描述

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

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

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

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

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

(1)

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

t0=β×n×m×θ

(2)

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

2 模型建立

2.1 前提假設(shè)

研究基于以下假設(shè)：

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

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

(3)堆場(chǎng)按進(jìn)口箱區(qū)和出口箱區(qū)分類，每個(gè)箱區(qū)有且只有一臺(tái)場(chǎng)橋作業(yè)；

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

2.2 符號(hào)說明

(1)輸入變量

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

(2)中間變量

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

(3)決策變量

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

2.3 優(yōu)化模型

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

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

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

3 模型求解

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

本文研究的AGV配置與調(diào)度優(yōu)化問題屬于NP-hard問題，很難獲得精確地最優(yōu)解，又因?yàn)樗⒌幕旌险麛?shù)規(guī)劃模型需要優(yōu)化兩個(gè)目標(biāo)，NSGA-Ⅱ算法[20]具有全局優(yōu)化性能，在多目標(biāo)優(yōu)化中有較為廣泛的應(yīng)用，因此，本文結(jié)合具體問題對(duì)NSGAⅠ算法進(jìn)行了改進(jìn)，詳細(xì)求解步驟如下：

(1)個(gè)體編碼和解碼

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

(2)初始種群生成

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

圖4 染色體

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

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

(4)交叉

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

圖5 染色體交叉

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

(5)變異

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

圖6 染色體變異

(6)終止條件設(shè)置

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

3.2 算法性能評(píng)價(jià)指標(biāo)

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

(1)收斂度

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

(28)

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

(2)分布性

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

(29)

(3)運(yùn)行時(shí)間

算法的復(fù)雜度直接影響算法的運(yùn)行時(shí)間，程序計(jì)算時(shí)間AT越小，算法性能越好。

4 算例分析

4.1 算例比較

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

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

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

4.2 實(shí)例分析

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

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

表2 進(jìn)出口箱區(qū)場(chǎng)橋作業(yè)集裝箱數(shù)量

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

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

(1)計(jì)算結(jié)果

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

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

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

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

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

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

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

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

(3)魯棒性分析

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

圖9 不同β和值對(duì)實(shí)際完工時(shí)間的影響

圖10 不同β和值對(duì)AGV利用率的影響

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

5 結(jié)論

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