郝小妮 靳文舟 査靚

(1.華南理工大學(xué) 土木與交通學(xué)院，廣東 廣州 510640;2.三峽大學(xué) 機(jī)械與動(dòng)力學(xué)院，湖北 宜昌 443002)

公交區(qū)域調(diào)度相比單線調(diào)度，能節(jié)省車輛、司機(jī)資源，提高車輛的運(yùn)營(yíng)效率［1］.國(guó)外研究并實(shí)施公交區(qū)域調(diào)度已40 余年，而國(guó)內(nèi)公交區(qū)域調(diào)度尚處于研究探索階段，仍以單線調(diào)度為主［2］.公交區(qū)域調(diào)度問(wèn)題包括:線網(wǎng)規(guī)劃→時(shí)刻表生成→公交車輛調(diào)度→駕駛員排班4 個(gè)連續(xù)的步驟［3］;公交車輛調(diào)度是區(qū)域調(diào)度過(guò)程中涉及車輛、司機(jī)調(diào)配和費(fèi)用節(jié)約的關(guān)鍵步驟，同時(shí)又受到時(shí)刻表的制約.區(qū)域公交車輛調(diào)度(RVSP)是在給定區(qū)域時(shí)刻表前提下，以所需車輛數(shù)最少或費(fèi)用最小為目標(biāo)，滿足相關(guān)運(yùn)營(yíng)約束，構(gòu)建完成所有車次任務(wù)的公交車輛的車次執(zhí)行序列(即車輛調(diào)度方案).區(qū)域公交車輛調(diào)度屬于多車場(chǎng)車輛調(diào)度問(wèn)題(MDVSP)，此類組合優(yōu)化問(wèn)題已被證明為NP-hard 問(wèn)題［4］，是公交領(lǐng)域的熱點(diǎn)研究問(wèn)題之一.

國(guó)外不少學(xué)者用網(wǎng)絡(luò)中的不同多商品模型來(lái)描述MDVSP 問(wèn)題［4-6］.Mesquita 等［7］應(yīng)用分枝定界法求解MDVSP 的各種多商品模型.Lobel［8］提出用一種稱為拉格朗日定價(jià)法的特殊列生成法來(lái)求解大規(guī)模MDVSP，是成功的求解方法之一.Haghani 等［9］提出了有線路時(shí)間約束的MDVSP 新0－1 規(guī)劃模型和算法，依據(jù)發(fā)車時(shí)間將車次分為上午、中午、下午車次，通過(guò)空駛與連續(xù)運(yùn)行的經(jīng)濟(jì)性比較定義了站場(chǎng)相容車次、線路相容車次，將總成本細(xì)化為時(shí)刻表車次成本、空駛車次成本、線路終點(diǎn)停留成本、車場(chǎng)停車成本四者之和，但卻沒有分析停車時(shí)間長(zhǎng)短對(duì)成本的影響，僅統(tǒng)一假設(shè)車場(chǎng)停車成本為零.Kliewer等［10］用時(shí)空網(wǎng)絡(luò)流模型描述MDVSP 問(wèn)題，可大大縮減變量規(guī)模，有助于求解大規(guī)模車輛調(diào)度問(wèn)題.總體上，國(guó)外研究文獻(xiàn)側(cè)重于用圖論和網(wǎng)絡(luò)流模型來(lái)描述區(qū)域公交車輛調(diào)度問(wèn)題，并對(duì)求解算法做了大量探索，尤其針對(duì)大規(guī)模RVSP.

國(guó)內(nèi)方面，劉志剛等［11-14］基于車場(chǎng)容量、續(xù)駛時(shí)間等，最小化所需車輛數(shù)與無(wú)效駕駛時(shí)間之和，分別建模研究區(qū)域公交車輛調(diào)度［11，13-14］、區(qū)域電車車輛調(diào)度［12］，并采用禁忌搜索算法［11］、蟻群算法［12-14］進(jìn)行求解.不同之處，魏明等［13］引入車次任務(wù)可靠度約束，探討不確定環(huán)境下的RVSP.上述文獻(xiàn)逐步考慮多種現(xiàn)實(shí)約束，大多基于最小費(fèi)用流網(wǎng)絡(luò)模型研究RVSP.

