陳仕軍,沈吟東

(華中科技大學(xué) 自動(dòng)化學(xué)院,武漢 430074)

加速列生成法求解乘務(wù)調(diào)度問題

陳仕軍,沈吟東*

(華中科技大學(xué) 自動(dòng)化學(xué)院,武漢 430074)

列生成法是求解乘務(wù)調(diào)度問題的有效數(shù)學(xué)規(guī)劃方法,但傳統(tǒng)列生成法存在收斂速度慢的缺點(diǎn).基于乘務(wù)問題特點(diǎn),提出三種加速列生成求解的策略:在列生成迭代過程中,每隔一定周期移除受限主問題的部分“差”變量,以減小問題規(guī)模;提出基于乘務(wù)問題特征的強(qiáng)標(biāo)號(hào)消除準(zhǔn)則和基于該準(zhǔn)則的二階段子問題求解法以加速子問題求解;利用分支樹求解整數(shù)解時(shí),提出一個(gè)能充分利用已有解信息的班次池策略,以減小整數(shù)解求解時(shí)間.利用實(shí)際公共交通中的 10 組案例對(duì)所提加速策略進(jìn)行測(cè)試.實(shí)驗(yàn)結(jié)果表明,這些加速策略能夠有效加速列生成的求解,適用于求解大規(guī)模的乘務(wù)調(diào)度問題.

系統(tǒng)工程;列生成法;加速策略;乘務(wù)調(diào)度;問題特征

1 引 言

乘務(wù)調(diào)度問題是公交企業(yè)普遍面對(duì)的重要問題,也是計(jì)算科學(xué)界的 NP 難題.有效的調(diào)度方法能提高管理效率,并節(jié)約大量的人力成本.從上世紀(jì)60年代開始,眾多學(xué)者和交通領(lǐng)域?qū)＜覍?duì)該問題進(jìn)行了深入研究,提出了各種有效的優(yōu)化模型和解決方法[1].

列生成方法是求解大規(guī)模線性規(guī)劃問題(LP)的有效方法,它通常與分支定界方法結(jié)合,用于解決大規(guī)模整數(shù)規(guī)劃問題(ILP)[2].該方法也被廣泛用于求解各類交通領(lǐng)域(公共交通、鐵路、航空等)的乘務(wù)調(diào)度問題[3,4].對(duì)于某些大規(guī)模 LP 問題( 稱主問題,記作 MP),其變量數(shù)可能太多以至于難于直接求解整個(gè) LP 問題.此時(shí),列生成方法顯示出其優(yōu)越性.其主要過程是:求解時(shí)只考慮分部分變量集上的 LP 問題(稱受限主問題,記作 RMP);求解后,根據(jù)其對(duì)偶乘子信息求解一個(gè)子問題(SP),以期得到能改進(jìn)目標(biāo)值的新變量(列);將新列加入 RMP 以擴(kuò)大其規(guī)模,再求解新的 RMP 問題.以上過程重復(fù)進(jìn)行,直到?jīng)]有改進(jìn) RMP 的新列為止.盡管列生成法已被應(yīng)用于解決多種大規(guī)模 ILP,但仍然存在不穩(wěn)定、收斂速度慢的缺點(diǎn)[2].

由列生成法的求解過程可知,列生成法的效率主要由兩方面決定:RMP 問題的求解速度與 SP 問題的求解速度.目前,部分文獻(xiàn)針對(duì)各種不同具體問題,從不同側(cè)面提出了一些改進(jìn)列生成效率的方法.例如,Gondzio[5]提出一種原始對(duì)偶內(nèi)點(diǎn)方法用于加速求解 RMP 的近似解.Elhallaoui 等[6]提出一個(gè)動(dòng)態(tài)約束集結(jié)方法,來減小 RMP 的退化程度以加快其收斂速度.由于乘務(wù)調(diào)度的子問題等價(jià)于帶資源約束的最短路問題 (RCSPP),是 NP 難題,部分學(xué)者對(duì) RCSPP 求解提出一些改進(jìn)方法,例如雙向動(dòng)態(tài)定界法[7]、狀態(tài)空間松弛法[8]等,并用于求解車輛路徑問題. 此外,Leitner 等[9]、 Alves 與 De Carvalho[10]基于問題特征,研究了對(duì)偶乘子穩(wěn)定性方法以加速列生成法的收斂速度,分別用于解決網(wǎng)絡(luò)設(shè)計(jì)和變尺度裝箱問題.上述加速求解方法都需要結(jié)合具體問題特征,難以直接應(yīng)用于解決乘務(wù)調(diào)度問題.本文基于乘務(wù)問題特點(diǎn),從主問題、子問題及整數(shù)解求解等方面,提出了三種加速策略用于解決乘務(wù)調(diào)度問題.

