陳定芳 （中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙 410075）

CHEN Dingfang (School of Traffic and Transportation Engineering,Central South University,Changsha 410075,China)

0 引言

編制每日行車(chē)計(jì)劃是城市公交運(yùn)營(yíng)企業(yè)的核心業(yè)務(wù)，科學(xué)合理的行車(chē)計(jì)劃不僅有利于更好地滿足乘客需求，還有利于提高行車(chē)計(jì)劃的執(zhí)行率和調(diào)度效率，從而降低運(yùn)營(yíng)成本。常規(guī)公交行車(chē)計(jì)劃包括發(fā)車(chē)時(shí)刻表、配車(chē)計(jì)劃、排班計(jì)劃三個(gè)部分。

傳統(tǒng)編制常規(guī)公交行車(chē)計(jì)劃主要采用順次化的方法，三個(gè)部分生成步驟是一個(gè)順序過(guò)程，目前針對(duì)這三個(gè)部分眾多學(xué)者分別進(jìn)行了深入研究：對(duì)于行車(chē)時(shí)刻表的研究大多是考慮公交運(yùn)營(yíng)成本和乘客滿意度對(duì)發(fā)車(chē)間隔進(jìn)行分析研究[1-2]；對(duì)于配車(chē)計(jì)劃是以發(fā)車(chē)時(shí)刻表為基礎(chǔ)，綜合考慮公共交通企業(yè)的經(jīng)濟(jì)效益和乘客所得到的服務(wù)，協(xié)調(diào)制定車(chē)輛的車(chē)次鏈計(jì)劃[3-4]；針對(duì)排班計(jì)劃大多以班次最少和運(yùn)營(yíng)總成本最小為目標(biāo)建立數(shù)學(xué)模型，利用列生成算法或啟發(fā)式算法求解編制駕駛員排班計(jì)劃[5]。也有學(xué)者針對(duì)行車(chē)計(jì)劃一體化編制進(jìn)行了研究，大多是假定單車(chē)場(chǎng)以及人、車(chē)數(shù)量相同，以客流需求為基礎(chǔ)生成發(fā)車(chē)時(shí)刻表，然后利用基于準(zhǔn)分配模型的競(jìng)拍算法或集合切割算法求解配車(chē)排班計(jì)劃[6]。

以往在排班計(jì)劃和配車(chē)計(jì)劃編制的研究中是根據(jù)行車(chē)時(shí)刻表求解當(dāng)日最優(yōu)的人、車(chē)配置及人、車(chē)分配計(jì)劃，并將發(fā)車(chē)時(shí)刻表獨(dú)立考慮，忽略了行車(chē)計(jì)劃編制過(guò)程中各部分之間的相關(guān)制約因素。然而，在公交線路營(yíng)運(yùn)中，由于浮動(dòng)變化的客流需求、駕駛員固定的輪休規(guī)則及班型限制和車(chē)輛續(xù)航里程的限制，即使公交企業(yè)給公交線路配置好最優(yōu)的人、車(chē)資源，也可能存在某天會(huì)出現(xiàn)人、車(chē)資源供給小于或大于需求的情況，人、車(chē)資源與需求難以每天均實(shí)現(xiàn)最優(yōu)匹配，當(dāng)人、車(chē)資源供給與需求沒(méi)有達(dá)到最優(yōu)匹配時(shí)該如何更合理地編制行車(chē)計(jì)劃是一個(gè)實(shí)際有待研究與解決的問(wèn)題。因此本文提出一種綜合考慮車(chē)輛續(xù)行里程、駕駛員的各種班型共存、人車(chē)綁定關(guān)系等約束的公共交通行車(chē)計(jì)劃一體化編制方法。

本文提出的公交行車(chē)計(jì)劃一體化編制方法是在生成時(shí)刻表時(shí)綜合考慮客流需求和線路現(xiàn)有的人、車(chē)資源約束，再將得到的行車(chē)時(shí)刻表作為營(yíng)運(yùn)基礎(chǔ)同時(shí)考慮包乘制下人、車(chē)綁定關(guān)系集成調(diào)度生成排班計(jì)劃和配車(chē)計(jì)劃。

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

