葉小青，亓?xí)酝R俊明，劉 琴，黃 強

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

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

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

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

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

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

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ù)表示線路總長度最短，前2個約束條件分別表示每個學(xué)校只有1條線路進入和1條線路離開，第3個約束條件表示除起始站點和終止站點外，各條線路均不構(gòu)成圈.

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

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

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

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

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

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

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

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

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

①線路每天的開收班時間：6:30-21:30，共計900min.

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

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

④司機每天上班不超過8h.

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

⑥每名司機每月至少完成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è)每個月有20個工作日和10個節(jié)假日，則每月班次總數(shù)：

(4)

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

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

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

3 排班方案模型的建立

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

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

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

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

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

(5)

(6)

(7)

3.2 約束條件的確定

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

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

(8)

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

(9)

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

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

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

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

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

4.1 閾值的確定

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

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

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

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

(12)

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

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

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)天累計運行時間

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

end

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

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

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

end

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

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

end

end

end

end

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

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

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

表1 華中農(nóng)業(yè)大學(xué)(起點)工作日排班方案信息表(前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é)(起點)節(jié)假日排班方案信息表(前10班次)Tab.2 The information table of scheduling program on holidays inthe starting point of Huazhong Agricultural University(top 10 shifts)

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

5 結(jié)語

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

參 考 文 獻

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

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

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

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

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

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

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

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

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

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

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

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

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