盧毅勤

上海電力學(xué)院 經(jīng)濟(jì)與管理學(xué)院，上海 200090

不確定環(huán)境下碼頭堆場(chǎng)設(shè)備集成調(diào)度優(yōu)化

盧毅勤

上海電力學(xué)院 經(jīng)濟(jì)與管理學(xué)院，上海 200090

集裝箱碼頭堆場(chǎng)設(shè)備調(diào)度優(yōu)化中，對(duì)確定條件下的內(nèi)集卡和場(chǎng)橋的聯(lián)合調(diào)度研究較多，且沒(méi)有考慮外集卡的隨機(jī)到達(dá)情況?？紤]內(nèi)集卡和場(chǎng)橋作業(yè)過(guò)程中的不確定性因素，包括：內(nèi)集卡行駛速度，場(chǎng)橋行走速度和作業(yè)時(shí)間，并考慮外集卡隨機(jī)到達(dá)堆場(chǎng)對(duì)于內(nèi)集卡調(diào)度作業(yè)的影響，構(gòu)建了不確定因素條件下的堆場(chǎng)設(shè)備集成調(diào)度優(yōu)化模型，其優(yōu)化目標(biāo)是在考慮外集卡隨機(jī)到達(dá)的情況下，最優(yōu)化堆場(chǎng)設(shè)備的作業(yè)時(shí)間。設(shè)計(jì)了求解模型的粒子群算法，并比較了一般確定性模型和考慮不確定因素優(yōu)化模型的結(jié)果。算例結(jié)果表明，所建立的模型和算法能有效真實(shí)地反映不確定因素對(duì)集裝箱碼頭堆場(chǎng)設(shè)備作業(yè)的影響。

不確定因素；集成調(diào)度；堆場(chǎng)設(shè)備；外集卡

1 引言

集裝箱堆場(chǎng)作為銜接海運(yùn)和內(nèi)陸系統(tǒng)的緩沖區(qū)域，對(duì)于減少船舶裝卸時(shí)間從而提高整個(gè)港口的作業(yè)效率和競(jìng)爭(zhēng)力都有著非常重要的意義。堆場(chǎng)設(shè)備調(diào)度主要包括場(chǎng)橋調(diào)度和內(nèi)集卡調(diào)度問(wèn)題，主要是對(duì)既定作業(yè)區(qū)內(nèi)，在任務(wù)與堆場(chǎng)設(shè)備數(shù)量一定的情況下，對(duì)場(chǎng)橋和集卡進(jìn)行作業(yè)任務(wù)的分配，使作業(yè)時(shí)間最短。楊朋[1]建立了同時(shí)考慮貨位分配和揀選路徑的集成優(yōu)化模型，縮短了集卡裝卸任務(wù)最小化單位指令周期的行程時(shí)間。趙寧[2]研究集卡的利用率，建立集裝箱港口發(fā)箱任務(wù)的集卡指派模型。Kim[3]等考慮場(chǎng)橋操作的不同限制條件，建立混合整數(shù)規(guī)劃模型，采用基于分支界定法和貪婪隨機(jī)適應(yīng)搜索過(guò)程的算法求解。Ng等[4-5]研究場(chǎng)橋優(yōu)化調(diào)度問(wèn)題，以等待時(shí)間最小化為目標(biāo)建立模型并用分支界定法求解。韓曉龍[6]通過(guò)建立兩階段規(guī)劃模型求解了場(chǎng)橋調(diào)度問(wèn)題。

在場(chǎng)橋與集卡集成調(diào)度研究中，Cao等[7]以出口箱集卡和場(chǎng)橋同步化作業(yè)的完工時(shí)間最小化為目標(biāo)，建立混合整數(shù)模型。樂(lè)美龍[8]構(gòu)建了場(chǎng)橋與集卡的協(xié)調(diào)調(diào)度模型，目標(biāo)是使所有作業(yè)總完工時(shí)間最短。但以上研究都是在確定情況下進(jìn)行的，目前國(guó)內(nèi)外對(duì)于不確定情況下堆場(chǎng)優(yōu)化調(diào)度研究比較有限。劉艷等[9]針對(duì)進(jìn)箱時(shí)間的不確定性，應(yīng)用模糊機(jī)會(huì)約束規(guī)劃方法平衡各箱區(qū)作業(yè)量，并以箱區(qū)作業(yè)量為約束條件，最小化集卡的行駛距離和同組進(jìn)口箱所占箱區(qū)的數(shù)量，建立箱位分配模糊優(yōu)化模型。周鵬飛[10]考慮了集裝箱進(jìn)出場(chǎng)時(shí)間的隨機(jī)不確定性,建立了出口箱位隨機(jī)規(guī)劃模型。但以上不確定性研究?jī)H僅針對(duì)堆場(chǎng)箱位分配問(wèn)題，不確定情況下堆場(chǎng)內(nèi)的設(shè)備調(diào)度優(yōu)化問(wèn)題仍然沒(méi)有得到解決。此外，以上研究均沒(méi)有考慮外集卡隨機(jī)到達(dá)對(duì)內(nèi)集卡調(diào)度作業(yè)的影響。目前我國(guó)碼頭廣泛采用的作業(yè)模式是內(nèi)、外集卡作業(yè)互不干擾，即外集卡要等待場(chǎng)橋?qū)?nèi)集卡全部服務(wù)完成以后，才能被空閑的場(chǎng)橋服務(wù)。這樣，雖然保證了堆場(chǎng)內(nèi)作業(yè)以最快速度完成，但是忽略了外集卡在堆場(chǎng)外的等待時(shí)間。對(duì)于碼頭的服務(wù)對(duì)象（如船舶公司）的成本會(huì)產(chǎn)生影響，可能導(dǎo)致碼頭業(yè)務(wù)的流失。