1.1 問(wèn)題提出

本文研究的是在公交企業(yè)現(xiàn)有資源（人、車(chē)）約束要求下盡可能的滿足客流需求生成行車(chē)時(shí)刻表，然后以行車(chē)時(shí)刻表為基礎(chǔ)，以滿足運(yùn)營(yíng)目標(biāo)和人員、車(chē)輛有效工作時(shí)間最大化為宗旨，綜合考慮駕駛員狀態(tài)、車(chē)輛狀態(tài)、人車(chē)線關(guān)系（包乘制）等約束條件，編制配車(chē)排班計(jì)劃。該問(wèn)題的約束條件有：

（1）每個(gè)車(chē)次有且僅有一位駕駛員和一輛車(chē)執(zhí)行；

（2）每一位駕駛員和每一輛車(chē)同一時(shí)間只能執(zhí)行一個(gè)車(chē)次工作；

（3）同一個(gè)駕駛員的兩個(gè)連續(xù)車(chē)次之間發(fā)車(chē)時(shí)間間隔的限制；

（4）駕駛員的班制班型及對(duì)應(yīng)的班型時(shí)段（發(fā)車(chē)時(shí)刻需在班型時(shí)段內(nèi)）；

（5）包乘制下的人車(chē)關(guān)系限制；

（6）所有車(chē)都由車(chē)場(chǎng)駛至線路首末站開(kāi)始營(yíng)運(yùn)，營(yíng)運(yùn)結(jié)束后需回到車(chē)場(chǎng)。

1.2 模型搭建

行車(chē)計(jì)劃的編制可描述為營(yíng)運(yùn)任務(wù)（行車(chē)時(shí)刻表）的生成和分配任務(wù)（配車(chē)排班）兩大部分。

1.2.1 行車(chē)時(shí)刻表編制模型

行車(chē)時(shí)刻表的編制實(shí)質(zhì)是確定發(fā)車(chē)間隔。本文是以公交企業(yè)資源一定為約束，盡可能地滿足客流需求為目標(biāo)建立模型，用以確定各時(shí)段的發(fā)車(chē)間隔，是以最大化滿足客流需求為目標(biāo)，即客流需求與公交營(yíng)運(yùn)供給之間差值的絕對(duì)值最小為目標(biāo)，如下所示：

式中：ti為i時(shí)段的發(fā)車(chē)間隔；Fmaxi為i時(shí)段最大斷面小時(shí)客流量；C為車(chē)容量；ρi為i時(shí)段內(nèi)的期望滿載率。

同時(shí)需要滿足以下約束條件：

（1）為保證公共交通企業(yè)的利益，線路時(shí)段的小時(shí)承載力不得大于線路時(shí)段的最大斷面小時(shí)客流量，以免造成運(yùn)力的浪費(fèi)。

（2）每個(gè)發(fā)車(chē)時(shí)刻代表一次工作任務(wù)的起點(diǎn)，在此問(wèn)題中所有生成的任務(wù)都需要被完成，故根據(jù)發(fā)車(chē)間隔計(jì)算出的i時(shí)段配車(chē)數(shù)不得大于i時(shí)段線路上班人數(shù)。

（3）線路營(yíng)運(yùn)任務(wù)總里程不得超出所有營(yíng)運(yùn)車(chē)輛的可營(yíng)運(yùn)續(xù)航里程總和，反之則有營(yíng)運(yùn)任務(wù)無(wú)法完成。

式中：L1,L2為上、下行營(yíng)運(yùn)里程；為i時(shí)段上、下行的營(yíng)運(yùn)任務(wù)數(shù)即營(yíng)運(yùn)車(chē)次數(shù)；m為線路時(shí)段數(shù)；lh為營(yíng)運(yùn)車(chē)輛h的可營(yíng)運(yùn)續(xù)航里程；a為所有營(yíng)運(yùn)車(chē)輛。

