梁承姬，王典雪，徐德洪

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

?

基于滾動策略的不確定干擾下場橋調(diào)度問題研究

梁承姬，王典雪*，徐德洪

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

目前影響集裝箱港口裝卸效率的“瓶頸”從岸邊作業(yè)轉(zhuǎn)移到堆場作業(yè).合理的場橋調(diào)度方案不僅可以提高堆場作業(yè)效率也可以配合集卡、岸橋，提高整個港口的裝卸效率.而在實(shí)施場橋調(diào)度方案時(shí)，總會出現(xiàn)各種不確定干擾因素使得原先的方案不能正常實(shí)行.針對這一問題 ，本文提出一種在滾動窗口策略下處理不確定干擾因素的場橋調(diào)度流程，即當(dāng)出現(xiàn)干擾時(shí)，觸發(fā)窗口再調(diào)度機(jī)制，以減少干擾的影響.并且建立了以任務(wù)完成最大延遲量最小化為目標(biāo)的混合整數(shù)規(guī)劃模型，采用改進(jìn)遺傳算法對模型進(jìn)行求解.通過案例分析對比，驗(yàn)證了算法的有效性以及滾動窗口策略下場橋調(diào)度方案更優(yōu)，更符合港口的實(shí)際運(yùn)營.

滾動窗口策略； 不確定干擾因素； 場橋調(diào)度； 改進(jìn)遺傳算法

集裝箱碼頭是陸地和海上運(yùn)輸?shù)倪B接點(diǎn)，并且作為多式聯(lián)運(yùn)的轉(zhuǎn)運(yùn)站和樞紐來進(jìn)行服務(wù)[1].因此，對于任何一個集裝箱碼頭來說，堆存效率以及在碼頭區(qū)的大量集裝箱運(yùn)輸都是至關(guān)重要的.目前影響集裝箱港口裝卸效率的“瓶頸”從岸邊作業(yè)轉(zhuǎn)移到堆場作業(yè).合理的場橋調(diào)度方案可以提高堆場作業(yè)效率，因此場橋調(diào)度問題的研究對于集裝箱港口的作業(yè)管理具有重要意義[2].對于場橋調(diào)度工作，目前主要是依據(jù)場橋就近原則，工作量平衡原則，場橋調(diào)度員憑借經(jīng)驗(yàn)進(jìn)行調(diào)度，缺乏系統(tǒng)性.場橋調(diào)度問題對于集裝箱碼頭的作業(yè)管理有著重要意義.本文將研究基于不確定因素下的場橋調(diào)度，為了達(dá)到優(yōu)化調(diào)度方案，使得堆場作業(yè)效率提高從而提高碼頭作業(yè)效率的目的.

目前已有不少學(xué)者對場橋調(diào)度問題進(jìn)行了研究.文獻(xiàn)[3]和文獻(xiàn)[4]討論了場橋的動態(tài)調(diào)度問題，在最小化剩余工作量的目標(biāo)下，確定場橋在箱區(qū)間移動的次數(shù)和路線.文中建立了混合整數(shù)規(guī)劃模型，并采用啟發(fā)式算法進(jìn)行求解.模型的基本假設(shè)中考慮了場橋之間的干涉約束，設(shè)定每個箱區(qū)中最多只能有兩臺場橋同時(shí)工作，有效避免了調(diào)度的不必要麻煩，通過算例分析，驗(yàn)證了方法的有效性.文獻(xiàn)[5]研究多臺場橋的調(diào)度問題時(shí)，考慮了場橋間的干涉因素以及具有不同服務(wù)時(shí)間的任務(wù)集，并建立了整數(shù)規(guī)劃模型.由于場橋調(diào)度問題為NP-hard問題，文章最后采用基于動態(tài)規(guī)劃的啟發(fā)式算法求解模型.計(jì)算結(jié)果表明，啟發(fā)式算法能夠有效地解決調(diào)度問題.以上文獻(xiàn)在考慮場橋調(diào)度問題的時(shí)候，只考慮了場橋作業(yè)時(shí)的干涉因素(由于場橋體積大，多臺場橋同時(shí)作業(yè)會出現(xiàn)“干涉”情況)，并沒有考慮到實(shí)際作業(yè)中會出現(xiàn)的不確定干擾因素(比如，由于某船舶需要緊急離港，該船上的箱子需要緊急處理，這樣，原先的場橋任務(wù)分配情況會受到干擾)，而在實(shí)際港口碼頭作業(yè)中，不確定的干擾因素是大量存在的，因此，本文將把不確定干擾因素考慮到場橋調(diào)度中來，企圖得到更符合實(shí)際的調(diào)度方案.