因此，本文綜合考慮外集卡等待時(shí)間和堆場(chǎng)內(nèi)集卡作業(yè)完成效率，統(tǒng)籌安排堆場(chǎng)設(shè)備作業(yè)順序，從而讓堆場(chǎng)設(shè)備在盡可能短的時(shí)間內(nèi)既完成對(duì)內(nèi)集卡的裝卸服務(wù)，又能提升碼頭對(duì)外集卡的服務(wù)能力，提高碼頭服務(wù)質(zhì)量，吸引更多業(yè)務(wù)。本文引入內(nèi)集卡運(yùn)行速度、場(chǎng)橋作業(yè)時(shí)間及行走速度這三大重要不確定性因素，同時(shí)考慮外集卡隨機(jī)到達(dá)堆場(chǎng)執(zhí)行裝卸任務(wù)對(duì)于堆場(chǎng)中內(nèi)集卡調(diào)度作業(yè)的影響。采用粒子群算法[11]（Particle Swarm Optimization，PSO）求解建立優(yōu)化模型。粒子群算法的優(yōu)勢(shì)在于簡(jiǎn)單容易實(shí)現(xiàn)，目前已廣泛應(yīng)用于函數(shù)優(yōu)化?？紤]不確定因素的堆場(chǎng)集成調(diào)度優(yōu)化更符合實(shí)際作業(yè)，對(duì)提高碼頭服務(wù)水平有著非常重要的意義，并為碼頭管理者解決實(shí)際作業(yè)調(diào)度提供重要的價(jià)值。

2 問(wèn)題描述及假設(shè)條件

2.1 問(wèn)題描述

港口內(nèi)具體布局如圖1所示：閘口是連接港內(nèi)外的通道，閘口與岸邊之間為港內(nèi)作業(yè)，其中不同的港口設(shè)置堆場(chǎng)、泊位的數(shù)量以及方位有所不同[12]。卸船時(shí)橋吊首先將集裝箱從船上卸至岸邊集卡，再由集卡將箱子運(yùn)送至指定堆場(chǎng)箱區(qū)內(nèi)，此時(shí)場(chǎng)橋再將箱子從集卡放到指定箱位中。裝船作業(yè)則是反向流程。問(wèn)題優(yōu)化的目標(biāo)是在考慮外集卡隨機(jī)到達(dá)情況下，給出一個(gè)內(nèi)集卡和場(chǎng)橋裝卸作業(yè)時(shí)間相互協(xié)調(diào)的任務(wù)分配方案，在考慮不確定因素并保證所有作業(yè)都已完成的情況下，使得場(chǎng)橋裝卸作業(yè)時(shí)間最短，減少場(chǎng)橋和內(nèi)集卡相互等待的時(shí)間，整體提升作業(yè)效率。場(chǎng)橋作業(yè)任務(wù)會(huì)因?yàn)橥饧ǖ碾S機(jī)到達(dá)而增加，從而需要對(duì)場(chǎng)橋和內(nèi)集卡進(jìn)行重新調(diào)配。

圖1 港口布局圖

本文引入堆場(chǎng)作業(yè)的三大不確定因素：內(nèi)集卡行駛速度、場(chǎng)橋作業(yè)時(shí)間及行走速度建立模型，按照上海港碼頭實(shí)際作業(yè)統(tǒng)計(jì)規(guī)律，用正態(tài)分布來(lái)處理這些隨機(jī)變量。同時(shí)外集卡到達(dá)時(shí)間服從Poisson分布。

2.2 假設(shè)條件

假設(shè)所調(diào)用的集卡全部為單掛集卡，集卡運(yùn)輸?shù)募b箱全部為40英尺標(biāo)準(zhǔn)箱，相同設(shè)備作業(yè)能力沒(méi)有差別，將所有裝卸作業(yè)任務(wù)編號(hào)并按照一定規(guī)則排序。有關(guān)模型的其他假設(shè)如下：

假設(shè)1裝卸任務(wù)固定,共有M個(gè)場(chǎng)橋參與堆場(chǎng)裝卸作業(yè)。所有裝船箱任務(wù)共n1個(gè),卸船箱任務(wù)n2個(gè)。

假設(shè)2所有任務(wù)對(duì)應(yīng)的集裝箱堆場(chǎng)位置和岸橋位置已知，在內(nèi)集卡任務(wù)分配完成后，選取最優(yōu)路徑完成裝卸任務(wù)，不考慮交通問(wèn)題，即每輛集卡完成各項(xiàng)裝卸任務(wù)的行駛距離是已知的。內(nèi)集卡作業(yè)的不確定性主要體現(xiàn)在行駛速度以及在場(chǎng)橋等待時(shí)間的不確定性上。

