葉小青，亓?xí)酝?，馬俊明，劉 琴，黃 強(qiáng)

(1 中南民族大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院，武漢 430074；2 中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

截至2013年1月，武漢市約有118萬名在校大學(xué)生，是全世界在校大學(xué)生數(shù)量最多的城市之一，2013年1月，武漢市人大代表提出在高校之間開通公交線路，得到了市長(zhǎng)唐良智的共鳴[1].此提議一方面有助于為高校學(xué)生之間的合作與交流提供便利，另一方面有利于推動(dòng)武漢市優(yōu)質(zhì)教學(xué)資源的共享.

公共交通是城市的重要組成部分，高校之間的公交線路是一種特殊的公共交通.如何設(shè)計(jì)公交線路并確定合理的排班方案是公交線路運(yùn)營(yíng)的基礎(chǔ)[2].由于城市交通線路復(fù)雜且具有較大的實(shí)用價(jià)值，近年來有許多學(xué)者對(duì)公交線路設(shè)計(jì)及其排班方案問題進(jìn)行了研究，利用優(yōu)化模型、圖論模型、綜合評(píng)價(jià)模型對(duì)公交線路進(jìn)行設(shè)計(jì)與選擇[3-5]，根據(jù)遺傳算法、并行遺傳算法求解了線路排班方案的粗粒度問題[2,6,7]，建立非線性隨機(jī)規(guī)劃模型模擬實(shí)際調(diào)度運(yùn)行中遇到的隨機(jī)因素，避免了傳統(tǒng)排班模型的弊端[8]，提出以最小化乘客等待時(shí)間為目標(biāo)的動(dòng)態(tài)調(diào)度模型，并采用遺傳算法對(duì)模型進(jìn)行了求解與驗(yàn)證[9]，在遺傳—模擬退火算法的基礎(chǔ)上，針對(duì)其在編碼操作、選擇操作和模擬退火的降溫操作中存在的不足進(jìn)行了幾點(diǎn)改進(jìn)，結(jié)合公交車輛調(diào)度自身的特點(diǎn)，兼顧公交公司與乘客的雙方利益建立公交車輛行車計(jì)劃模型，并結(jié)合實(shí)例，應(yīng)用改進(jìn)的遺傳—模擬退火算法對(duì)模型進(jìn)行了優(yōu)化求解，驗(yàn)證了改進(jìn)的遺傳—模擬退火算法的有效性和優(yōu)異性[10].

現(xiàn)有研究大都考慮的是常規(guī)線路的排班方案，然而高校間公交線路排班方案與常規(guī)線路相比具有明顯的差異性，比如對(duì)于高校學(xué)生而言，節(jié)假日是出行高峰期，而常規(guī)的線路中每天的上下班都是高峰期，而且高校間公交線路的發(fā)車間隔應(yīng)明顯大于常規(guī)線路.從公平性和效率性的角度出發(fā)，司機(jī)之間的工作時(shí)長(zhǎng)和工作量應(yīng)盡量相等，且公交線路應(yīng)該充分滿足客流需求.基于此，本文根據(jù)調(diào)查結(jié)果，以武漢市洪山區(qū)10所高校為研究對(duì)象，首先基于旅行商問題設(shè)計(jì)一條貫穿10所高校的公交線路，然后從公平性角度，并結(jié)合基本假設(shè)確定班次和所需要的司機(jī)人數(shù)，進(jìn)一步從充分滿足客流需要的效率性角度建立多目標(biāo)優(yōu)化模型確定最優(yōu)排班方案.

1 基于旅行商問題公交線路的設(shè)計(jì)

根據(jù)我們項(xiàng)目組的調(diào)查與統(tǒng)計(jì)，武漢市高校學(xué)生出行主要集中在洪山區(qū)一帶，包括武漢大學(xué)、華中科技大學(xué)、武漢理工大學(xué)、華中師范大學(xué)、中南財(cái)經(jīng)政法大學(xué)、中國(guó)地質(zhì)大學(xué)(武漢)、華中農(nóng)業(yè)大學(xué)、中南民族大學(xué)、武漢紡織大學(xué)、武漢體育學(xué)院.一條好的公交線路應(yīng)該貫穿這10所高校且經(jīng)過的路程最短，屬于典型的旅行商(TSP)問題.旅行商問題是在尋求單一旅行者由起點(diǎn)出發(fā)，通過所有給定的需求點(diǎn)之后，最后再回到原點(diǎn)的最小路徑成本[11].本文將建立旅行商問題的數(shù)學(xué)規(guī)劃模型設(shè)計(jì)公交線路.

1.1 基于旅行商問題公交線路數(shù)學(xué)規(guī)劃模型的建立

用dij表示學(xué)校i與學(xué)校j之間的距離.xij=1或0(1表示走過學(xué)校i到學(xué)校j的路，0表示沒有選擇走這條路)i,j=1,2,…，10，則有如下規(guī)劃模型[12]：

模型(1)中目標(biāo)函數(shù)表示線路總長(zhǎng)度最短，前2個(gè)約束條件分別表示每個(gè)學(xué)校只有1條線路進(jìn)入和1條線路離開，第3個(gè)約束條件表示除起始站點(diǎn)和終止站點(diǎn)外，各條線路均不構(gòu)成圈.

1.2 距離的修正及公交線路的確定

其中r>0是衰減指數(shù)，mij表示單位時(shí)間(統(tǒng)計(jì)周期為月)內(nèi)學(xué)校i前往學(xué)校j的平均人數(shù)，Ni表示單位時(shí)間內(nèi)學(xué)校i出行的學(xué)生人數(shù).

對(duì)距離進(jìn)行修正的原則是縮小互訪頻次較高的高校間的距離，但縮小應(yīng)該是“適當(dāng)?shù)摹?，令r=0∶0.1∶1，對(duì)r在不同取值情況下進(jìn)行聚類，結(jié)果顯示當(dāng)r=0.2時(shí)聚類效果最好，因此取r=0.2.