文獻(xiàn)[6]考慮了一種動態(tài)滾動策略的場橋調(diào)度決策方案，建立了最小化箱區(qū)內(nèi)所有任務(wù)的延遲量以及場橋轉(zhuǎn)場距離的整數(shù)規(guī)劃模型，提出了一種結(jié)合仿真模型的啟發(fā)式算法，并建立仿真模型以推進(jìn)計(jì)劃周期，對任務(wù)組的延誤進(jìn)行評估.同時(shí)，采用遺傳算法對啟發(fā)式算法得到的初始解進(jìn)行優(yōu)化.通過算例驗(yàn)證，提出的動態(tài)滾動策略更貼近于碼頭實(shí)際作業(yè)情況，比靜態(tài)滾動方法得出更精確的調(diào)度方案.文獻(xiàn)[7]進(jìn)行了基于時(shí)間窗的場橋調(diào)度研究，利用干涉管理思想，解決場橋?qū)嶋H調(diào)度中產(chǎn)生的操作困難，得出相應(yīng)的模型函數(shù)求得最優(yōu)調(diào)度策略；其次，引入時(shí)間窗概念，通過設(shè)置理性的時(shí)間窗，構(gòu)造帶有時(shí)間窗的場橋調(diào)度函數(shù)模型，使整個場橋調(diào)度中存取箱作業(yè)盡量滿足集裝箱計(jì)劃到達(dá)時(shí)刻表，減少存取箱作業(yè)的提前或延遲，以達(dá)到集卡等待時(shí)間最小化，最大化場橋利用效率.以上兩篇文獻(xiàn)，從設(shè)計(jì)滾動時(shí)段的角度，針對場橋調(diào)度，進(jìn)行周期性的滾動更新，這比以往的靜態(tài)調(diào)度得到更優(yōu)良的調(diào)度方案；文獻(xiàn)[6]采用遺傳算法對啟發(fā)式算法的初始解進(jìn)行優(yōu)化，驗(yàn)證該方法的有效性，而戴開梅則加入時(shí)間窗，運(yùn)用啟發(fā)式算法求解，雖然都取得有效成果，但兩篇文獻(xiàn)仍然沒有將不確定干擾因素考慮進(jìn)來，此外，兩篇文獻(xiàn)提出的是離散時(shí)間下的場橋調(diào)度問題，而場橋調(diào)度是實(shí)時(shí)調(diào)度，并且實(shí)時(shí)調(diào)度問題會經(jīng)常出現(xiàn)new arrival moves handling，因此，本文將從連續(xù)時(shí)間角度考慮場橋?qū)崟r(shí)調(diào)度問題.

文獻(xiàn)[8]考慮了基于遺傳算法的車間動態(tài)調(diào)度研究，考慮了車間作業(yè)在不確定因素影響下，進(jìn)行滾動優(yōu)化機(jī)制，利用改進(jìn)遺傳算法求解.實(shí)例證明，采用該方法可以使得車間作業(yè)效率大大提高.文獻(xiàn)[9]對動態(tài)泊位調(diào)度引入滾動窗口技術(shù)，并采用Memetic算法進(jìn)行計(jì)算求解得出較優(yōu)的泊位調(diào)度方案，文中的Memetic算法結(jié)合了禁忌搜索和遺傳算法求解，禁忌搜索用于局部搜索，遺傳算法用于全局優(yōu)化，算例證明了該算法在解決此問題時(shí)的有效性.文獻(xiàn)[10]針對連續(xù)泊位與橋吊集成調(diào)度求解的困難，引入一種基于滾動策略的優(yōu)化方法，將動態(tài)抵泊的船舶按照順序分成若干連續(xù)的調(diào)度窗口，設(shè)計(jì)滾動窗口的滾動機(jī)制，采用啟發(fā)式算法求解，通過算例分析說明利用滾動調(diào)度方法能有效解決大規(guī)模的調(diào)度問題.以上3篇文獻(xiàn)都將滾動窗口策略引用到動態(tài)調(diào)度問題里面來，并得到較優(yōu)的調(diào)度方案.滾動調(diào)度方法的主要思想在于，通過反復(fù)求解小規(guī)模優(yōu)化問題來取代求解大規(guī)模調(diào)度問題，這樣，將問題簡化，同時(shí)得到更優(yōu)解決方案.但是，這些思想目前還沒有在場橋調(diào)度中得到運(yùn)用；因此，本文將從連續(xù)時(shí)間角度考慮場橋?qū)崟r(shí)調(diào)度問題，根據(jù)集裝箱動態(tài)到達(dá)的順序，將調(diào)度過程分為連續(xù)的調(diào)度窗口，將大規(guī)模的調(diào)度分解，引用滾動窗口策略方法，通過此方法解決場橋作業(yè)中的不確定干擾因素.基于前面有學(xué)者采用遺傳算法求解驗(yàn)證了該算法在求解此類問題的有效性，因此，本文將繼續(xù)用遺傳算法求解.

1 問題描述

