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

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