陳孫延 沈瑩瑩 仇佳輝

摘要：在經(jīng)濟高速發(fā)展的當(dāng)今社會，城市交通壓力陡增，公交系統(tǒng)對于滿足人們的出行需求，緩解城市交通壓力發(fā)揮著無可替代的作用。文章對于公交車排班問題進行研究，力求使用最少的公交車數(shù)量來滿足不同時間段內(nèi)的運營要求，提高公交車排班的合理化，合理配置有限的資源以促進經(jīng)濟社會的發(fā)展。文章中模型的建立以考慮公交車成本、乘客候車成本為基礎(chǔ)：問題一，在理論研究中，公交車排班問題便可看作資源的合理分配問題。在一定的約束條件下，合理安排有限的公交車的資源即運行車輛數(shù)、運行時間的調(diào)度方法確定其先后順序，采用優(yōu)化模型，以獲得時間的最優(yōu)化。求得徐州市2路公交車在早高峰時段（6：00～8：00）運行所需要使用的最少公交車數(shù)量為16輛。問題二，在滿足乘客需求的情況下，尋求乘客等待時間最少和運營成本最低的平衡點，以上述兩個方面為目標(biāo)的公交車排班方案，采用最少的公交車數(shù)量盡量減少了運營投入。此問題為多目標(biāo)優(yōu)化問題，采用多元線性規(guī)劃進行求解。求得徐州市2路公交車完成一整天的運行所需要最少的公交車的數(shù)量為雙班車21輛，單班車0輛。問題三，在問題二的基礎(chǔ)上，要求單班車不少于3輛。在問題二已建立的模型上增加約束條件，使一整天運行所需的公交數(shù)量最少。求得徐州市2路公交車完成一整天的運行所需要最少的公交車的數(shù)量為單班車3輛，雙班車18輛。問題四，相比問題一、二、三，更為貼近實際情況，其主要的數(shù)學(xué)思想在根本上是一致的，仍然為多元線性規(guī)劃優(yōu)化思想。采用搭建了主要的模型后，增加相應(yīng)的約束條件并進行結(jié)合實際情況的調(diào)整的方法，求得徐州市2路公交車完成一整天的運行所需要最少的公交車的數(shù)量為單班車4輛，雙班車19輛。

關(guān)鍵詞：公交車排班問題；多元線性規(guī)劃；優(yōu)化模型

一、問題重述

（一）引言

隨著經(jīng)濟社會不斷發(fā)展，人們的出行需求迅猛增長，公交系統(tǒng)的作用日益凸顯，同時也面臨著前所未有的挑戰(zhàn)。城市的公交系統(tǒng)的優(yōu)化可以緩解城市交通壓力，有利于節(jié)能減排低碳發(fā)展，同時也可以減輕公交車司機的工作負(fù)荷，避免疲勞駕駛，提高司機師傅的工作滿意度。合理編排公交車行車計劃，既符合城市公交集團人性化管理的要求，也符合提高公交車運營效率和服務(wù)質(zhì)量的重要舉措。

（二）問題的提出

現(xiàn)代社會的發(fā)展對城市公交系統(tǒng)的完善提出了進一步的要求。通過合理編排公交車的行車計劃，可以更好地服務(wù)于城市居民，更好地服務(wù)于經(jīng)濟社會的發(fā)展，從而達到經(jīng)濟效益和社會效益的統(tǒng)一。如何使用最少數(shù)量的公交車來滿足不同時間段內(nèi)運營要求，在深入理解公交業(yè)務(wù)需求和客運行業(yè)特點的基礎(chǔ)上，將題設(shè)問題抽象成一個明確、完整的數(shù)學(xué)模型，對模型進行求解，立足實際，設(shè)計出最優(yōu)的排班方案。

在該問題中，公交車公司采用單班車和雙班車進行排班，駕駛員工作時間有限，公交車的行車信息表已知，如何在滿足乘車需求的基礎(chǔ)之上，在一定時間內(nèi)采用最少數(shù)量的公交車進行排班運營。

二、問題分析

