運用貝葉斯優(yōu)化算法求解駕駛員調度問題.pdf

1、對于公共交通企業(yè)而言，駕駛員成本占有運營成本相當大的比例。駕駛員調度問題就是研究如何優(yōu)化安排一組駕駛員來完成事先確定的車輛運營任務，目標是采用最少的班次和最小的運營成本，該問題被公認為NP難問題，因此對其研究解決具有主要的現(xiàn)實意義和理論價值。在現(xiàn)實駕駛員調度問題中，調度員通常是遵循一系列的規(guī)則和規(guī)則之間的關系來構造調度方案的。由于貝葉斯網(wǎng)絡常常被用來模擬多個變量之間的關系，并具有學習和推理功能，本文嘗試使用貝葉斯優(yōu)化算法到來求解駕駛員調

2、度問題。
　　 在本文貝葉斯優(yōu)化算法求解的駕駛員調度問題，一個貝葉斯網(wǎng)絡就是一個調度方案。首先根據(jù)駕駛員調度領域具體知識，考慮可能影響班次選擇的因素，設置了工時成本、駕駛員利用率、駕駛段數(shù)量、連續(xù)駕駛段數(shù)量、LP松弛解、班次評價函數(shù)六種規(guī)則，并基于規(guī)則構建了駕駛員調度問題的貝葉斯網(wǎng)絡；接著根據(jù)駕駛員調度的目標，設計了成本排序、混合隨機選擇構造策略集；然后每次通過學習前一代的策略集來指導當代的貝葉斯網(wǎng)絡的構建，再從當代的貝葉斯網(wǎng)絡

3、中按上述兩種方法挑選一些貝葉斯網(wǎng)絡形成新的策略集，不斷重復改進，最后輸出最優(yōu)貝葉斯網(wǎng)絡。同時為了滿足兩種策略集方法的求解要求，設計了一組調整方案:無權重規(guī)則構造貝葉斯網(wǎng)絡、有權重規(guī)則構造貝葉斯網(wǎng)絡、概率構造貝葉斯網(wǎng)絡、駕駛段工作分配、成本計算。
　　 在不同規(guī)則組合方案下，對駕駛員調度問題使用基于成本排序策略、混合隨機選擇策略的貝葉斯優(yōu)化算法進行編程測試，發(fā)現(xiàn)基于混合隨機選擇策略和六種規(guī)則的貝葉斯算法得到的結果最優(yōu)，因此可以得出