首先,在傳統(tǒng)列生成方法中,RMP 的規(guī)模在持續(xù)增大.當(dāng) RMP 增大到一定規(guī)模后,其求解會(huì)花費(fèi)較長(zhǎng)時(shí)間.為此,本文設(shè)計(jì)了一個(gè)“差”(無助于改進(jìn)目標(biāo)值)變量移除策略來降低 RMP 的增長(zhǎng)規(guī)模,并加速列生成求解.其次,在求解子問題時(shí),需要利用多標(biāo)號(hào)動(dòng)態(tài)規(guī)劃方法求解 RCSPP.為了提高求解效率,一般采用標(biāo)號(hào)消除準(zhǔn)則消除部分標(biāo)號(hào),只保留帕累托(Pareto) 最優(yōu)標(biāo)號(hào)集[11].注意到實(shí)際中 Pareto 最優(yōu)解仍然包含大量標(biāo)號(hào)(特別是當(dāng)網(wǎng)絡(luò)和資源集規(guī)模較大時(shí)),且很多標(biāo)號(hào)不會(huì)成為最優(yōu)解.為此,本文基于乘務(wù)問題特點(diǎn),提出一種新的強(qiáng)標(biāo)號(hào)消除準(zhǔn)則,并基于此提出一個(gè)二階段子問題求解方法,以提高子問題求解效率.最后,利用分支定界方法求解整數(shù)解時(shí),需要在每個(gè)節(jié)點(diǎn)利用列生成法計(jì)算其相應(yīng) LP 解.因此,子問題對(duì)應(yīng)的RCSPP 求解也要在整個(gè)分支樹進(jìn)行,使得整數(shù)解求解花費(fèi)太多時(shí)間.本文考慮在搜索整個(gè)分支樹時(shí),充分利用已有解信息,提出一種班次池策略:即為每個(gè)節(jié)點(diǎn)設(shè)計(jì)一個(gè)班次池用于繼承其父節(jié)點(diǎn)已生成的既有班次.在求解子節(jié)點(diǎn)的子問題時(shí),優(yōu)先考慮其班次池中的班次,只有當(dāng)班次池中沒有班次能改進(jìn)目標(biāo)值時(shí)才調(diào)用 RCSPP 以生成新班次.該方法能減少子問題的求解時(shí)間,從而能縮小整數(shù)解的求解時(shí)間.

2 乘務(wù)調(diào)度模型

乘務(wù)調(diào)度問題可描述為[12,13]:在滿足各種勞動(dòng)法規(guī)約束下,合理安排乘務(wù)員去執(zhí)行所有給定的車輛任務(wù),并使得所用乘務(wù)員數(shù)量最少或總工時(shí)成本最小.

一般,乘務(wù)調(diào)度可以用集覆蓋模型來表示.記最小值乘段集合 M={1,2,…,m},所有可行班次集合 N={1,2,…,n},班次 j∈ N 的成本 cj.對(duì)于?i∈ M 和 ?j∈ N, 若班次 j包含 i,則記 aij=1;否則記 aij=0.對(duì)于 ?j∈ N,定義決策變量 xj如下:xj=1 表示班次 j被選擇,否則 xj=0.則乘務(wù)調(diào)度模型可描述為

目標(biāo)函數(shù)(1)是最小化總成本;約束(2)表明每個(gè)最小值乘段至少被一個(gè)乘務(wù)班次所覆蓋;約束

(3)是0-1 決策變量.

3 基于列生成法的乘務(wù)調(diào)度問題求解

3.1 基本的列生成算法