但是，現(xiàn)有文獻(xiàn)假設(shè)公交客流量一天內(nèi)是均勻的，時(shí)刻表均衡分布.實(shí)際上，一天內(nèi)不同時(shí)刻的公交客流量差異顯著，高峰值一般出現(xiàn)在上午7:00～9:00 和下午17:00～19:00，7:00 前和20:00 后屬于低峰期，其余為平峰時(shí)段;并且通過(guò)調(diào)研發(fā)現(xiàn)，我國(guó)大城市的公交線路客流高峰時(shí)間、空間分布非常集中，從而參與公交區(qū)域調(diào)度的多條線路客流高峰將在時(shí)間、空間上相互疊加，導(dǎo)致總體客流的高低峰客流量差異會(huì)進(jìn)一步加大;很顯然，客流高峰、低平峰期對(duì)車輛的需求量存在較大差異;如果忽視這種差異，全天按高峰流量配車，將導(dǎo)致低平峰時(shí)段車輛和司機(jī)出現(xiàn)較多空閑等待時(shí)間，造成資源浪費(fèi)，因此需要研究實(shí)際公交客流量非均勻分布且多條線路客流高峰時(shí)間、空間分布集中情況下的區(qū)域公交車輛調(diào)度問(wèn)題.針對(duì)客流量的不均衡特征，文中提出了抽停策略，即在低平峰期停運(yùn)部分公交車輛，減少車輛和司機(jī)的等待時(shí)間，減少所需司機(jī)數(shù)和企業(yè)運(yùn)營(yíng)成本，緩解目前公交企業(yè)中存在的駕駛員不足矛盾.

1 問(wèn)題描述及建模

根據(jù)一天之中公交客流量具有時(shí)間分布不均衡的特點(diǎn)，將所需公交車分為兩類:單班車ksv和雙班車kdv，單班車在早高峰及其前后1～2 h 內(nèi)出車執(zhí)行車次任務(wù)，之后該車抽停(車輛停運(yùn)期可用于旅游包車等業(yè)務(wù))，駕駛員休息，下午再出場(chǎng)參與晚高峰及其前后1～2 h 的公交運(yùn)營(yíng)，單班車全天只需一個(gè)駕駛員.相應(yīng)地，雙班車在公交運(yùn)營(yíng)時(shí)間范圍內(nèi)需要兩個(gè)駕駛員換班駕駛完成全天的運(yùn)營(yíng)任務(wù).文中擬在考慮公交客流時(shí)間分布不均衡及參與區(qū)域調(diào)度的多條線路客流高峰時(shí)空分布集中的情況下，基于低平峰期停運(yùn)部分車輛的抽停策略，從“部分班次被某輛車完成”的集合劃分問(wèn)題角度研究RVSP，第一目標(biāo)最小化所需車輛數(shù)、車輛等待時(shí)間和空駛時(shí)間三者之和，第二目標(biāo)最大化車輛利用率，提出一個(gè)新的區(qū)域公交車輛調(diào)度模型.

1.1 假設(shè)條件

(1)道路交通狀態(tài)穩(wěn)定，運(yùn)營(yíng)時(shí)間范圍內(nèi)各條公交線路的車次運(yùn)行時(shí)間為某一恒定值.

(2)要求所有公交車輛準(zhǔn)時(shí)從相應(yīng)車場(chǎng)出發(fā)執(zhí)行每一個(gè)車次任務(wù).

(3)公交車輛完成一個(gè)車次后，可不做任何停留立即開始執(zhí)行下一車次.

(4)公交車加滿氣后，其所能運(yùn)行的總時(shí)間或總里程為一確定值，與司機(jī)駕駛習(xí)慣、交通狀況無(wú)關(guān).

(5)單班車可在抽停期間加氣，因此車輛調(diào)度方案中不考慮單班車的加氣，僅考慮雙班車的加氣要求.

1.2 參數(shù)定義

