2011數(shù)學(xué)建模--公交司機(jī)排班方案模型--模擬

1、2010高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽承 諾 書(shū)我們仔細(xì)閱讀了中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白，在競(jìng)賽開(kāi)始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的, 如果引用別人的成果或其他公開(kāi)的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號(hào)是（從A/B/C/D中選擇一項(xiàng)填寫）： 我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名

2、號(hào)的話）： 所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜?參賽隊(duì)員 (打印并簽名) ：1. 2. 3. 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 日期： 2011 年07 月 24 日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：2010高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽編 號(hào) 專 用 頁(yè)賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分備注全國(guó)統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國(guó)前編號(hào)）：全國(guó)評(píng)閱編號(hào)（由全國(guó)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：公交司機(jī)排班方案模型摘要本文就公交司機(jī)排班問(wèn)題應(yīng)用遺傳算法和多目標(biāo)規(guī)劃建立數(shù)學(xué)模型。運(yùn)營(yíng)車輛智能排班問(wèn)題是公交車輛智能調(diào)度需要解決的典型問(wèn)題之一

3、，本文應(yīng)用已有的數(shù)據(jù)，并兼顧到乘客和公交公司的雙重利益，建立起一個(gè)符合實(shí)際情況的數(shù)學(xué)模型。在此基礎(chǔ)上引入了遺傳算法（GA），針對(duì)公交智能排班問(wèn)題，構(gòu)造了符合行車規(guī)律的編碼方式、遺傳算子，并實(shí)現(xiàn)了程序的編碼工作，最后進(jìn)行了模擬實(shí)驗(yàn)。問(wèn)題一在一定的約束條件下，如何合理安排其組織部分（操作）所占有資源、運(yùn)行時(shí)間及先后順序，以獲得運(yùn)輸成本或時(shí)間最優(yōu)化。在理論研究中，車輛班次問(wèn)題可看做資源分配問(wèn)題。問(wèn)題二在保證運(yùn)營(yíng)效率的情況下尋求乘客等待時(shí)間最少和保證服務(wù)水平的前提下使車隊(duì)運(yùn)營(yíng)效率較高，基于以上的考慮行車時(shí)刻表的編制應(yīng)是在滿足客流需求的前提下，盡量減少不必要的投入，這是個(gè)多目標(biāo)優(yōu)化問(wèn)題，遺傳算法是解決公

4、交排班問(wèn)題的有效方法之一。問(wèn)題三是在一定的約束條件下，合理安排排班方案使司機(jī)總數(shù)最少，以達(dá)到資源的合理分配。關(guān)鍵詞：公交智能排班；遺傳算法；遺傳算子一、問(wèn)題的重述目前，隨著某市經(jīng)濟(jì)進(jìn)一步的發(fā)展，道路變得越來(lái)越多。公交優(yōu)先，百姓優(yōu)先，為此某市公交總公司開(kāi)辟了各種線路，有市內(nèi)線，近郊線，遠(yuǎn)郊線，旅游線，機(jī)場(chǎng)線，社區(qū)線等140多條線路，以滿足老百姓出行需要。而現(xiàn)實(shí)是有的線路司機(jī)不足，常常存在向其他車隊(duì)借調(diào)司機(jī)和車輛跑班，影響其他線路的排班秩序；有的線路司機(jī)需要每天開(kāi)車1213小時(shí)，影響司機(jī)的休息，從而給交通留下安全隱患；有的線路因經(jīng)常堵車，打亂了線路調(diào)度計(jì)劃，使得交接班司機(jī)和乘客怨聲載道。一般，公交

