公共泊位系統(tǒng)中通過遺傳算法制定的泊位調(diào)度計(jì)劃

《公共泊位系統(tǒng)中通過遺傳算法制定的泊位調(diào)度計(jì)劃》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、公共泊位系統(tǒng)中通過遺傳算法制定的泊位調(diào)度計(jì)劃簡介：大多數(shù)港口的集裝箱泊位被船舶運(yùn)營商租賃出去，為了讓他們直接參與和負(fù)責(zé)集裝箱的處理過程,從而獲得更高的生產(chǎn)力。然而這種方法適用的情況是有大量船舶掛靠港口，集裝箱作業(yè)量大且穩(wěn)定。如果船舶和集裝箱的數(shù)量不足，就不可能會(huì)節(jié)約成本。在過去的幾年里日本的港口收費(fèi)一貫的高于其他的主要樞紐港口，一部分增加的成本是由于相對(duì)較小的港口貨運(yùn)量卻過多投資的緣故。在上述背景下，,通過引入公共泊位系統(tǒng)來限制泊位數(shù)量是很有意義的。在此系統(tǒng)中的泊位分配，即為到港船只的裝卸作業(yè)分配泊位，在使周

2、轉(zhuǎn)時(shí)間最小化的過程中起重要作用，這是因?yàn)橐粋€(gè)特定的船舶裝卸時(shí)間在每一個(gè)泊位不一定是相同的。雖然公共泊位系統(tǒng)不受大多數(shù)國家的大型集裝箱港口的歡迎,但土地稀缺的港口仍在使用它，如新加坡、香港和釜山等。本文的目的是為解決泊位分配問題開發(fā)一個(gè)遺傳算法(GA)，Imai等人對(duì)待所謂的靜態(tài)泊位分配問(SBAP)如下，給定一組船只在規(guī)劃周期的開始準(zhǔn)備接受服務(wù)，找到一組作業(yè)，來使包括等待接受服務(wù)時(shí)間在內(nèi)的時(shí)間總和最小化。這個(gè)問題可以簡化成一個(gè)經(jīng)典的二維分配問題(或加權(quán)兩偶匹配問題)，可以通過多項(xiàng)式解決。動(dòng)態(tài)泊位分配問題(DB

3、AP)是SBAP的一般化情況，是對(duì)待船舶在規(guī)劃周期的開始后，附帶準(zhǔn)備時(shí)間等待接受服務(wù)。DBAP不知道要解決有界多項(xiàng)式的時(shí)間，因此,為解決DBAP提議采用基于拉格朗日松弛法的啟發(fā)式。DBAP假定每個(gè)泊位每次只服務(wù)一只船，事實(shí)上,它可以服務(wù)多個(gè)船只，只要泊位長度不小于船舶總長度(包括一些限額)。稍后將顯示,這種服務(wù)假設(shè)下的DBAP，可以作為一個(gè)非線性規(guī)劃制定。為了促進(jìn)解決這類DBAP，我們使用遺傳算法GAs。大多數(shù)港口研究將他們的注意力集中在戰(zhàn)略和戰(zhàn)術(shù)問題上。由于大量的集裝箱泊位是由具體的航運(yùn)公司私營的,很少研究

4、是關(guān)于在公共泊位系統(tǒng)進(jìn)行泊位調(diào)度。Lai和Shih出于為使香港HIT碼頭的泊位更有效的使用，對(duì)泊位分配問題提出一些啟發(fā)式算法。盡管我們的問題并非如此，他們的問題假設(shè)先到先得（FCFS）的分配策略,因此他們的解決方案可能不如我們的好。Brown等人視船舶為停在軍港，他們確定使船舶在港總收益最大化的，船到港作業(yè)的最佳集合，軍港的泊位計(jì)劃和商業(yè)港口泊位計(jì)劃有著重要的區(qū)別，前者是尋求適當(dāng)?shù)姆?wù)時(shí)發(fā)生移泊，新到達(dá)的船舶必須分配給一個(gè)已經(jīng)在服務(wù)船舶的泊位。這種處理方法在商港不大可能。考慮到移泊和其他與商港不相關(guān)的因素。從

5、而使軍港的問題不適合商業(yè)港口。Imai等人考慮商業(yè)港口的泊位分配問題，大多數(shù)服務(wù)隊(duì)列一般根據(jù)先到先得（FCFS）原則處理。他們得出結(jié)論，為了得到高效的港口生產(chǎn)力，最理想的船到泊位的任務(wù)分配，應(yīng)該建立一個(gè)不考慮先到先得原則的機(jī)制。然而，這可能會(huì)導(dǎo)致一些船舶對(duì)服務(wù)序列不滿。為了結(jié)合這泊位性能和服務(wù)序列的滿意度兩個(gè)標(biāo)準(zhǔn)來評(píng)估，他們開發(fā)出一個(gè)啟發(fā)式算法，來找出一組不算差的解決方案，使泊位性能最大化以及服務(wù)序列的不滿最小化。但是他們的服務(wù)原則不適用于動(dòng)態(tài)分配。遺傳算法正在越來越多的用于解決棘手的問題，如NP難問題。大多

6、數(shù)的機(jī)器調(diào)度問題屬于這類NP難問題，幾項(xiàng)研究應(yīng)經(jīng)成功地將遺傳算法應(yīng)用于機(jī)器調(diào)度問題。Chan和Imai為多個(gè)船舶靠泊的泊位分配問題，開發(fā)了一個(gè)基于遺傳算法的啟發(fā)式。模型：DBAP做出如下假設(shè)：（a）每條船必須在某一泊位，接受且只接受一次服務(wù)（b）船只必須在一個(gè)滿足該船物理?xiàng)l件（水深和碼頭長度）的泊位接受服務(wù),（c）每條船的裝卸時(shí)間取決于他所在的泊位。i（=1，…I）∈B是一組泊位j（=1，…J）∈V是一組船Cij是j船在i泊位的裝卸時(shí)間Aj是j船到港時(shí)間WDi是泊位水深QLi是i泊位的碼頭長度Dj是j船的吃水

7、深度，包括停泊的安全垂直距離Lj是j船的長度，包括水平安全長度當(dāng)j船在i泊位接受服務(wù)時(shí)Xij=1，否則Xij=0當(dāng)j’船在同一泊位正在接受服務(wù)時(shí)，j船也開始他的服務(wù)時(shí)Yjj’=1，否則Yjj’=0mj是j船開始接受服務(wù)的時(shí)間在DBAP的公式中，決策變量是Xij，Yjj’和mj。公式（1）使是船只造成的總服務(wù)時(shí)間最小化。約束方程（2）保證每條船必須在某一泊位，接受且只接受一次服務(wù)。約束集合（3）保證當(dāng)船舶到達(dá)后肯定會(huì)受到服務(wù)。約束方程（4）保證j船的吃水（包括安全距離）不會(huì)超出分配泊位的水深。約束方程（7）保證

8、j船和j’船的全長（包括安全距離）不超過i泊位的碼頭長度。約束方程（6）和（7）表示的是j船和j’船在同一泊位接受服務(wù)。在這些約束當(dāng)中，mj+ΣCijXij表示j船的離開時(shí)間，而mj’+ΣCij’Xij’表示j’船的離開時(shí)間。因此mj+ΣCijXij-mj’（11）代表j’船的開始服務(wù)時(shí)間與j船的離開時(shí)間的差別，mj’+ΣCij’Xij’-mj（12）代表j船的開始服務(wù)時(shí)間與j’船的離開時(shí)間的差別。