利用Lingo對(duì)模型(1)進(jìn)行求解，得到最佳路線為：華中農(nóng)業(yè)大學(xué)(3，起點(diǎn))—武漢理工大學(xué)(2)—武漢大學(xué)(0)—華中師范大學(xué)(9)—武漢體育學(xué)院(8)—中國(guó)地質(zhì)大學(xué)(4)—華中科技大學(xué)(1)—中南民族大學(xué)(6)—武漢紡織大學(xué)(7)—中南財(cái)經(jīng)政法大學(xué)(5)—華中農(nóng)業(yè)大學(xué)(3，終點(diǎn)).公交路線如圖1所示.

圖1 武漢市洪山區(qū)10所高校間公交線路圖Fig.1 The bus route map of ten universitiesin Hongshan District of Wuhan

由圖1所示，該線路構(gòu)成一個(gè)閉環(huán)，修正后的距離之和為24.82km，實(shí)際總長(zhǎng)30.6km，該公交線路將距離較近的學(xué)校(如華中科技大學(xué)和中國(guó)地質(zhì)大學(xué)(武漢)；中南民族大學(xué)、武漢紡織大學(xué)和中南財(cái)經(jīng)政法大學(xué))設(shè)置為相鄰的站點(diǎn)，同時(shí)將華中農(nóng)業(yè)大學(xué)設(shè)置為起點(diǎn)和終點(diǎn)，是較為合理的，因?yàn)槟虾蟮揽諘缜覂H有一路公交(570路)，華中農(nóng)業(yè)大學(xué)學(xué)生眾多，將其設(shè)置為起點(diǎn)和終點(diǎn)不會(huì)對(duì)現(xiàn)有公交系統(tǒng)產(chǎn)生較大的影響.

同時(shí)，由于該線路是一條環(huán)形線路，因此可以從正向和反向同時(shí)開設(shè)公交，以滿足不同方向?qū)W生的需求.

2 線路司機(jī)人數(shù)的確定

以上述公交線路為研究藍(lán)本，考慮該線路的排班方案.排班方案的確定主要從司機(jī)角度，在線路已經(jīng)設(shè)計(jì)好的基礎(chǔ)之上，根據(jù)線路的運(yùn)行時(shí)間、學(xué)生在工作日和出行日的出行規(guī)律以及司機(jī)的工作時(shí)間來確定司機(jī)人數(shù).根據(jù)文獻(xiàn)[13]的結(jié)論，做出如下模型假設(shè)：

①線路每天的開收班時(shí)間：6:30-21:30，共計(jì)900min.