列生成算法主要用于求解 ILP 的線性松弛問題(稱為主問題,記做 MP),以得到 ILP 的下界.其主要是通過迭代求解一系列的受限主問題(RMP)和子問題(SP),最終收斂到最優(yōu)解.其中,RMP 對(duì)應(yīng)部分變量(列或班次)集上的線性松弛問題,SP在于生成能改進(jìn) RMP 目標(biāo)函數(shù)值的新班次.記第 r次迭代時(shí),受限主問題為 RMPr,子問題為 SPr.記 RMPr對(duì)應(yīng)的部分變量集,則 RMPr為如下優(yōu)化問題:

由于 RMPr只考慮了部分變量集以外仍可能有改進(jìn)目標(biāo)值的變量.根據(jù)線性規(guī)劃單純型原理,能改進(jìn)目標(biāo)值的變量是具有負(fù)判別數(shù)的變量.記約束(5)對(duì)應(yīng)的對(duì)偶乘子向量為, 則對(duì)于 ?j∈ N,其判別數(shù) rcj計(jì)算如下:

為了判斷 N-r以外是否具有負(fù)判別數(shù)的變量,需要求解具有最小負(fù)判別數(shù)的變量.因此,子問題SPr為如下優(yōu)化問題:式(8)中,Pr返回具有最小負(fù)判別數(shù)的變量集.

有了上述定義,列生成算法求解乘務(wù)調(diào)度問題的基本步驟如下:

Step1r ← 0,構(gòu)造初始列集,形成初始受限主問題 RMP0;

Step2求解受限主問題 RMPr,得到約束(5)對(duì)應(yīng)的對(duì)偶乘子向量 πr;

Step3求解子問題 SPr,以得到改進(jìn) RMPr目標(biāo)值的班次集 Pr;

Step4若 Pr= ? ,則已經(jīng)求得 MP 的最優(yōu)解,轉(zhuǎn) Step6;

Step5將新班次集 Pr加入到 RMPr,即

Step6若 MP 最優(yōu)解是整數(shù)解,則停止;

Step7對(duì)當(dāng)前節(jié)點(diǎn)分支,用分支定界方法求解整數(shù)解.

在 Step1 中,通過設(shè)置人工變量方法構(gòu)造初始列集,從而形成初始 RMP0.由于新生成的班次需要滿足多種班次合法性約束,因此 Step3 中的子問題 SPr等價(jià)于帶資源約束的最短路問題(RCSPP),需要利用多標(biāo)號(hào)動(dòng)態(tài)規(guī)劃方法求解[11].最后,Step7中利用基于換班機(jī)會(huì)(RO)的分支策略求整數(shù)解,具體參見 3.3 節(jié).

3.2 三種列生成法的加速策略

本文基于乘務(wù)問題特點(diǎn)從主問題求解、子問題求解及整數(shù)解等方面,提出了三種列生成的加速求解策略.

(1)列移除策略.

基本列生成算法中,RMPr的規(guī)模隨迭代次數(shù) r在不斷增大,其求解速度會(huì)逐漸變慢(特別是對(duì)大規(guī)模問題).為了限制 RMPr的增長(zhǎng)規(guī)模,考慮迭代求解過程中移除 RMPr中較“差” (無助于改進(jìn)RMPr目標(biāo)值) 的變量集,從而加快求解 RMPr速度.根據(jù)線性規(guī)劃單純型原理,具有負(fù)判別數(shù)的變量可能會(huì)改進(jìn) RMPr的目標(biāo)值,而且負(fù)判別數(shù)越小,有可能改進(jìn) RMPr的目標(biāo)值越多.相反,具有正判別數(shù)的變量無助于改進(jìn) RMPr目標(biāo)值.基于此,本文“差”變量將指具有非負(fù)判別數(shù)的變量,判別數(shù)越大,相應(yīng)的變量就越差.但需注意,對(duì)于任何變量,其判別數(shù)會(huì)隨 RMPr的變化而改變,因此“差”變量在 RMP求解迭代一定次數(shù)后,也可能變成非“差”變量,并改進(jìn) RMPr的目標(biāo)值.而且,RMPr對(duì)應(yīng)的變量集與對(duì)偶乘子是相互影響的,頻繁移除變量可能會(huì)影響對(duì)偶乘子 πr的穩(wěn)定性.因此,本文采取每隔一定迭代次數(shù) rout( 列移除頻率) 從 RMP 中移除一部分“差”變量,且在列生成的迭代初期和迭代末期,不移除變量.記 zr為的 RMPr目標(biāo)值, εphase為接近 0的正數(shù).首先,將列生成過程分三個(gè)階段:當(dāng) r ＜ 5時(shí),稱迭代初期;當(dāng) (zr-1-zr)/zr≥ εphase時(shí),為迭代中期;其余為迭代末期.記當(dāng)前 RMPr的變量數(shù) nr,解中非零基變量的數(shù)量為,從 RMPr移除的列數(shù)量按如下計(jì)算:,此處α ∈ [0,1) 表示從 RMPr中移除“差”變量的比例.