假設(shè)3所有任務(wù)分配給N輛內(nèi)集卡,集卡l的重車(chē)和空車(chē)行駛速度為隨機(jī)變量ηl和ξl；所有場(chǎng)橋的作業(yè)時(shí)間是隨機(jī)變量，記為γ；場(chǎng)橋行走速度為隨機(jī)變量，記為υ。

假設(shè)4每個(gè)場(chǎng)橋的工作時(shí)間從它開(kāi)始第一項(xiàng)任務(wù)算起，并在該場(chǎng)橋完成分配到的最后一項(xiàng)任務(wù)時(shí)結(jié)束，總時(shí)間為第一個(gè)場(chǎng)橋開(kāi)始任務(wù)到最后一個(gè)場(chǎng)橋完成任務(wù)之間的時(shí)間。

假設(shè)5外集卡在隨機(jī)的時(shí)間到達(dá)指定堆場(chǎng)區(qū)域，該堆場(chǎng)區(qū)域的場(chǎng)橋在完成當(dāng)期任務(wù)后對(duì)外集卡進(jìn)行服務(wù)。

3 不確定環(huán)境下堆場(chǎng)設(shè)備集成調(diào)度優(yōu)化建模

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

將堆場(chǎng)內(nèi)的作業(yè)抽象為一個(gè)不確定優(yōu)化模型，需要將問(wèn)題抽象為一個(gè)網(wǎng)絡(luò)圖。假設(shè)目前需要分配給內(nèi)集卡和場(chǎng)橋的任務(wù)指令有n個(gè)，每個(gè)指令對(duì)應(yīng)堆場(chǎng)和岸橋之間的裝卸任務(wù)，并將裝船任務(wù)組成的集合記為CH，卸船任務(wù)組成的集合記為UL，在網(wǎng)絡(luò)圖中對(duì)應(yīng)于n個(gè)節(jié)點(diǎn)V={1,2,…,n}。引入虛擬任務(wù)點(diǎn)的概念[13]，一個(gè)虛擬任務(wù)點(diǎn)表示一項(xiàng)指令，任意兩個(gè)虛擬節(jié)點(diǎn)i,j之間的距離為從虛擬任務(wù)點(diǎn)i的卸載點(diǎn)到 j的裝載點(diǎn)之間的距離，記為dij?？梢?jiàn)，集卡在任意兩個(gè)虛擬任務(wù)點(diǎn)之間為空車(chē)行駛，且一般來(lái)說(shuō)，dij≠dji。

為了將內(nèi)集卡裝載任務(wù)構(gòu)造成一個(gè)回路，假設(shè)有一個(gè)虛擬任務(wù)點(diǎn)O，它到任意點(diǎn)之間的距離為0，即所有內(nèi)集卡從虛擬任務(wù)點(diǎn)O開(kāi)始任務(wù)。假設(shè)任務(wù)分配給N輛內(nèi)集卡，用1≤l≤N 記為表示車(chē)輛序列；假設(shè)任務(wù)分配給M個(gè)場(chǎng)橋，同樣表示場(chǎng)橋序列。

決策變量如下：

Xl

ij表示內(nèi)集卡l是否從第i項(xiàng)任務(wù)的卸載點(diǎn)直接至第 j項(xiàng)任務(wù)的裝載點(diǎn)。即當(dāng)Xlij=1時(shí)，內(nèi)集卡完成任務(wù)i之后去完成任務(wù) j。記內(nèi)集卡l完成的任務(wù)集合為Jl，顯然有

Ym表示場(chǎng)橋m是否在完成第i個(gè)裝卸任務(wù)后完成

ij第 j個(gè)裝卸任務(wù)。即當(dāng)Yimj=1時(shí)，場(chǎng)橋m完成任務(wù)i后去完成任務(wù) j。記場(chǎng)橋m完成的任務(wù)集合為Qm，顯然有

模型中的其他參數(shù)如下：

ηl和ξl為內(nèi)集卡l的重車(chē)行駛速度和空車(chē)行駛速度，這兩組是不確定變量。

γ為場(chǎng)橋完成一吊普通箱裝卸作業(yè)的時(shí)間，是不確定變量。

υ為場(chǎng)橋在堆場(chǎng)指定區(qū)域內(nèi)的移動(dòng)速度，是不確定變量。

Sm,Fm為場(chǎng)橋m開(kāi)始和結(jié)束工作的時(shí)刻。

ak為完成全部作業(yè)的時(shí)間內(nèi)第k輛外集卡(k=1,2,…,K)到達(dá)堆場(chǎng)指定區(qū)域的時(shí)刻。

δ為場(chǎng)橋?qū)ν饧ㄟM(jìn)行服務(wù)的平均時(shí)間。

3.2 數(shù)學(xué)模型

3.2.1 復(fù)雜模型