本題以簡單的環(huán)路公交路線為例，即公交車從A點出發(fā)，經(jīng)過一系列站點后再次回到A點為1個班次。1輛公交車從起點出發(fā)到達終點停止為1個班次。公交車公司有兩種類型的班車：單班車和雙班車。通常情況下，均可以用于排班。

單班車：由同一個駕駛員駕駛的公交車。單班車通常要求在早高峰跑2～3個班次，晚高峰2～3個班次，一天不超過5個班次。

雙班車：由兩個駕駛員駕駛的公交車。雙班車要求上、下午各一個司機，上午和下午司機的工作時間盡可能均勻，并且都不超過8小時。每輛雙班車一天運行不超過10個班次。

（一）問題一分析

考慮到一輛公交車在早高峰時段內(nèi)能夠運行不止1次的班次，因此班次的數(shù)量并不能準(zhǔn)確地對應(yīng)所需公交車的數(shù)量。由于早高峰時段的時間長度有限，在合理的模型假設(shè)的前提即忽略其他因素的條件下，本文利用簡單的時間軸分析出運行過程中實際需要的車輛數(shù)為6：00～7：20這一時間段內(nèi)發(fā)出的公交車數(shù)。同時，由于在早高峰時段內(nèi)單雙班車并無區(qū)別，只是當(dāng)單班車運行時需要運行2個班次。由分析可知，單班車和雙班車的具體數(shù)量是有多組可行解的。

（二）問題二分析

所謂排班問題就是為了某一目的面對共同使用的資源實行時間分配，通?？杀硎緸樵谝唤M或幾組不等式的約束條件下，求解目標(biāo)函數(shù)的優(yōu)化。城市公交車輛運輸系統(tǒng)相應(yīng)的排班問題有如下特點：每輛公交車在一整天的運行過程中只遵循一種運行模式，不會中途變化；每輛車按時發(fā)出，根據(jù)不同的運行時段，準(zhǔn)時完成運行任務(wù)。

問題二要求給出徐州市2路公交車完成一整天的運行所需要最少的公交車數(shù)，其數(shù)學(xué)模型采用的優(yōu)化指標(biāo)為：在不影響乘客出行的前提下，乘客的等待時間和公交車運行班次最少，并避免出現(xiàn)較大的發(fā)車時間間隔，采用多元線性規(guī)劃模型解決公交車排班問題。

（三）問題三分析

問題在的模型按照題中所提要求即在問題二建立的模型的基礎(chǔ)上增加相應(yīng)的約束條件?？紤]到實際問題的現(xiàn)實性，因此在增加約束條件得到相應(yīng)的額可行解后，還應(yīng)按照實際條件做出調(diào)整。

（四）問題四分析

拋開問題一、二、三的限制，建立一個更為貼近實際的數(shù)學(xué)模型，但同時又是在研究完上述問題的基礎(chǔ)上建立模型，其主要的數(shù)學(xué)思想在根本上是一致的，仍然為多元線性規(guī)劃優(yōu)化思想。搭建了主要的模型后，增加相應(yīng)的約束條件并進行貼近實際的調(diào)整，最終得到數(shù)學(xué)模型的現(xiàn)實求解。

三、模型假設(shè)

影響公交車排班的因素眾多，且其中很多因素都是隨機的，為研究造成了諸多不便。為了抓住重點，簡化模型的建立與求解，現(xiàn)作出以下的假設(shè)：在同一時間段內(nèi)，相鄰兩車的發(fā)車時間間隔在無特殊情況下相等；公交車運行的單程時間，已經(jīng)包含乘客在各站（包括起點和終點）的上下車時間；每輛公交車可以運行一整天不需要加油；公交車按照行車時間表準(zhǔn)時進站和出站，途中沒有堵車和意外事故；公交車回到終點后不需要停留，可以繼續(xù)進行下一班次的運行；發(fā)車間隔以分鐘為最小單位；以13：30劃分雙班車司機的上午與下午的工作時間段；在車站等待的絕大數(shù)人不會離去。

四、符號說明（見表1）

五、模型建立

（一）模型Ⅰ（問題一的模型）

1. 確定目標(biāo)函數(shù)