式中：hi為i時(shí)段的時(shí)段長(zhǎng)度。

lh由營(yíng)運(yùn)車(chē)輛h自身的續(xù)航里程和其綁定駕駛員的班型共同決定。若車(chē)輛h自身的續(xù)航里程減去車(chē)輛從停車(chē)場(chǎng)到首末站的b個(gè)往返里程大于其綁定駕駛員的班型總估計(jì)最大車(chē)次數(shù)的總營(yíng)運(yùn)里程數(shù)（其中b為車(chē)輛h綁定的駕駛員人數(shù)），且車(chē)輛h的營(yíng)運(yùn)車(chē)次必須由其綁定駕駛員完成，則車(chē)輛h的可營(yíng)運(yùn)續(xù)航里程為其綁定駕駛員的班型總估計(jì)最大車(chē)次數(shù)的總營(yíng)運(yùn)里程數(shù)；反之，車(chē)輛h的可營(yíng)運(yùn)續(xù)航里程由其自身的續(xù)航里程所決定。具體關(guān)系如下：

式中：lzh為車(chē)輛h自身續(xù)航里程；l為車(chē)輛從停車(chē)場(chǎng)到首末站的1個(gè)往返里程；Dh為車(chē)輛h綁定駕駛員的班型總估計(jì)最大車(chē)次數(shù)的總營(yíng)運(yùn)里程數(shù)，每位駕駛員的班型估計(jì)最大車(chē)次數(shù)的總營(yíng)運(yùn)里程數(shù)由其班型時(shí)段和時(shí)段上、下行單程行程時(shí)長(zhǎng)以及上、下行營(yíng)運(yùn)里程共同決定。

（4）時(shí)段發(fā)車(chē)間隔應(yīng)不大于行政法規(guī)、標(biāo)準(zhǔn)規(guī)定的各地方各時(shí)段的最大發(fā)車(chē)間隔。

式中：tmaxi為i時(shí)段的法定最大發(fā)車(chē)間隔。

1.2.2 配車(chē)排班計(jì)劃編制模型

本文是在行車(chē)時(shí)刻表的基礎(chǔ)上，合理地生成駕駛員的班次鏈，再根據(jù)固定的人車(chē)關(guān)系生成所有的車(chē)次鏈。此問(wèn)題中，營(yíng)運(yùn)任務(wù)一定且完成每一營(yíng)運(yùn)任務(wù)的成本固定，配車(chē)排班計(jì)劃對(duì)營(yíng)運(yùn)成本影響不大但對(duì)駕駛員的有效工作時(shí)間比影響較大，因此本文將總的有效工作時(shí)間比最大化作為計(jì)劃編制的目標(biāo)：

式中：xjk為決策變量，表示駕駛員j是否選中營(yíng)運(yùn)車(chē)次k；tdk為營(yíng)運(yùn)車(chē)次k的單程行程時(shí)間長(zhǎng)；Tj表示駕駛員j的在班時(shí)間，即為上班簽到至下班簽退的時(shí)段長(zhǎng)度；K為所有營(yíng)運(yùn)車(chē)次；Q為所有營(yíng)運(yùn)駕駛員。

同時(shí)需要滿足以下約束條件：

（1）確保每個(gè)營(yíng)運(yùn)車(chē)次k都能且僅能被一位駕駛員、一輛營(yíng)運(yùn)車(chē)輛所覆蓋。

式中：yhk為決策變量，表示營(yíng)運(yùn)車(chē)輛h是否選中營(yíng)運(yùn)車(chē)次k；H為所有營(yíng)運(yùn)車(chē)輛。

（2）每位駕駛員選中的營(yíng)運(yùn)車(chē)次的總里程數(shù)，不得超過(guò)駕駛員對(duì)應(yīng)車(chē)輛的總續(xù)航里程數(shù)。

式中：lh為營(yíng)運(yùn)車(chē)輛h的可營(yíng)運(yùn)續(xù)航里程數(shù)；Lk為營(yíng)運(yùn)車(chē)次k的營(yíng)運(yùn)里程數(shù)；H（）j為駕駛員j對(duì)應(yīng)的所有車(chē)輛。