為了體現(xiàn)場(chǎng)橋服務(wù)外集卡對(duì)整體碼頭作業(yè)效率的影響，考慮增加一個(gè)關(guān)于外集卡的“獎(jiǎng)勵(lì)項(xiàng)”。假設(shè)作業(yè)期間場(chǎng)橋服務(wù)外集卡幫助外集卡節(jié)省的等待的時(shí)間為，獎(jiǎng)勵(lì)項(xiàng)函數(shù)定義為，其中 f(?)為單調(diào)遞增函數(shù)，滿(mǎn)足 f(0)=0。構(gòu)建數(shù)學(xué)模型M1如下：

式（1）為目標(biāo)函數(shù)，表示場(chǎng)橋完成全部任務(wù)的總時(shí)間，目標(biāo)是使其最小。Xlij,Ymij為決策變量；約束條件（2）保證所有任務(wù)都已完成，即內(nèi)集卡對(duì)于每個(gè)虛擬任務(wù)點(diǎn)至少執(zhí)行了一次；約束條件（3）與（4）保證每項(xiàng)任務(wù)只由一輛內(nèi)集卡一次完成，并沒(méi)有重復(fù)執(zhí)行相同的任務(wù)；式（5）至式（7）保證場(chǎng)橋執(zhí)行了所有任務(wù)有且僅有一次；式（8）表示自變量的取值范圍為0-1離散變量；式（9）與式（10）表示場(chǎng)橋開(kāi)始和結(jié)束工作的時(shí)刻和場(chǎng)橋每項(xiàng)任務(wù)開(kāi)始和結(jié)束工作的時(shí)刻之間的關(guān)系；式（11）表示場(chǎng)橋每項(xiàng)任務(wù)開(kāi)始和結(jié)束時(shí)刻之間的關(guān)系；式（12）表示場(chǎng)橋完成一項(xiàng)任務(wù)后，下一項(xiàng)任務(wù)開(kāi)始的時(shí)刻，這里考慮了場(chǎng)橋是否被調(diào)配為外集卡服務(wù)；式（13）表示場(chǎng)橋?yàn)橥饧ǚ?wù)后，外集卡減少的等待時(shí)間；式（14）表示內(nèi)集卡完成一項(xiàng)裝卸任務(wù)所需時(shí)間，包括內(nèi)集卡運(yùn)行時(shí)間和岸橋平均等待時(shí)間（Til）+堆場(chǎng)場(chǎng)橋等待時(shí)間場(chǎng)橋移動(dòng)到下一裝卸任務(wù)位置的時(shí)間場(chǎng)橋作業(yè)時(shí)間（τ），由此得到內(nèi)集卡完成一項(xiàng)任務(wù)起始時(shí)刻之間的關(guān)系；式（15）中表示內(nèi)集卡在兩個(gè)虛擬任務(wù)點(diǎn)之間空車(chē)行駛的時(shí)間，由此可得集卡在前一項(xiàng)任務(wù)完成時(shí)刻和后一項(xiàng)任務(wù)開(kāi)始時(shí)刻之間的關(guān)系；式（16）表示裝船和卸船時(shí)，內(nèi)集卡l被分配去完成任務(wù)i到達(dá)堆場(chǎng)指定位置的時(shí)刻gil和內(nèi)集卡l開(kāi)始任務(wù)i的時(shí)刻il之間的關(guān)系。

模型M1與文獻(xiàn)[14]相比，部分約束條件類(lèi)似，但模型M1更為復(fù)雜，表現(xiàn)在以下幾個(gè)方面：

（1）文獻(xiàn)[14]只考慮了內(nèi)場(chǎng)集卡和場(chǎng)橋的優(yōu)化，而模型M1兼顧了外集卡作業(yè)服務(wù)問(wèn)題。

（2）模型M1的目標(biāo)函數(shù)引入了關(guān)于外集卡節(jié)約等待時(shí)間獎(jiǎng)勵(lì)項(xiàng)，獎(jiǎng)勵(lì)函數(shù)的確定會(huì)對(duì)模型求出的最優(yōu)解有很大的影響。

（3）外集卡節(jié)約的等待時(shí)間和模型優(yōu)化目標(biāo)函數(shù)中的作業(yè)總時(shí)間是耦合的，因此也增加了模型的復(fù)雜度和求解難度。

考慮到實(shí)際作業(yè)的特點(diǎn)，作業(yè)優(yōu)化主要以?xún)?nèi)集卡裝卸作業(yè)為目標(biāo)，在保證內(nèi)集卡作業(yè)效率的前提下才會(huì)考慮外集卡服務(wù)的問(wèn)題。注意到關(guān)于模型M1的目標(biāo)函數(shù)如何選取和以及模型如何快速準(zhǔn)確求解都比較困難，在下一小節(jié)中，將簡(jiǎn)化上述模型，針對(duì)外集卡服務(wù)給出一個(gè)貪婪類(lèi)算法。

3.2.2 簡(jiǎn)化模型

針對(duì)引入外集卡服務(wù)后模型M1求解復(fù)雜的問(wèn)題，本小節(jié)給出一種更為實(shí)用的貪婪算法：當(dāng)場(chǎng)橋完成上一項(xiàng)裝卸任務(wù)，執(zhí)行下一個(gè)任務(wù)的集卡還沒(méi)有到達(dá)場(chǎng)橋，安排場(chǎng)橋外等待區(qū)域內(nèi)排隊(duì)時(shí)間最長(zhǎng)的外集卡服務(wù)。于是得到如下簡(jiǎn)化模型M2：