(2)強(qiáng)標(biāo)號(hào)消除準(zhǔn)則.

利用 RCSPP 求解子問題時(shí),先構(gòu)建有向網(wǎng)絡(luò)圖 G(V,A),V 與 A 分別表示節(jié)點(diǎn)集和弧集.記 s與 t分別為 G(V,A) 的開始點(diǎn)與結(jié)束點(diǎn).利用多標(biāo)號(hào)動(dòng)態(tài)規(guī)劃求解 RCSPP 時(shí),用標(biāo)號(hào)表示從 s到達(dá)當(dāng)前節(jié)點(diǎn) i∈ V 的有向路徑.這里,ci表示該路徑的成本,sri表示該路徑消耗資源 r∈ R 的量,R 表示全部資源集.由于每個(gè)標(biāo)號(hào) li都需要通過有向弧 (i,j) 延伸至結(jié)點(diǎn) j( 當(dāng)滿足資源約束時(shí)),得到節(jié)點(diǎn) j的標(biāo)號(hào) lj.因此,標(biāo)號(hào)延伸過程將生成大量標(biāo)號(hào).為了消除不會(huì)成為最優(yōu)解的標(biāo)號(hào)(只保留 Pareto 最優(yōu)標(biāo)號(hào)),一般采取如下標(biāo)號(hào)消除準(zhǔn)則[11]:

該標(biāo)號(hào)消除方法能夠減少各個(gè)節(jié)點(diǎn)的標(biāo)號(hào)數(shù)量,且保證最優(yōu)標(biāo)號(hào)不會(huì)被消除.為了進(jìn)一步加快求解速度,本文提出一個(gè)強(qiáng)標(biāo)號(hào)消除準(zhǔn)則,主要是在定義標(biāo)號(hào)消除準(zhǔn)則時(shí)只考慮部分重要資源集 R? R,從而能消除更多的標(biāo)號(hào).不失一般性,假定標(biāo)號(hào)消除準(zhǔn)則只考慮前個(gè)資源,則新的強(qiáng)標(biāo)號(hào)消除準(zhǔn)則如下:

此標(biāo)號(hào)消除準(zhǔn)則,能夠消除更多標(biāo)號(hào)集,但可能會(huì)損失某些 Pareto 最優(yōu)標(biāo)號(hào).因此,本文在求解子問題時(shí)采取二階段的標(biāo)號(hào)消除準(zhǔn)則:在第一階段使用強(qiáng)消除標(biāo)號(hào)準(zhǔn)則;當(dāng)無法生成具有負(fù)判別數(shù)的新列時(shí),在第二階段使用原標(biāo)號(hào)消除準(zhǔn)則,從而保證子問題的最優(yōu)性.需要注意的是,執(zhí)行強(qiáng)標(biāo)號(hào)消除準(zhǔn)則時(shí),如何選取重要資源集 R直接影響二階段-子問題求解的性能.對(duì)于 R的選擇,需要根據(jù)問題特征或?qū)嶒?yàn)方法決定.對(duì)于本文所考慮的乘務(wù)調(diào)度問題,原資源集 R 包含5種資源:a.工作時(shí)間長(zhǎng)度tw;b.駕駛時(shí)間長(zhǎng)度 td;c.跨度時(shí)間長(zhǎng)度 tsp;d.連續(xù)駕駛段時(shí)長(zhǎng) tspl;e.連續(xù)駕駛段數(shù)量 nspl.由于工作時(shí)間長(zhǎng)度 tw直接影響班次成本和效率,本文通過試驗(yàn)也證實(shí)該資源是最為重要的資源,對(duì)消除大量非最優(yōu)標(biāo)號(hào)起重要作用.因此,本文利用強(qiáng)標(biāo)號(hào)消除準(zhǔn)則時(shí)只考慮該資源,即.需要說明的是,強(qiáng)標(biāo)號(hào)消除準(zhǔn)則在應(yīng)用于其他問題如車輛路徑問題時(shí),重要資源的選擇仍然依賴于問題相關(guān)經(jīng)驗(yàn)或?qū)嶒?yàn)方法.

