考慮車輛續航里程的公交行車計劃編制方法研究

陳定芳 （中南大學 交通運輸工程學院，湖南 長沙 410075）

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

0 引言

編制每日行車計劃是城市公交運營企業的核心業務，科學合理的行車計劃不僅有利于更好地滿足乘客需求，還有利于提高行車計劃的執行率和調度效率，從而降低運營成本。常規公交行車計劃包括發車時刻表、配車計劃、排班計劃三個部分。

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

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

本文提出的公交行車計劃一體化編制方法是在生成時刻表時綜合考慮客流需求和線路現有的人、車資源約束，再將得到的行車時刻表作為營運基礎同時考慮包乘制下人、車綁定關系集成調度生成排班計劃和配車計劃。

1 問題描述與建模

1.1 問題提出

本文研究的是在公交企業現有資源（人、車）約束要求下盡可能的滿足客流需求生成行車時刻表，然后以行車時刻表為基礎，以滿足運營目標和人員、車輛有效工作時間最大化為宗旨，綜合考慮駕駛員狀態、車輛狀態、人車線關系（包乘制）等約束條件，編制配車排班計劃。該問題的約束條件有：

（1）每個車次有且僅有一位駕駛員和一輛車執行；

（2）每一位駕駛員和每一輛車同一時間只能執行一個車次工作；

（3）同一個駕駛員的兩個連續車次之間發車時間間隔的限制；

（4）駕駛員的班制班型及對應的班型時段（發車時刻需在班型時段內）；

（5）包乘制下的人車關系限制；

（6）所有車都由車場駛至線路首末站開始營運，營運結束后需回到車場。

1.2 模型搭建

行車計劃的編制可描述為營運任務（行車時刻表）的生成和分配任務（配車排班）兩大部分。

1.2.1 行車時刻表編制模型

行車時刻表的編制實質是確定發車間隔。本文是以公交企業資源一定為約束，盡可能地滿足客流需求為目標建立模型，用以確定各時段的發車間隔，是以最大化滿足客流需求為目標，即客流需求與公交營運供給之間差值的絕對值最小為目標，如下所示：

式中：ti為i時段的發車間隔；Fmaxi為i時段最大斷面小時客流量；C為車容量；ρi為i時段內的期望滿載率。

同時需要滿足以下約束條件：

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

（2）每個發車時刻代表一次工作任務的起點，在此問題中所有生成的任務都需要被完成，故根據發車間隔計算出的i時段配車數不得大于i時段線路上班人數。

（3）線路營運任務總里程不得超出所有營運車輛的可營運續航里程總和，反之則有營運任務無法完成。

式中：L1,L2為上、下行營運里程；為i時段上、下行的營運任務數即營運車次數；m為線路時段數；lh為營運車輛h的可營運續航里程；a為所有營運車輛。

式中：hi為i時段的時段長度。

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

式中：lzh為車輛h自身續航里程；l為車輛從停車場到首末站的1個往返里程；Dh為車輛h綁定駕駛員的班型總估計最大車次數的總營運里程數，每位駕駛員的班型估計最大車次數的總營運里程數由其班型時段和時段上、下行單程行程時長以及上、下行營運里程共同決定。

（4）時段發車間隔應不大于行政法規、標準規定的各地方各時段的最大發車間隔。

式中：tmaxi為i時段的法定最大發車間隔。

1.2.2 配車排班計劃編制模型

本文是在行車時刻表的基礎上，合理地生成駕駛員的班次鏈，再根據固定的人車關系生成所有的車次鏈。此問題中，營運任務一定且完成每一營運任務的成本固定，配車排班計劃對營運成本影響不大但對駕駛員的有效工作時間比影響較大，因此本文將總的有效工作時間比最大化作為計劃編制的目標：

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

同時需要滿足以下約束條件：

（1）確保每個營運車次k都能且僅能被一位駕駛員、一輛營運車輛所覆蓋。

式中：yhk為決策變量，表示營運車輛h是否選中營運車次k；H為所有營運車輛。

