基于列生成技術(shù)的乘務(wù)調(diào)度問(wèn)題研究.pdf

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

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

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

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

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

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

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