(3)班次池策略加速求解整數(shù)解.

利用分支定界求解整數(shù)解時(shí),需要在分支樹的每個(gè)節(jié)點(diǎn)調(diào)用 RCSPP 求解子問題,從而搜索整個(gè)分支定界樹將消耗太多時(shí)間.本文考慮充分利用父節(jié)點(diǎn)已有信息,從而加速子問題求解.方法是:為每個(gè)節(jié)點(diǎn)設(shè)計(jì)一個(gè)班次池,并繼承父節(jié)點(diǎn)的班次信息.對(duì)于節(jié)點(diǎn) k,包含兩個(gè)班次集,即班次池與當(dāng)前 RMP 對(duì)應(yīng)的班次集.若節(jié)點(diǎn) k 的父節(jié)點(diǎn)為h,則按如下得到:

當(dāng)利用列生成方法求解非根節(jié)點(diǎn) k時(shí),分成兩階段進(jìn)行:先在班次池 Spk里利用列生成方法,直到無改進(jìn)當(dāng)前 RMP 的目標(biāo)值為止;再利用 RCSPP 調(diào)用子問題以得到改進(jìn)的班次.

3.3 整數(shù)解求解

當(dāng)原問題的線性松弛解是整數(shù)解時(shí),則該解即為原乘務(wù)調(diào)度問題的最優(yōu)解.否則(分?jǐn)?shù)解),需要利用分支定界方法以求其整數(shù)解,本文將利用基于換班機(jī)會(huì)(RO) 的分支方法.Fores 等[14]曾提出過類似的方法,但沒有給出如何選擇 RO 的具體方法.記當(dāng)前分?jǐn)?shù)解對(duì)應(yīng)的班次集 N-,全部換班機(jī)會(huì)集合 RO.對(duì) ?r∈ RO,記班次集為

Jr={j|r在班次 j的內(nèi)部,

對(duì)當(dāng)前分?jǐn)?shù)解,尋找換班機(jī)會(huì) p ∈ RO,使得

對(duì)當(dāng)前節(jié)點(diǎn)采取如下分支:

當(dāng)在整個(gè)分支定界樹上使用列生成算法時(shí),上述分支策略很容易在子問題中得到實(shí)現(xiàn),只需要?jiǎng)h除子問題網(wǎng)絡(luò)圖 G(V,A) 上與分支策略不兼容的弧集即可.

4 計(jì)算與實(shí)驗(yàn)結(jié)果

為測(cè)試算法性能,采用實(shí)際公共交通中遇到的10 組實(shí)例.算法代碼用 C++編寫,在具有奔騰雙核T4300 2.1G 處理器、2 G 內(nèi)存的筆記本上運(yùn)行,并利用 CPLEX 12.4 作為線性規(guī)劃求解器來求解受限主問題 RMP.實(shí)驗(yàn)結(jié)果中,所有時(shí)間用秒表示.

(1)列移除策略與強(qiáng)標(biāo)號(hào)消除規(guī)則的實(shí)驗(yàn)結(jié)果.

在執(zhí)行列移除策略時(shí),需要設(shè)置如下 3個(gè)參數(shù):列生成 迭代期劃分參數(shù)εphase、 移除列頻率rout、移除列比例參數(shù) α .先通過一些初步實(shí)驗(yàn),發(fā)現(xiàn)列移除頻率 rout對(duì)算法性能影響很大.因此,先實(shí)驗(yàn)確定階段劃分參數(shù) εphase=10-6和移除比例 α = 0.2,再實(shí)驗(yàn) rout的取值.表2 統(tǒng)計(jì)了 rout取不同參數(shù)值時(shí)列生成求解根節(jié)點(diǎn)到最優(yōu)解所需的時(shí)間.因?yàn)閞out太大時(shí),起不到加速作用,只測(cè)試了 rout≤ 6 的情況.當(dāng) rout=0 時(shí),表示不移除列,此時(shí)算法即為傳統(tǒng)的列生成方法.表1 的最后一列,記錄了利用強(qiáng)標(biāo)號(hào)消除規(guī)則后的計(jì)算結(jié)果.