由于不同班次可由同一輛公交車完成，結(jié)合時間分配，通過求該時間段內(nèi)最少班次，在不等式的約束條件下，繼而求在早高峰時段（6：00～8：00）運行所需要使用的最少公交車數(shù)量。

S1為第一時間段即早高峰時段（6：00-8：00）內(nèi)需要的班次，T1為第一時間段即早高峰時段的時間長度為120分鐘，Δt1為第一時間段即早高峰時段（6：00～8：00）的發(fā)車間隔。

2. 確定約束條件

（1）最大最小發(fā)車時間間隔約束

任意相鄰兩車之間的發(fā)車間隔要滿足最大最小發(fā)車時間間隔約束，即：

（二）模型Ⅱ（問題二的模型）

1. 確定不同時間段的最優(yōu)發(fā)車間隔

（1）確定目標(biāo)函數(shù)

公交車排班以服務(wù)乘客為前提，但是在排班過程中必須兼顧到經(jīng)濟效益。公交車排班應(yīng)該是在滿足乘客需求的前提下，盡可能少的使用公交車，減少不必要的投入。因此，這是一個多目標(biāo)規(guī)劃問題。

①考慮一天內(nèi)總的班次最少

將問題二中的一整天劃分為4個時間段來簡化模型的建立，便于理解。

②考慮一天內(nèi)乘客等待的時間最短

這兩個目標(biāo)是既相互聯(lián)系又相互矛盾的，不可能使兩者同時達到最小。這樣就需要尋求一個平衡點，得到總體的最優(yōu)?，F(xiàn)在將兩項加權(quán)合并為單目標(biāo)函數(shù)，考慮將這兩項算成一種費用。

第一項發(fā)車班次總和折算成公交公司的運輸費用。由徐州市公交公司的調(diào)研數(shù)據(jù)可知，平均每車每公里的成本是320元，這個費用包括了司機的勞動工資、耗油、折舊、維修與管理等各項費用之和。因此，一天之內(nèi)公交車發(fā)車的班次總和其價值可以進行如下折算：

第二項乘客總的等車時間可以折算為乘客等車損失的費用。由徐州市統(tǒng)計局相關(guān)資料可知，徐州市2全部職工的每月平均工資為4947.75元。假設(shè)平均每天的工作時間為8小時。

目標(biāo)函數(shù)包括了公交車公司和乘客兩方的利益，由于這兩個目標(biāo)存在著相互沖突性，兩個目標(biāo)函數(shù)就存在一個權(quán)值的問題，體現(xiàn)在目標(biāo)函數(shù)中兩項的加權(quán)系數(shù)的大小。在同一線路的不同時間段加權(quán)系數(shù)的最優(yōu)值是不同的。例如：從公交車公司的角度考慮，早高峰時段是多數(shù)乘客的上班時間，這段時間內(nèi)所需要的公交車輛數(shù)最多的。從乘客的方面考慮，早高峰對于乘客的利益影響較大，乘客希望此時的時間比較短，這個時候乘客等車時間加權(quán)系數(shù)較大。初始化時取加權(quán)系數(shù)為0.2和0.8，在計算中根據(jù)結(jié)果逐步進行比較、調(diào)整。

（2）確定約束條件

最大最小發(fā)車時間間隔約束。任意相鄰兩車之間的發(fā)車間隔要滿足最大最小發(fā)車時間間隔約束，即：

2. 確定所需公交車的最少數(shù)量

（1）確定目標(biāo)函數(shù)

問題二要求建立適當(dāng)?shù)哪Ｐ颓蠼獬鲂熘菔?路公交車運行一整天需要的最少公交車數(shù)量，總的公交車數(shù)量為單班車與雙班車的數(shù)量之和。由此確定目標(biāo)函數(shù)：

（2）確定約束條件

①考慮問題二是在問題一的基礎(chǔ)上

②考慮單班車自身的約束條件

單班車通常要求在早高峰跑2～3個班次，晚高峰2～3個班次，一天不超過5個班次。

早晚高峰中單班車必須要運行2個班次，總的單班車、早高峰期單班車、晚高峰期單班車數(shù)量一致。

限制單班車運行的班次在早晚高峰期所需的總班次內(nèi)。