5、公司按月給司機(jī)排班。下面是某條線路的基本情況（附件），請(qǐng)你根據(jù)有關(guān)數(shù)據(jù)完成下列問(wèn)題。規(guī)定：（1）司機(jī)每天上班時(shí)間不超過(guò)8小時(shí)；（2）司機(jī)連續(xù)開(kāi)車不得超過(guò)4小時(shí)；（3）每名司機(jī)至少每月完成120班次。問(wèn)題一：根據(jù)五月份的節(jié)假日情況，求出當(dāng)月最少班次總數(shù)；問(wèn)題二：闡述你對(duì)上述規(guī)定的理解，并根據(jù)你的理解建立適當(dāng)?shù)臄?shù)學(xué)模型，合理地設(shè)計(jì)五月份該線路的司機(jī)排班方案；問(wèn)題三： 根據(jù)五月份該線路的司機(jī)排班方案，計(jì)算出每天需要的司機(jī)人數(shù)，假如規(guī)定每個(gè)司機(jī)每周連續(xù)工作五天，休息兩天。請(qǐng)你通過(guò)某周（周一至周日）需要司機(jī)人數(shù)求出司機(jī)總數(shù)最少的排班方案。有關(guān)的數(shù)據(jù)為：1、該線路的開(kāi)收班時(shí)間：冬令（12月3月）：6:15

6、18:20， 夏令（4月11月）：6:2018:102、該線路的司機(jī)人數(shù)：15人3、該線路排班間隔：平時(shí)：810分鐘/班；高峰（上下班）：6:008:30，11:3013:30，16:3018:00：48分鐘/班節(jié)假日：510分鐘/班4、該線路的運(yùn)行時(shí)間:正常：8085分鐘/班高峰：100120分鐘/班二、問(wèn)題的分析公交車排班問(wèn)題是城市公交調(diào)度的核心內(nèi)容，是公交調(diào)度人員、司乘人員進(jìn)行工作以及公交車輛正常運(yùn)行的基本依據(jù)。公交排班的目的是確定最優(yōu)或者近似最優(yōu)的運(yùn)營(yíng)車輛的發(fā)車時(shí)刻表。公交車隊(duì)按照時(shí)刻表發(fā)車能夠達(dá)到最高的運(yùn)營(yíng)效率和服務(wù)水平。本題選用某市的某條線路運(yùn)營(yíng)車隊(duì)作為排班對(duì)象，不失一般性，只考慮

7、上行線路，即要優(yōu)化發(fā)車時(shí)刻表。所謂排班問(wèn)題就是為了某一目的面對(duì)共同使用的資源實(shí)行時(shí)間分配，通?？杀硎緸樵诘仁交蛘卟坏仁降募s束條件下，求解目標(biāo)函數(shù)的優(yōu)化。城市公交車輛運(yùn)輸系統(tǒng)是定時(shí)，定線行駛，并按客流量、流向的變化而不斷調(diào)節(jié)的隨機(jī)服務(wù)系統(tǒng)，其相應(yīng)的排班問(wèn)題有如下特點(diǎn)：（1） M為公交車輛集，每輛車在運(yùn)輸運(yùn)行中只遵循一種運(yùn)輸方式。（2） 每輛車按時(shí)發(fā)車，根據(jù)不同的運(yùn)行時(shí)段，準(zhǔn)時(shí)完成運(yùn)輸任務(wù)。公交車輛運(yùn)輸排班問(wèn)題是指，在固定行駛線路上，根據(jù)不同時(shí)段、依照一定的次序關(guān)系，合理地編排運(yùn)輸車輛運(yùn)行作業(yè)形式，以達(dá)到供需平衡，滿足系統(tǒng)的性能指標(biāo)。本文采用的優(yōu)化指標(biāo)為：在不影響乘客出行的前提下，乘客的等待時(shí)間和

8、公司發(fā)車次數(shù)最少，并避免出現(xiàn)“大間隔”。本文采用遺產(chǎn)算法優(yōu)化公交車輛運(yùn)營(yíng)排班問(wèn)題。三、模型的假設(shè)制定公交車調(diào)度方案需要考慮的因素非常多,且很多因素都是隨機(jī)的。為了抓住重點(diǎn),簡(jiǎn)化模型建立及求解,必須作一定的簡(jiǎn)化假設(shè)和設(shè)定：（1）各公交車為同一車輛類型；（2）在同一時(shí)間段內(nèi)，相鄰兩車發(fā)車時(shí)間間隔相等；（3）公交車按調(diào)度時(shí)間表準(zhǔn)時(shí)進(jìn)站和出站，車速恒定，保持勻速行駛，途中沒(méi)有堵車和意外事故；（4）各時(shí)段以內(nèi)乘客到站服從均勻分布；（5）每輛車經(jīng)過(guò)各個(gè)車站時(shí)不會(huì)留有乘客；（6）在車站等待的人絕大多數(shù)不會(huì)離去；（7）以分鐘作為最小的時(shí)間單位；四、符號(hào)說(shuō)明 表示平時(shí)第時(shí)段的時(shí)段長(zhǎng)度；表示平時(shí)第段時(shí)間的發(fā)車間隔

