陳孫延 沈瑩瑩 仇佳輝

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

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

一、問(wèn)題重述

（一）引言

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

（二）問(wèn)題的提出

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

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

二、問(wèn)題分析

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

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

雙班車：由兩個(gè)駕駛員駕駛的公交車。雙班車要求上、下午各一個(gè)司機(jī)，上午和下午司機(jī)的工作時(shí)間盡可能均勻，并且都不超過(guò)8小時(shí)。每輛雙班車一天運(yùn)行不超過(guò)10個(gè)班次。

（一）問(wèn)題一分析

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

（二）問(wèn)題二分析

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

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

（三）問(wèn)題三分析

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

（四）問(wèn)題四分析

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

三、模型假設(shè)

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

四、符號(hào)說(shuō)明（見(jiàn)表1）

五、模型建立

（一）模型Ⅰ（問(wèn)題一的模型）

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

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

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

2. 確定約束條件

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

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

（二）模型Ⅱ（問(wèn)題二的模型）

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

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

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

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

將問(wèn)題二中的一整天劃分為4個(gè)時(shí)間段來(lái)簡(jiǎn)化模型的建立，便于理解。

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

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

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

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

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

（2）確定約束條件

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

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

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

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

（2）確定約束條件

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

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

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

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

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

限制每輛單班車一整天的運(yùn)行班次不超過(guò)5個(gè)班次。

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

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

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

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

（三）模型Ⅲ（問(wèn)題三的模型）

問(wèn)題三的模型即在問(wèn)題二的模型上增加約束條件

x1≥3

滿足問(wèn)題三中的單班車不少于三輛的要求

模型Ⅲ：

（四）模型Ⅳ（問(wèn)題四的模型）

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

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

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

（2）確定約束條件

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

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

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

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

minN=x1+x2（24）

（2）確定約束條件

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

單班車在早晚高峰必須要運(yùn)行2-3個(gè)班次

x1=x13=x15（25）

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

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

限制每輛單班車一整天的運(yùn)行班次不超過(guò)5個(gè)班次。

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

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

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

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

六、模型求解

（一）模型Ⅰ的求解

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

即最少需要24班次。

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

……

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

利用MATLAB求解有

Δt1=5S1′=16

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

（二）模型Ⅱ的求解

1. 模型Ⅱ.a的求解

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

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

2. 模型Ⅱ.b的求解

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

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

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

（三）模型Ⅲ的求解

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

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

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

（四）模型Ⅳ的求解

1. 模型Ⅳ.a的求解

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

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

2. 模型Ⅳ.b的求解

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

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

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

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

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

（2）雙班車輛運(yùn)行5班次以后，上午、下午班司機(jī)進(jìn)行換班，換班時(shí)間最少為20分鐘（含最短停站時(shí)間）。——即雙班車輛運(yùn)行5班次以后，雙班車在終點(diǎn)站停站超過(guò)20分鐘。

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

七、模型的擴(kuò)展與評(píng)價(jià)

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

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

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

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

參考文獻(xiàn)：

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

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

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

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