約束條件為模型M1中的式（1）～（11）、（13）～（15）以及式（17）。式（17）表示場(chǎng)橋完成一項(xiàng)任務(wù)后，是否被調(diào)配為等待時(shí)間最長(zhǎng)的外集卡服務(wù)。

3.3 模型性質(zhì)描述

根據(jù)集裝箱碼頭作業(yè)特點(diǎn)，通常場(chǎng)橋一般只會(huì)服務(wù)一個(gè)指定的區(qū)域，不會(huì)像集卡一樣在整個(gè)堆場(chǎng)范圍移動(dòng)，所以場(chǎng)橋?qū)τ谘b卸任務(wù)的選擇是有限制的。在目前絕大多數(shù)實(shí)際作業(yè)中，場(chǎng)橋完成裝卸任務(wù)的順序一般由它服務(wù)區(qū)域內(nèi)等待的內(nèi)集卡執(zhí)行的裝卸任務(wù)決定，即在場(chǎng)橋服務(wù)區(qū)域內(nèi)，正在等待的集卡需要執(zhí)行哪一項(xiàng)裝卸任務(wù)，場(chǎng)橋就執(zhí)行對(duì)應(yīng)的裝卸任務(wù)。當(dāng)有多輛集卡同時(shí)在場(chǎng)橋服務(wù)區(qū)域內(nèi)等待時(shí)，為了減少場(chǎng)橋的運(yùn)行時(shí)間，通常會(huì)優(yōu)先服務(wù)距離當(dāng)前裝卸作業(yè)位置距離的集卡。根據(jù)上述模型描述，本文求解模型時(shí)充分考慮決策變量之間的聯(lián)系，給出通過(guò)和其他參數(shù)來(lái)確定的方法。按照排隊(duì)論的基本原則，將場(chǎng)橋看作服務(wù)臺(tái)，到達(dá)堆場(chǎng)的集卡根據(jù)裝卸任務(wù)到達(dá)指定位置。當(dāng)場(chǎng)橋完成某項(xiàng)裝卸任務(wù)后，下一項(xiàng)任務(wù)就是在堆場(chǎng)指定區(qū)域等待距離最近的集卡所執(zhí)行的裝卸任務(wù)。多次實(shí)際模擬計(jì)算以及對(duì)碼頭作業(yè)的調(diào)研證明，本文模型更加符合真實(shí)作業(yè)環(huán)境，并可以得到有效的優(yōu)化結(jié)果。

4 粒子群算法求解過(guò)程

PSO是一種新的模仿鳥(niǎo)類(lèi)群體行為的智能優(yōu)化算法，現(xiàn)已成為進(jìn)化算法的一個(gè)新的重要分支。和遺傳算法相似，它也是從隨機(jī)解出發(fā)，通過(guò)迭代尋找最優(yōu)解，也是通過(guò)適應(yīng)度來(lái)評(píng)價(jià)解的品質(zhì)。但是它比遺傳算法規(guī)則更為簡(jiǎn)單，它沒(méi)有遺傳算法的“交叉”（Crossover）和“變異”（Mutation）操作。它通過(guò)追隨當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu)。本文建立的模型中，所有自變量為離散變量，即設(shè)備作業(yè)的任務(wù)選擇。當(dāng)這些離散變量確定以后，根據(jù)實(shí)際碼頭作業(yè)的數(shù)據(jù)，可以確定設(shè)備的位移、速度以及完成時(shí)間等連續(xù)變量。本文采用的PSO算法快速計(jì)算這些離散變量，通過(guò)適應(yīng)度函數(shù)的變化趨勢(shì)來(lái)得到近似最優(yōu)值。

4.1 算法流程

PSO初始化為一群隨機(jī)粒子，然后通過(guò)迭代找到最優(yōu)解。在每一次迭代中，粒子通過(guò)跟蹤兩個(gè)“極值”來(lái)更新自己。第一個(gè)就是粒子本身所找到的最優(yōu)解，稱(chēng)為個(gè)體極值 fk；另一個(gè)極值就是整個(gè)種群目前找到的最優(yōu)解，這個(gè)極值是全局極值 fbest。

在一個(gè)n維的目標(biāo)搜索空間中，n為裝卸任務(wù)總數(shù)。整個(gè)粒子群體由K個(gè)粒子構(gòu)成，每個(gè)粒子看作n維空間中的一個(gè)點(diǎn)。 x=(xk1,xk2,…,xkn)，xki∈[1,N]，且xki為整數(shù)，表示任務(wù)分配給內(nèi)集卡的編號(hào)。在粒子位置給定后，每輛集卡分配到任務(wù)編號(hào)。對(duì)于每一輛集卡來(lái)說(shuō)，以第一個(gè)編號(hào)作為開(kāi)始任務(wù)，完成每項(xiàng)后，采用貪婪法則選擇距離最近的任務(wù)為下一任務(wù)。同時(shí)，考慮到協(xié)調(diào)場(chǎng)橋的需要，讓一半集卡的第一項(xiàng)任務(wù)為裝船任務(wù)，另一半集卡的第一項(xiàng)任務(wù)為卸船任務(wù)。每個(gè)粒子對(duì)應(yīng)的速度為v=(vk1,vk2,…,vkn)。初始狀態(tài)通過(guò)隨機(jī)值給出。