在場橋調(diào)度中，存在場橋來不及處理任務(wù)，集卡等待的情況，這造成了集卡資源的浪費(fèi)，作業(yè)分配不合理也影響了集裝箱碼頭的作業(yè)效率，從而降低了貨物吞吐量.在實(shí)際集裝箱碼頭作業(yè)中，存在許多不確定因素，比如：船舶到港時(shí)間的不確定會影響集裝箱是否能按時(shí)被處理；場橋可能出現(xiàn)機(jī)械故障，不能及時(shí)對集裝箱服務(wù)；集裝箱延遲到達(dá)，但又急需處理等等因素.為了更好達(dá)到客戶需求，本文引用“滾動窗口策略”來解決動態(tài)調(diào)度問題，當(dāng)發(fā)生不確定干擾因素時(shí)立即重調(diào)度，如果未發(fā)生干擾因素，則進(jìn)行之前設(shè)定的周期滾動調(diào)度.這樣做目的是實(shí)現(xiàn)場橋?qū)崟r(shí)調(diào)度，從而節(jié)省時(shí)間，使服務(wù)水平得到提高.場橋調(diào)度的流程如圖1.

圖1 場橋調(diào)度流程圖Fig.1 The process of YC schedule

滾動窗口策略的工作原理為：在初始時(shí)刻，從所有待處理任務(wù)中選取一定數(shù)目的任務(wù)，加入任務(wù)窗口進(jìn)行調(diào)度并產(chǎn)生初始調(diào)度方案，這是靜態(tài)調(diào)度問題；但在初始方案的執(zhí)行過程中，由于作業(yè)環(huán)境情況的變化，需要進(jìn)行再調(diào)度，也就是動態(tài)調(diào)度；這時(shí)將已完工的任務(wù)從任務(wù)窗口中移去，再加入一批待處理任務(wù)到任務(wù)窗口中，重新對任務(wù)窗口內(nèi)的任務(wù)進(jìn)行靜態(tài)調(diào)度.這樣的過程重復(fù)進(jìn)行，直到所有任務(wù)都完成，這就是滾動窗口調(diào)度策略.

滾動調(diào)度方法的主要思想是滾動優(yōu)化，把不確定性調(diào)度問題分解成一系列動態(tài)但確定的調(diào)度問題，通過將動態(tài)調(diào)度過程分解成連續(xù)靜態(tài)調(diào)度窗口，然后在線優(yōu)化每個滾動窗口，使系統(tǒng)在此窗口內(nèi)達(dá)到最優(yōu)，再平移窗口并更新窗口中優(yōu)化問題的參數(shù)，以此循環(huán)，直到所有任務(wù)完成.首先建立一個動態(tài)調(diào)度裝卸任務(wù)窗口，窗口任務(wù)數(shù)量的選取根據(jù)集裝箱碼頭實(shí)際的作業(yè)情況來確定，一般按照先到先服務(wù)的原則選取一定數(shù)量的任務(wù)加入到場橋調(diào)度窗口，對當(dāng)前窗口下的任務(wù)建立數(shù)學(xué)優(yōu)化模型，求解得出當(dāng)前的場橋調(diào)度方案，并設(shè)定周期的滾動時(shí)間；當(dāng)觸發(fā)再調(diào)度機(jī)制的突發(fā)事件出現(xiàn)時(shí)，實(shí)施再調(diào)度.將已完成的任務(wù)從滾動窗口移除，并把需要緊急處理的任務(wù)移入滾動窗口，使當(dāng)前窗口中的裝卸任務(wù)數(shù)量保持一定的平衡，場橋進(jìn)行任務(wù)再分配，不斷的重復(fù)上述過程，直到所有的裝卸任務(wù)全部完成.

假設(shè)設(shè)定周期性的再調(diào)度每間隔30 min調(diào)度一次，從0時(shí)刻開始，根據(jù)已到達(dá)場區(qū)任務(wù)以及任務(wù)處理優(yōu)先權(quán)等原則，進(jìn)行初始調(diào)度計(jì)劃，各場橋進(jìn)行任務(wù)安排，開始作業(yè)；隨著任務(wù)的進(jìn)行，到達(dá)的任務(wù)會發(fā)生變化，任務(wù)處理順序也會發(fā)生相應(yīng)變化，假設(shè)在時(shí)刻20 min時(shí)出現(xiàn)某緊急任務(wù)需要處理，時(shí)刻50 min該任務(wù)處理完成，那么，該系統(tǒng)調(diào)度時(shí)刻為20 min、30 min、50 min、60 min，以此類推，直到所有任務(wù)完成.圖2即為任務(wù)受到干擾時(shí)的處理情況.

圖2 處理干擾的調(diào)度示意圖Fig.2 The dealing of the interference