限制每輛單班車一整天的運行班次不超過5個班次。

③考慮單班車和雙班車總的約束條件

滿足單班車和雙板車運行的班次足夠運行完一整天的4個時間段的總班次，即保證一整天的公交系統(tǒng)的正常運行。

④考慮不同時間段內(nèi)發(fā)車間隔的約束

此模型中的不同時間段的發(fā)車時間間隔采用各個時間段的最優(yōu)發(fā)車時間間隔模型中求解得知的各個時間段的發(fā)車間隔。

（三）模型Ⅲ（問題三的模型）

問題三的模型即在問題二的模型上增加約束條件

x1≥3

滿足問題三中的單班車不少于三輛的要求

模型Ⅲ：

（四）模型Ⅳ（問題四的模型）

1. 確定不同時間段的最優(yōu)發(fā)車間隔

（1）確定目標(biāo)函數(shù)

確定不同時段的最優(yōu)發(fā)車間隔模型是一致的，參數(shù)的個數(shù)以及設(shè)置不同導(dǎo)致最終的求解不同。目標(biāo)函數(shù)為：

（2）確定約束條件

最大最小發(fā)車時間間隔約束，同時段內(nèi)任意兩車之間的發(fā)車間隔要滿足最大最小發(fā)車時間間隔約束，即

2. 確定所需公交車的最少數(shù)量

（1）確定目標(biāo)函數(shù)

求解處運行一整天所需的最少的公交車數(shù)量為目標(biāo)，因此目標(biāo)函數(shù)為：

minN=x1+x2（24）

（2）確定約束條件

①考慮單班車自身的約束條件

單班車在早晚高峰必須要運行2-3個班次

x1=x13=x15（25）

總的單班車、早高峰期、晚高峰期單班車數(shù)量一致。

限制單班車運行的班次在早晚高峰所需的總班次內(nèi)。

限制每輛單班車一整天的運行班次不超過5個班次。

②考慮雙班車自身的約束條件

③考慮單班車和雙班車總的約束條件

保證一天的公交車系統(tǒng)的正常運行。

④考慮不同時間段內(nèi)發(fā)車間隔的約束

六、模型求解

（一）模型Ⅰ的求解

將函數(shù)及數(shù)據(jù)帶入MATLAB計算，得：

即最少需要24班次。

但是由于班次無法對應(yīng)公交車數(shù)量，因此做出如圖1（時間軸）的分析。

……

由所繪時間軸可知，運行中實際需要的公交車數(shù)量為6：00～7：20這一時間段內(nèi)發(fā)出的公交車數(shù)量。修改（1）式模型有：

利用MATLAB求解有

Δt1=5S1′=16

得出最終結(jié)果：徐州市2路公交車，在早高峰時段（6：00～8：00）運行所需要使用的最少公交車數(shù)量為16輛。單班車、雙班車在早高峰時段可看作同種運行模式，單雙班車的具體數(shù)量如表2所列。

（二）模型Ⅱ的求解

1. 模型Ⅱ.a的求解

利用MATLAB編程求解可得出以下結(jié)論如表3所示。

考慮到MATLAB求解出的可行解不一定滿足實際問題的要求，在車輛的實際排班過程中還需要對不同的實際情況做出微調(diào)。經(jīng)過實驗，最終將晚高峰時段的最優(yōu)發(fā)車時間間隔調(diào)整為4分鐘。

2. 模型Ⅱ.b的求解

利用MATLAB編程求解可得出以下結(jié)論。

最少公交車數(shù)量為20輛，其中單班車0輛，雙班車20輛。

根據(jù)模型Ⅱ的求解，可得到的徐州市2路公交車排班計劃表，其中總車輛數(shù)20輛，雙班車總數(shù)量20輛，單班車總數(shù)量為0，所有車的總班次數(shù)208次。

（三）模型Ⅲ的求解

利用MATLAB編程求解可得出以下結(jié)論。

最少公交車數(shù)量為21輛，其中單班車3輛，雙班車18輛。