構(gòu)造不確定情況下堆場(chǎng)調(diào)度優(yōu)化的粒子群算法如下（圖2）：

步驟1算法初始化，隨機(jī)給出初始狀態(tài)粒子群位置并計(jì)算適應(yīng)度函數(shù)。

步驟2算法開(kāi)始，更新粒子位置和速度。

每一步迭代過(guò)程中，粒子根據(jù)單個(gè)粒子和所有粒子的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整。 fk=(fk1,fk2,…,fkn)，k=1,2,…,K為第k個(gè)粒子迭代到目前為止搜索到的最優(yōu)值。 fbest=(fb1,fb2,…,fbn)為整個(gè)粒子群粒子迭代到目前為止搜索到的最優(yōu)值。這兩個(gè)因素決定下一步搜索的速度和位置。粒子根據(jù)以下式子進(jìn)行更新和調(diào)整自己的位置：

參數(shù)w是慣性權(quán)重，表示保持原來(lái)速度的系數(shù)，采用線(xiàn)性約減策略來(lái)決定w的值，即

c1和c2是粒子跟蹤自己歷史最優(yōu)值和群體最優(yōu)值的權(quán)重系數(shù)，也稱(chēng)學(xué)習(xí)因子或加速因子，使粒子能夠調(diào)整自身方向，向粒子本身最優(yōu)值和群體最優(yōu)值靠近，通常設(shè)置為2；rand1和rand2表示[0,1]區(qū)間內(nèi)均勻分布的隨機(jī)數(shù)，這兩個(gè)參數(shù)是用來(lái)保持整個(gè)粒子群個(gè)體的多樣性；ρ表示更新位置的步長(zhǎng)，通常稱(chēng)為約束因子，設(shè)置為1。

據(jù)有關(guān)數(shù)據(jù)統(tǒng)計(jì)，住院期間的母乳喂養(yǎng)率較高，出院后則大幅下降。出生后6個(gè)月內(nèi)的純母乳喂養(yǎng)率僅為20.8%。產(chǎn)褥期會(huì)出現(xiàn)多種母乳喂養(yǎng)的問(wèn)題，導(dǎo)致產(chǎn)婦對(duì)母乳喂養(yǎng)信心不足，甚至停止母乳喂養(yǎng)。

步驟3解碼。

由于問(wèn)題的特殊性，這一模型的每個(gè)粒子的位置代表任務(wù)分配給內(nèi)集卡的編號(hào)，必須是1～N之間的整數(shù)。因此在粒子群算法每次迭代更新位置之后，都需要進(jìn)行解碼，解碼方式為對(duì)于粒子位置每個(gè)分量取整，這樣就可以得到有實(shí)際意義的粒子位置。由于在算法過(guò)程中粒子進(jìn)行運(yùn)動(dòng)和解碼時(shí)，并未涉及堆場(chǎng)作業(yè)和各種不確定因素，因此粒子群算法中的這幾個(gè)主要步驟就比較容易實(shí)現(xiàn)，從而提升了算法的效率。

步驟4計(jì)算適應(yīng)度函數(shù)。

每步迭代之后，根據(jù)每個(gè)粒子新的位置，可以計(jì)算每個(gè)粒子的適應(yīng)度函數(shù)。計(jì)算時(shí)，本文模型基于排隊(duì)論的基本原理計(jì)算場(chǎng)橋在堆場(chǎng)裝卸作業(yè)以及集卡行駛和等待的時(shí)間，具體計(jì)算流程如圖2所示。在給定某個(gè)粒子的位置后，可以得到集卡作業(yè)調(diào)度方案，此時(shí)運(yùn)用蒙特卡洛方法實(shí)現(xiàn)集卡在堆場(chǎng)等待和裝卸作業(yè)過(guò)程，計(jì)算從第一個(gè)場(chǎng)橋開(kāi)始工作至場(chǎng)橋結(jié)束所有裝卸任務(wù)的總時(shí)間。同時(shí)，在計(jì)算過(guò)程中，由于集卡行駛速度和場(chǎng)橋裝卸和移動(dòng)時(shí)間為不確定變量，故采用模擬的方法估計(jì)函數(shù)值。

圖2 適應(yīng)度函數(shù)計(jì)算流程圖

步驟5判斷終止條件,決定迭代是否繼續(xù)進(jìn)行下去。

綜上所述，粒子群算法流程如圖3所示。

圖3 粒子群算法流程圖

4.2 分布處理

與以往確定性模型的文章一般采用統(tǒng)計(jì)數(shù)據(jù)的均值代替隨機(jī)變量不同，本文根據(jù)上海港碼頭實(shí)際作業(yè)數(shù)據(jù)統(tǒng)計(jì)規(guī)律，內(nèi)集卡在完成運(yùn)輸任務(wù)的行駛時(shí)間基本服從正態(tài)分布N(μ,σ)，其均值 μ 通過(guò)統(tǒng)計(jì)抽樣，由距離除以平均速度估計(jì)得到；輕車(chē)和重車(chē)在運(yùn)輸時(shí)的平均速度相差不大，但重車(chē)行駛受到外界影響較多，因此標(biāo)準(zhǔn)差σ相對(duì)較大。場(chǎng)橋在堆場(chǎng)指定區(qū)域的行走速度以及作業(yè)時(shí)間基本服從正態(tài)分布。同時(shí)外集卡到達(dá)時(shí)間服從Poisson分布。