T={T1，T2，…，TN}為所有區(qū)域調(diào)度范圍內(nèi)不同公交線路的固定時(shí)刻表對(duì)應(yīng)的N 個(gè)車次任務(wù)構(gòu)成的集合;對(duì)?TiT，要求車輛在開始時(shí)刻ts，Ti從某個(gè)車場(chǎng)po，Ti出發(fā)，并在結(jié)束時(shí)刻ta，Ti到達(dá)車場(chǎng)pe，Ti;D 為車場(chǎng)集合，M 為車場(chǎng)數(shù)量;Vd為從車場(chǎng)dD 出發(fā)的相應(yīng)車輛集合，為從車場(chǎng)d 出發(fā)的車輛數(shù)，Cd則為車場(chǎng)容量.=dtx1為車輛k 離開車場(chǎng)d 開始執(zhí)行車次鏈的時(shí)刻;而到達(dá)?xi起始點(diǎn)po，xi的時(shí)刻為=+time(po，x1，pe，x1)+…+time(pe，xi－1，po，xi)，如該車輛在xi的出發(fā)點(diǎn)po，xi加油加氣，令，則為車輛在車場(chǎng)加油或加氣所需時(shí)間;對(duì)?xi－1，xiTkd，若time(pe，xi－1，po，xi)≠0，即從車次xi－1的終點(diǎn)到車次xi的起點(diǎn)時(shí)間不為零的空車行駛稱為空駛車次(Deadhead Trip)，而time(po，xi，pe，xi)則為從車次xi起點(diǎn)至終點(diǎn)的運(yùn)行時(shí)間，time(g，h)(?g，hD)為車輛在兩車場(chǎng)間的空駛運(yùn)行時(shí)間.ci(i=0，1，2)為權(quán)重系數(shù);tmax為每輛車受燃料限制的最大續(xù)駛時(shí)間;車輛每天的工作時(shí)間記為集合tI={tzgf，twgf，tpf}，其中表示一天之中的早高峰時(shí)段和晚高峰時(shí)段，tpf表示一天之中的平峰時(shí)段，即除去早晚高峰時(shí)段的其它運(yùn)營(yíng)時(shí)段.tksv表示單班每天的運(yùn)營(yíng)時(shí)間，tkdv表示雙班車每天的運(yùn)營(yíng)時(shí)間.

1.3 決策變量

1.4 建立模型

目標(biāo)函數(shù)為

約束條件為

目標(biāo)函數(shù)式(1)表示完成給定時(shí)刻表所需的公交車輛數(shù)、車輛在執(zhí)行車次過(guò)程中的等待時(shí)間及空駛車次時(shí)間三者費(fèi)用之和最小.目標(biāo)函數(shù)式(2)表示最大化車輛的使用效率，即車輛等待時(shí)間占總工作時(shí)間的比例最小.允許單班車在平峰期抽停有助于實(shí)現(xiàn)此目標(biāo).約束條件式(3)表示一輛公交車僅屬于一個(gè)車場(chǎng);式(4)表示給定時(shí)刻表中所有車次都應(yīng)被執(zhí)行;式(5)表示一個(gè)車次只能被一輛公交車執(zhí)行，一輛公交車同時(shí)只能執(zhí)行一個(gè)車次;式(6)表示一輛車從某車場(chǎng)出發(fā)，完成一天中的一系列車次任務(wù)后，收車回到原車場(chǎng);式(7)保證任意時(shí)刻進(jìn)入車場(chǎng)的車輛數(shù)不超過(guò)該車場(chǎng)容量;式(8)表示公交車到達(dá)某一車次起點(diǎn)的時(shí)刻應(yīng)小于等于該車次的發(fā)車時(shí)刻，是某車次被一輛車完成必須滿足的約束條件;式(9)表示車輛在執(zhí)行某公交車次前是否加氣;式(10)表示單班車每天的工作時(shí)間范圍;式(11)表示雙班車每天的工作時(shí)間范圍.

2 最大最小蟻群算法求解區(qū)域公交車輛調(diào)度問(wèn)題