表1 列移除策略與強(qiáng)標(biāo)號(hào)消除規(guī)則實(shí)驗(yàn)結(jié)果Table1 The results of column removing strategy and strong label eliminating rule

從表1 中可以看出,當(dāng) rout=3 時(shí)采用列移除策略的算法平均性能達(dá)到最好( 與 rout=0 比較).從表1的最后一列可以看出,強(qiáng)標(biāo)號(hào)消除準(zhǔn)則總體上能進(jìn)一步降低計(jì)算時(shí)間.但實(shí)例6和實(shí)例8的結(jié)果差于只采用列移除策略的測(cè)試結(jié)果.一方面與參數(shù)設(shè)置有關(guān),另一方面也說明了兩種策略同時(shí)使用時(shí),其間也會(huì)相互影響.

(2)班次池策略實(shí)驗(yàn)結(jié)果.

測(cè)試整數(shù)解時(shí),采用深度優(yōu)先搜索策略,設(shè)置最大搜索節(jié)點(diǎn)數(shù) nmax=500,分別考慮基于班次池策略的列生成與傳統(tǒng)列生成法.表2與表3分別記錄了傳統(tǒng)列生成法和利用本文班次池策略求解整數(shù)解的結(jié)果.在表2 與表3 中,“t-RMP”記錄求解受限主問題的總時(shí)間,“t-SP” 記錄求解子問題的總時(shí)間,“t-Total” 記錄求解整數(shù)解的總時(shí)間,“ IP”記錄最優(yōu)整數(shù)解,“LP-root” 記錄根節(jié)點(diǎn)線性松弛解,最后一列“nNode”記錄求解的節(jié)點(diǎn)數(shù),“Gap”計(jì)算上下界相對(duì)間隙,其計(jì)算公式為 Gap=(IP-LP-root)·100/LP-root.

通過比較兩種方法,發(fā)現(xiàn)本文所提的班次池策略能明顯加速列生成方法.10 組實(shí)例中,只有第 2組花費(fèi)了更多時(shí)間求解整數(shù)解,但其求解的節(jié)點(diǎn)數(shù)為 500,多于傳統(tǒng)列生成方法求解的節(jié)點(diǎn)數(shù) 155.此外,本文所提的班次池策略,在花費(fèi)較少求解時(shí)間的同時(shí),大多數(shù)測(cè)試實(shí)例都得到了更好(Gap 更小)的整數(shù)解.只有第 2 組和第 3 組求得的整數(shù)解比傳統(tǒng)的列生成方法略差.因此,總體上本文所提的加速策略能夠改進(jìn)傳統(tǒng)的列生成方法.

表2 傳統(tǒng)列生成方法的整數(shù)解Table2 The integer solutions obtained by traditional column generation

表3 基于班次池策略列生成法的整數(shù)解Table3 The integer solutions obtained by the column generation using column pool strategy

5 研究結(jié)論

本文基于乘務(wù)問題特點(diǎn),提出了三種加速策略以改進(jìn)列生成方法,用于求解乘務(wù)調(diào)度問題.首先,提出了列移除策略,從受限主問題中移除迭代過程中不太可能改進(jìn)當(dāng)前目標(biāo)值的部分列集,目的是減小主問題的求解負(fù)擔(dān).其次,在求解子問題時(shí),提出一種基于乘務(wù)問題特點(diǎn)的強(qiáng)標(biāo)號(hào)消除策略,以減小子問題求解時(shí)的標(biāo)號(hào)數(shù)量,并提出二階段子問題求解法.最后,提出利用班次池策略繼承已有解的班次信息,加速整數(shù)解的求解.通過實(shí)際中的 10 組測(cè)試實(shí)例,表明這些策略能對(duì)傳統(tǒng)的列生成方法起到改進(jìn)作用.