5 算例與分析

5.1 試驗(yàn)算例

5.2 評(píng)價(jià)與分析

選取種群大小K=10，應(yīng)用Matlab軟件求解。上百次的試驗(yàn)結(jié)果顯示，選取參數(shù)wmax=1,wmin=0.5時(shí)，算法的計(jì)算結(jié)果和速度都比較理想。本文觀察了500步迭代的考慮不確定性因素的模型和一般確定性模型的目標(biāo)函數(shù)值如圖4所示。圖中表明，考慮不確定性因素的模型中，由于粒子群算法適應(yīng)度函數(shù)具有隨機(jī)性，優(yōu)化模型的目標(biāo)函數(shù)的變化并不是完全單調(diào)下降的，但整體上具有下降的趨勢(shì)。從目標(biāo)函數(shù)值來(lái)看，作業(yè)時(shí)間從初始狀態(tài)的50 min最后減少到接近31～33 min，大大提升了集卡運(yùn)輸作業(yè)效率。大約200多步迭代之后，目標(biāo)函數(shù)值的變化幅度明顯縮小，逐步接近最優(yōu)值。同時(shí)，由于外集卡到達(dá)時(shí)間具有隨機(jī)性，在完成指定任務(wù)作業(yè)過(guò)程中，外集卡到達(dá)的數(shù)量會(huì)有一些差異，這也就導(dǎo)致迭代過(guò)程始終具有較大的震蕩性，目標(biāo)函數(shù)值會(huì)在一定范圍的數(shù)值中變化。與此同時(shí)從圖中可知，粒子群算法的收斂性態(tài)并沒(méi)有因?yàn)殡S機(jī)項(xiàng)的引入帶來(lái)很大的影響，所以它在求解不確定情況下兼顧外集卡作業(yè)的堆場(chǎng)設(shè)備作業(yè)優(yōu)化問(wèn)題上是非常有效的，而本模型顯然更貼近實(shí)際作業(yè)狀況。

圖4 考慮不確定性因素模型和一般確定性模型的目標(biāo)函數(shù)結(jié)果比較

同時(shí)，圖4也是對(duì)采用粒子群算法得出的一般確定性模型結(jié)果與考慮不確定性因素模型的結(jié)果進(jìn)行比較。一般確定性模型是將不確定模型中的隨機(jī)變量用它們的期望值代替，外集卡的到達(dá)時(shí)刻是隨機(jī)值。算法的其他所有步驟都和不確定模型算法相同。圖4可得，考慮不確定因素模型收斂結(jié)果最優(yōu)值為31.5 min，一般確定性模型為42.2 min。一般確定模型算法結(jié)果收斂性態(tài)很差，得到的最優(yōu)值估計(jì)要差很多。

圖5是在不考慮外集卡隨機(jī)到達(dá)影響下，一般確定性模型與考慮不確定性因素模型的堆場(chǎng)設(shè)備作業(yè)時(shí)間的比較。考慮不確定因素模型最終計(jì)算結(jié)果約為28.5 min。所以對(duì)比圖4和圖5的結(jié)果可知，考慮外集卡作業(yè)后，堆場(chǎng)整體作業(yè)時(shí)間大約增加了3 min，而在30 min左右的作業(yè)時(shí)間內(nèi)，到達(dá)外集卡數(shù)量的平均值為3輛。堆場(chǎng)對(duì)于外集卡總的作業(yè)時(shí)間約為100 s×3=300 s。所以，綜合考慮外集卡作業(yè)可以有效提升堆場(chǎng)對(duì)于內(nèi)外集卡作業(yè)的整體效率。

圖5 不考慮外集卡到達(dá)影響的一般確定性模型與不確定性模型結(jié)果比較

本文給出的算法在計(jì)算復(fù)雜度方面有很大的優(yōu)勢(shì)。如果采用遍歷算法，其復(fù)雜度隨著自變量數(shù)量增加指數(shù)上升；而從上面的算例中發(fā)現(xiàn)，本文給出的PSO算法在200多步迭代后就計(jì)算得到了比較好的近似最優(yōu)值，計(jì)算復(fù)雜度是可控的。

6 結(jié)論

本文建立集裝箱碼頭堆場(chǎng)設(shè)備集成調(diào)度優(yōu)化模型，模型中同時(shí)考慮了內(nèi)集卡、場(chǎng)橋和外集卡之間的相互協(xié)調(diào)，并且考慮了實(shí)際作業(yè)中的不確定性因素，包括：內(nèi)集卡行駛速度、場(chǎng)橋作業(yè)時(shí)間和行走速度，以及外集卡的到達(dá)時(shí)間。與傳統(tǒng)只考慮確定環(huán)境下內(nèi)集卡和場(chǎng)橋的調(diào)度優(yōu)化相比，本文模型可以提高堆場(chǎng)作業(yè)調(diào)度的整體性與協(xié)調(diào)性，并更貼近實(shí)際作業(yè)情況，提高碼頭服務(wù)質(zhì)量。粒子群算法可以提高模型的求解效率，算例分析結(jié)果表明，該模型和算法可以在兼顧外集卡作業(yè)的情況下有效解決不確定環(huán)境下集裝箱碼頭堆場(chǎng)的集成調(diào)度優(yōu)化問(wèn)題。所設(shè)計(jì)的算例規(guī)模雖小，但已經(jīng)能夠說(shuō)明模型的合理性。