②工作日(主要是周一到周五)出行的學(xué)生相對(duì)較少，發(fā)車間隔服從(20,30)(單位：分鐘，下同)上的均勻分布；節(jié)假日出行的學(xué)生相對(duì)較多，發(fā)車間隔服從(10,20)上的均勻分布.

③完成一次線路運(yùn)行的時(shí)間：工作日為60～80 min/班，節(jié)假日為80～100 min/班.

④司機(jī)每天上班不超過8h.

⑤司機(jī)連續(xù)開車不得超過4h.

⑥每名司機(jī)每月至少完成60班次.

用x1表示工作日排班間隔，根據(jù)假設(shè)①，x1:U(20,30)，工作日每天開班次數(shù)為：

(2)

其中[x]表示不小于x的最小整數(shù).

用x2表示節(jié)假日排班間隔，根據(jù)假設(shè)③，x2:U(10,20)，節(jié)假日每天開班次數(shù)：

(3)

不失一般性，設(shè)每個(gè)月有20個(gè)工作日和10個(gè)節(jié)假日，則每月班次總數(shù)：

(4)

由于xi(i=1,2)為隨機(jī)變量，考慮M的理論最大和最小值沒有實(shí)際意義，因此考慮班次總數(shù)的期望值.

E(x1)=25，E(x2)=15，工作日平均每天開班36次，節(jié)假日平均每天開班60次，月均班次總數(shù)1320次.

為了確定司機(jī)人數(shù)，注意到極端情況發(fā)生在節(jié)假日，假設(shè)每次均花費(fèi)100min才完成一次線路運(yùn)行，則此時(shí)節(jié)假日工作時(shí)長(zhǎng)為6000min，而根據(jù)假設(shè)④，每名司機(jī)每天最多工作480min，因此至少需要司機(jī)12.5名.同時(shí)考慮到請(qǐng)假等不確定因素，認(rèn)為為該線路安排15名公交司機(jī)是合理的.

3 排班方案模型的建立

好的排班方案既要具有公平性，又要有效率性.公平性即各個(gè)司機(jī)之間的工作班次和工作時(shí)長(zhǎng)應(yīng)盡量均衡，效率性即排班方案應(yīng)該滿足客流需求，因此可建立多目標(biāo)優(yōu)化模型.

3.1 目標(biāo)函數(shù)的建立

用xijk表示第i天第j班次第k號(hào)司機(jī)是否開車，引入0-1變量，即：

其中i=1,2,…，30，j=1,2,…,m，k=1,2,…,15,工作日時(shí)m=36，節(jié)假日對(duì)應(yīng)m=60，司機(jī)總?cè)藬?shù)n=15.

用cijk表示第i天第j班次第k號(hào)司機(jī)此班次所用時(shí)間，當(dāng)xijk=0時(shí)，cijk=0；當(dāng)xijk=1時(shí)，cijk服從如下的均勻分布：

(5)

(6)

(7)

3.2 約束條件的確定

根據(jù)假設(shè)④,⑤,⑥，可以確定如下約束：

(1)司機(jī)每天上班時(shí)間不超過8h(480min)，即：

(8)

(2)由于每班次至少60 min，最多100 min，所以連續(xù)開車不超過4h等價(jià)于不能連續(xù)開車4班次, 即：

(9)

(3)司機(jī)每月至少完成60個(gè)班次，即：

(10)

聯(lián)立(7)～(10)式，得到公交車排班方案的多目標(biāo)優(yōu)化模型：

(11)

4 排班方案模型的求解

模型(11)屬于多目標(biāo)優(yōu)化模型，多目標(biāo)優(yōu)化模型沒有全局意義上的最優(yōu)解，線性加權(quán)法和分層排序法是多目標(biāo)優(yōu)化模型常用的求解方法.線性加權(quán)法主要按各分函數(shù)的重要程度，對(duì)應(yīng)地選擇一組加權(quán)系數(shù)，其所有加權(quán)系數(shù)和為1，各分函數(shù)與加權(quán)系數(shù)乘積的線性組合構(gòu)成一個(gè)評(píng)價(jià)函數(shù)，求新的評(píng)價(jià)函數(shù)最優(yōu)解.分層排序法主要思想是基于各個(gè)目標(biāo)函數(shù)并按某種意義分清主次，按重要程度逐一排隊(duì)，然后依次對(duì)分目標(biāo)函數(shù)求各自的最優(yōu)解.由于模型(11)中S1和S2分別代表司機(jī)的月工作班次方差和月工作時(shí)間方差，而且后者以分鐘為單位，最終結(jié)果將會(huì)很大，這樣必定會(huì)導(dǎo)致兩者的量綱差異性較大，不適合線性加權(quán)法；同時(shí)，S1和S2在本模型中的重要程度相同，沒有主次之分，因此也不適合分層排序法.考慮到本模型的復(fù)雜性主要在于約束條件，因此采用如下算法步驟對(duì)模型進(jìn)行求解.