根據(jù)螞蟻“尋找食物”的群體行為，意大利學(xué)者首先提出了蟻群算法.蟻群算法具有正反饋、分布式計(jì)算以及啟發(fā)式搜索等特點(diǎn)，該算法迅速成為眾多學(xué)者的研究焦點(diǎn)，它是求解調(diào)度問(wèn)題、圖著色、圖像處理及資源分配等組合優(yōu)化問(wèn)題的最有效算法之一［15-18］.蟻群算法已經(jīng)在解決旅行商問(wèn)題(TSP)、車輛路徑問(wèn)題(VRP)等獲得了比較理想的結(jié)果.本質(zhì)上，TSP 是VRP 的基本問(wèn)題，而VSP 與VRP 又具有較強(qiáng)相似性，即如果將RVSP 問(wèn)題中的每個(gè)具有固定行駛時(shí)間的車次任務(wù)簡(jiǎn)化為一個(gè)節(jié)點(diǎn)，則RVSP問(wèn)題就可作為一個(gè)VRP 來(lái)求解，因此文中擬用蟻群算法求解RVSP.另外，由于蟻群算法是基于構(gòu)建性的優(yōu)化算法，不是基于鄰域搜索的;而RVSP 問(wèn)題的車次集合劃分特性，使得構(gòu)建性算法較鄰域搜索算法更適用于求解RVSP.

由于基本蟻群算法存在收斂速度慢、易陷入局部最優(yōu)等缺陷，Thomas 等［16-17］提出了最大最小蟻群算法(MMAS)，較好地克服了蟻群算法的缺陷，成為求解離散組合優(yōu)化問(wèn)題最好的蟻群算法之一.所以，文中采用最大最小蟻群算法求解離散組合優(yōu)化問(wèn)題RVSP.

2.1 MMAS 簡(jiǎn)介

MMAS 對(duì)螞蟻算法的改進(jìn)主要體現(xiàn)在以下3點(diǎn):①只對(duì)最優(yōu)解所屬路徑上的信息素進(jìn)行更新，以提高優(yōu)化效率;②為避免搜索停滯，信息素水平被限制于［min，max］區(qū)間內(nèi);③初始時(shí)刻信息素水平設(shè)為max，有利于算法初期螞蟻大范圍的“探索”.

2.2 構(gòu)建問(wèn)題的解

不同于TSP 問(wèn)題，RVSP 的解由螞蟻種群協(xié)作產(chǎn)生，且為群體共同表達(dá)，因此有必要介紹其構(gòu)建機(jī)制.首先定義解的形式和解空間集.區(qū)域公交車輛調(diào)度的MMAS 解是由車次節(jié)點(diǎn)、加氣標(biāo)識(shí)和空駛標(biāo)識(shí)按一定次序組合構(gòu)成，每只螞蟻模擬一輛公交車，蟻群共同協(xié)作完成完整的車次任務(wù).在解的構(gòu)建過(guò)程中，加入時(shí)間軸變量tr.在蟻群協(xié)作機(jī)制中涉及到的集合及算法原理.

1)設(shè)xk(k=1，2，…，N)為車次節(jié)點(diǎn)，S 為總車次集合.S 按尚無(wú)車執(zhí)行車次與已有車執(zhí)行車次劃分為兩個(gè)集合Sa和Sn，滿足以下關(guān)系式:Sa+Sn=S且SaSn=，其中Sn={xi|xiexecutedj，j=1，2，…，ants，i≠j}，ants 為螞蟻總數(shù).

2)螞蟻的禁忌表由兩個(gè)集合構(gòu)成:可執(zhí)行車次集allowed 和已執(zhí)行車次集executed.allowed 和executed 滿足:

由于每個(gè)車次只允許由一輛車執(zhí)行，螞蟻的allowed 集合構(gòu)成如下:式中，pcur為螞蟻當(dāng)前所在的站場(chǎng);當(dāng)allowed=?時(shí)，螞蟻完成其當(dāng)天的車次任務(wù).

3)每個(gè)站場(chǎng)正在等待執(zhí)行任務(wù)的螞蟻集合為NCi(i=1，2，3).

定義第i 條線路初始階段所需的最小螞蟻數(shù)為ai(i=1，2，…，n).在初始階段，按每條線路最小螞蟻數(shù)的要求，將螞蟻置于線路的起始車次上.蟻群的協(xié)作機(jī)制涉及到個(gè)體螞蟻的行為動(dòng)作及群體的協(xié)調(diào)，分為正常選擇車次、加氣、空車調(diào)度3 種，以蟻群中的第i 只螞蟻為例說(shuō)明.

(1)正常選擇車次.螞蟻i 在正常情況下按概率在其allowedi集合中選擇下一車次xj(j≥2)，須滿足