9、；表示節(jié)假日的時(shí)段長(zhǎng)度；表示節(jié)假日的發(fā)車間隔；表示第段時(shí)間的發(fā)車間隔（包括平時(shí)和節(jié)假日）；表示某月除去節(jié)假日后總的天數(shù)；表示某月節(jié)假日總的天數(shù)；表示某月發(fā)車總班次；表示在整個(gè)調(diào)度周期內(nèi)發(fā)車車次總數(shù)；表示線路的車站總數(shù)；表示第站在調(diào)度周期內(nèi)隨時(shí)間變化的乘客到達(dá)率（=1，2，）；表示目標(biāo)函數(shù)中總發(fā)車車次的加權(quán)系數(shù)；表示目標(biāo)函數(shù)中乘客總的等車時(shí)間的加權(quán)系數(shù)；表示線路總公里數(shù)；表示所有乘客總的等車時(shí)間（min）；表示乘客總的等車時(shí)間成本（元）；表示公交公司的總的運(yùn)行費(fèi)用（元）；五、模型的建立5.1 模型（問(wèn)題一的模型）5.1.1 確定目標(biāo)函數(shù)求某月最少班次就是為了某一目的面對(duì)共同使用的資源實(shí)行時(shí)間分配

10、，可表示為在等式或不等式的約束下，求解目標(biāo)函數(shù)的優(yōu)化。本題采用的優(yōu)化指標(biāo)為：在不影響乘客出行的前提下，使得公司發(fā)車班次最少。于是定義目標(biāo)函數(shù)某一月最少的發(fā)車班次為 ： (排車班次受到平時(shí)時(shí)間段和節(jié)假日時(shí)段的影響，故將排班次數(shù)分為平時(shí)時(shí)段與節(jié)假日時(shí)段兩種情況。上述目標(biāo)函數(shù)中為某月平時(shí)時(shí)段的發(fā)車總班次，為某月節(jié)假日時(shí)段的發(fā)車總班次。 5.1.2 確定約束條件 （1）最大最小發(fā)車時(shí)間間隔約束任意相鄰兩車之間的發(fā)車間隔要滿足最大最小發(fā)車時(shí)間間隔約束，即： (=1，2)其中：表示相鄰兩車之間的最大發(fā)車間隔();表示相鄰兩車之間的最小發(fā)車間隔()。（2）兩個(gè)相鄰的發(fā)車間隔之差的約束為保證發(fā)車時(shí)刻的連續(xù)性，

11、任意兩個(gè)相鄰的發(fā)車間隔之差不宜太大，即(=1，2)其中： 表示兩相鄰發(fā)車間隔之差的限值。5.2 模型（問(wèn)題二的模型）5.2.1 確定目標(biāo)函數(shù)公交司機(jī)排班是公交企業(yè)對(duì)社會(huì)的承諾，決定著為乘客服務(wù)的水平，發(fā)車間隔越小，服務(wù)水平越高，但是公交企業(yè)投入的成本越高，公交司機(jī)的排班應(yīng)是在滿足客流需求的前提下，盡量減少不必要的投入，這是個(gè)多目標(biāo)規(guī)劃問(wèn)題。以一個(gè)月內(nèi)總的發(fā)車次數(shù)來(lái)反映公交公司的利益，通過(guò)乘客的總的等車時(shí)間來(lái)反映乘客的利益。（1）考慮一月內(nèi)總的發(fā)車次數(shù)最少： (（2）一月內(nèi)乘客總的等車時(shí)間最短：=(這兩個(gè)目標(biāo)是相互聯(lián)系矛盾的，不可能同時(shí)達(dá)到雙方最小。當(dāng)增大時(shí)，第一項(xiàng)是在減小的，而第二項(xiàng)是在增大的

12、。這樣就形成了一個(gè)需要尋求平衡點(diǎn)的問(wè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ù)可知，平均每車公里的成本是260元，這個(gè)費(fèi)用包括了司乘人員的勞動(dòng)工資、車輛耗油、車輛折舊費(fèi)用等等各項(xiàng)費(fèi)用之和的折算。因此，一月內(nèi)總的發(fā)車車次由價(jià)值來(lái)衡量，可以折算為：= 260()(=1，2)第二項(xiàng)乘客總的等車時(shí)間也可以折算為乘客等車損失的費(fèi)用。根據(jù)有關(guān)資料的報(bào)道（河南省人民政府網(wǎng)/zwgk），許昌市2010年城鎮(zhèn)居民的平均工資水平為1374.19元/月，按照

13、雙休日工作及法定的放假時(shí)間，現(xiàn)在一個(gè)月大概有天的休息時(shí)間，即有天在工作，平均每天按工作8小時(shí)計(jì)算。平均每分鐘的工資為：=(元)乘客總的等車時(shí)間成本為：= (然后，通過(guò)加權(quán)系數(shù)和將價(jià)值化后的兩部分合并，使得公交優(yōu)化排班問(wèn)題成為一個(gè)單目標(biāo)優(yōu)化問(wèn)題。合并后的目標(biāo)函數(shù)：260 ()+(；目標(biāo)函數(shù)可以用乘客利益和公司利益分為兩類，這兩類目標(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í)間里所需的車輛數(shù)也是最多的。從乘

14、客的方面考慮，早上上班遲到對(duì)他的利益所示相當(dāng)大，因此乘客希望等車的時(shí)間比較短，這個(gè)時(shí)候乘客等車時(shí)間的加權(quán)系數(shù)要大些。初始化時(shí)取兩加權(quán)系數(shù)為0.2和0.8，然后在計(jì)算過(guò)程中根據(jù)結(jié)果逐步進(jìn)行比較、調(diào)整。5.2.2 確定約束條件（1）平均滿載率的約束平均滿載率= =其中：表示車輛滿載時(shí)的容量（人/車）；表示每車平均期望滿載率()。（2）最大最小發(fā)車時(shí)間間隔約束任意相鄰兩車之間的發(fā)車間隔要滿足最大最小發(fā)車時(shí)間間隔約束，即： (=1，2)其中：表示相鄰兩車之間的最大發(fā)車間隔();表示相鄰兩車之間的最小發(fā)車間隔()。六、模型的求解6.1 模型的求解由國(guó)家頒布的節(jié)假日安排可知，五月份的國(guó)家法定節(jié)日有五一勞動(dòng)

15、節(jié)（5月1日、2日、3日），雙休日為8天，則五月份公交司機(jī)的排班需按照：節(jié)假日有11天，正常有20天。我們知道五月份排班需按照夏令（4月11月），因此該線路的開(kāi)收班時(shí)間：6:2018:10。即=20，=11。則有： ( (=1，2)(=1，2)我們已經(jīng)知道平時(shí)的高峰時(shí)段為（上下班）：6:008:30，11:3013:30，16:3018:00；則非高峰時(shí)段為8:3011:30，13:3016:30，18:0018:10；又知道高峰時(shí)段的發(fā)車間隔需48分鐘/班，非高峰時(shí)段的發(fā)車間隔需810分鐘/班。節(jié)假日的發(fā)車間隔需510分鐘/班。將函數(shù)及數(shù)據(jù)帶入Lingo計(jì)算，得：平時(shí)發(fā)車間隔=10（分鐘/班

16、），高峰時(shí)段發(fā)車間隔=8（分鐘/班），節(jié)假日的發(fā)車間隔=10（分鐘/班）；此時(shí)得的最小值為2080+1172=2392即五月份最少需2392班次。發(fā)車班次時(shí)間表五月開(kāi)收班時(shí)間6:2018:10平時(shí)正常8:3011:3013:3016:3018:0018:10810分鐘/班高峰6:008:3011:3013:3016:3018:0048分鐘/班節(jié)假日510分鐘/班發(fā)車時(shí)間節(jié)假日06:2006:3006:4006:5007:0007:1007:2007:3007:4007:5008:0008:1008:2008:3008:4008:5009:0009:1009:2009:3009:4009:501

17、0:0010:1010:2010:3010:4010:5011:0011:1011:2011:3011:4011:5012:0012:1012:2012:3012:4012:5013:0013:1013:2013:3013:4013:5014:0014:1014:2014:3014:4014:5015:0015:1015:2015:3015:4015:5016:0016:1016:2016:3016:4016:5017:0017:1017:2017:3017:4017:5018:0018:10發(fā)車時(shí)間平時(shí)06:2006:2806:3606:4406:5207:0007:0807:1607:24

18、07:3207:4007:4807:5608:0408:1208:2008:2808:3808:4808:5809:0809:1809:2809:3809:4809:5810:0810:1810:2810:3810:4810:5811:0811:1811:2811:3611:4411:5212:0012:0812:1612:2412:3212:4012:4812:5613:0413:1213:2013:2813:3813:4813:5814:0814:1814:2814:3814:4814:5815:0815:1815:2815:3815:4815:5816:0816:1816:2816:36

19、16:4416:5217:0017:0817:1617:2417:3217:4017:4817:5618:06節(jié)假日時(shí)每天發(fā)車班次為72班平時(shí)每天發(fā)車班次為80班6.2 模型的求解本實(shí)驗(yàn)的數(shù)據(jù)是許昌市公交公司某線路的客流數(shù)據(jù)?？土餍畔⑷鐖D所示： 圖2 客流信息時(shí)刻分布圖從上表可以看出6:008:30，11:3013:30，16:3018:00是乘客乘車的高峰時(shí)段。在滿足乘客出行的前提下，根據(jù)高峰時(shí)段乘客量及發(fā)車的時(shí)間間隔來(lái)做出合理的車輛排班計(jì)劃。遺傳算法的參數(shù)：種群規(guī)模為48，個(gè)體選擇采用適應(yīng)度的輪盤賭選擇法，交叉概率為0.8，變異概率為0.05，迭代次數(shù)50次。在30代完全運(yùn)行完畢以后，可以

20、得到最優(yōu)的個(gè)體。根據(jù)這個(gè)最優(yōu)個(gè)體，可以計(jì)算出在每個(gè)時(shí)段的發(fā)車班次如圖3，并根據(jù)各個(gè)時(shí)段的發(fā)車間隔做出車輛的排班計(jì)劃。圖3 平時(shí)時(shí)段發(fā)車次數(shù)分布圖圖4 節(jié)假日發(fā)車次數(shù)分布圖七、模型的擴(kuò)展與評(píng)價(jià)綜上可見(jiàn)，遺傳算法應(yīng)用于公交車輛排班具有很好的效果，它能夠在排班優(yōu)化問(wèn)題的巨大搜索空間中可靠的找到最優(yōu)近似解，當(dāng)然本文在具體的運(yùn)算過(guò)程中，對(duì)乘客流量的分布設(shè)置具有很大的假定性，同時(shí)認(rèn)為公交車輛勻速行駛也不符合實(shí)際情況。但是從遺傳算法的鹽酸過(guò)程可以看出，算法的收斂性并不依賴于乘客的分布形式或者道路的通行狀況，因此在實(shí)際應(yīng)用過(guò)程中，只要乘客流量分布和道路狀況能夠比較準(zhǔn)確給出，本文所涉及的遺傳算法就能夠得出一個(gè)相當(dāng)好的結(jié)果。關(guān)于能力的分析是公路設(shè)備運(yùn)輸運(yùn)用和服務(wù)水平確定的重要基礎(chǔ)之一。本文結(jié)合國(guó)內(nèi)外能力研究的成果，從服務(wù)質(zhì)量角度提出了能力評(píng)價(jià)的理論和方法，從總體上看，這種理論的基礎(chǔ)是突出“以人為本”的理念，論文根據(jù)公路區(qū)段、車站運(yùn)輸設(shè)備運(yùn)用的特點(diǎn)，