基于智能優(yōu)化的乘務(wù)調(diào)度與輪班問題研究.pdf

1、隨著我國城市化和機(jī)動(dòng)化進(jìn)程迅猛發(fā)展，道路擁堵等問題日益嚴(yán)重，城市交通面臨嚴(yán)峻挑戰(zhàn)，優(yōu)先發(fā)展公共交通勢在必行，如何建設(shè)和管理現(xiàn)代化的公共交通系統(tǒng)已成為我國經(jīng)濟(jì)社會(huì)發(fā)展中亟待解決的重大理論和現(xiàn)實(shí)問題。在公共交通規(guī)劃與運(yùn)營中，乘務(wù)調(diào)度與輪班問題是關(guān)鍵問題，決定了乘務(wù)員的工作方案，有效方案可以提高公共交通運(yùn)營效率，降低運(yùn)營成本，保障乘務(wù)員真正享受國家勞動(dòng)法賦予的權(quán)益。它包含兩個(gè)順序執(zhí)行的子問題：乘務(wù)調(diào)度問題和乘務(wù)輪班問題，其中前者是后者的基礎(chǔ)，

2、它們是 NP難問題，其復(fù)雜性主要在于大規(guī)模、多目標(biāo)、特別是有一系列復(fù)雜多樣的勞動(dòng)法規(guī)約束。因此，研制高效的求解算法具有十分重要的現(xiàn)實(shí)意義和理論意義。目前，智能優(yōu)化方法是主要求解方法類別之一，但是問題的高度復(fù)雜性使得對該類算法的研究仍有很大發(fā)展空間，其中，深刻理解問題的領(lǐng)域知識(shí)并將其融入算法設(shè)計(jì)中是算法設(shè)計(jì)的關(guān)鍵和難點(diǎn)，需要深入研究。此外，乘務(wù)調(diào)度問題中的班次評價(jià)是一個(gè)復(fù)雜多屬性決策問題，是很多乘務(wù)調(diào)度方法的基礎(chǔ)，然而現(xiàn)有的多屬性決策班次

3、評價(jià)方法研究很少。
　　針對以上問題，本文首先從不同角度研制了四種乘務(wù)調(diào)度方法，其中，研制了兩種多屬性決策班次評價(jià)方法，隨后研制了兩種多目標(biāo)乘務(wù)輪班方法，具體如下：
　　提出了一種自適應(yīng)演化乘務(wù)調(diào)度方法，它定義了一個(gè)新的染色體表示方法，具有直觀、短小，允許表達(dá)非可行乘務(wù)方案的特點(diǎn)，其初始長度是專門設(shè)計(jì)為最優(yōu)班次總數(shù)的下界，有助于保證和分析解的質(zhì)量，設(shè)計(jì)了帶增補(bǔ)和刪除策略的交叉和變異操作，使得染色體長度能夠在算法迭代過程中自適

4、應(yīng)地增大或減小，實(shí)驗(yàn)表明算法的計(jì)算速度快、求解質(zhì)量高。
　　提出了灰關(guān)聯(lián)分析（Grey Relational Analysis，GRA）班次評價(jià)方法。為了確定GRA班次評價(jià)方法中的最優(yōu)參數(shù)，進(jìn)一步提出了一種基于GRA的演化乘務(wù)調(diào)度算法（Evolutionary crew scheduling algorithm based on GRA，EGRA），最優(yōu)調(diào)度方案會(huì)隨著這些參數(shù)相應(yīng)得到。EGRA是一種專門設(shè)計(jì)的嵌入快速局部搜索的混合

5、遺傳算法，其中的局部搜索是精致設(shè)計(jì)的，用以提升算法的集中性，實(shí)驗(yàn)測試說明了EGRA的優(yōu)越性。
　　提出了基于 GRA的變迭代貪婪乘務(wù)調(diào)度方法（Variable Iterated Greedy crew scheduling approach based on GRA，GRAVIG），GRAVIG裁剪了變迭代貪婪算法（Variable Iterated Greedy，VIG）求解乘務(wù)調(diào)度問題，其中嵌入了GRA班次評價(jià)方法作為調(diào)度過程

6、中班次評價(jià)的求解器，較大地提升了VIG的搜索能力，此外，還精心設(shè)計(jì)了一種基于偏向概率的破壞階段，它能夠使得“好的”班次可以保留在方案中，同時(shí)又不丟失隨機(jī)性。實(shí)驗(yàn)測試結(jié)果表明該方法是有效的。
　　提出了逼近理想解排序（TOPSIS）班次評價(jià)方法。同時(shí)設(shè)計(jì)了變鄰域搜索乘務(wù)調(diào)度方法（Variable Neighbourhood Search crew scheduling approach，VNS），VNS裁剪了變鄰域搜索算法求解乘務(wù)調(diào)

7、度問題，其中，設(shè)計(jì)了兩種帶概率的復(fù)合鄰域結(jié)構(gòu)，極大地增大了搜索空間的多樣性。在VNS中嵌入了TOPSIS方法以作為調(diào)度過程中班次評價(jià)的求解器，較大地提升了VNS的搜索能力，在VNS中還嵌入了模擬退火算法（Simulated Annealing，SA）以進(jìn)行有效的局部探索，最后實(shí)驗(yàn)測試結(jié)果表明方法的有效性。
　　提出了兩種多目標(biāo)乘務(wù)輪班方法，即模擬退火乘務(wù)輪班方法（Multi-Objective SA crew rostering

8、approach，MOSA）和變鄰域搜索乘務(wù)輪班方法（multi-objective Variable Neighbourhood Search crew rostering approach，VNS），它們使用了兩種評價(jià)接受函數(shù)來更好地處理用戶偏好。在MOSA中，首先設(shè)計(jì)了一個(gè)啟發(fā)式來構(gòu)建初始解，接著設(shè)計(jì)了一個(gè)基于SA的可行性修復(fù)算法來使該解可行，最后，設(shè)計(jì)了一個(gè)基于SA的非支配解生成算法來獲得非支配解。其中，設(shè)計(jì)了增量評價(jià)策略，鄰域