當(dāng)突發(fā)因素出現(xiàn)時(shí)，場橋應(yīng)該優(yōu)先處理干擾因素，此時(shí)應(yīng)該暫時(shí)“封存”原先任務(wù)，進(jìn)行重調(diào)度，當(dāng)干擾因素處理結(jié)束，進(jìn)行場橋重調(diào)度，直到任務(wù)完成.以需要緊急處理的集裝箱為例.

由于船舶需要緊急離港，該船上的箱子需要及時(shí)處理.定義p1為正在作業(yè)的任務(wù)，p2為待入場任務(wù)，其具體步驟如下：

Step1：將需要緊急處理的任務(wù)安插到p1之后，同時(shí)暫時(shí)“封存”p2中的所有待處理的任務(wù)；

Step2：計(jì)算p1中所有任務(wù)的完工時(shí)間以及場橋的釋放時(shí)間；

Step3：運(yùn)用遺傳算法進(jìn)行調(diào)度，得到對于緊急處理任務(wù)的優(yōu)化結(jié)果；

Step4：當(dāng)緊急處理的任務(wù)被處理完畢后，p2中待處理任務(wù)的預(yù)期處理順序和服務(wù)場橋已經(jīng)不同.計(jì)算緊急處理的任務(wù)被安排之后所有場橋的可釋放時(shí)刻；

Step5：運(yùn)用遺傳算法進(jìn)行再調(diào)度，生成新的調(diào)度方案.

例如，圖2中從上到下是場橋處理任務(wù)的順序，每個圈代表一個任務(wù)，圈中的數(shù)字代表任務(wù)編號，其中，灰色為發(fā)生擾動計(jì)劃的任務(wù)，圖中虛線指任務(wù)的擾動計(jì)劃.任務(wù)初始安排如圖2(a)所示，由于任務(wù)進(jìn)行到100 min時(shí)，任務(wù)15，16，18，19需要緊急處理，因此，應(yīng)優(yōu)先安排，此時(shí)，調(diào)用GA進(jìn)行場橋重調(diào)度，以在規(guī)定時(shí)間完成緊急任務(wù)的前提下最小化任務(wù)延遲量為目標(biāo).原來任務(wù)11由YC2服務(wù)，重調(diào)度后置于任務(wù)15之后，由YC3處理；任務(wù)18，19則安插在YC2處理的任務(wù)8和任務(wù)13之間，任務(wù)13和10也相繼往后移動.即重調(diào)度后YC2發(fā)生變化的任務(wù)處理順序依次為18、19、13、10，而YC3處理完任務(wù)16后的任務(wù)處理順序由原來的18、 15 、19變?yōu)?5、11.得到的新調(diào)度方案，如圖2中圖(b)所示.其作業(yè)流程圖如圖3所示：

圖3 滾動策略調(diào)用GA作業(yè)流程圖Fig.3 The progress of rolling-horizon decision strategy using GA

2 模型建立

在每個時(shí)間窗內(nèi)建立以任務(wù)完成最大延遲量最小化為目標(biāo)的混合整數(shù)規(guī)劃模型.本文研究的案例來自一個有4個箱區(qū)的堆場，集裝箱均為20英尺，考慮4小時(shí)作業(yè)時(shí)段，數(shù)據(jù)來自于某港口碼頭實(shí)際業(yè)務(wù)數(shù)據(jù).為避免場橋作業(yè)中出現(xiàn)干涉，假設(shè)單個箱區(qū)內(nèi)同時(shí)作業(yè)的場橋數(shù)不超過兩臺；滾動策略為每小時(shí)滾動一次，突發(fā)干擾因素只考慮緊急任務(wù)情況；每個時(shí)段場橋的任務(wù)數(shù)量不應(yīng)該超過場橋從當(dāng)前時(shí)間到計(jì)劃完成時(shí)間的工作能力.前期未完成的任務(wù)仍然被視為一個新的任務(wù)，該任務(wù)的到達(dá)時(shí)間即為當(dāng)前滾動周期的開始時(shí)間.假設(shè)場橋在平行場區(qū)間的移動距離按箱區(qū)長度計(jì)算，在垂直區(qū)間的移動設(shè)定所有轉(zhuǎn)彎以及垂直行駛時(shí)間固定為3*3.5 min；假設(shè)場橋完成一次move(一次存箱或取箱任務(wù))的時(shí)間是3 min；無突發(fā)干擾因素發(fā)生時(shí)，每臺場橋在一個時(shí)段內(nèi)只能在某一箱區(qū)服務(wù)，且場橋必須處理完當(dāng)前任務(wù)才能處理下一個任務(wù).

2.1 基本假設(shè)

1) 堆場內(nèi)用于卸裝作業(yè)的場橋型號、司機(jī)水平等相同，確保場橋作業(yè)效率一致；

2) 集卡運(yùn)行速度，場橋作業(yè)效率均一致；