式中，ts(xj)為車次xj的起始時(shí)刻，te(xj－1)為車次xj－1的運(yùn)行時(shí)間.選擇方法在后續(xù)第5 節(jié)中詳細(xì)描述.其后更新executedi及allowedi;并更新其連續(xù)運(yùn)行時(shí)間tcR，i和車次集合Sa和Sn.

(2)加氣.螞蟻存在最大連續(xù)行駛時(shí)間限制.在其完成當(dāng)前車次后按下式對(duì)其狀態(tài)進(jìn)行檢查

式中，tlj為起始站場(chǎng)為pcur的線路j 運(yùn)行時(shí)間;若螞蟻i 滿足式(14)，則對(duì)其進(jìn)行加氣，加氣完成后更新其allowedi，按正常選擇車次的方法在allowedi中選擇下一車次xj(j≥3)，則此車次滿足

式中，tF為加氣時(shí)間，xj－1='fuel'.

(3)空車調(diào)度.為滿足車次執(zhí)行完備性要求，隨著tr的遞增，需要不斷檢測(cè)執(zhí)行時(shí)刻處于［tr+tdh，tr+tH］的車次狀態(tài).即

式中，tdh為站場(chǎng)間的空駛時(shí)間，tH定義為狀態(tài)檢測(cè)的時(shí)間窗口上限.若xiSa則按下列規(guī)則進(jìn)行空車調(diào)度或者增加螞蟻數(shù).

(a1)當(dāng)antk處于車次xi所屬站場(chǎng)時(shí)，antk原先正等待執(zhí)行的車次xl的起始時(shí)刻應(yīng)大于xi的起始時(shí)刻，即ts(xl)≥ts(xi);

(a2)當(dāng)antk處于與班次xi所屬站場(chǎng)不同時(shí)，antk原先正等待執(zhí)行的車次xl的起始時(shí)刻應(yīng)大于xi起始時(shí)刻與調(diào)度時(shí)間之和，即ts(xl)≥ts(xi)+tdh.

antj在完成空車調(diào)度并更新其allowedj集合之后，選擇下一車次并等待執(zhí)行車次xi.同時(shí)定義antj在車次任務(wù)xi的前一個(gè)任務(wù)節(jié)點(diǎn)為'DH'.

(b)當(dāng)antk不滿足上述條件或者?NCj=(j=1，2，3)時(shí)，新增一個(gè)螞蟻用于執(zhí)行車次xi.

同時(shí)，存在單班車與雙班車的區(qū)別.在增加螞蟻以執(zhí)行車次xi時(shí)，若xi滿足:ts(xi)tksv，tksv為單班車激活時(shí)間窗，則增加的螞蟻(公交車)屬性為單班車，且處于激活狀態(tài);當(dāng)單班車執(zhí)行完其當(dāng)前車次任務(wù)xi后，若滿足ts(xi)+te(xi)?tksv，則將該螞蟻(即單班車)的激活標(biāo)識(shí)復(fù)位，即不再處于激活狀態(tài)，無(wú)需選擇下一車次任務(wù)，此為單班車的退出機(jī)制.

2.3 信息素和啟發(fā)式信息

在進(jìn)行局部搜索時(shí)，螞蟻在考慮車次節(jié)點(diǎn)間的信息素濃度的同時(shí)，也會(huì)考慮車次間的等待時(shí)間，因此引入啟發(fā)式信息ηij，定義為車次xi，xj之間等待時(shí)間的倒數(shù)

2.4 信息素更新規(guī)則

最大最小蟻群算法中，每條軌跡上的信息量都限制在［min(t)，max(t)］之間，較好地避免了搜索面的局部停滯.在完成所有車次選擇后，對(duì)信息素進(jìn)行全局更新，信息素更新采用如下規(guī)則［14］

式中，ρ(0 ＜ρ ＜1)表示信息素?fù)]發(fā)系數(shù)，1－ρ 表示信息素的殘留度;ij(t)為t 次迭代路徑(xi，xj)上的信息素濃度;δij(t)是路徑(xi，xj)上信息素的增量，即σ(σ≥0)個(gè)精英種群本次迭代在路徑(xi，xj)留下的信息素之和，其計(jì)算式為

第k 個(gè)精英種群留下的信息素增量為

式中，Q 為種群迭代留下的總信息素，fso-far-best(k，t)為迭代的當(dāng)前最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值.每次迭代完成后，更新max(t)、min(t)的值，其計(jì)算公式為

