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

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

2、了一種遺傳算法（GA）來(lái)解決現(xiàn)實(shí)世界的QCSAP問(wèn)題。此外，針對(duì)小規(guī)模問(wèn)題所提出的算法比LINGO軟件更有效率。計(jì)算結(jié)果表明，該算法對(duì)大規(guī)模的QCSAP尤其有效。一.摘要電子信息工程學(xué)電子信息工程學(xué)院院 二.問(wèn)題描述 過(guò)去的十年中集裝箱在海上運(yùn)輸中的應(yīng)用增長(zhǎng)的十分迅速。集裝箱碼頭作為貨物裝卸的區(qū)域在港口起著至關(guān)重要的作用。集裝箱碼頭的生產(chǎn)能力主要有兩個(gè)因素影響（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ò)程主要包括泊位規(guī)劃、岸橋調(diào)度規(guī)劃、卸船和裝船規(guī)劃。在泊位規(guī)劃過(guò)程中，靠泊時(shí)間和位置必須被確定。岸橋調(diào)度規(guī)劃必須為船上每個(gè)倍指定岸橋服務(wù)順序和服務(wù)時(shí)間，本論文提出的QCSAP模型是在制定船舶作業(yè)規(guī)劃的第二步。電子信息工程學(xué)電子信息工程學(xué)院院 假設(shè)條件1.對(duì)于QCSAP模型,船靠碼頭的位置和船的裝卸工作量是給定的輸入量；2.岸橋起重機(jī)在裝卸效率和從一個(gè)倍移動(dòng)速度是相同的；3.每對(duì)岸橋的之間的安全距離取決于一個(gè)倍的寬度，每個(gè)倍在同一時(shí)間只能有一臺(tái)岸橋工作；4.每只船分為縱向的倍，每個(gè)倍容

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

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

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