考慮岸橋等待時(shí)間的碼頭作業(yè)調(diào)度優(yōu)化模型

考慮岸橋等待時(shí)間的碼頭作業(yè)調(diào)度優(yōu)化模型

目前，港口市場(chǎng)的競(jìng)爭(zhēng)日益激烈。提高港口競(jìng)爭(zhēng)力已成為港口運(yùn)營(yíng)商面臨的主要問(wèn)題。而在影響港口競(jìng)爭(zhēng)力的諸多因素中,船舶裝卸作業(yè)的最大完工時(shí)間,是最為關(guān)鍵的一個(gè)因素,因?yàn)樵撝笜?biāo)直接關(guān)系到船舶能否盡早離港。在實(shí)際操作中,岸橋作業(yè)調(diào)度(QuayCraneScheduling,QCS)作為港口裝卸作業(yè)的重要組成部分,對(duì)裝卸作業(yè)最大完工時(shí)間起著決定性作用。因此,優(yōu)化岸橋作業(yè)調(diào)度問(wèn)題,對(duì)提高船舶裝卸作業(yè)效率和提升港口競(jìng)爭(zhēng)力具有十分重要的意義。岸橋作業(yè)調(diào)度旨在將船舶裝卸作業(yè)任務(wù)合理分配給岸橋,并確定每臺(tái)岸橋上的作業(yè)序列及作業(yè)時(shí)間,從而達(dá)到船舶裝卸時(shí)間最短的目標(biāo)。現(xiàn)有的研究文獻(xiàn)中,Lim等考慮了岸橋干擾約束(碰撞與穿越),建立了岸橋作業(yè)總產(chǎn)出最大化模型,并通過(guò)動(dòng)態(tài)規(guī)劃、概率禁忌搜索與啟發(fā)式算法求解;KIM等將同一貝位的裝卸作業(yè)劃分為多個(gè)containergroup,視每個(gè)containergroup為作業(yè)任務(wù),考慮到各任務(wù)間的優(yōu)先及干擾關(guān)系,以最小化船舶作業(yè)最大完工時(shí)間及各岸橋完工總時(shí)間為目標(biāo)建立了模型,并運(yùn)用分枝定界法、貪婪隨機(jī)適應(yīng)性搜索算法進(jìn)行求解;Lim等將岸橋作業(yè)調(diào)度問(wèn)題視為平行機(jī)調(diào)度問(wèn)題,以最小化最大完工時(shí)間為目標(biāo)建立了模型,對(duì)大規(guī)模問(wèn)題采用了模擬退火算法求解;Lee等證明了岸橋作業(yè)調(diào)度問(wèn)題是NP完全問(wèn)題,建立了最小化最大完工時(shí)間模型,并通過(guò)遺傳算法進(jìn)行求解,目的是優(yōu)化岸橋作業(yè)的艙位順序;Bierwirth等彌補(bǔ)了文獻(xiàn)中關(guān)于任務(wù)干擾約束的不足,建立了新的整數(shù)規(guī)劃模型;曾慶成等建立了最小化最大完工時(shí)間模型,并用貪婪隨機(jī)適應(yīng)性搜索方法對(duì)遺傳算法進(jìn)行了改進(jìn),提高了求解效率;韓笑樂(lè)等基于混合裝卸模式建立了最小化最大完工時(shí)間模型,并采用啟發(fā)式算法進(jìn)行求解;李晨等對(duì)具有岸橋干擾約束(碰撞與穿越)及甲板約束的混合裝卸岸橋作業(yè)調(diào)度問(wèn)題進(jìn)行了分析,并提出了能均勻化岸橋負(fù)荷的遺傳算法。綜觀上述研究,在目標(biāo)函數(shù)方面,多以最小化最大完工時(shí)間為主,而忽略了岸橋等待時(shí)間對(duì)岸橋作業(yè)調(diào)度的影響。本文旨在研究最小化最大完工時(shí)間與岸橋等待時(shí)間雙目標(biāo)優(yōu)化下的岸橋作業(yè)調(diào)度問(wèn)題,同時(shí)考慮岸橋不可穿越與安全距離約束。1最大1個(gè)岸橋的作業(yè)調(diào)度當(dāng)集裝箱船舶?？恐链a頭后,岸橋即開(kāi)始對(duì)船舶進(jìn)行作業(yè)。由于各岸橋共用同一根固定導(dǎo)軌,且只能沿導(dǎo)軌橫向移動(dòng),因此各岸橋的相對(duì)位置關(guān)系不能發(fā)生改變,即岸橋不可相互穿越;另外,考慮到安全因素,岸橋之間必須留有一定的安全距離,以防止作業(yè)過(guò)程中發(fā)生碰撞。在實(shí)際操作中,同一貝位上的裝卸任務(wù)只能由1臺(tái)岸橋作業(yè),在該岸橋完成相應(yīng)貝位的作業(yè)后才移至下一貝位。一個(gè)貝位的作業(yè)時(shí)間與該貝位的裝卸箱量有關(guān),通常情況下,裝卸箱量為40箱左右的貝位需要的作業(yè)時(shí)間在1h左右,而岸橋在相鄰2個(gè)貝位的移動(dòng)時(shí)間不會(huì)超過(guò)1min。岸橋作業(yè)調(diào)度旨在將裝卸作業(yè)任務(wù)合理分配給岸橋,并確定每臺(tái)岸橋上的作業(yè)序列及作業(yè)時(shí)間,從而達(dá)到既定目標(biāo)。在已有文獻(xiàn)研究中,該既定目標(biāo)多數(shù)情況下設(shè)定為最小化船舶裝卸作業(yè)的最大完工時(shí)間,以達(dá)到船舶盡早離泊的目的,但僅將最大完工時(shí)間作為目標(biāo)衡量存在一定的局限性,因?yàn)槠鋬H反映了單船裝卸效率,而忽略了多船舶同時(shí)作業(yè)時(shí)裝卸效率的提高。以圖1為例,某船有5個(gè)貝位需要裝卸,所需的作業(yè)時(shí)間(min)p(1,2,3,4,5)=(10,20,40,20,15),分配2臺(tái)岸橋至該船舶,2臺(tái)岸橋的最早可用時(shí)間均為0時(shí)刻,且為防止碰撞,岸橋間需間隔1個(gè)貝位的安全作業(yè)距離。圖1給出了2種不同的調(diào)度方案,2個(gè)方案的最大完工時(shí)間均為70min,以已有文獻(xiàn)的單目標(biāo)標(biāo)準(zhǔn)對(duì)其進(jìn)行衡量,兩者是等價(jià)的,且均為最優(yōu)化方案;但明顯地,圖1(b)方案中,岸橋2需要等待25min,這大大降低岸橋2的利用率,并對(duì)碼頭整體運(yùn)作效率產(chǎn)生不利影響。在碼頭現(xiàn)場(chǎng)裝卸作業(yè)中,如果作業(yè)船舶A的某岸橋提前完成了工作任務(wù),該岸橋通常會(huì)被指派至鄰近船舶B,以支援船舶B的裝卸作業(yè),盡量縮短所有船舶在港總時(shí)間,提高泊位利用率,這一現(xiàn)象在集裝箱業(yè)務(wù)繁忙的大港是普遍存在的,如上海港。顯然,從現(xiàn)場(chǎng)操作角度看,圖1(a)方案更能發(fā)揮岸橋相互支援的作用。由此可見(jiàn),僅以最小化最大完工時(shí)間為標(biāo)準(zhǔn)對(duì)岸橋作業(yè)調(diào)度進(jìn)行衡量,存在一定的缺陷,忽略了岸橋在多船舶之間進(jìn)行相互支援這一現(xiàn)實(shí)情況,有必要對(duì)其進(jìn)行改進(jìn)。本文引入岸橋等待時(shí)間這一目標(biāo),旨在研究具有最小化最大完工時(shí)間與岸橋等待時(shí)間雙目標(biāo)的岸橋作業(yè)調(diào)度問(wèn)題(QuayCraneSchedulingProblemwithMakespanandWaitingTime,QCSPMWT),目的在于最小化最大完工時(shí)間的同時(shí),盡量減少岸橋等待時(shí)間,有利于岸橋更好地支援鄰近船舶作業(yè),從而提高碼頭整體運(yùn)作效率,并提升港口的競(jìng)爭(zhēng)力。2岸橋調(diào)度優(yōu)化算法假設(shè)所分配的岸橋數(shù)量及最早可用時(shí)間均為已知的,各岸橋作業(yè)能力之間沒(méi)有差別,集裝箱船舶劃分為若干貝位,貝位與岸橋均沿同一方向進(jìn)行編號(hào),有關(guān)QCSPMWT的其他假設(shè)如下:假設(shè)1各岸橋在同一導(dǎo)軌上,因此不能相互穿越;同時(shí),為保證作業(yè)安全,相鄰的岸橋間需保持一定的距離。假設(shè)2同一貝位的作業(yè)只能由1臺(tái)岸橋完成,且只有完成該貝位的作業(yè)后,岸橋才能移至下一貝位。假設(shè)3與裝卸作業(yè)時(shí)間相比,岸橋在貝位間的移動(dòng)時(shí)間較小,因此予以忽略。定義Q表示岸橋集合,B表示集裝箱船需要裝卸的貝位集合,pi為岸橋裝卸貝位i(i∈B)的作業(yè)時(shí)間,M為足夠大的正數(shù),Eq為在同一臺(tái)岸橋q上裝卸的貝位的集合,鄰近的2臺(tái)岸橋至少保持h個(gè)貝位的安全作業(yè)距離。決策變量如下:xi,q—1,貝位i是由岸橋q裝卸的;0,其他Cmax—所有貝位的最大完工時(shí)間(makespan)yi,j,q—1,貝位i、j均由同一臺(tái)岸橋q裝卸;0,其他zi,j,q—1,岸橋q裝卸的順序?yàn)樽鳂I(yè)i在j之前(連續(xù)的);0,其他fi,q—1,貝位i是岸橋q所操作的第1項(xiàng)作業(yè);0,其他vi,j—1,貝位j的開(kāi)始作業(yè)時(shí)間不早于貝位i的完成時(shí)間;0,其他本文設(shè)定的優(yōu)化目標(biāo)為最小化岸橋調(diào)度的makespan(Cmax)與總等待時(shí)間W?？紤]到碼頭現(xiàn)場(chǎng)調(diào)度中,到港船舶較多,裝卸作業(yè)又涉及多層次的協(xié)調(diào),更加需要一個(gè)可以直接采用的調(diào)度方案,而非一個(gè)龐大的非支配解集合;同時(shí),鑒于這2個(gè)目標(biāo)又具有相同的單位量綱(可用時(shí)間單位表示),因此為其設(shè)定相應(yīng)權(quán)重λ1、λ2,將其轉(zhuǎn)化為如下目標(biāo)函數(shù):式中,約束(2)對(duì)Cmax作出了定義。約束(3)對(duì)岸橋等待總時(shí)間做出了定義,由兩部分組成:(1)為各岸橋第1項(xiàng)作業(yè)所在貝位的開(kāi)始作業(yè)時(shí)間與岸橋最早可用時(shí)間(0時(shí)刻)之差的總和,即各岸橋第1項(xiàng)作業(yè)的等待時(shí)間;(2)為各岸橋后續(xù)作業(yè)所在貝位的開(kāi)始作業(yè)時(shí)間與其連續(xù)的前序作業(yè)完成時(shí)間之差的總和,即各岸橋后續(xù)作業(yè)等待時(shí)間之和。約束(4)保證每個(gè)貝位的開(kāi)始作業(yè)時(shí)間都在0時(shí)刻之后。約束(5)保證每個(gè)貝位都只能由1臺(tái)岸橋作業(yè)。約束(6)保證每臺(tái)岸橋有且僅有1個(gè)初始操作的貝位。約束(7)保證1個(gè)貝位最多只能是1個(gè)岸橋的初始操作貝位。約束(8)保證對(duì)同一岸橋作業(yè)序列中的2個(gè)連續(xù)任務(wù),后一任務(wù)的開(kāi)始作業(yè)時(shí)間應(yīng)大于前一任務(wù)的完成時(shí)間。約束(9)與(10)給出了xi,q與yi,j,q的關(guān)系,當(dāng)xi,q=xj,q=1時(shí),yi,j,q=yj,i,q=1。約束(11)與(12)保證任意1個(gè)貝位最多有1個(gè)連續(xù)的前序作業(yè)和1個(gè)連續(xù)的后續(xù)作業(yè)。約束(13)保證每臺(tái)岸橋上的作業(yè)按照既定的次序進(jìn)行。約束(14)為岸橋干擾約束,即當(dāng)貝位i、j在作業(yè)時(shí)間段上有重疊時(shí),對(duì)應(yīng)的作業(yè)岸橋不能相互穿越。當(dāng)貝位i、j(i<j)在作業(yè)時(shí)間段上有重疊時(shí),vi,j+vj,i=0,因假設(shè)岸橋編號(hào)與貝位編號(hào)均沿同一方向由小到大,如果岸橋q作業(yè)貝位i,岸橋k作業(yè)貝位j,則q+1≤k,即岸橋不可相互穿越作業(yè)。約束(15)為岸橋安全距離約束,當(dāng)貝位i、j(i<j)在作業(yè)時(shí)間段上有重疊時(shí),vi,j+vj,i=0,因假設(shè)岸橋編號(hào)與貝位編號(hào)均沿同一方向由小到大,如果岸橋q作業(yè)貝位i,岸橋k作業(yè)貝位j,則i+h<j,即有時(shí)間重疊作業(yè)的2臺(tái)岸橋至少保持h個(gè)貝位的安全作業(yè)距離。約束(16)對(duì)目標(biāo)函數(shù)的權(quán)重做出規(guī)定,因最大完工時(shí)間更重要,故λ1>λ2。3遺傳計(jì)算方法3.1開(kāi)始裝卸與時(shí)間在遺傳算法中,將岸橋作業(yè)調(diào)度分為2個(gè)子問(wèn)題:(1)貝位分割與排列,將貝位在岸橋之間進(jìn)行分配,并決定每臺(tái)岸橋的作業(yè)序列;(2)貝位作業(yè)時(shí)間,決定該序列下每一貝位的開(kāi)始裝卸與完工時(shí)間。其中,前一問(wèn)題可在染色體編碼中考慮,而后一問(wèn)題則會(huì)在適應(yīng)值函數(shù)中考慮。本文采用十進(jìn)制法進(jìn)行編碼,每條染色體代表模型的1個(gè)解,圖2為1個(gè)有10個(gè)貝位,2臺(tái)岸橋調(diào)度方案的染色體編碼,0代表不同岸橋間的間隔符。染色體編碼的對(duì)應(yīng)解已經(jīng)考慮了約束條件(5)~(7)、(9)~(13)和(17),每個(gè)滿足這些約束條件的解都能找到一個(gè)染色體個(gè)體編碼與之對(duì)應(yīng)。約束條件(2)~(4)、(8)、(14)~(16)將在適應(yīng)度函數(shù)計(jì)算中得到體現(xiàn)。3.2遺傳算法染色體編碼染色體編碼方式的不同,會(huì)對(duì)遺傳算法的搜索空間造成一定影響,進(jìn)而影響算法的效率與解的穩(wěn)定性。在設(shè)計(jì)遺傳算法時(shí),有必要對(duì)算法的搜索空間進(jìn)行討論。定理1在約束條件(5)~(7)、(9)~(13)和(17)的限制下,上述遺傳算法的搜索空間大小為Pbb×Cb-1q-1,其中,b、q分別代表貝位數(shù)量與岸橋數(shù)量。證明該遺傳算法染色體編碼過(guò)程相當(dāng)于首先將b個(gè)貝位數(shù)進(jìn)行全排列,有Pbb種排法;然后在某全排列中的b-1個(gè)空檔中插入q-1個(gè)0,這樣就有Cb-1q-1種排法。因此,該遺傳算法的搜索空間大小為Pbb×Cb-1q-1。證畢鑒于算法的搜索空間較大,采用隨機(jī)生成初始種群的方法,增大初始種群的個(gè)體多樣性,以盡可能增加遺傳算法的全局搜索能力,避免陷入局部最優(yōu)。同時(shí)考慮約束條件(5)~(7)、(9)~(13)和(17),避免產(chǎn)生不可行解。在算法運(yùn)行初期,經(jīng)常會(huì)產(chǎn)生一些適應(yīng)度超常(如很大)的個(gè)體,從而控制選擇過(guò)程,致使算法收斂于局部最優(yōu)解。為避免這種早期收斂現(xiàn)象的發(fā)生,本文采用基于排序的適應(yīng)度計(jì)算,首先計(jì)算出種群中每個(gè)個(gè)體的目標(biāo)函數(shù)值,然后將其按升序排列,目標(biāo)函數(shù)值最小的排第1位,最大的排第N(N為種群規(guī)模)位,則第i位置個(gè)體的適應(yīng)度為式(18)即為適應(yīng)度函數(shù),其有效地控制了超常個(gè)體的復(fù)制概率,維持了種群多樣性。在選擇過(guò)程中,則采用輪盤(pán)賭的選擇機(jī)制。3.4無(wú)重復(fù)基因順序填入位置針對(duì)模型的特點(diǎn),本文采用順序交叉法,如圖3所示。首先,隨機(jī)地選擇2個(gè)切點(diǎn)X、Y,然后交換中間部分,接著從第2個(gè)切點(diǎn)Y后第1個(gè)基因起列出原順序,去掉已有基因,最后從第2個(gè)切點(diǎn)Y后第1個(gè)位置起,將獲得的無(wú)重復(fù)基因順序填入。通過(guò)染色體變異,改變貝位的岸橋分配,本文采用換位變異,隨機(jī)地選取不同岸橋作業(yè)序列中的2個(gè)基因,交換基因如圖4所示。4求解參數(shù)的算法本文以下數(shù)據(jù)中,岸橋裝卸作業(yè)能力均為1箱/min,岸橋最早可用時(shí)間均為0時(shí)刻。遺傳算法求解參數(shù):種群大小Pop=50,遺傳迭代次數(shù)G=200,交叉概率Pc=0.8和變異概率Pm=0.1。實(shí)驗(yàn)在IntelPentiumDual-CoreT20801.73GHz的處理器,1GB內(nèi)存的PC上進(jìn)行,采用MATLAB7.0編程實(shí)現(xiàn)。4.1下界面為評(píng)價(jià)遺傳算法的質(zhì)量,有必要對(duì)問(wèn)題的下界進(jìn)行分析。定理2在釋放模型中岸橋不可穿越約束與安全距離約束后,問(wèn)題的一個(gè)下界為式中:q為岸橋數(shù)量;B為貝位集合;pi為第i貝位的作業(yè)時(shí)間;λ1為權(quán)重。證明船舶裝卸的總作業(yè)時(shí)間包括各個(gè)貝的作業(yè)時(shí)間之和,及所有岸橋的等待時(shí)間,現(xiàn)假定各岸橋不存在等待現(xiàn)象,即W=0,則總作業(yè)時(shí)間為因岸橋數(shù)量為q,故整個(gè)系統(tǒng)的目標(biāo)函數(shù)值必然大于等于證畢此時(shí),遺傳算法所求得的優(yōu)化解的質(zhì)量為4.2調(diào)整算例2:雙目標(biāo)qcsp該小節(jié)通過(guò)2個(gè)算例來(lái)測(cè)試模型與算法的有效性。其中,算例1數(shù)據(jù)規(guī)模較小,而算例2數(shù)據(jù)規(guī)模較大。算例1本算例數(shù)據(jù)來(lái)自文獻(xiàn)中的示例,經(jīng)本文模型與算法求解,算法運(yùn)行10次,取其中最優(yōu)的結(jié)果。在該最優(yōu)實(shí)驗(yàn)中,程序迭代至60次時(shí),目標(biāo)函數(shù)值變得穩(wěn)定并趨于收斂,程序運(yùn)行過(guò)程耗時(shí)7.57s?？紤]到文獻(xiàn)與本文求解的結(jié)果中,岸橋等待時(shí)間均為0,同時(shí)也為了便于更直觀地與文獻(xiàn)中數(shù)據(jù)進(jìn)行對(duì)比,將相關(guān)數(shù)據(jù)進(jìn)行調(diào)整:(1)文獻(xiàn)中未考慮岸橋安全距離約束,本算例也釋放該約束;(2)文獻(xiàn)中僅考慮最大完工時(shí)間,本算例也做相應(yīng)設(shè)定,λ1=1,λ2=0。對(duì)比結(jié)果如表1所示。算例2本算例給出20個(gè)貝位,分配4臺(tái)岸橋進(jìn)行作業(yè),相鄰2臺(tái)岸橋間至少保持2個(gè)貝位的安全作業(yè)距離,即h=2,設(shè)定λ1=0.8,λ2=0.2,其他參數(shù)如前所述,貝位裝卸量如表2所示。由定理1可知,該算例的算法搜索空間為2.3575E+21,在上述參數(shù)設(shè)置下,通過(guò)MATLAB程序設(shè)計(jì)遺傳算法求解該算例,程序運(yùn)行10次,取其中最優(yōu)的結(jié)果。在該最優(yōu)實(shí)驗(yàn)中,目標(biāo)函數(shù)隨遺傳算法迭代次數(shù)增加的變化趨勢(shì)如圖5所示,當(dāng)算法迭代次數(shù)達(dá)到105次時(shí),目標(biāo)函數(shù)值變得穩(wěn)定并趨于收斂,程序運(yùn)行過(guò)程耗時(shí)15.78s,求解結(jié)果如表3所示;同時(shí),為與僅考慮makespan的單目標(biāo)模型對(duì)比,設(shè)定λ1=1,λ2=0,求解結(jié)果如表4所示。顯然,與單目標(biāo)QCSP相比,雙目標(biāo)QCSPMWT在最大完工時(shí)間上稍遜于單目標(biāo),但兩者差距不大,僅相差了2min;而雙目標(biāo)優(yōu)化在控制岸橋等待時(shí)間方面卻具有明顯優(yōu)勢(shì),岸橋等待時(shí)間僅有15min,比單目標(biāo)優(yōu)化減少了29min,優(yōu)化效果十分顯著。同時(shí),經(jīng)QCSPMWT優(yōu)化后,岸橋4的完工時(shí)間從148min降低到116min,從而能夠更好地支援其他船舶的裝卸作業(yè)。4.3不同目標(biāo)的岸橋作業(yè)調(diào)度模型及實(shí)驗(yàn)結(jié)果該小節(jié)通過(guò)大量的數(shù)據(jù)實(shí)驗(yàn),將本文所建立的雙目標(biāo)岸橋作業(yè)調(diào)度模型QCSPMWT(Cmax,W)與已有研究中單目標(biāo)岸橋作業(yè)調(diào)度模型QCSP(Cmax)作以對(duì)比研究。假設(shè)有50個(gè)貝,岸橋數(shù)量q分別為3,4,5臺(tái),3000~6000個(gè)集裝箱,為避免人為設(shè)置因素造成的偏差,每個(gè)貝位的集裝箱量bi從中隨機(jī)產(chǎn)生,且根據(jù)不同情形做如下調(diào)整:情形1隨機(jī)產(chǎn)生的各貝位集裝箱量總和大于設(shè)定的總集裝箱量(如3000),則(1)每個(gè)貝位的集裝箱量平均減少不大于的最大整數(shù)個(gè)集裝箱;(2)產(chǎn)生新的bi后,箱量最多的貝位再減少個(gè)集裝箱。情形2機(jī)產(chǎn)生的各貝位集裝箱量總和小于設(shè)定的的集裝箱量(如3000),則(1)每個(gè)貝位的集裝箱量平均增加不大于的最大整數(shù)個(gè)集裝箱;(2)產(chǎn)生新的bi后,箱量最少的貝位再增加個(gè)集裝箱。情形3隨機(jī)產(chǎn)生的各貝位集裝箱量總和等于設(shè)定的總集裝箱量(如3000),則不做調(diào)整。顯然,隨著裝卸總量從3000逐漸增加至6000,各貝位的平均集裝箱量也隨之增加。同時(shí),每組實(shí)驗(yàn)中,單目標(biāo)QCSP(λ1=1,λ2=0)與雙目標(biāo)QCSPMWT(λ1=0.8,λ2=0.2)各進(jìn)行10次實(shí)驗(yàn)并取其平均值。為了便于兩者更好地進(jìn)行對(duì)比,對(duì)于單目標(biāo)QCSP,也計(jì)算出其實(shí)際發(fā)生的岸橋等待時(shí)間,