本文今后的研究重點(diǎn)和方向包括考慮外集卡在閘口服務(wù)時(shí)間對(duì)于堆場(chǎng)設(shè)備作業(yè)的影響，同時(shí)協(xié)調(diào)內(nèi)外集卡的作業(yè)從而進(jìn)一步提升作業(yè)效率等。

[1]楊朋，繆立新，戚銘堯.多載具自動(dòng)化存取系統(tǒng)貨位分配和揀選路徑集成優(yōu)化[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，51（2）：261-266.

[2]趙寧，宓為建，何軍良.集裝箱碼頭發(fā)箱任務(wù)的集卡指派模型[J].上海海事大學(xué)學(xué)報(bào)，2011，32（1）：8-12.

[3]Kim K H，Park Y M.A crane scheduling method for port container terminals[J].European Journal of Operational Research，2004，156（3）：752-768.

[4]Ng W C，Mak K L.Yard crane scheduling in port container terminals[J].Journal of Applied Mathematics，2005，29（3）：263-276.

[5]Ng W C，Mak K L，Zhang Y X.Scheduling trucks in containerterminalsusing a genetic algorithm[J].Engineering Optimization，2007，39（1）：33-47.

[6]韓曉龍，丁以中.集裝箱碼頭港口龍門(mén)吊配置優(yōu)化研究[J].中國(guó)航海，2008，31（1）：6-9.

[7]Cao J X，Lee D H，Chen J H，et al.The integrated yard truckand yard cranescheduling problem：Benders’decomposition-based methods[J].Transportation Research，2010（4）：344-353.

[8]樂(lè)美龍，包節(jié)，范志強(qiáng).龍門(mén)吊與集卡協(xié)同調(diào)度問(wèn)題研究[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（14）：241-248.

[9]劉艷，周鵬飛，康海貴.集裝箱堆場(chǎng)箱位分配模糊優(yōu)化研究[J].水運(yùn)工程，2009（11）：1-5.

[10]周鵬飛，李丕安.不確定條件下集裝箱堆場(chǎng)出口箱具體箱位優(yōu)選[J].工業(yè)工程，2013，16（1）：25-30.

[11]Tandon V，Mounayri H E，Kishawy H.NC end milling optimization using evolutionary computation[J].International Journal of Machine Tools and Manufacture，2002，42（5）：595-605.

[12]李莉.集卡港內(nèi)作業(yè)與港外運(yùn)輸綜合調(diào)度研究[D].天津：天津工業(yè)大學(xué)，2011.

[13]李臻，雷定猷.多車(chē)場(chǎng)車(chē)輛優(yōu)化調(diào)度模型及算法[J].交通運(yùn)輸工程學(xué)報(bào)，2004，4（l）：83-86.

[14]Lu Yiqin，Le Meilong.The integrated optimization of container terminal scheduling with uncertain factors[J].Computers and Industrial Engineering，2014，75：209-216.

LU Yiqin

School of Economicsamp;Management,Shanghai University of Electric Power,Shanghai 200090,China

Integrated scheduling optimization of yard equipment with uncertain factors at container terminal.Computer Engineering and Applications,2017,53（21）：247-253.

On the scheduling optimization of the yard equipment,more studied the combined dispatching of the inner container trucks and yard cranes under deterministic conditions,and less considered the random arrival time of the outer container trucks.The uncertain factors including the speed of the inner container trucks,the speed and the operation time of the yard cranes are considered.And according to the effect of the random arrival time of the outer container trucks on the scheduling operation of the inner container trucks,the optimization model considering the uncertain factors of the integrated scheduling of the yard equipment is established.The objective is to minimize the operation time of the yard equipment considering the random arrival time of the outer container trucks.So the particle swarm optimization algorithm is designed to settle the model,and the optimized results of the uncertain model are compared with that of the deterministic model.The numerical experiments and results represent that the model and the algorithm truly and effectively reflect the effect of the uncertain conditions on the operation of the yard equipment.

uncertain factors;integrated scheduling;yard equipment;outer container trucks

A

U691

10.3778/j.issn.1002-8331.1704-0437

中小物流企業(yè)信息化方案與決策（No.H2016-029）；國(guó)家自然科學(xué)基金（No.71171129）；上海市科委科研計(jì)劃項(xiàng)目（No.12510501600，No.14DZ2280200）。

盧毅勤（1980—），女，博士，講師，研究領(lǐng)域?yàn)榧b箱碼頭作業(yè)系統(tǒng)調(diào)度優(yōu)化，E-mail：lu_yiqin@163.com。

2017-05-03

2017-06-20

1002-8331（2017）21-0247-07