（3）每位駕駛員的班次鏈中的每相鄰兩車(chē)次之間的最小時(shí)間間隔約束，以保證每位駕駛員能夠在其每一任務(wù)開(kāi)始前到達(dá)任務(wù)開(kāi)始地點(diǎn)。

式中：tfc、tfk為營(yíng)運(yùn)車(chē)次c、k的發(fā)車(chē)時(shí)間；tdk為營(yíng)運(yùn)車(chē)次k的單程行程時(shí)長(zhǎng)；xjck為駕駛員j是否完成營(yíng)運(yùn)車(chē)次k之后又將開(kāi)始營(yíng)運(yùn)車(chē)次c；tzk為營(yíng)運(yùn)車(chē)次k營(yíng)運(yùn)結(jié)束后的適當(dāng)駐站時(shí)間。

（4）每位駕駛員的所承擔(dān)的營(yíng)運(yùn)車(chē)次的發(fā)車(chē)時(shí)刻都應(yīng)該在其班型時(shí)段內(nèi)。

式中：tfk為營(yíng)運(yùn)車(chē)次k的發(fā)車(chē)時(shí)間；Tj1、Tj2為駕駛員j的上班時(shí)段的開(kāi)始時(shí)間、結(jié)束時(shí)間。

（5）駕駛員j所承擔(dān)的營(yíng)運(yùn)車(chē)次k都能且僅能被與駕駛員j有綁定人車(chē)關(guān)系的一輛營(yíng)運(yùn)車(chē)輛選中。

（6）定義決策變量為0-1整數(shù)變量，即表示不選中、選中。

2 求解算法

2.1 行車(chē)時(shí)刻表部分

本文中行車(chē)時(shí)刻表的編制是在資源一定的情況下盡可能的滿足客流需求。在資源充足的情形下，各時(shí)段發(fā)車(chē)間隔是滿足客流需求下的最大發(fā)車(chē)間隔；在資源缺乏的情形下，各時(shí)段發(fā)車(chē)間隔是資源充分使用下的最小發(fā)車(chē)間隔，可根據(jù)需要設(shè)定決策目標(biāo)，本文以乘客總等待時(shí)間增加量最小為目標(biāo)來(lái)采取策略調(diào)整發(fā)車(chē)間隔。具體計(jì)算步驟如下所示：

Step1：根據(jù)數(shù)學(xué)公式計(jì)算滿足客流需求下各時(shí)段的最大發(fā)車(chē)間隔。

式中：tigmaxi為滿足客流需求下時(shí)段i的最大發(fā)車(chē)間隔。

Step2：判斷線路各時(shí)段營(yíng)運(yùn)駕駛員人數(shù)Pi是否大于等于各時(shí)段發(fā)車(chē)間隔為tjgmaxi時(shí)各時(shí)段所需要的最小營(yíng)運(yùn)駕駛員數(shù)Pmini，

其中：

（1） 若判斷為是，則進(jìn)入step3；

（2）若判斷為否，則表示存在時(shí)段i的人車(chē)資源不能完全滿足客流需求，同時(shí)需根據(jù)駕駛員資源調(diào)整時(shí)段i的發(fā)車(chē)間隔。將不能滿足Pi≥Pmini的時(shí)段i的發(fā)車(chē)間隔重新計(jì)算，具體如下：

Step3：判斷所有營(yíng)運(yùn)車(chē)輛的可營(yíng)運(yùn)續(xù)航里程總和是否大于等于各時(shí)段發(fā)車(chē)間隔為tjgmaxi時(shí)線路營(yíng)運(yùn)任務(wù)總里程。

（1）若判斷為是，則發(fā)車(chē)間隔的計(jì)算完成，ti=tjgmaxi，并輸出發(fā)車(chē)時(shí)刻表。

