1、乘務(wù)調(diào)度問題是指在滿足各種勞動法規(guī)和實際約束的條件下，將給定的車輛任務(wù)集進(jìn)行切分和組合，形成一組乘務(wù)員可執(zhí)行的班次集，并使得班次總成本（總數(shù)或總工時）最小化。該問題是公交運營管理與規(guī)劃的核心問題之一，有效的乘務(wù)調(diào)度方法對提高公交運營效率和降低人力資源成本具有重要意義。目前，解決乘務(wù)調(diào)度問題存在著兩個方面的難題。一方面，乘務(wù)調(diào)度問題是NP難問題，研究大規(guī)模乘務(wù)調(diào)度問題的求解方法一直是公交調(diào)度與組合優(yōu)化領(lǐng)域的熱點和難點之一。目前，傳統(tǒng)整數(shù)線

2、性規(guī)劃（ILP）方法、元啟發(fā)式方法（遺傳算法、禁忌搜索等）和以列生成技術(shù)為主的數(shù)學(xué)規(guī)劃方法是求解該問題的主要方法。傳統(tǒng)ILP方法受變量和約束數(shù)量的限制，求解能力有限；元啟發(fā)式方法相對求解速度快，但難以保證解的最優(yōu)性；列生成法不受問題規(guī)模的限制，且能夠求得次優(yōu)解甚至最優(yōu)解，但具有收斂速度慢的缺點。另一方面，常用的乘務(wù)調(diào)度模型（如集覆蓋模型）過于理想化，其求解結(jié)果在實際應(yīng)用時，時常不能滿足運營企業(yè)的實際要求和期望，具有一定的局限性。

3、　　為了克服上述難題，本文對大規(guī)模乘務(wù)調(diào)度問題的快速求解方法和更一般化的乘務(wù)調(diào)度模型兩方面進(jìn)行了研究。首先，提出了基于問題特征與縮減問題規(guī)模的方法，以處理帶“中式用餐”約束的大規(guī)模乘務(wù)調(diào)度問題；其次，從多種不同角度出發(fā)，研究了求解大規(guī)模乘務(wù)調(diào)度問題的快速列生成方法；最后，為了克服傳統(tǒng)乘務(wù)調(diào)度模型的缺點，建立了更加一般化的乘務(wù)調(diào)度擴(kuò)展模型，并提出了相應(yīng)的列生成方法。主要研究內(nèi)容和成果如下：
　　（1）提出了基于縮減問題規(guī)模的ILP方

4、法以求解帶“中式用餐”約束乘務(wù)調(diào)度問題。主要是利用“中式用餐”約束和乘務(wù)問題特征，提出篩選換班機會（乘務(wù)員換班的時間與地點對）集的啟發(fā)式方法，再利用基于“生成與選擇”的ILP方法求解，并在“生成”階段處理“中式用餐”約束問題。最后，通過實驗說明所提方法的有效性。
　?。?）基于乘務(wù)問題特征，提出了帶換班機會選擇的乘務(wù)調(diào)度網(wǎng)絡(luò)流模型，并利用Dantzig-Wolfe分解原理將網(wǎng)絡(luò)流模型轉(zhuǎn)化為帶換班機會選擇的集覆蓋模型，設(shè)計了列生成法

5、用于求解集覆蓋模型的松弛解，從而得到所求問題的下界。最后，提出一種快速求解整數(shù)解的逐步迭代方法：即利用松弛解信息，逐步確定不被使用的換班機會集，并利用列生成法求解未被確定換班機會集上的更小規(guī)模的乘務(wù)調(diào)度問題松弛解。通過實例驗證，該方法能快速得到問題的整數(shù)解，并且與下界進(jìn)行比較，結(jié)果表明大多數(shù)實例取得了次優(yōu)解或最優(yōu)解。
　?。?）為了克服傳統(tǒng)列生成法求解乘務(wù)調(diào)度問題時子問題求解（利用精確的動態(tài)規(guī)劃方法）太耗時的缺點，提出了集成新列選

6、擇與構(gòu)造的兩階段乘務(wù)調(diào)度方法。通過分析實際乘務(wù)班次的構(gòu)成特點，設(shè)計了快速構(gòu)造高效班次池的啟發(fā)式方法。在求解子問題時，優(yōu)先從班次池中選擇能改進(jìn)目標(biāo)值的班次；當(dāng)無法找到所需班次時，調(diào)用精確的構(gòu)造式方法生成新班次。通過實例，將該方法與傳統(tǒng)方法進(jìn)行比較，該方法在求解時間上能減小20％。
　?。?）根據(jù)乘務(wù)調(diào)度問題特點，從受限主問題、子問題求解以及整數(shù)求解方面提出三種針對列生成方法的新加速策略：在列生成過程中，定期移除受限主問題的部分“差”

7、列，以減小主問題的規(guī)模；在利用多標(biāo)號動態(tài)規(guī)劃求解子問題時，提出一種強標(biāo)號消除準(zhǔn)則，并提出基于強標(biāo)號消除準(zhǔn)則的二階段法以加速子問題求解；提出一種班次池策略以繼承已有解信息，從而加速整數(shù)解的求解。通過實例計算和比較，結(jié)果說明這些策略能對列生成算法起到一定的加速作用。
　?。?）針對傳統(tǒng)基于單純集覆蓋（或集分割）模型不能反映實際中乘務(wù)員與運營企業(yè)的偏好或某些特定約束的缺點，提出一種帶有多種外加約束的擴(kuò)展集覆蓋模型。該模型能反映實際問題中