[1] Hickman M,Mirchandani P,Vo? S(Eds.).Computeraided systems in public transport[M].Lecture notes in economics and mathematical systems,Berlin:Springer, 2008,volume 600.

[2] Lubbecke M E,Desrosiers J.Selected topics in column generation[J].Operations Research,2005,53(6): 1007-1023.

[3] Abbink E,Albino L,Dollevoet T,et al.Solving large scale crew scheduling problems in practice[J]. Public Transport,2011,3(2):149-164.

[4] Gamache M,Soumis F,Marquis G,et al.A column generation approach for large-scale aircrew rostering problems[J].Operations Research,1999,47(2): 247-263.

[5] Gondzio J,González-Brevis P,Munari P.New developments in the primal-dual column generation technique[J]. European JournalofOperational Research,2013,224(1):41-51.

[6] Elhallaoui I,Villeneuve D,Soumis F,et al.Dynamic aggregation of set-partitioning constraints in column generation[J].Operations Research,2005,53(4): 632-45.

[7] Righini G,Salani M.Symmetry helps:bounded bidirectional dynamic programming for the elementary shortest path problem with resource constraints[J]. Discrete Optimization,2006,3(3):255-273.

[8] Righini G,Salani M.New dynamic programming algorithms for the resource constrained elementary shortest path problem[J].Networks,2008,51(3): 155-70.

[9] Leitner M,Raidl G R,Pferschy U.Accelerating column generation for a survivable network design problem[C]//Proceedings of the International Network Optimization Conference,2009.

[10] Alves C,De Carvalho J M V.Accelerating column generation for variable sized bin-packing problems[J]. European Journal of Operational Research,2007,183 2009,26(11):132-135.]

[6] Yi Qi,Lei Yu,Mehdi Azimi,et al.Determination of storage lengths of left-turn lanes at signalized intersections[R]. Journal of the Transportation Research Board,No.2023,Transportation Research Board of the National Academies,Washington,D.C., 2007:102-111.

[7] 李麗麗. 信號(hào)交叉口左轉(zhuǎn)交通流中的臨界問題研究[D]. 長(zhǎng)春:吉林大學(xué),2009:62-63.[LI L L. Research on the critical question of left-turn traffic organization at signalized intersections[D].Chang chun:JiLin University,2009:62-63.] (3):1333-1352.

[11] Feillet D,Dejax P,Gendreau M,et al.An exact algorithm for the elementary shortest path problem with resourceconstraints: Application to some vehicle routing problems[J].Networks,2004,44(3): 216-229.

[12] Chen S,Shen Y.An improved column generation algorithm for crew scheduling problems[J].Journal of Information and Computational Science,2013,10 (1):175-183.

[13] Shen Y,Peng K,Chen K,et al.Evolutionary crew scheduling with adaptive chromosomes [J]. Transportation Research Part B,2013,56(10): 174-185.

[14] Fores S,Proll L,Wren A.TRACS II:a hybrid IP/ heuristic driver scheduling system for public transport [J].Journal of the Operational Research Society, 2002,53(10):1093-100.

Accelerating Column Generation for Solving Crew Scheduling Problems

CHEN Shi-jun,SHEN Yin-dong
(School of Automation,Huazhong University of Science and Technology,Wuhan 430074,China)

Column generation is an efficient math programming approach to solve crew scheduling problems.However,it has the drawback of slow convergence.Three accelerating strategies are presented, based on problem-specific knowledge to speed up its solving process.The first one is to remove some ‘ bad' variables from the restricted master problem after a certain number of iterations.The second one is that a strong label cutting rule is presented,and a two-phase solution approach is proposed to solve the subproblem.The last one is that a shift pool strategy which can use the exiting solution information is proposed to reduce the time to solve integer solutions.Finally,ten real-world instances are tested,and the computational results show that the proposed strategies can accelerate the column generation algorithm.

systems engineering;column generation;accelerating strategies;crew scheduling;problemspecific knowledge

1009-6744(2014)01-0144-06

U268.6

A

2013-09-09

2013-10-31錄用日期:2013-11-12

國家自然科學(xué)基金(70971044,71171087,61304175).

陳仕軍(1980-),男,湖北襄陽人,博士生.*通訊作者:yindong@hust.edu.cn