3) 一個任務(wù)組的集裝箱放到同一箱區(qū)，來自于同一船舶；

4) 場橋在完成集裝箱任務(wù)過程中，集卡的配置數(shù)目是充足的；

5) 所有場橋在同一計(jì)劃時(shí)間段，同時(shí)開始和結(jié)束該時(shí)段的作業(yè).

2.2 參數(shù)設(shè)計(jì)

NP：計(jì)劃時(shí)間域內(nèi)計(jì)劃時(shí)間段總數(shù)；

NTt：t計(jì)劃時(shí)段內(nèi)集裝箱任務(wù)組數(shù)量；

NTit：t計(jì)劃時(shí)間段內(nèi)集裝箱任務(wù)組中包含的集裝箱任務(wù)數(shù)量i；

Bit：t計(jì)劃時(shí)間段內(nèi)集裝箱任務(wù)組所在的箱區(qū)；

Nc：當(dāng)前計(jì)劃時(shí)間段內(nèi)的新任務(wù)組數(shù)量；

j： 新的集裝箱任務(wù)組；

S： 箱區(qū)s的可用容量；

M：需要作業(yè)的集裝箱集M={1，2，…，m}；

NC：場區(qū)中可用的場橋總數(shù)；

k： 場橋k編號；

NTj：當(dāng)前計(jì)劃時(shí)間段內(nèi)新任務(wù)組j里的任務(wù)數(shù)量；

TPit：t計(jì)劃時(shí)間段內(nèi)集裝箱任務(wù)組i的計(jì)劃完成時(shí)間；

TRit：t計(jì)劃時(shí)間段內(nèi)集裝箱任務(wù)組i的實(shí)際完成時(shí)間；

TPj：當(dāng)前時(shí)段新任務(wù)組j的計(jì)劃完成時(shí)間；

TRj：當(dāng)前時(shí)段新任務(wù)組j的實(shí)際完成時(shí)間；

v： 場橋作業(yè)效率；

2.3 決策變量

如果場橋k在t時(shí)段內(nèi)分配給集裝箱任務(wù)i，xikt=1；否則，xikt=0.

如果集裝箱任務(wù)i放到箱區(qū)s，yis=1；否則，yis=0.

2.4 約束條件

j=(1，2，…，NC)，

(1)

i=(1，2，…，NTt)，

(2)

Tli-Tai>0，

(3)

(4)

(5)

i∈(1，2，…，NTt)， t=(1，2，…，NP)，

(6)

(7)

(8)

xikt=0 or 1， t=(1，2，…，NP)，

i=(1，2，…，NTt);k=(1，2，…，NC)，

(9)

TBiot=0 or 1， t=(1，2，…，NP)，

i=(1，2，…，NTt); o=(1，2，…，NTt)，i≠0.

(10)

約束條件(1)表示任意時(shí)段內(nèi)，一臺場橋只能同時(shí)服務(wù)一個集裝箱任務(wù)組；(2)表示任意時(shí)段內(nèi)，一個集裝箱任務(wù)組有且只有一臺場橋服務(wù)；(3)表示每個集裝箱任務(wù)組必須在集卡到達(dá)箱區(qū)后才開始被服務(wù)；(4)表示需要存放的集裝箱總數(shù)不大于堆場容量；(5)表示當(dāng)前時(shí)段內(nèi)總的任務(wù)數(shù)量等于每個時(shí)段內(nèi)任務(wù)數(shù)量和；(6)表示任意時(shí)段，同一場區(qū)同時(shí)作業(yè)的場橋數(shù)不超過兩臺 ；(7)表示任何時(shí)段內(nèi)被分配作業(yè)的場橋數(shù)量不大于總的場橋數(shù)量；(8)表示場橋工作能力不超過集裝箱任務(wù)數(shù)量；(9)、(10)均是二進(jìn)制表示.

2.5 目標(biāo)函數(shù)

(NTi(t-1)-NTit)v，

(11)

(12)

(13)

(11)是目標(biāo)函數(shù)，旨在求滾動計(jì)劃時(shí)段內(nèi)的任務(wù)完成時(shí)間的延遲量最小.(12)指當(dāng)前滾動時(shí)段內(nèi)總的計(jì)劃任務(wù)量；(13)指當(dāng)前滾動時(shí)段總的任務(wù)完成量.

3 算例分析

3.1 遺傳算法

場橋調(diào)度問題是一個NP難的問題，計(jì)算復(fù)雜度很高，很難用現(xiàn)有的研究技術(shù)在合理時(shí)間內(nèi)獲得滿意的解.在解決場橋調(diào)度問題時(shí)，以往的研究中有采用模擬退火算法，禁忌搜索算法以及啟發(fā)式算法等方法求解的，而對于滾動策略來說，使用啟發(fā)式算法計(jì)算量太大，根據(jù)參考文獻(xiàn)有學(xué)者采用遺傳算法求解并得到較好結(jié)果，因此，本文考慮使用改進(jìn)的遺傳算法來解決該問題.下面是對遺傳算法的具體解決方案解釋.