（2）若判斷為否，則采取乘客總等待時(shí)間增加量最小為目標(biāo)來(lái)采取策略調(diào)整部分時(shí)段i的發(fā)車(chē)間隔。具體調(diào)整步驟如下所示：

①計(jì)算需要減少的車(chē)次數(shù)nj。

②假設(shè)每個(gè)時(shí)段都減少nj，各時(shí)段的發(fā)車(chē)間隔將調(diào)整為同時(shí)判斷是否存在tjgtzi≥tmaxi。若判斷為是，令tjgtzi≤tmaxi對(duì)應(yīng)的tjgtzi=tmaxi，其余tjgtzi=tjgtzi；若判斷為否，令tjgtzi=tjgtzi。③計(jì)算（Fi為時(shí)段i的乘客人數(shù)），令最小的Ttzi對(duì)應(yīng)的i時(shí)段的tjgmaxi=tjgtzi，其他時(shí)段i對(duì)應(yīng)的tjgmaxi=jgmaxi，并重復(fù)step3，直至輸出發(fā)車(chē)時(shí)刻表停止。

2.2 配車(chē)排班部分

配車(chē)、排班問(wèn)題是一個(gè)非常復(fù)雜的組合優(yōu)化問(wèn)題，且被世界公認(rèn)為NP難問(wèn)題，通常采用列生成法和啟發(fā)式算法求解。本文采用矩陣式編碼遺傳算法求解該問(wèn)題，每一行代表一個(gè)營(yíng)運(yùn)車(chē)次，每一列代表一位駕駛員，如此可設(shè)定每一個(gè)營(yíng)運(yùn)車(chē)次和每一位駕駛員的相關(guān)屬性更加簡(jiǎn)單便捷的添加約束條件，解決多種班型駕駛員共存的問(wèn)題。目標(biāo)函數(shù)作為適應(yīng)度值。編碼方式如下：

矩陣編碼方法是將矩陣整體作為遺傳子代個(gè)體，不需要將矩陣展開(kāi)成一串元素，能確保子代個(gè)體基因的完整性。

若矩陣Ai為m×n階矩陣，遺傳子代第k代種群Pk個(gè)體的數(shù)目為｝表示該種群，其中：）稱為矩陣染色體的基因元素

3 模擬計(jì)算與結(jié)果分析

實(shí)例數(shù)據(jù)說(shuō)明：由客流需求、駕駛員班型及駕駛員綁定的車(chē)輛續(xù)行里程根據(jù)行車(chē)時(shí)刻表求解算法得到258個(gè)營(yíng)運(yùn)車(chē)次。其中駕駛員人數(shù)有31個(gè)，駕駛員班型有10個(gè)上午班、10個(gè)下午班和11個(gè)單班三種。

情形1：當(dāng)駕駛員綁定的車(chē)輛續(xù)航里程無(wú)限大，即車(chē)輛的可營(yíng)運(yùn)續(xù)航里程為其綁定駕駛員的班型總估計(jì)最大車(chē)次數(shù)的總營(yíng)運(yùn)里程數(shù)時(shí)，以已生成的行車(chē)時(shí)刻表為基礎(chǔ)，配車(chē)排班算法獨(dú)立實(shí)驗(yàn)10次生成的滿意解的最大值與最小值如圖1、圖2所示。

從圖1、圖2中可看出在10次獨(dú)立實(shí)驗(yàn)中最后生成的滿意解的適應(yīng)度最大值與最小值的差值為0.00523，在此實(shí)例中每位駕駛員的平均在班時(shí)間約為8小時(shí)，可計(jì)算出這兩次獨(dú)立實(shí)驗(yàn)中平均每位駕駛員一天的空閑時(shí)間差值僅約為2.5min，31位駕駛員一天總的空閑時(shí)間相差77.8min，兩次獨(dú)立實(shí)驗(yàn)的差異很小。由此可見(jiàn)該算法的魯棒性較好，結(jié)果穩(wěn)定。