（2）每位駕駛員選中的營運車次的總里程數，不得超過駕駛員對應車輛的總續航里程數。

式中：lh為營運車輛h的可營運續航里程數；Lk為營運車次k的營運里程數；H（）j為駕駛員j對應的所有車輛。

（3）每位駕駛員的班次鏈中的每相鄰兩車次之間的最小時間間隔約束，以保證每位駕駛員能夠在其每一任務開始前到達任務開始地點。

式中：tfc、tfk為營運車次c、k的發車時間；tdk為營運車次k的單程行程時長；xjck為駕駛員j是否完成營運車次k之后又將開始營運車次c；tzk為營運車次k營運結束后的適當駐站時間。

（4）每位駕駛員的所承擔的營運車次的發車時刻都應該在其班型時段內。

式中：tfk為營運車次k的發車時間；Tj1、Tj2為駕駛員j的上班時段的開始時間、結束時間。

（5）駕駛員j所承擔的營運車次k都能且僅能被與駕駛員j有綁定人車關系的一輛營運車輛選中。

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

2 求解算法

2.1 行車時刻表部分

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

Step1：根據數學公式計算滿足客流需求下各時段的最大發車間隔。

式中：tigmaxi為滿足客流需求下時段i的最大發車間隔。

Step2：判斷線路各時段營運駕駛員人數Pi是否大于等于各時段發車間隔為tjgmaxi時各時段所需要的最小營運駕駛員數Pmini，

其中：

（1） 若判斷為是，則進入step3；

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

Step3：判斷所有營運車輛的可營運續航里程總和是否大于等于各時段發車間隔為tjgmaxi時線路營運任務總里程。

（1）若判斷為是，則發車間隔的計算完成，ti=tjgmaxi，并輸出發車時刻表。

（2）若判斷為否，則采取乘客總等待時間增加量最小為目標來采取策略調整部分時段i的發車間隔。具體調整步驟如下所示：

①計算需要減少的車次數nj。

②假設每個時段都減少nj，各時段的發車間隔將調整為同時判斷是否存在tjgtzi≥tmaxi。若判斷為是，令tjgtzi≤tmaxi對應的tjgtzi=tmaxi，其余tjgtzi=tjgtzi；若判斷為否，令tjgtzi=tjgtzi。③計算（Fi為時段i的乘客人數），令最小的Ttzi對應的i時段的tjgmaxi=tjgtzi，其他時段i對應的tjgmaxi=jgmaxi，并重復step3，直至輸出發車時刻表停止。

2.2 配車排班部分

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

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

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

3 模擬計算與結果分析

實例數據說明：由客流需求、駕駛員班型及駕駛員綁定的車輛續行里程根據行車時刻表求解算法得到258個營運車次。其中駕駛員人數有31個，駕駛員班型有10個上午班、10個下午班和11個單班三種。

情形1：當駕駛員綁定的車輛續航里程無限大，即車輛的可營運續航里程為其綁定駕駛員的班型總估計最大車次數的總營運里程數時，以已生成的行車時刻表為基礎，配車排班算法獨立實驗10次生成的滿意解的最大值與最小值如圖1、圖2所示。

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

情形2：將此實例中的部分車輛續行里程進行限制，并且此部分車輛的可營運續航里程由其自身的續航里程所決定，但可以完成已生成的258個營運車次，此時算法運算結果的適應度值迭代情況如圖3所示。

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

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

對比圖1和圖4可見其最大適應度值相差為0.0225，31位駕駛員一天總的空閑時間相差約334.8min，且適應度值有較大下降。這是因為本文中討論的有效工作時間比是參與營運的時間與在班時間的比值，而駕駛員到車場進行換車的這一行為產生的車次為非營運車次，非營運時間的增加會降低駕駛員的有效工作時間比。

圖1 不受車輛續航里程限制時滿意解適應度最大值

圖2 不受車輛續航里程限制時滿意解適應度最小值

圖3 情形2下的適應度值迭代情況

圖4 情形3下的適應度值迭代情況

4 結論

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