然后再比較確定最大最小信息素的當(dāng)前值:當(dāng)信息素ij(t)＞max(t)時(shí)，設(shè)置ij(t)=max(t);同理，當(dāng)ij(t)＜min(t)時(shí)，設(shè)置ij(t)=min(t).

2.5 選擇機(jī)制

螞蟻k 按概率在其allowed 空間中選擇下一節(jié)點(diǎn)車次xj.其選擇公式為

2.6 目標(biāo)函數(shù)值

以種群協(xié)作產(chǎn)生的解計(jì)算目標(biāo)函數(shù)值(以種群中第i 只螞蟻為例).

式中，antN為種群最終的螞蟻數(shù)，Timew為車輛總的等待時(shí)間，Timedh為總的空駛時(shí)間，且滿足

2.7 算法步驟

步驟1 各項(xiàng)參數(shù)初始化，迭代次數(shù)gen=1，最大迭代次數(shù)mGen=200，蟻群數(shù)grp=10，蟻群規(guī)模ants=24;

步驟2 蟻群序數(shù)i=1;

步驟3 路徑信息素設(shè)置為 (gen)，當(dāng)gen=1時(shí)，其為初始信息素;將蟻群i 置于各線路最早的車次節(jié)點(diǎn)T(0);同時(shí)蟻群根據(jù)路徑信息素選擇其車次鏈的下一班次節(jié)點(diǎn)T(1);

步驟4 根據(jù)算法原理描述的方法執(zhí)行蟻群i的完整車次鏈(即解Slni(gen))的搜索;

步驟5 對(duì)解Slni(gen)進(jìn)行評(píng)價(jià)，計(jì)算其目標(biāo)函數(shù)值，更新最優(yōu)解，同時(shí)計(jì)算路徑信息素增量Δi(gen);

步驟6 i=i+1;

步驟7 若i＞grp，則將整個(gè)路徑的信息素更新為(gen+1)，轉(zhuǎn)步驟7;否則，轉(zhuǎn)步驟3;

步驟8 gen=gen+1，若gen＞mGen，輸出最優(yōu)解，算法結(jié)束;否則，轉(zhuǎn)步驟2.

3 算例分析

某公交公司擬采取區(qū)域調(diào)度模式經(jīng)營(yíng)6 條公交線路以降低營(yíng)運(yùn)成本，所有的公交線路相關(guān)信息及固定時(shí)刻表信息如表1 和表2 所示，各個(gè)車場(chǎng)之間的車輛空駛時(shí)間信息如表3 所示.已知的相關(guān)線路、車輛參數(shù):早晚高峰時(shí)段分別為［7:00，9:00］、［17:00，19:00］，tmax=480 min，tF=20 min，Cd=25.

表1 公交線路信息Table 1 Bus routes information

表2 線路時(shí)刻表Table 2 Timetable of routes

表3 空駛車次時(shí)間信息Table 3 Time information of deadhead trip

