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

公共泊位系統(tǒng)中通過遺傳算法制定的泊位調(diào)度計(jì)劃簡介： 大多數(shù)港口的集裝箱泊位被船舶運(yùn)營商租賃出去，為了讓他們直接參與和負(fù)責(zé)集裝箱的處理過程,從而獲得更高的生產(chǎn)力。然而這種方法適用的情況是有大量船舶掛靠港口，集裝箱作業(yè)量大且穩(wěn)定。如果船舶和集裝箱的數(shù)量不足，就不可能會節(jié)約成本。在過去的幾年里日本的港口收費(fèi)一貫的高于其他的主要樞紐港口，一部分增加的成本是由于相對較小的港口貨運(yùn)量卻過多投資的緣故。在上述背景下，,通過引入公共泊位系統(tǒng)來限制泊位數(shù)量是很有意義的。在此系統(tǒng)中的泊位分配，即為到港船只的裝卸作業(yè)分配泊位，在使周轉(zhuǎn)時(shí)間最小化的過程中起重要作用，這是因?yàn)橐粋€(gè)特定的船舶裝卸時(shí)間在每一個(gè)泊位不一定是相同的。雖然公共泊位系統(tǒng)不受大多數(shù)國家的大型集裝箱港口的歡迎,但土地稀缺的港口仍在使用它，如新加坡、香港和釜山等。 本文的目的是為解決泊位分配問題開發(fā)一個(gè)遺傳算法(GA)，Imai等人對待所謂的靜態(tài)泊位分配問(SBAP) 如下，給定一組船只在規(guī)劃周期的開始準(zhǔn)備接受服務(wù)，找到一組作業(yè)，來使包括等待接受服務(wù)時(shí)間在內(nèi)的時(shí)間總和最小化。這個(gè)問題可以簡化成一個(gè)經(jīng)典的二維分配問題(或加權(quán)兩偶匹配問題)，可以通過多項(xiàng)式解決。動態(tài)泊位分配問題(DBAP)是SBAP的一般化情況，是對待船舶在規(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)公司私營的,很少研究是關(guān)于在公共泊位系統(tǒng)進(jìn)行泊位調(diào)度。 Lai和Shih出于為使香港HIT碼頭的泊位更有效的使用，對泊位分配問題提出一些啟發(fā)式算法。盡管我們的問題并非如此，他們的問題假設(shè)先到先得（FCFS）的分配策略,因此他們的解決方案可能不如我們的好。 Brown等人視船舶為停在軍港，他們確定使船舶在港總收益最大化的，船到港作業(yè)的最佳集合，軍港的泊位計(jì)劃和商業(yè)港口泊位計(jì)劃有著重要的區(qū)別，前者是尋求適當(dāng)?shù)姆?wù)時(shí)發(fā)生移泊，新到達(dá)的船舶必須分配給一個(gè)已經(jīng)在服務(wù)船舶的泊位。這種處理方法在商港不大可能。考慮到移泊和其他與商港不相關(guān)的因素。從而使軍港的問題不適合商業(yè)港口。 Imai等人考慮商業(yè)港口的泊位分配問題，大多數(shù)服務(wù)隊(duì)列一般根據(jù)先到先得（FCFS）原則處理。他們得出結(jié)論，為了得到高效的港口生產(chǎn)力，最理想的船到泊位的任務(wù)分配，應(yīng)該建立一個(gè)不考慮先到先得原則的機(jī)制。然而，這可能會導(dǎo)致一些船舶對服務(wù)序列不滿。為了結(jié)合這泊位性能和服務(wù)序列的滿意度兩個(gè)標(biāo)準(zhǔn)來評估，他們開發(fā)出一個(gè)啟發(fā)式算法，來找出一組不算差的解決方案，使泊位性能最大化以及服務(wù)序列的不滿最小化。但是他們的服務(wù)原則不適用于動態(tài)分配。 遺傳算法正在越來越多的用于解決棘手的問題，如NP難問題。大多數(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船的吃水深度，包括停泊的安全垂直距離 Lj是j船的長度，包括水平安全長度當(dāng)j船在i泊位接受服務(wù)時(shí)Xij=1，否則Xij=0 當(dāng)j船在同一泊位正在接受服務(wù)時(shí)，j船也開始他的服務(wù)時(shí)Yjj=1，否則Yjj=0 mj是j船開始接受服務(wù)的時(shí)間在DBAP的公式中，決策變量是Xij，Yjj和mj。公式（1）使是船只造成的總服務(wù)時(shí)間最小化。約束方程（2）保證每條船必須在某一泊位，接受且只接受一次服務(wù)。約束集合（3）保證當(dāng)船舶到達(dá)后肯定會受到服務(wù)。約束方程（4）保證j船的吃水（包括安全距離）不會超出分配泊位的水深。約束方程（7）保證j船和j船的全長（包括安全距離）不超過i泊位的碼頭長度。約束方程（6）和（7）表示的是j船和j船在同一泊位接受服務(wù)。在這些約束當(dāng)中，mj+CijXij表示j船的離開時(shí)間，而mj+CijXij表示j船的離開時(shí)間。因此mj+CijXij- mj（11）代表j船的開始服務(wù)時(shí)間與j船的離開時(shí)間的差別， mj+CijXij- mj（12）代表j船的開始服務(wù)時(shí)間與j船的離開時(shí)間的差別。因此，如果j船和j船在同一特定港口有重疊部分，方程（11）（12）都是正值，否則其中一個(gè)為負(fù)值。它的合理性描述如下：如果j船在j船開始服務(wù)前已經(jīng)結(jié)束服務(wù)了，方程（11）為負(fù)，方程（12）為正。如果他們以相反的順序提供服務(wù)，那方程（11）為正，方程（12）為負(fù)。因此如果Yjj=1，那么約束方程（6）的左半部分0，約束方程（7）的左半部分=0。否則約束方程（6）的左半部分=0，約束方程（7）的左半部分0。 過程： T表示在一個(gè)子問題里面分配給泊位的船舶的數(shù)量。k表示在泊位服務(wù)序列的位置， S(k)表示在第k個(gè)為止接受服務(wù)的船舶。L(S(k)表示S(k)的長度。假設(shè)在某一作業(yè)時(shí)間有pl艘serviced ship，然后最后一艘離開的船用V(1)表示，剩余其他的serviced ship按離開的相反的順序記為V(2)、V(3)V(pl)。（即倒數(shù)第二艘離開的為V(2)以此類推）。需注意,如果沒有觀察到幾項(xiàng)服務(wù)同時(shí)發(fā)生,將pl設(shè)置為1。 Step 1.讓k=1 Step 2.如果kT，終止。否則讓i=1，并且在子問題和上代子問題中為S(k)找到serviced ship。在serviced ship中選擇最后離開的船表示為V(1)。 Step 3.如果所有的serviced ship都檢查完畢，就執(zhí)行下面過程： 讓pl=i，m=1.將V(i)（i=1，pl）帶入上面提到的與離開時(shí)間相逆的序列。 跳轉(zhuǎn)到Step 5. 否則，從serviced ship中隨意地選出一艘，跳轉(zhuǎn)到Step 4. Step 4.選出來的船定為j船，如果為j船和V(1)的服務(wù)重疊了，讓i=i+1，V(i)=j，跳回Step 3. Step 5.如果mpl，讓S(k)到達(dá)后就開始它的服務(wù)，并且跳到Step 9.Step 6.如果 泊位長度（即如果，服務(wù)重疊的船舶和S(k)船的總長度不超過泊位長度），跳轉(zhuǎn)到Step 8.否則設(shè)置clock