Step2：不考慮目標(biāo)函數(shù)的取值，對(duì)約束條件進(jìn)行隨機(jī)模擬，得到一種符合條件的排班方案；

該求解思想的算法流程圖如圖2所示.

圖2 模型求解的算法流程圖Fig.2 The algorithm flow chart of model solution

4.1 閾值的確定

模型結(jié)果的好壞很大程度上取決于閾值的確定.閾值的確定應(yīng)該充分體現(xiàn)排班方案所應(yīng)滿足的公平性(排班方案的效率性體現(xiàn)在約束條件中)，確定的閾值過大，則模型的精確度會(huì)過低；閾值過小，則模型的求解代價(jià)會(huì)過大.借助概率論與數(shù)理統(tǒng)計(jì)中次序統(tǒng)計(jì)量和分位數(shù)的概念，本文采用如下步驟確定閾值：

Step1：隨機(jī)模擬約束條件進(jìn)行100次，產(chǎn)生100組目標(biāo)函數(shù)值，每組目標(biāo)函數(shù)值均包括班次方差和工作時(shí)間方差；

Step2：將目標(biāo)函數(shù)值按照從小到大的順序進(jìn)行排列，用S1(i)和S2(i)分別表示排列后的第i個(gè)班次方差和工作時(shí)間方差；

該閾值確定方法表明僅接受隨機(jī)模擬中80分位及以上的目標(biāo)函數(shù)取值.利用MATLAB進(jìn)行模擬，得到閾值

(12)

4.2 排班方案的模擬結(jié)果

在圖2所示的流程圖的基礎(chǔ)上，本文采用MATLAB語言進(jìn)行編程求解，其程序偽代碼如下：

Function

put(flag); %輸入當(dāng)月天數(shù)信息，1表示節(jié)假日，0表示非節(jié)假日

size(flag); %當(dāng)月天數(shù)

for k=1:size(flag) %循環(huán)輸入調(diào)整當(dāng)月所有天數(shù)的排班信息

all(zeros) %所有排班初始信息置零

while T<=900 %當(dāng)天累計(jì)運(yùn)行時(shí)間

Bus(k,Num,4) %初始化當(dāng)天所有班次四項(xiàng)信息

end

for i=1:Num %循環(huán)更新所有當(dāng)天班次四項(xiàng)信息

for j=1:n %循環(huán)更新第n個(gè)司機(jī)的信息

if Dr(k,j,:)=1 %如果司機(jī)所有的要求都滿足

end

if Dr(k,j,:)=0 %如果該司機(jī)不是所有的要求都滿足

Dr(k,j,:)=0—>Dr(k,j,:) %更新該司機(jī)的信息使其滿足要求

end

end

end

end

printf( ) %輸出結(jié)果

基于上述代碼可得到該公交線路的排班方案及司機(jī)工作量統(tǒng)計(jì)表.公交車的發(fā)車時(shí)間一旦確定，則各個(gè)站點(diǎn)的具體到站時(shí)間取決于相鄰兩站點(diǎn)間的距離和該路段交通情況，具有一定的隨機(jī)性.盡管各個(gè)站點(diǎn)在工作日與節(jié)假日排班方案的結(jié)果均由計(jì)算機(jī)隨機(jī)模擬求得，但均符合模型假設(shè)②和③：即學(xué)生的平均等車時(shí)間分別不超過25 min(工作日)和15 min(節(jié)假日)，每班次的時(shí)長(zhǎng)不超過80 min(工作日)和100 min(節(jié)假日).需要出行的學(xué)生可以根據(jù)發(fā)車時(shí)間合理地安排自己何時(shí)去車站候車.

