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

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

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

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

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

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

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

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

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

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

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

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

12、。這樣就形成了一個需要尋求平衡點的問題，得到總體的最優(yōu)?，F(xiàn)在將兩項加權(quán)合并為單目標函數(shù)，這里我們考慮將兩項都這算為一種費用。第一項總的發(fā)車車次可折算為公交公司的運輸費用。我們由公交公司的調(diào)研數(shù)據(jù)可知，平均每車公里的成本是260元，這個費用包括了司乘人員的勞動工資、車輛耗油、車輛折舊費用等等各項費用之和的折算。因此，一月內(nèi)總的發(fā)車車次由價值來衡量，可以折算為：= 260()(=1，2)第二項乘客總的等車時間也可以折算為乘客等車損失的費用。根據(jù)有關(guān)資料的報道（河南省人民政府網(wǎng)/zwgk），許昌市2010年城鎮(zhèn)居民的平均工資水平為1374.19元/月，按照

13、雙休日工作及法定的放假時間，現(xiàn)在一個月大概有天的休息時間，即有天在工作，平均每天按工作8小時計算。平均每分鐘的工資為：=(元)乘客總的等車時間成本為：= (然后，通過加權(quán)系數(shù)和將價值化后的兩部分合并，使得公交優(yōu)化排班問題成為一個單目標優(yōu)化問題。合并后的目標函數(shù)：260 ()+(；目標函數(shù)可以用乘客利益和公司利益分為兩類，這兩類目標是相互沖突的，兩個目標函數(shù)就存在一個權(quán)值的問題，體現(xiàn)在目標函數(shù)中兩項的加權(quán)系數(shù)的大小。在不同的線路，甚至同一線路的不同時段加權(quán)系數(shù)的最優(yōu)值都是不相同的。例如：工作日的高峰正是多數(shù)乘客上班時間，也是一天中乘坐公交車人數(shù)的高峰期，所以這段時間里所需的車輛數(shù)也是最多的。從乘

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

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

16、），高峰時段發(fā)車間隔=8（分鐘/班），節(jié)假日的發(fā)車間隔=10（分鐘/班）；此時得的最小值為2080+1172=2392即五月份最少需2392班次。發(fā)車班次時間表五月開收班時間6:2018:10平時正常8:3011:3013:3016:3018:0018:10810分鐘/班高峰6:008:3011:3013:3016:3018:0048分鐘/班節(jié)假日510分鐘/班發(fā)車時間節(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ā)車時間平時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é)假日時每天發(fā)車班次為72班平時每天發(fā)車班次為80班6.2 模型的求解本實驗的數(shù)據(jù)是許昌市公交公司某線路的客流數(shù)據(jù)?？土餍畔⑷鐖D所示： 圖2 客流信息時刻分布圖從上表可以看出6:008:30，11:3013:30，16:3018:00是乘客乘車的高峰時段。在滿足乘客出行的前提下，根據(jù)高峰時段乘客量及發(fā)車的時間間隔來做出合理的車輛排班計劃。遺傳算法的參數(shù)：種群規(guī)模為48，個體選擇采用適應(yīng)度的輪盤賭選擇法，交叉概率為0.8，變異概率為0.05，迭代次數(shù)50次。在30代完全運行完畢以后，可以

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