公交车排班模型.docx

-公交车排班模型中的线性规划求解问题摘要本文研究的是在满足各时段（早高峰、日间平峰、晚高峰，晚平峰四个时段）时间，公交车以一定间隔连续发车的条件下，排班的最优问题。根据各小题的约束条件，用运筹学中的线性规划知识建立模型，再利用Lingo求解,分别算出所需公交车总数以及单班车、双班车各需求量，制定排班的优化方案。对于题目条件，我们有三个设想，其一，根据现实生活经验可知，公交车发车间隔相对固定，方便市民安排计划候车出行；其二，从简化模型的角度考虑，每辆车的司机固定，即司机间不允许换车开车；其三，单班车一天不超过5个班次，即认定为所有单班车一天总班次相加不超过5班。对于题目一，从各班次发车间隔相等这一假定条件出发，要使在早高峰时段运行的车辆数最少，只需发车间隔尽可能大，于是我们取早的最大发车间隔5分钟来安排发车，由于该题无对单班车数量的其他要求，我们假定单班车在早高峰时段安排2辆，同时考虑到车辆要完成一个班次的运行后才可进行下一班次，建立相关模型，用Lingo编程求解得早高峰时段总共运行24个班次，所需的最少公交车数为16辆。对于问题二，在已有模型的基础上，综合考虑全天的工作安排，发车间隔仍取每个阶段的最大发车间隔，同样的，考虑到单班车只在高峰期运行，在早高峰运行2到3个班次，在晚高峰运行2到3个班次，且每天运行不超过五个班次，根据资源利用的最大化原则，我们知道单班车数不能超过3辆，这里我们仍假设单班车数为2辆，根据题目要求，我们要使每辆公交车的工作时间和上下午司机的工作时间尽可能均匀，且要使车辆的利用率得到最大，根据以上条件建立公交车排班模型，用Lingo编程求解得全天总共运行120个班次，所需的最少公交车数为16辆。具体公交车排班计划表见表21。对于问题三，该题约束了单班车数量不少于3辆，由问题二的分析既得单班车数量为3辆，改变问题二模型中的相关参数，用Lingo编程求解得全天总共运行120个班次，所需的最少公交车数为16辆。具体公交车排班计划表见表31。对于问题四，进行调整后，全天共六个时段，并且增加了限制条件，根据问题二的方法，增加双班车数量、餐点和换班时间的约束，用Lingo编程求解得全天总共运行191个班次，所需的最少公交车数为22辆。关键词：公交车排班线性规划 Lingo建模贝叶斯算法一、问题重述（一）、问题背景随着*市经济的快速发展，公交车系统对于人们的出行扮演着越来越重要的角色。在公交车资源有限的情况下，合理的编排公交车的行车计划成为公交公司亟待解决的问题。以下给出公交车排班问题中的部分名词说明和假设。（1）班次：1辆公交车从起点出发到达终点停止为1个班次。（2）公交车公司有两种类型的班车：单班车和双班车。除非特殊说明，单班车和双班车都可以用于公交车排班。（3）单班车：由同一个驾驶员驾驶的公交车。单班车通常要求在早高峰跑2-3个班次，晚高峰2-3个班次，一天不超过5个班次。（4）双班车：由两个驾驶员驾驶的公交车。双班车要求上、下午各一个司机，上午和下午司机的工作时间尽可能均匀，并且都不超过8小时。每辆双班车一天运行不超过10个班次。（5）公交车运行的单程时间，已经包含乘客在各站(包括起点和终点)的上下车时间。（6）假设每辆公交车可以运行1整天不需要加油。（7）末班车的发车时间，可以在原有发车间隔的基础上调整2分钟（±2分钟）。（8）本题以简单的环路公交路线为例，即公交车从A点出发，经过一系列站点后再次回到A点为1个班次。（9）最短停站时间是指公交车完成1个班次之后，开始运行下一个班次之前，需要在终点停留的最短的时间。在问题1-3中，每辆公交车的最短停站时间为0，即：公交车回到终点后不需要停留，可以继续进行下一班次的运行。（二）、问题要求问题1. *市2路公交车，从*市火车站出发后经沿途站点后回到*市火车站，2路公交车行车信息如表1。请建立数学模型，计算*市2路公交车，在早高峰时段(6:00-8:00)运行所需要使用的最少公交车数量(需要给出含单班车和双班车各多少辆)。问题2. 在问题1的基础上，请建立数学模型并设计相应的求解算法，给出*市2路公交车完成一整天的运行所需要最少的公交车的数量(需要给出含单班车和双班车各多少辆)，并按照表2的格式给出公交车排班计划表。问题3. 在问题2的基础上，如果要求单班车不少于3辆，请建立数学模型并设计相应的求解算法，给出*市2路公交车完成一整天的运行所需要最少的公交车的数量(需要给出含单班车和双班车各多少辆)，并按照表2的格式给出公交车排班计划表。问题4. 在公交车排班过程中，除以上要求之外，还需要考虑如下的实际因素的限制：（a）单班车司机不安排吃饭，所有双班车司机都安排吃饭(早餐和晚餐)，每餐饭需要20分钟用餐时间。早餐8:00开始供应，10:00截止；晚餐18:00开始供应，20:00截止。（b）限定双班车辆的数量为19辆。（c）双班车辆运行5班次以后，上午、下午班司机进行换班，换班时间最少为20分钟(含最短停站时间)。请建立数学模型并设计相应的求解算法，并以表3给出的行车信息表为例，给出*市2路公交车行车信息调整后，完成一整天的运行所需要最少的公交车的数量(需要给出含单班车和双班车各多少辆)，并按照表2的格式给出公交车排班计划表。附录：表1 *市2路公交车行车信息表时段性质时段开始时间时段结束时间单程时间(分钟)发车间隔(分钟)最短停站时间(分钟)早高峰时段06:0008:00804.0±1.00日间平峰时段08:0016:00707.0±2.00晚高峰时段16:0018:00804.0±2.00晚平峰时段18:0020:30754.5±2.50表2 *市2路公交车排班计划表车辆编号车辆性质(填写单班或双班)起点发车时间返回终点时间每辆车的总的班次上午司机班次(仅双班车需要填写)下午司机班次(仅双班车需要填写)12.汇总信息：总车辆数( )，总双班车数量( )，总单班车数量( )，所有车的总班次数( )注：本表格可以根据需要增减行数（第一行和最后一行不能删除），不能增减列数。表3 调整后的*市2路公交车行车信息表时段性质时段开始时间时段结束时间单程时间(分钟)发车间隔(分钟)最短停站时间(分钟)早平峰时段04:3005:00707.0±2.010早平峰时段05:0006:00704.5±1.510早高峰时段06:0008:00753.0±1.010日间平峰时段08:0016:00754.5±1.510晚高峰时段16:0018:00753.0±1.010晚平峰时段18:0022:15706.5±2.010二、问题分析公交车排班模型中的四个问题的处理要分两个步骤进行：第一，确定该时段时间以及发车间隔，并根据相关假设，确定约束条件；第二，在最少公交车总数已确定的条件下，算出单班车、双班车数的最优解及排班方式。具体分析如下：四个问题均是典型的线性规划模型及求解的问题。故该问题的求解步骤如下：首先应确定该问题的目标函数，再确定决策变量，并表示出所有的约束条件，最后用Lingo编程求解即可。三、模型假设1.公交车车速恒定，平稳行驶，途中没有堵车以及意外发生；2.以分钟作为最小时间单位；3.各班次的发车间隔都相等；4.每辆车的司机固定，即司机间不允许换车行驶；5.单班车一天不超过5个班次认为所有单班车一天总班次相加不超过5班；6.在高峰、平峰交接点临近时，若所剩余时间已不足于当前时段的发车间隔，则按照下一时段的发车间隔来排班。四、符号说明1，：每个时段公交车发车总数，i=1,2,3,4,5,6；2，：每个时段公交车单班车发车总数，i=1,2,3,4,5,6；3，：每个时段公交车双班车发车总数，i=1,2,3,4,5,6；4，：全天公交车发车班次总数；5，：每个时段公交车发车班次数，i=1,2,3,4,5,6；6，：每个时段公交车发车间隔，i=1,2,3,4,5,6；7，：每个时段时长，i=1,2,3,4,5,6；五、模型的建立与求解从所要解决的的问题和对问题所做的假设出发，本文对问题一建立了模型，求得早高峰时段所需的最少公交车数为16辆；对问题二建立了模型，求得全天所需最少公交车数为16辆；对问题三建立了模型，求得全天所需最少公交车数为16辆；对问题四建立了模型，求得全天所需最少公交车数为22辆。问题一的求解：模型的一般表达式：此模型中，以早高峰公交车发车总数为目标函数，以早高峰单班车数和早高峰双班车数为决策变量，以每车单程时间处于发车总数与发车间隔的乘积这一区间为约束条件，建立最优化模型。由于早高峰的发车间隔为41（分钟），根据假设3，各班次的发车间隔都相等，因此在早高峰的2个小时内，每辆公交车的发车间隔都相同，为3,4,5分钟中的一个，故设其为，且由题干知，单班车通常要在早高峰时段跑2-3个班次，相对于双班车没有班次限制这一优点，单班车较浪费资源，故我们假定早高峰时段单班车排班尽可能少，仅排2个班次，即=2。经过上述分析，我们建立以下模型：目标函数：min M1=M11+M12约束条件：s.t.M11+M12×t180M11+M12-1×t1<80M11=23t15M1,M12,t1Z模型求解：编写程序，运用Lingo求解得出M11=2，M12=13.9999，t1=5，根据整数约束显然可知，间隔时间为5分钟，早高峰时段所需的最少公交车数为16辆，其中单班车2辆，双班车14辆。程序及运行结果见附录1。问题二的求解：模型的一般表达式：此模型中，根据全天四个时段时长的不同，并以各班次发车间隔相等这一假定条件，以全天公交车发车班次总数为目标函数，以四个时段的发车班次为决策变量，以每个时段时长处于发车总数与发车间隔的乘积这一区间为约束条件，建立最优模型。问题二建立在问题一的基础上，由于在问题一中我们已经求得早高峰这一时段所需的最少公交车数为16辆（其中2辆单班车，14辆双班车），因此，我们可以提出一可行想法：能否运用这16辆公交车合理规划，完成一天的乘客运输任务？为解决这一问题，我们先假设能够用这16辆公交车进行全天的排班，则只要能够求出各时段的班次数，进而得全天的班次数后，我们就能对全天进行排班。经过上述分析，我们建立如下模型：目标函数：min P=i=14 Ni约束条件：s.t. i=1k Ni×tii=1k Qi k=1,2,3,4 i=1k Ni×ti-tki=1k Qi k=1,2,3,43t155t292t362t47模型求解：编写程序，运用Lingo求解得出早高峰间隔时间为5分钟，早平峰间隔9分钟，晚高峰间隔时间6分钟，晚平峰间隔7分钟，全天所需的最少公交车数为16辆，其中单班车2辆，双班车14辆，程序及运行结果见附录2。对于lingo求解的结果进行分析，我们可以看到，最后所求得的最小班次为119班，然而，在排班的最后，我们可以发现，编号为8的公交车倒数第二个班次返回终点的时间为20:29，然而截止晚平峰截止时间为20:30，根据题干要求：末班车的发车时间，可以在原有发车间隔的基础上调整2分钟（±2分钟），而晚平峰发车间隔为2-7分钟，因此，编号为8的公交车末班车在20:30分发车，因此在原有的119个班次上再加一班,为120班。表21*市2路公交车排班计划表车辆编号车辆性质(填写单班或双班)起点发车时间返回终点时间每辆车的总的班次上午司机班次(仅双班车需要填写)下午司机班次(仅双班车需要填写)1双班车6:007:208447:208:408:5410:0411:0012:1013:0614:1615:1216:2216:5718:1718:2519:402双班车6:057:258447:258:459:0310:1311:0912:1913:1514:2515:2116:3117:0318:2318:3219:473双班车6:107:308447:308:509:1210:2211:1812:2813:2414:3415:3016:4017:0918:2918:3919:544双班车6:157:358447:358:559:2110:3111:2712:3713:3314:4315:3916:4917:1518:3518:4620:015双班车6:207:408447:409:009:3010:4011:3612:4613:4214:5215:4816:5817:2118:4118:5320:086双班车6:257:459457:459:059:3910:4911:4512:5513:5115:0115:5717:0717:2718:4719:0020:1520:1721:327双班车6:307:509457:509:109:4810:5811:5413:0414:0015:1016:0317:2317:3318:5319:0720:2220:2421:398双班车6:357:559457:559:159:5711:0712:0313:1314:0915:1916:0917:2917:3918:5919:1420:2920:3021:459双班车6:408:008448:009:1010:0611:1612:1213:2214:1815:2816:1517:3517:4519:0719:2120:3610双班车6:458:058448:099:1910:1511:2512:2113:3114:2715:3716:2117:4117:5119:1119:2820:4311双班车6:508:108448:189:2810:2411:3412:3013:4014:3615:4616:2717:4717:5719:1719:3520:5012双班车6:558:158448:279:3710:3311:4312:3913:4914:4515:5516:3317:5318:0419:1919:4220:5713双班车7:008:208448:369:4610:4211:5212:4813:5814:5416:0416:3917:5918:1119:2619:4921:0414双班车7:058:258448:459:5510:5112:0112:5714:0715:0316:1316:4518:0518:1819:3319:5621:1115单班车7:108:30216:5118:1116单班车7:158:351汇总信息：总车辆数(16)，总双班车数量(14)，总单班车数量(2)，所有车的总班次数(120)问题三的求解：模型的一般表达式：此模型中，由于仍是求全天公交车最少的数量，因此基本的思想方法与问题二相同，但根据题干给出的限制条件，模型需要进行修改。问题三建立在问题二的基础上，由于在问题二中我们已经求得全天所需的最少公交车数为16辆（其中2辆单班车，14辆双班车），但是，由资源约束可知，单班车一天行驶班次不超过5次，通常要求在早高峰跑2-3个班次，晚高峰2-3个班次，因此可知，单班车数量需小于4辆（若恰好4辆，全部利用的最小班次也是各开一班，不满足跑2-3个班次），而由题干条件可知单班车需不少于3辆，则显然单班车的数量即限制为3辆。而双班车的数量是否还是13辆，我们则需要再次建模确定，不妨仍旧考虑早高峰期间的公交车排班。经过上述分析，我们建立如下模型：目标函数：min M1=M11+M12约束条件：s.t.M11+M12×t180M11+M12-1×t1<80M11=33t15模型求解：编写程序，运用Lingo求解得出M11=3，M12=12.9999，t1=5，根据整数约束显然可知，间隔时间为5分钟，早高峰时段所需的最少公交车数为16辆，其中单班车3辆，双班车13辆。程序及运行结果见附录3。因此，我们可以做出假设：能够用这16辆公交车进行全天的排班，则只要能够求出各时段的班次数，进而得全天的班次数后，我们就能对全天进行排班。而排班的班次模型代码则与问题二一致（详见附录二）。对于lingo求解的结果进行分析，我们可以看到，最后所求得的最小班次为119班，然而，在排班的最后，我们可以发现，编号为8的公交车倒数第二个班次返回终点的时间为20:29，然而截止晚平峰截止时间为20:30，根据题干要求：末班车的发车时间，可以在原有发车间隔的基础上调整2分钟（±2分钟），而晚平峰发车间隔为2-7分钟，因此，编号为8的公交车末班车在20:30分发车，因此在原有的119个班次上再加一班,为120班。表31 *市2路公交车排班计划表车辆编号车辆性质(填写单班或双班)起点发车时间返回终点时间每辆车的总的班次上午司机班次(仅双班车需要填写)下午司机班次(仅双班车需要填写)1双班车6:007:209547:208:408:459:5510:4211:5212:3913:4914:3615:4616:2117:4117:4519:0719:1420:292双班车6:057:259547:258:458:5410:0410:5112:0112:4813:5814:4515:5516:2717:4717:5119:1119:2120:363双班车6:107:309547:308:509:0310:1311:0012:1012:5714:0714:5416:0416:3317:5317:5719:1719:2820:434双班车6:157:359457:358:559:1210:2211:0912:1913:0614:1615:0316:1316:3917:5918:0419:1919:3520:505双班车6:207:409457:409:009:2110:3111:1812:2813:1514:2515:1216:2216:4518:0518:1119:2619:4220:576双班车6:257:459457:459:059:3010:4011:2712:3713:2414:3415:2116:3116:5118:1118:1819:3319:4921:047双班车6:307:509457:509:109:3910:4911:3612:4613:3314:4315:3016:4016:5718:1718:2519:4019:5621:118双班车6:357:559457:559:159:4810:5811:4512:5513:4214:5215:3916:4917:0318:2318:3219:4720:0321:189双班车6:408:009458:009:109:5711:0711:5413:0413:5115:0115:4816:5817:0918:2918:3919:5420:1021:2510双班车6:458:059458:099:1910:0611:1612:0313:1314:0015:1015:5717:0717:1518:3518:4620:0120:1721:3211双班车6:508:109458:189:2810:1511:2512:1213:2214:0915:1916:0317:2317:2718:4718:5320:0820:2421:3912双班车6:558:159458:279:3710:2411:3412:2113:3114:1815:2816:0917:2917:3318:5319:0020:1520:3021:4513双班车7:008:208448:369:4610:3311:4312:3013:4014:2715:3716:1517:3517:3918:5919:0720:2214单班车7:058:25217:2118:4115单班车7:108:30116单班车7:158:351汇总信息：总车辆数(16)，总双班车数量(13)，总单班车数量(3)，所有车的总班次数(120)问题四的求解：模型的一般表达式：此模型中，由于仍是求全天公交车最少的数量，因此基本的思想方法与问题二相同，但根据题干给出的限制条件，模型需要进行修改，下面简述约束条件的一些限制：硬约束：行车时间应不超过8小时；双班车辆运行5班次以后，上午、下午班司机进行换班，换班时间最少为20分钟(含最短停站时间)。软约束：任一班次驾驶段时间长度不可超过相应班型最短和最长工作时间长度；所有双班车司机都安排吃饭(早餐和晚餐)，每餐饭需要20分钟用餐时间。早餐8:0010:00；晚餐18:0020:00；用餐必须在规定的时间*围内完成，并且在指定的可用餐地点进行。由于题干已经给出条件：（b）限定双班车辆的数量为19辆，因此我们先对双班车进行排班，最终缺少的车辆即安排单班车，最终求解得到3辆单班车，具体计划表如下：表41 *市2路公交车排班计划表车辆编号车辆性质(填写单班或双班)起点发车时间返回终点时间每辆车的总的班次上午司机班次(仅双班车需要填写)下午司机班次(仅双班车需要填写)1双班车4:305:4010556:217:367:499:049:3910:5411:3312:4813:2714:4215:0116:1616:2917:4417:5419:0920:2221:322双班车4:395:4910556:257:407:539:089:4511:0011:3912:5413:3214:4715:0616:2116:3317:4817:5819:1320:3021:403双班车4:485:5810556:297:447:579:129:5111:0611:4513:0013:3714:5215:1116:2616:3717:5218:0619:1620:3821:484双班车4:576:0710556:337:488:039:189:5711:1211:5113:0613:4214:5715:1616:3116:4117:5618:1419:2420:4621:565双班车5:036:1310556:377:528:099:2410:0311:1811:5713:1213:4715:0215:2116:3616:4918:0418:2219:3220:5422:046双班车5:096:1910556:417:568:159:3010:0911:2412:0313:1813:5215:0715:2616:4116:5318:0818:3019:4021:0222:127双班车5:156:2510556:458:008:219:3610:1511:3012:0913:2413:5715:1215:3116:4616:5718:1218:3819:4821:1022:208双班车5:216:3110556:498:048:279:4210:2111:3612:1513:3014:0215:1715:3616:5117:0118:1618:4619:5621:1822:289双班车5:276:3710556:538:088:339:4810:2711:4212:2113:3614:0715:2215:4016:5517:0518:2018:5420:0421:2622:3610双班车5:336:4310556:578:128:399:5410:3311:4812:2713:4214:1215:2715:4517:0017:1318:2819:0220:1221:3422:4411双班车5:396:4910557:018:168:4510:0010:3911:5412:3313:4814:1715:3215:5017:0517:1718:3219:1020:2021:4222:5212双班车5:456:5510557:058:208:5110:0610:4512:0012:3913:5414:2215:3715:5517:1017:2118:3619:1820:2821:5023:0013双班车5:517:0110557:138:288:5710:1210:5112:0612:4514:0014:2715:4216:0017:1517:2518:4019:2620:3621:5823:0814双班车5:577:0710557:178:329:0310:1810:5712:1212:5114:0614:3215:4716:0517:2017:3018:4519:3420:4422:0623:1615双班车6:017:1610557:298:449:0910:2411:0312:1812:5714:1214:3715:5216:0917:2417:3418:4919:4220:5222:1523:2516双班车6:057:209547:338:489:1510:3011:0912:2413:0314:1814:4215:5716:1317:2817:3818:5319:5021:0017双班车6:097:249547:378:529:2110:3611:1512:3013:0914:2414:4716:0216:1717:3217:4218:5719:5821:0818双班车6:137:289547:418:569:2710:4211:2112:3613:1514:3014:5216:0716:2117:3617:4619:0120:0621:1619双班车6:177:329547:459:009:3310:4811:2712:4213:2114:3614:5716:1216:2517:4017:5019:0520:1421:2420单班车7:098:24216:4518:0021单班车7:218:36217:0918:2422单班车7:258:401汇总信息：总车辆数(22)，总双班车数量(19)，总单班车数量(3)，所有车的总班次数(191)六、模型的结果与评价一、模型的结果对于题目一，求解得早高峰时段总共运行24个班次，所需的最少公交车数为16辆。对于问题二，在已有模型的基础上，综合考虑全天的工作安排，用Lingo编程求解得全天总共运行120个班次，所需的最少公交车数为16辆。具体公交车排班计划表见表21。对于问题三，改变问题二模型中的相关参数，用Lingo编程求解得全天总共运行120个班次，所需的最少公交车数为16辆。具体公交车排班计划表见表31。对于问题四，增加双班车数量、餐点和换班时间的约束，用Lingo编程求解得全天总共运行191个班次，所需的最少公交车数为22辆。二、模型的评价优点：（1）文中数据以表格的方式给出，较为清晰，直观；（2）先求解出四个阶段的班次数，再细化求解所需最少车辆数，简化了模型，更利用求解。（3）模型理论严谨，假设大胆合理。（4）模型能与实际紧密联系，结合实际情况对所提出的问题进行求解，使模型更贴近实际，通行性、推广性更强。缺点：（1）该模型由于对公交车的排班问题已经简化，没有考虑到客流量以及乘客的满意程度，所以模型需进一步完善。（2）该问题中的班次排列中班次的时间间隔没有做到完全的规定，对于乘客来说，这样的安排不能够更好的进行搭乘。七、参考文献1邓婕./运用贝叶斯优化算法求解驾驶员调度问题idu./view/81b571e948d7c1c709a14564.html?qq-pf-to=pcqq.discussion，；2*道元等./ 数学建模案例精选P28-41页: 科学,2003. 3；3 清华大学数学建模讲义关于集循环函数应用章节（姜启源）/网络查询2009.5；八、附录附录1模型的一般表达式：model:min=M11+M12;(M11+M12)*t1>=80;(M11+M12-1)*t1<80;3<=t1;t1<=5;M11=2;gin(M12);gin(t1);end附录2模型的一般表达式：model:min=N1+N2+N3+N4;Q1=120;Q2=480;Q3=120;Q4=150;N1*t1>=Q1;N1*t1+N2*t2>=Q1+Q2;N1*t1+N2*t2+N3*t3>=Q1+Q2+Q3;N1*t1+N2*t2