由于輸出結(jié)果龐大，表1～2僅給出華中農(nóng)業(yè)大學(xué)(起點(diǎn)站)工作日和節(jié)假日前10個(gè)班次的具體排班方案.

表1 華中農(nóng)業(yè)大學(xué)(起點(diǎn))工作日排班方案信息表(前10班次)Tab.1 The information table of scheduling program on weekdays in the starting point of Huazhong Agricultural University(top 10 shifts)

表2 華中農(nóng)業(yè)大學(xué)(起點(diǎn))節(jié)假日排班方案信息表(前10班次)Tab.2 The information table of scheduling program on holidays inthe starting point of Huazhong Agricultural University(top 10 shifts)

表3 15名司機(jī)月度班次和工作時(shí)長(zhǎng)統(tǒng)計(jì)表Tab.3 The statistics of monthly shift and working hours of 15 drivers

5 結(jié)語

本文首先根據(jù)互訪人數(shù)對(duì)高校間的距離進(jìn)行了修正，建立基于旅行商問題(TSP)的數(shù)學(xué)規(guī)劃模型，設(shè)計(jì)出一條貫穿武漢市洪山區(qū)10所高校間的公交線路.其次從效率性入手，通過期望分析確定了該公交線路上合適的司機(jī)人數(shù)；再從公平性角度，以司機(jī)的工作量和工作時(shí)長(zhǎng)方差最小入手建立了多目標(biāo)優(yōu)化模型，通過設(shè)定閾值，結(jié)合計(jì)算機(jī)模擬確定了公交司機(jī)在工作日和節(jié)假日的排班方案，結(jié)果表明該方案下公交司機(jī)的工作量和工作時(shí)長(zhǎng)非常均衡，具有一定的推廣意義.

參 考 文 獻(xiàn)

[1] 大楚網(wǎng). 武漢今年送大學(xué)生“三大福利”，試點(diǎn)高校間通公交[EB/OL]. [2013-6-18].http://hb.qq.com/a/20130108/000402.htm.

[2] 衷 明. 基于并行遺傳算法的智能公交排班研究[J]. 計(jì)算機(jī)時(shí)代，2011(12)：18-20.

[3] 周文峰，李珍萍，劉洪偉，等. 最優(yōu)公交線路選擇問題的數(shù)學(xué)模型及算法[J].運(yùn)籌與管理，2008，17(5)：80-84.

[4] 馬良河，劉信斌，廖大慶. 城市公交線路網(wǎng)絡(luò)圖的最短路與乘車路線問題[J].數(shù)學(xué)的實(shí)踐與認(rèn)知，2004，34(6)：38-44.

[5] 錢 萌，彭張節(jié)，陳樹林，等. 基于綜合評(píng)價(jià)指數(shù)的城市公交線路選擇優(yōu)化模型[J].吉林大學(xué)學(xué)報(bào)：信息科學(xué)版，2008，26(2)：180-185.

[6] 李越鵬. 基于遺傳算法的公交車輛智能排班研究[J]. 交通運(yùn)輸系統(tǒng)工程與信息，2003，3(1)：41-44.

[7] 王 寧，宮生文. 基于遺傳算法的公交智能排班系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)算機(jī)時(shí)代，2008(9)：38-40.

[8] 楊 磊，劉衛(wèi)朋，周 磊. 基于改進(jìn)的隨機(jī)公交調(diào)度問題的數(shù)學(xué)模型[J]. 河北工業(yè)大學(xué)學(xué)報(bào)，2010，39(1)：74-78.

[9] 姚寶珍. 城市公交樞紐布局與運(yùn)營(yíng)調(diào)度方法研究[D]. 北京：北京交通大學(xué)，2011.

[10] 黃宏用. 改進(jìn)的遺傳—模擬退火算法在公交排班中的應(yīng)用[D]. 蘭州：蘭州理工大學(xué)，2011.

[11] 刁在筠. 運(yùn)籌學(xué)[M]. 3版. 北京：高等教育出版社，2005.

[12] 司守奎. 數(shù)學(xué)建模算法與應(yīng)用[M].北京：國(guó)防工業(yè)出版社,2011.

[13] 數(shù)據(jù)堂. 公交司機(jī)排班方案[EB/OL]. [2013-6-20]. http://www.datatang.com/data/39666.