情形2：將此實(shí)例中的部分車(chē)輛續(xù)行里程進(jìn)行限制，并且此部分車(chē)輛的可營(yíng)運(yùn)續(xù)航里程由其自身的續(xù)航里程所決定，但可以完成已生成的258個(gè)營(yíng)運(yùn)車(chē)次，此時(shí)算法運(yùn)算結(jié)果的適應(yīng)度值迭代情況如圖3所示。

對(duì)比圖1和圖3可見(jiàn)其最大適應(yīng)度值相差僅為0.0083，31位駕駛員一天總的空閑時(shí)間相差約123.5min，且適應(yīng)度值有略微下降。這是因?yàn)楫?dāng)車(chē)輛續(xù)航里程受到限制但駕駛員、車(chē)輛資源能滿足線路整天的營(yíng)運(yùn)要求時(shí)，與情形1比較這部分駕駛員的營(yíng)運(yùn)車(chē)次會(huì)減少，為保證線路營(yíng)運(yùn)高峰時(shí)段駕駛員的供給，這部分駕駛員需減少在非高峰時(shí)段的營(yíng)運(yùn)車(chē)次并在首末站做更長(zhǎng)等待。

情形3：將部分車(chē)輛的續(xù)航里程進(jìn)行限制且不能完成已生成的258個(gè)營(yíng)運(yùn)車(chē)次，本文討論在完成同樣營(yíng)運(yùn)車(chē)次下車(chē)輛續(xù)航里程對(duì)駕駛員有效工作時(shí)間比的影響，故在此對(duì)這一部分駕駛員做多綁定一輛車(chē)的處理以保證行車(chē)時(shí)刻表中營(yíng)運(yùn)任務(wù)的完成，并設(shè)定車(chē)場(chǎng)與線路首末站之間來(lái)回一趟約40min，此時(shí)算法運(yùn)算結(jié)果的適應(yīng)度值迭代情況如圖4所示。

對(duì)比圖1和圖4可見(jiàn)其最大適應(yīng)度值相差為0.0225，31位駕駛員一天總的空閑時(shí)間相差約334.8min，且適應(yīng)度值有較大下降。這是因?yàn)楸疚闹杏懻摰挠行Чぷ鲿r(shí)間比是參與營(yíng)運(yùn)的時(shí)間與在班時(shí)間的比值，而駕駛員到車(chē)場(chǎng)進(jìn)行換車(chē)的這一行為產(chǎn)生的車(chē)次為非營(yíng)運(yùn)車(chē)次，非營(yíng)運(yùn)時(shí)間的增加會(huì)降低駕駛員的有效工作時(shí)間比。

圖1 不受車(chē)輛續(xù)航里程限制時(shí)滿意解適應(yīng)度最大值

圖2 不受車(chē)輛續(xù)航里程限制時(shí)滿意解適應(yīng)度最小值

圖3 情形2下的適應(yīng)度值迭代情況

圖4 情形3下的適應(yīng)度值迭代情況

4 結(jié)論

本文提出了一種考慮車(chē)輛續(xù)行里程、駕駛員各種班型、人車(chē)綁定關(guān)系等約束將行車(chē)時(shí)刻表、配車(chē)計(jì)劃、排班計(jì)劃統(tǒng)一協(xié)調(diào)編制的常規(guī)公共交通行車(chē)計(jì)劃一體化編制方法，并分別采用貪婪算法和矩陣編碼式遺傳算法有效地對(duì)行車(chē)時(shí)刻表、配車(chē)排班計(jì)劃進(jìn)行求解。能夠有效地將公交線路現(xiàn)有資源與客流需求有機(jī)統(tǒng)一、協(xié)調(diào)分配，同時(shí)減少駕駛員的空閑休息時(shí)間，提高駕駛員有效工作時(shí)間比。通過(guò)實(shí)例對(duì)比分析發(fā)現(xiàn)車(chē)輛的續(xù)行里程對(duì)駕駛員的有效工作時(shí)間比有一定的影響，具體的影響方式和程度，以及考慮此種影響下如何更小營(yíng)運(yùn)成本的配置不同續(xù)行里程的車(chē)輛可進(jìn)行進(jìn)一步研究。