解決岸橋調(diào)度問題新的數(shù)學模型的高效算法

1、電子信息工程學電子信息工程學院院 AN EFFICIENT ALGORITHM FOR SOLVING A NEWMATHEMATICAL MODEL FOR A QUAY CRANE SCHEDULING PROBLEM IN CONTAINER PORTS 一種解決岸橋調(diào)度數(shù)學模型的高效算法 匯報人：曹星旗電子信息工程學電子信息工程學院院 目錄摘要12問題描述3數(shù)學模型4遺傳算法5總結(jié)電子信息工程學電子信息工程學院院 本文提出了一種新的集裝箱岸橋調(diào)度和分配問題的混合整數(shù)規(guī)劃（MIP）模型，即QCSAP模型。利用傳統(tǒng)的方法和優(yōu)化工具在合理的時間內(nèi)獲得最佳的解決方案是非常困難的。因此，本文提出

2、了一種遺傳算法（GA）來解決現(xiàn)實世界的QCSAP問題。此外，針對小規(guī)模問題所提出的算法比LINGO軟件更有效率。計算結(jié)果表明，該算法對大規(guī)模的QCSAP尤其有效。一.摘要電子信息工程學電子信息工程學院院 二.問題描述 過去的十年中集裝箱在海上運輸中的應(yīng)用增長的十分迅速。集裝箱碼頭作為貨物裝卸的區(qū)域在港口起著至關(guān)重要的作用。集裝箱碼頭的生產(chǎn)能力主要有兩個因素影響（1）Ship operations where containers are discharged from and onto a ship；（2）receiving anddelivery operations where conta

3、iners are transfered to and from outside trucks； 船舶作業(yè)的規(guī)劃過程主要包括泊位規(guī)劃、岸橋調(diào)度規(guī)劃、卸船和裝船規(guī)劃。在泊位規(guī)劃過程中，靠泊時間和位置必須被確定。岸橋調(diào)度規(guī)劃必須為船上每個倍指定岸橋服務(wù)順序和服務(wù)時間，本論文提出的QCSAP模型是在制定船舶作業(yè)規(guī)劃的第二步。電子信息工程學電子信息工程學院院 假設(shè)條件1.對于QCSAP模型,船靠碼頭的位置和船的裝卸工作量是給定的輸入量；2.岸橋起重機在裝卸效率和從一個倍移動速度是相同的；3.每對岸橋的之間的安全距離取決于一個倍的寬度，每個倍在同一時間只能有一臺岸橋工作；4.每只船分為縱向的倍，每個倍容

4、納一排集裝箱，船上所有倍的長度是相同的，船長就是所有倍的長度。三.數(shù)學模型電子信息工程學電子信息工程學院院 三數(shù)學模型電子信息工程學電子信息工程學院院 三數(shù)學模型電子信息工程學電子信息工程學院院 遺傳算法已被廣泛用于在組合優(yōu)化問題，如排序和調(diào)度問題。它是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應(yīng)度大小選擇（selection）個體，并借助于自然遺傳學的遺傳算子（genetic operators）進行組合交叉（cro

5、ssover）和變異（mutation），產(chǎn)生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼（decoding），可以作為問題近似最優(yōu)解。四.遺傳算法電子信息工程學電子信息工程學院院 遺傳算法實現(xiàn)的初始和最重要的一步是問題的表示和染色體的設(shè)計，本文把每個調(diào)度計劃中的工作作為一個染色體上的基因。在每一條船中，第一個基因表示了給船分配的岸橋數(shù)量，每條船上所有的工作都有一串編碼。1.染色體表示及初步解程序電子信息工程學電子信息工程學院院 在本文中我們用雙交叉算子來表示染色體分開的兩部分，第一行基因表示為船的分配的岸橋序列，另一條基

6、因每條船上每個工作的序列。對于第一部分和第二部分我們選擇用算術(shù)交叉和擴展修補交叉。2.遺傳算子設(shè)計電子信息工程學電子信息工程學院院 繁殖過程中親本的選擇十分重要，親本的選擇策略意味著如何選擇當前種群中的染色體，它將會決定下一代的基因。最常用的方法是輪盤選擇法，每個染色體分配的圓盤的大小與染色體的尺寸成正比。在每一次旋轉(zhuǎn)中，圓盤標記部分對應(yīng)的染色體作為親本池。3.親本選擇策略電子信息工程學電子信息工程學院院 我們使用一個半貪婪的策略，接受遺傳算子所產(chǎn)生的后代。在這一策略中，如果其適應(yīng)度低于該策略其親本平均適應(yīng)度，新一代的后代將為被接受。這種策略減少了算法的計算時間，并單調(diào)收斂于最佳的解決方案附近。4.子代接受則略電子信息工程學電子信息工程學院院 我們選擇了兩個標準作為停止規(guī)則：（1）最大迭代代數(shù)（2）當前代對染色體適應(yīng)度的標準偏差。5.停止規(guī)則電子信息工程學電子信息工程學院院 在本文中，我們提出了一種高效的遺傳算法來解決岸橋的調(diào)度問題，對于擴展的岸橋調(diào)度問題提出了一種混合整數(shù)規(guī)劃模型，這是本文的主要研究