3.1.1 染色體編碼 本文采用的是二維編碼，分別表示場橋作業(yè)順序，以及場橋的任務(wù)組作業(yè)量.染色體采用整數(shù)形式編碼.具體形式如下.

圖4 染色體編碼Fig.4 The chromosome encoding

染色體編碼可理解為：若場橋j在任務(wù)i的作業(yè)順序是0，表示場橋j不服務(wù)任務(wù)組i；此時(shí)，該基因處的作業(yè)量即為0.每條場橋染色體的長度為NT1+Nc.該染色體表示：場橋1給任務(wù)組3服務(wù)，作業(yè)量為20個move(move為場橋作業(yè)量的單位，表示場橋經(jīng)過一次起重和落重，完成一次裝卸任務(wù))，場橋2先為任務(wù)組1完成24個move，再給任務(wù)組2完成35個move.

3.1.2 種群初始化 種群初始化方法如下流程圖所示，假設(shè)種群規(guī)模為n，也就是說，要形成完整的種群，需要將該方法重復(fù)n次.

圖5 種群初始化Fig.5 The population initialization

3.1.3 適應(yīng)度函數(shù) 適應(yīng)度函數(shù)的公式如下：

(14)

目標(biāo)函數(shù)值越小，適應(yīng)度函數(shù)值越小，個體適應(yīng)度越高.

3.1.4 父代選擇 父代選擇的步驟為

Step3：計(jì)算個體的累計(jì)概率.

Step4：產(chǎn)生n個0到1之間的隨機(jī)數(shù).

Step5：如果隨機(jī)數(shù)落在兩個個體的累積概率之間，則選擇累積概率較高的那個個體.

3.1.5 遺傳算子設(shè)計(jì) 遺傳算子設(shè)計(jì)步驟如下.

1) 選擇

為了減少整個程序運(yùn)行時(shí)間，本文考慮選擇算子采用較簡單的隨機(jī)遍歷選擇策略.具體操作像輪盤賭一樣計(jì)算選擇概率ps，只是隨機(jī)遍歷選擇法中等距離的選擇體，如圖6所示，設(shè)newpoint 為需要選擇的個體數(shù)目，進(jìn)行等距離的選擇個體，選擇指針的距離是1/newpoint ，第一個指針的位置由[0，1/newpoint ]的均勻隨機(jī)數(shù)決定.

圖6 隨機(jī)遍歷選擇法Fig.6 The method of random traversal selection

本文采用整數(shù)編碼，一般整數(shù)編碼采用普通的單點(diǎn)交叉或者多點(diǎn)交叉方式.為了更好地控制修正發(fā)生的概率和修正幅度，本文設(shè)計(jì)一種基于滑動窗口的兩點(diǎn)交叉算子，其具體思想如下.

Step1： 選取兩個個體作為父代，在選取的父代中按設(shè)定的滑動窗口大小內(nèi)隨機(jī)確定兩個交叉點(diǎn)，形成一個交叉的基因片段窗口，基因片段為不超過設(shè)定的滑動窗口大小的連續(xù)基因組成，如圖7所示.

交換后發(fā)現(xiàn)有重復(fù)基因(圖中陰影部分標(biāo)出)；

圖7 根據(jù)設(shè)定窗口大小選擇基因片段Fig.7 According to the setted window size selecting gene

圖8 交換基因后的染色體Fig.8 The chromosome after exchanging gene

圖9 重復(fù)基因修正流程圖Fig.9 The progress of gene repair

圖10 修正過后的子染色體Fig.10 The repaired chromosome

2) 變異

為了避免算法陷入局部最優(yōu)，設(shè)計(jì)合理的變異算子使得增加后代多樣性.本文設(shè)計(jì)了一種非線性變異算子進(jìn)行染色體變異，表達(dá)式為

Offspring=

上式中，A和B分別是變異的上限和下限，r是0到1之間的一個隨機(jī)數(shù)，N為種群當(dāng)前的迭代次數(shù)，M為種群的最大迭代次數(shù)，c為變異的調(diào)節(jié)參數(shù).場橋作業(yè)順序的變異范圍是[0，NT1+Nc].計(jì)劃周期開始時(shí)已有任務(wù)組的作業(yè)量變異范圍為[0，NTi1]而周期內(nèi)新出現(xiàn)任務(wù)組的作業(yè)量變異范圍為[0，NTk].此外，若染色體某基因的作業(yè)順序維為0，則其任務(wù)組作業(yè)量維也必須為0.