采用C 語(yǔ)言編寫求解RVSP 問(wèn)題的MMAS 程序，默認(rèn)設(shè)置如下相關(guān)參數(shù):mGen=2000，ants=24，grp=10，(0)=max(0)=1.0，α=1，β=2，ρ=0.8，Q=1000，b=20，ai=4 (i=1，2，…，6)，c0=500，c1=1.0，c2=2.5，tH=25 min，=1.經(jīng)過(guò)計(jì)算，得到問(wèn)題的最優(yōu)解目標(biāo)函數(shù)值為29 409，對(duì)應(yīng)的最優(yōu)車輛調(diào)度方案如表4 所示.從表4 中結(jié)果可知:完成370 個(gè)車次任務(wù)總共需派遣42 輛車(從車場(chǎng)A、B、C 初始調(diào)度的車輛數(shù)分別為9、19、14)，其中包含13 輛單班車，經(jīng)加油25 次和空駛63 次，所有車輛的總工作時(shí)間為29149 min、等待時(shí)間為5 459 min、空駛時(shí)間為1180 min.便于對(duì)比分析，文中也編程對(duì)370 個(gè)車次任務(wù)進(jìn)行了車輛全部為雙班車的常規(guī)調(diào)度，調(diào)度結(jié)果如表5 所示.表6 為文中調(diào)度方案與常規(guī)調(diào)度方案的對(duì)比，從表6 數(shù)據(jù)可知:文中調(diào)度方案的車輛等待時(shí)間占總工作時(shí)間比例為18%，而常規(guī)調(diào)度方案為28%，改進(jìn)率達(dá)34%;與常規(guī)調(diào)度方案相比，文中調(diào)度方案可節(jié)省4034 min 的等待時(shí)間(按照一個(gè)司機(jī)每天工作480 min，等于一天可節(jié)省8 個(gè)司機(jī));更重要的是，采取手工駕駛員排班方式(即單班車配1 個(gè)駕駛員;雙班車車次鏈總工作時(shí)間大于8h 需配置2 個(gè)駕駛員，否則僅需1 個(gè)駕駛員)，文中模型所得車輛調(diào)度方案需配置67 個(gè)駕駛員，常規(guī)調(diào)度方案則需81 個(gè)駕駛員，節(jié)省14 個(gè)駕駛員，改進(jìn)率達(dá)17%.由此可見，文中考慮客流時(shí)間分布不均衡特征，采取低平峰期的抽停策略而建立的改進(jìn)區(qū)域公交車輛調(diào)度模型，明顯減少了公交車輛的等待時(shí)間及所需駕駛員人數(shù)，節(jié)省了公交公司運(yùn)營(yíng)開支.

表4 包含單班車的車輛調(diào)度方案1)Table 4 Vehicle scheduling scheme including single duty bus

續(xù)表4

表5 常規(guī)車輛調(diào)度方案Table 5 Conventional vehicle scheduling scheme

續(xù)表5

表6 兩種車輛調(diào)度方案的對(duì)比分析Table 6 Comparison and analysis of two vehicle scheduling schemes

4 結(jié)語(yǔ)

文中考慮實(shí)際公交客流的時(shí)間分布不均衡，相應(yīng)時(shí)刻表也非均衡的特征，以及參與公交區(qū)域調(diào)度的多條線路客流高峰時(shí)間、空間分布集中使得總體客流的高低峰客流量差異進(jìn)一步加大的情況，提出低平峰時(shí)段停運(yùn)部分公交車輛的抽停策略，從“部分班次被某輛車完成”的集合劃分問(wèn)題角度研究RVSP，建立一個(gè)新的區(qū)域公交車輛調(diào)度模型，以所需車輛數(shù)、車輛等待時(shí)間與空駛時(shí)間三者費(fèi)用之和最小為第一目標(biāo)，第二目標(biāo)是要求車輛等待時(shí)間占總工作時(shí)間比例最小，采用MMAS 算法求解該模型.算例結(jié)果顯示，新模型所得含單班車的車輛調(diào)度結(jié)果與全部為雙班車的常規(guī)調(diào)度結(jié)果相比，各個(gè)調(diào)度指標(biāo)均有所改進(jìn)，其中，車輛等待時(shí)間及其所占比重改進(jìn)率分別達(dá)到42%、34%，車輛等待時(shí)間可減少4 034 min(相當(dāng)于一天可節(jié)省8 個(gè)司機(jī)(按8 h制))，更重要的是，文中模型所得車輛調(diào)度方案比常規(guī)車輛調(diào)度方案可少配置14 個(gè)駕駛員，改進(jìn)率達(dá)17%.由此可見，文中考慮客流量差異特征，在低平峰期采取抽停策略建立的改進(jìn)區(qū)域公交車輛調(diào)度模型，明顯減少了公交車輛的等待時(shí)間及駕駛員人數(shù)，節(jié)省了公交公司運(yùn)營(yíng)開支，從而證明文中模型合理、有效.

提高車輛的使用效率是區(qū)域公交車輛調(diào)度的根本目標(biāo).區(qū)域公交車輛和駕駛員的一體化調(diào)度可以進(jìn)一步提高車輛利用率，減少所需駕駛員數(shù)，是下一步的研究方向之一.

［1］鄒迎，李建國(guó).公共交通區(qū)域運(yùn)營(yíng)組織與調(diào)度系統(tǒng)研究［J］.運(yùn)輸系統(tǒng)工程與信息，2003，3(2):38-42.Zou Ying，Li Jian-guo.Research in the regional operation organization and dispatching of public transportation［J］.Journal of Transportation Systems Engineering and Information Technology，2003，3(2):38-42.