根據(jù)模型Ⅲ的求解，可得到徐州市2路公交車排班計劃表，其中總車輛數(shù)為21輛，總雙班車數(shù)量18輛，總單班車數(shù)量3輛，所有車的總班次數(shù)199次。

（四）模型Ⅳ的求解

1. 模型Ⅳ.a的求解

利用MATLAB編程求解可得出以下結(jié)論如表4所示。

考慮到MATLAB求解出的可行解不一定滿足實際問題的要求，在車輛的實際排班過程中還需要對不同的實際情況做出微調(diào)。經(jīng)過實驗，最終將晚高峰時段的最優(yōu)發(fā)車時間間隔調(diào)整為4分鐘。

2. 模型Ⅳ.b的求解

利用MATLAB編程求解可得出以下結(jié)論。

最少公交車數(shù)量為23輛，其中單班車4輛，雙班車19輛。

根據(jù)模型Ⅱ的求解，可得到徐州市2路公交車排班的計劃表，其中總車輛數(shù)23輛，總雙班車數(shù)量19輛，總單班車數(shù)量4輛，所有車的總班次數(shù)195次。

驗證模型Ⅳ求解得到的徐州市2路公交車排班表：

（1）單班車司機不安排吃飯，所有雙班車司機都安排吃飯（早餐和晚餐），每餐飯需要20分鐘用餐時間。早餐8：00開始供應(yīng)，10：00截止；晚餐18：00開始供應(yīng)，20：00截止?！丛?：00～10：00以及18：00～20：00這兩個時間段內(nèi)雙班車的班次中至少有1次在終點站停站超過20分鐘。

（2）雙班車輛運行5班次以后，上午、下午班司機進行換班，換班時間最少為20分鐘（含最短停站時間）?！措p班車輛運行5班次以后，雙班車在終點站停站超過20分鐘。

驗證可知模型Ⅳ求解得到的徐州市2路公交車排班表符合問題四的約束條件。

七、模型的擴展與評價

公交車排班是影響公交運營系統(tǒng)運行成本、效率和服務(wù)能力、水平的重要內(nèi)容，是公共交通系統(tǒng)著重研究核心內(nèi)容之一。其中，公交行車計劃編制，包括發(fā)車頻率、發(fā)車時刻表、運力和司乘配置計劃是公共交通系統(tǒng)靜態(tài)調(diào)度的主要內(nèi)容。

在公交靜態(tài)調(diào)度優(yōu)化的研究中，為了滿足乘客出行需求盲目增加運營車輛將導(dǎo)致企業(yè)運營成本的增加，線路上投入車輛過多，引發(fā)滿載率過低也是一種不必要的資源浪費。所以，在問題二、三中通過分析公交企業(yè)利益即公交企業(yè)運營成本和出行者利益即出行者候車成本，建立以企業(yè)運營成本最小和出行者候車成本最小的車輛發(fā)車間隔模型，利用多元線性規(guī)劃方法，借助MATLAB進行模型求解。

本文中，采用多元線性規(guī)劃模型在題設(shè)約束條件下較為完整地解決了公交車排班的問題，得出了符合要求的徐州市2路公交車排班計劃表（即為表3～2、表4～1）。由此可見，采用多元線性規(guī)劃模型及優(yōu)化模型對公交車進行排班，制定出排班計劃表，有效合理地配置了公交車輛資源，提高了公交公司的人性化管理水平。

但是，本文中的公交車排班計劃僅對于原始的靜態(tài)情況進行排班，未考慮道路狀況和突發(fā)狀況等實際情況，對實際問題進行了簡化和抽象，所以，與實際問題存在一定的差異，有待于更進深入地研究，模型也有待于更進一步地優(yōu)化。

參考文獻：

[1]李躍鵬，等.基于遺傳算法的公交車輛智能排班研究[J].交通運輸系統(tǒng)工程與信息，2003（01）.

[2]臧輝，成俊.基于遺傳算法的公交車輛智能排班研究[J].武漢職業(yè)技術(shù)學(xué)院學(xué)報，2007（03）.

[3]王慶榮，等.基于遺傳算法的公交智能排班系統(tǒng)應(yīng)用研究[J].計算機仿真，2011（03）.

（作者單位：南京郵電大學(xué)）