3.1.6 基因修復(fù) 在交叉與變異完成后，有可能產(chǎn)生不可行后代，此時(shí)需要進(jìn)行用基因修復(fù).本文設(shè)計(jì)的基因修復(fù)具體規(guī)則如下：

規(guī)則1 如果場橋j被分配給任務(wù)組i，但此時(shí)另外一臺場橋正在對任務(wù)組i服務(wù)，那么場橋j應(yīng)該被分配給其他沒有場橋作業(yè)的任務(wù)組.

規(guī)則2 如果場橋j被分配給任務(wù)組i，但此時(shí)已經(jīng)有兩臺場橋在任務(wù)組i所在的箱區(qū)作業(yè)，那么場橋j應(yīng)該被分配到另一個任務(wù)組，且該任務(wù)組所在箱區(qū)正在工作的場橋數(shù)不大于1.

3.1.7 子代接收策略 在交叉、變異和基因修復(fù)完成后，將所有的后代按照適應(yīng)值排列，并將序號大于種群規(guī)模數(shù)的后代舍棄.

3.1.8 終止條件設(shè)定 當(dāng)算法的迭代次數(shù)達(dá)到最大迭代次數(shù)時(shí)，算法終止.算法的最大迭代次數(shù)由實(shí)驗(yàn)決定.

3.2 算例分析—以突發(fā)緊急任務(wù)為例

本文算例基于一個在4個箱區(qū)具有4臺場橋?qū)?7個任務(wù)組的作業(yè)的情景，算例在可作業(yè)時(shí)間為240 min的時(shí)段內(nèi)進(jìn)行，在MATLAB上用遺傳算法進(jìn)行求解.算例輸入數(shù)據(jù)見表1所示.

表1 算例初始數(shù)據(jù)

表1中，TN指任務(wù)組編號，Slot指任務(wù)目標(biāo)堆存位置，PT指任務(wù)組準(zhǔn)備時(shí)間，V指每個任務(wù)組包含任務(wù)量.首先，進(jìn)行無干擾情況下的周期驅(qū)動的滾動窗口策略的算例，在MALAB上用遺傳算法求解得到的任務(wù)分配方案如圖11所示.

圖11 無干擾情況下場橋調(diào)度方案Fig.11 YC schedule without interference

由上圖，可直觀看到，在無干擾情況下，實(shí)施周期驅(qū)動的滾動策略調(diào)度方案，對任務(wù)進(jìn)行合理安排，使得每個滾動窗口內(nèi)的目標(biāo)函數(shù)最優(yōu)，使每個窗口內(nèi)延遲量最小，該方案下，所有任務(wù)完成時(shí)間為228 min，圖中M指任務(wù)組，M右邊第一個數(shù)字指所在箱區(qū)，后兩位數(shù)字代表箱子存放位置，圖中從左向右即為場橋服務(wù)的順序.

本文考慮一種基于急件插入情況的突發(fā)干擾因素，某時(shí)刻由于船舶急需離港，該船上的集裝箱急需處理，此時(shí)，應(yīng)該將屬于該船上的任務(wù)作為緊急任務(wù)插入，調(diào)整場橋分配，重新安排任務(wù).算例設(shè)定滾動計(jì)劃為60 min進(jìn)行一次周期滾動，同時(shí)，突發(fā)任務(wù)出現(xiàn)時(shí)進(jìn)行重新調(diào)度，定義同一個箱區(qū)內(nèi)的可以集中裝卸的多個任務(wù)為一個任務(wù)組，任務(wù)組作為場橋作業(yè)的最小化單位，場橋一次作業(yè)叫做一個move.下面進(jìn)行有干擾情況的算例分析.

由于在任務(wù)進(jìn)行到第100 min時(shí)，來自箱區(qū)3的任務(wù)組15，16，18，19需要在一個小時(shí)后處理完，因此進(jìn)行緊急處理，此時(shí)發(fā)生重調(diào)度計(jì)劃，因此，第二次滾動的調(diào)度方案受到干擾，進(jìn)行重調(diào)度后的調(diào)度方案和無干擾情況進(jìn)行對比可知，場橋2和場橋3發(fā)生重調(diào)度，場橋2和場橋3作業(yè)路徑分別為：

M207?M217?M201?M314?

M316?M220?M210；

M311?M318?M303?M309?

M305?M212.

而在無干擾情況下，場橋2和場橋3的作業(yè)路徑分別為：

M209?M212?M208?M211?

M213?M210；

M317?M320?M314?M316?

M318?M315?M319.

在滿足緊急任務(wù)按時(shí)完成并使得所有任務(wù)完成時(shí)間最短，任務(wù)延遲量最小的情況下，得到如圖12所示的場橋調(diào)度方案，該方案下所有任務(wù)完成最短時(shí)間為213 min.

圖12 有干擾情況下場橋調(diào)度方案Fig.12 YC schedule with interference

4 結(jié)論