［2］王大勇，臧學(xué)運(yùn)，王海星.公交區(qū)域車輛調(diào)度優(yōu)化研究現(xiàn)狀與發(fā)展［J］.北京交通大學(xué)學(xué)報(bào)，2008，32(3):42-45.Wang Da-yong，Zang Xue-yun，Wang Hai-xing.Research on situation and development trend for optimization theory and method of public transit vehicle scheduling problem［J］.Journal of Beijing Jiaotong University，2008，32(3):42-45.

［3］Haghani A，Banihashemi M.A comparative analysis of bus transit vehicle scheduling models［J］.Transportation Research Part B:Methodological，2003，37(4):301-322.

［4］Bertossi A，Carraresi P，Gallo G.On some matching problems arising in vehicle scheduling models［J］.Networks，1987，17:271-281.

［5］Lamatsch A.An approach to vehicle scheduling with depot capacity constraints［C］∥Proceedings of the Fifth international Workshop on Computer-aided Scheduling of Public Transport.Berlin Heidelberg:Springer-Verlag，1992:181-195.

［6］Mesquita M，Paixao J.Multiple depot vehicle scheduling problem:a new heuristic based on quasi-assignment algorithm［C］∥Proceedings of the 5th International Workshop on Computer-aided Scheduling of Public Transport.Berlin Heidelberg:Springer-Verlag，1992:167-180.

［7］Mesquita M，Paixao J.Exact algorithms for the multipledepot vehicle scheduling problem based on multi-commodity network flow type formulations［C］∥Proceedings of the 7th International Conference on Computer-aided Scheduling of Public Transport.Berlin Heidelberg:Springer-Verlag，1999:174-187.

［8］Lobel A.Solving large-scale multiple-depot scheduling problems［C］∥Proceedings of the 7th International Conference on Computer-aided Scheduling of Public Transport.Berlin Heidelberg:Springer-Verlag，1999:193-220.

［9］Haghani A，Banihashemi M.Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints［J］.Transportation Research Part A:Policy and Practice，2002，36(4):309-333.

［10］Kliewer N，Mellouli T，Suhl L.A time-space network based exact optimization model for multi-depot bus scheduling［J］.European Journal of Operational Research，2006，175(3):1616-1627.

［11］劉志剛，申金升.區(qū)域公交時(shí)刻表及車輛調(diào)度雙層規(guī)劃模型［J］.系統(tǒng)工程理論與方法，2007，27(11):

135-141.Liu Zhi-gang，Shen Jin-sheng.Regional bus operation bilevel programming model integrating timetabling and vehicle scheduling ［J］.Systems Engineering-Theory ＆Practice，2007，27(11):135-141.

［12］Wang H，Shen J.Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints［J］.Applied Mathematics and Computation，2007，190(2):1237-1249.

［13］魏明，靳文舟，孫博，求解區(qū)域公交車輛調(diào)度問(wèn)題的蟻群算法研究［J］.公路交通科技，2011，28(6):141-152.Wei Ming，Jin Wen-zhou，Sun Bo.Ant colony Algorithm for regional bus scheduling problem ［J］.Journal of Highway and Transportation Research and Development，2011，28(6):141-152.

［14］Hao X，Jin W，Wei M.Max-min ant system for bus transit multi-depot vehicle scheduling problem with route time constraints［C］∥Proceedings of the World Congress on Intelligent Control and Automation (WCICA).Beijing:Institute of Electrical and Electronics Engineers Inc，2012:555-560.

［15］Dorigo M，Gambardella L M.Ant colonies for the traveling salesman problem ［J］.Biosystems，1997，43(2):73-81.

［16］Thomas Stuztle，Holger Hoos.Max-Min ant system and local search for the traveling salesman problem［C］∥Proceedings of the IEEE Conference on Evolutionary Computation.Indianapolis:IEEE，1997:309-314.

［17］Thomas Stutzle，Holger Hoos.Improvements on the ant system:introducing max-min ant system［C］∥Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms.Wien:Springer-Verlag，1998:245-249.

［18］段海濱.蟻群算法原理及其應(yīng)用［M］.北京:科學(xué)出版社，2005:244-247.