三峽工程兩壩聯(lián)合通航調(diào)度算法研究.pdf

1、三峽—葛洲壩聯(lián)合通航調(diào)度系統(tǒng)是長(zhǎng)江三峽河段上特有的一種內(nèi)河航運(yùn)調(diào)度系統(tǒng)，三峽工程的修建大大改善了長(zhǎng)江中上游航道的通航條件，但不可否認(rèn)的是，隨著長(zhǎng)江中上游航運(yùn)的日益繁忙，三峽大壩和葛洲壩必將成為這一水域的通航瓶頸，“十一五”期間，交通部計(jì)劃投資一百五十億元人民幣實(shí)施的長(zhǎng)江黃金水道建設(shè)中，重點(diǎn)推進(jìn)的六大工程中就包括三峽過(guò)壩運(yùn)輸擴(kuò)能(其他五項(xiàng)工程分別是航道治理、港口建設(shè)、船型標(biāo)準(zhǔn)化、水運(yùn)保障及干支聯(lián)動(dòng))。由于三峽大壩和下游的葛洲壩相距不到40

2、公里(大約為普通船只2-4小時(shí)左右的航程)，兩者構(gòu)成了一個(gè)有機(jī)的整體，因此要充分發(fā)揮該水域的航運(yùn)能力就必須對(duì)兩座大壩的通航設(shè)施(包括三峽大壩的雙線五級(jí)船閘和目前尚未投入使用的升船機(jī)，以及葛洲壩的三線單級(jí)船閘)和所有過(guò)壩船只實(shí)行統(tǒng)一的通航調(diào)度管理，針對(duì)船舶過(guò)壩的聯(lián)合通航調(diào)度是這一管理模式中的主要環(huán)節(jié)，而設(shè)計(jì)穩(wěn)定高效的調(diào)度算法是實(shí)現(xiàn)聯(lián)合通航調(diào)度穩(wěn)定高效的關(guān)鍵。
　　 本文首先通過(guò)借鑒受到加工車間調(diào)度問(wèn)題的研究成果，提出了聯(lián)合通航調(diào)度

3、問(wèn)題的非線性混合整數(shù)規(guī)劃模型，這一模型主要基于聯(lián)合通航調(diào)度問(wèn)題與柔性制造調(diào)度問(wèn)題的相似性，從柔性制造調(diào)度問(wèn)題的混合整數(shù)規(guī)劃模型演化而來(lái)，同時(shí)結(jié)合二維packing模型描述了船舶在閘室中停泊位置的優(yōu)化編排問(wèn)題，該模型是一種強(qiáng)NP-hard復(fù)雜度的組合優(yōu)化問(wèn)題，因此對(duì)于大規(guī)模的航運(yùn)調(diào)度來(lái)說(shuō)，可行時(shí)間內(nèi)的精確優(yōu)化算法是不存在的。靜態(tài)環(huán)境中的優(yōu)化能力是對(duì)調(diào)度算法的基本要求，為了在可行的計(jì)算時(shí)間內(nèi)得到穩(wěn)定有效的優(yōu)化性能，本文提出了一種混合優(yōu)化算法

4、將針對(duì)船舶過(guò)壩時(shí)間表的優(yōu)化計(jì)算轉(zhuǎn)化為針對(duì)船閘閘次時(shí)間表的優(yōu)化計(jì)算。閘次時(shí)間表優(yōu)化模型也是一種混合整數(shù)規(guī)劃模型，我們提出的混合優(yōu)化算法是一種具有啟發(fā)式變換策略的隨機(jī)局域搜索算法和模擬退火算法的合成，其中隨機(jī)局域搜索算法針對(duì)整數(shù)型優(yōu)化變量，而模擬退火算法針對(duì)實(shí)數(shù)型優(yōu)化變量，基于實(shí)際通航數(shù)據(jù)的測(cè)算表明該算法優(yōu)化性能穩(wěn)定，并且計(jì)算速度和優(yōu)化效果能夠滿足實(shí)際應(yīng)用的需要。與上述針對(duì)的是全局靜態(tài)調(diào)度問(wèn)題的混合優(yōu)化算法相比，更具有實(shí)用價(jià)值的是復(fù)雜環(huán)境中

5、的動(dòng)態(tài)調(diào)度算法。在加工制造領(lǐng)域，滾動(dòng)時(shí)域方法(Rolling Horizon Procedure,RHP)在Job Shop問(wèn)題的單機(jī)以及并行多機(jī)系統(tǒng)動(dòng)態(tài)調(diào)度中取得了非常好的效果，本文借鑒這一思路，設(shè)計(jì)了基于閘次時(shí)間表優(yōu)化的聯(lián)合通航調(diào)度滾動(dòng)時(shí)域算法，在滾動(dòng)時(shí)段內(nèi)采用具有啟發(fā)式剪枝策略的分枝定界算法搜索最優(yōu)解。靜態(tài)調(diào)度模型下的測(cè)試結(jié)果表明該算法的全局優(yōu)化能力和計(jì)算速度均優(yōu)于全局混合優(yōu)化算法。而在實(shí)際的動(dòng)態(tài)調(diào)度環(huán)境中，由于系統(tǒng)參數(shù)和船舶航行

6、的隨機(jī)性，滾動(dòng)時(shí)段內(nèi)的短期計(jì)劃往往只有部分能夠準(zhǔn)確執(zhí)行，而當(dāng)實(shí)際環(huán)境與預(yù)測(cè)值相差過(guò)大時(shí)就需要進(jìn)行調(diào)度調(diào)整或者重調(diào)度，與Job Shop中的單機(jī)和并行多機(jī)系統(tǒng)不同的是，聯(lián)合通航調(diào)度系統(tǒng)是一種雙服務(wù)臺(tái)(大壩)的串聯(lián)結(jié)構(gòu)，各服務(wù)臺(tái)面臨的輸入輸出環(huán)境是不同的，往往并不需要同時(shí)進(jìn)行調(diào)度調(diào)整或者重調(diào)度，因此我們?cè)O(shè)計(jì)了一種異步滾動(dòng)時(shí)域調(diào)度策略以提高滾動(dòng)時(shí)域方法的靈活性并降低重調(diào)度的計(jì)算量。最后本文介紹了聯(lián)合通航調(diào)度算法在實(shí)際的航運(yùn)管理系統(tǒng)中的應(yīng)用，現(xiàn)

7、階段調(diào)度算法主要用于長(zhǎng)時(shí)段內(nèi)的調(diào)度計(jì)劃編制問(wèn)題，從更大的時(shí)間跨度來(lái)看，這也是一種滾動(dòng)時(shí)域調(diào)度，然而由于時(shí)域長(zhǎng)度過(guò)大(通常為24小時(shí))，該問(wèn)題以及具有了全局靜態(tài)優(yōu)化的性質(zhì)，同時(shí)在實(shí)際系統(tǒng)中需要考慮的優(yōu)化目標(biāo)更加復(fù)雜，我們采取了利用較短時(shí)段內(nèi)的滾動(dòng)時(shí)域算法得到調(diào)度計(jì)劃初值，然后運(yùn)用全局混合優(yōu)化算法進(jìn)一步改進(jìn)調(diào)度計(jì)劃的方法。目前這一算法已經(jīng)實(shí)際應(yīng)用于長(zhǎng)江三峽通航管理局的“三峽—葛洲壩水利樞紐通航調(diào)度系統(tǒng)”中，并取得了較好的效果，得到了調(diào)度專家