本文針對場橋動態(tài)調(diào)度中，由于不確定干擾因素的影響，導(dǎo)致原先的調(diào)度方案發(fā)生變化這一問題進(jìn)行研究，提出滾動窗口策略來解決該問題，當(dāng)突發(fā)因素發(fā)生時(shí)，及時(shí)調(diào)整調(diào)度方案，算例證明，滾動策略能有效解決該問題，由于滾動策略進(jìn)行的是每個滾動窗口中的優(yōu)化，從而來實(shí)現(xiàn)全局的優(yōu)化，這種方案能夠節(jié)約計(jì)算時(shí)間，適用于大規(guī)模的問題.本文采用改進(jìn)的遺傳算法，利用MATLAB來求解場橋調(diào)度模型.

[1] LI W，WU Y，PETERING M E H，et al. Discrete time model and algorithms for container yard crane scheduling [J]. European Journal of Operational Research，2009，198(1): 165-172.

[2] STAHLBOCK R，VOΒ S. Operations research at container terminals: a literature update[J]. OR Spectrum，2008，30(1):1-52.

[3] ZHANG C Q，WAN Y W，LIU J Y, et al. Dynamic crane deploymention container storage yards[J]. Transportation Research Part B，2002，36(6):537-555

[4] RICHARD J, LIN N, ZHANG C Q. A heuristic for dynamic yard crane deployment in a container terminal[J]. IIE Transactions，2003，35: 161-174

[5] HG W C. Crane scheduling in container yards with inter-crane interference[J]. European Journal of Operational Research，2005，164: 64-78

[6] CHANG D F，WEI Y ，JIANG Z H ，et al. Developing a dynamic rolling-horizon decision strategy for yard crane scheduling[J]. Advanced Engineering Informatics，2011，25: 485-494．

[7] 梁承姬，戴開梅. 基于集裝箱任務(wù)組時(shí)間窗的堆場場橋調(diào)度模型建立與求解[J].河南科學(xué)，2013，31(4): 477-483．

[8] 張富生，劉長安. 基于遺傳算法的車間動態(tài)調(diào)度研究[D].山東：山東大學(xué)，2013．

[9] 林志國，王 諾. 基于滾動窗口的集裝箱碼頭泊位動態(tài)調(diào)度研究[D].遼寧：大連海事大學(xué)，2010．

[10] 肖 玲，胡志華. 基于滾動策略的集裝箱碼頭連續(xù)泊位與橋吊集成調(diào)度[J].計(jì)算機(jī)應(yīng)用，2013，33(10)：2969-2973．

[11] HE J L，CHANG D F，WEI J, et al. A hybrid parallel genetic algorithm for yard crane scheduling[J]. Transportation Research Part E，2010，46: 136-155．

[12] 嚴(yán) 偉，宓為建，萇道方，等. 一種基于最佳優(yōu)先搜素算法的集裝箱堆場場橋調(diào)度策略[J].中國工程機(jī)械學(xué)報(bào)，2008，6(1):95-100．

[13] KIM H K，LEE M，WANG H H.Sequencing delivery and receiving operations for yard cranes in port container terminals[J]. International Journal of Production Economics，2003，84(3):283-292．

[14] LI W K，WU Y，PETERING M, et al.A continuous time model for multiple yard crane scheduling with last minute job arrivals[J]. Int J Production Economics，2012，136: 332-343．

[15] 劉文君. Memetic算法研究與工程應(yīng)用[D]. 武漢：華中科技大學(xué)，2007．

Research of the yard crane schedule with uncertain interference that based on the rolling-horizon decision strategy

LIANG Chengji，WANG Dianxue，XU Dehong

(Logistics Research Center，Scientific Research Academy，Shanghai Maritime University，Shanghai 201306)

Currently，the “bottleneck” affecting the efficiency of container port handling was transferred from the berth to the yard. A reasonable yard crane schedule can improve the efficiency of yard work，so the research of yard crane schedule has an important effect on the management of container ports. Based on the uncertain interference factors in the yard crane operation，a dynamic rolling-horizon decision strategy was proposed to deal with the problem that how to reduce the uncertain interference factors and thus improve efficiency of yard crane. A mixed integer programming model was established to minimize the maximum delaying time at blocks and the improved Genetic algorithm was used to solve the model. According to the analysis of examples，this algorithm is useful and the dynamic rolling-horizon decision strategy is effective in scheduling the yard crane under uncertain interference factors．

rolling-horizon decision strategy; uncertain disturb factors; yard crane schedule; improved genetic algorithm

2016-04-22.

國家自然科學(xué)基金項(xiàng)目(71471110,71301101);上海市科委項(xiàng)目(14170501500).

1000-1190(2016)05-0695-09

F512.5

A

*通訊聯(lián)系人. E-mail: wangdianxue519@519.com.