2011数学建模--公交司机排班方案模型--模拟.doc

2010高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2011 年07 月 24 日赛区评阅编号（由赛区组委会评阅前进行编号）：2010高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：公交司机排班方案模型摘要本文就公交司机排班问题应用遗传算法和多目标规划建立数学模型。运营车辆智能排班问题是公交车辆智能调度需要解决的典型问题之一，本文应用已有的数据，并兼顾到乘客和公交公司的双重利益，建立起一个符合实际情况的数学模型。在此基础上引入了遗传算法（GA），针对公交智能排班问题，构造了符合行车规律的编码方式、遗传算子，并实现了程序的编码工作，最后进行了模拟实验。问题一在一定的约束条件下，如何合理安排其组织部分（操作）所占有资源、运行时间及先后顺序，以获得运输成本或时间最优化。在理论研究中，车辆班次问题可看做资源分配问题。问题二在保证运营效率的情况下寻求乘客等待时间最少和保证服务水平的前提下使车队运营效率较高，基于以上的考虑行车时刻表的编制应是在满足客流需求的前提下，尽量减少不必要的投入，这是个多目标优化问题，遗传算法是解决公交排班问题的有效方法之一。问题三是在一定的约束条件下，合理安排排班方案使司机总数最少，以达到资源的合理分配。关键词：公交智能排班；遗传算法；遗传算子一、问题的重述目前，随着某市经济进一步的发展，道路变得越来越多。公交优先，百姓优先，为此某市公交总公司开辟了各种线路，有市内线，近郊线，远郊线，旅游线，机场线，社区线等140多条线路，以满足老百姓出行需要。而现实是有的线路司机不足，常常存在向其他车队借调司机和车辆跑班，影响其他线路的排班秩序；有的线路司机需要每天开车1213小时，影响司机的休息，从而给交通留下安全隐患；有的线路因经常堵车，打乱了线路调度计划，使得交接班司机和乘客怨声载道。一般，公交公司按月给司机排班。下面是某条线路的基本情况（附件），请你根据有关数据完成下列问题。规定：（1）司机每天上班时间不超过8小时；（2）司机连续开车不得超过4小时；（3）每名司机至少每月完成120班次。问题一：根据五月份的节假日情况，求出当月最少班次总数；问题二：阐述你对上述规定的理解，并根据你的理解建立适当的数学模型，合理地设计五月份该线路的司机排班方案；问题三： 根据五月份该线路的司机排班方案，计算出每天需要的司机人数，假如规定每个司机每周连续工作五天，休息两天。请你通过某周（周一至周日）需要司机人数求出司机总数最少的排班方案。有关的数据为：1、该线路的开收班时间：冬令（12月3月）：6:1518:20， 夏令（4月11月）：6:2018:102、该线路的司机人数：15人3、该线路排班间隔：平时：810分钟/班；高峰（上下班）：6:008:30，11:3013:30，16:3018:00：48分钟/班节假日：510分钟/班4、该线路的运行时间:正常：8085分钟/班高峰：100120分钟/班二、问题的分析公交车排班问题是城市公交调度的核心内容，是公交调度人员、司乘人员进行工作以及公交车辆正常运行的基本依据。公交排班的目的是确定最优或者近似最优的运营车辆的发车时刻表。公交车队按照时刻表发车能够达到最高的运营效率和服务水平。本题选用某市的某条线路运营车队作为排班对象，不失一般性，只考虑上行线路，即要优化发车时刻表。所谓排班问题就是为了某一目的面对共同使用的资源实行时间分配，通常可表示为在等式或者不等式的约束条件下，求解目标函数的优化。城市公交车辆运输系统是定时，定线行驶，并按客流量、流向的变化而不断调节的随机服务系统，其相应的排班问题有如下特点：（1） M为公交车辆集，每辆车在运输运行中只遵循一种运输方式。（2） 每辆车按时发车，根据不同的运行时段，准时完成运输任务。公交车辆运输排班问题是指，在固定行驶线路上，根据不同时段、依照一定的次序关系，合理地编排运输车辆运行作业形式，以达到供需平衡，满足系统的性能指标。本文采用的优化指标为：在不影响乘客出行的前提下，乘客的等待时间和公司发车次数最少，并避免出现“大间隔”。本文采用遗产算法优化公交车辆运营排班问题。三、模型的假设制定公交车调度方案需要考虑的因素非常多,且很多因素都是随机的。为了抓住重点,简化模型建立及求解,必须作一定的简化假设和设定：（1）各公交车为同一车辆类型；（2）在同一时间段内，相邻两车发车时间间隔相等；（3）公交车按调度时间表准时进站和出站，车速恒定，保持匀速行驶，途中没有堵车和意外事故；（4）各时段以内乘客到站服从均匀分布；（5）每辆车经过各个车站时不会留有乘客；（6）在车站等待的人绝大多数不会离去；（7）以分钟作为最小的时间单位；四、符号说明 表示平时第时段的时段长度；表示平时第段时间的发车间隔；表示节假日的时段长度；表示节假日的发车间隔；表示第段时间的发车间隔（包括平时和节假日）；表示某月除去节假日后总的天数；表示某月节假日总的天数；表示某月发车总班次；表示在整个调度周期内发车车次总数；表示线路的车站总数；表示第站在调度周期内随时间变化的乘客到达率（=1，2，）；表示目标函数中总发车车次的加权系数；表示目标函数中乘客总的等车时间的加权系数；表示线路总公里数；表示所有乘客总的等车时间（min）；表示乘客总的等车时间成本（元）；表示公交公司的总的运行费用（元）；五、模型的建立5.1 模型（问题一的模型）5.1.1 确定目标函数求某月最少班次就是为了某一目的面对共同使用的资源实行时间分配，可表示为在等式或不等式的约束下，求解目标函数的优化。本题采用的优化指标为：在不影响乘客出行的前提下，使得公司发车班次最少。于是定义目标函数某一月最少的发车班次为 ： (排车班次受到平时时间段和节假日时段的影响，故将排班次数分为平时时段与节假日时段两种情况。上述目标函数中为某月平时时段的发车总班次，为某月节假日时段的发车总班次。 5.1.2 确定约束条件 （1）最大最小发车时间间隔约束任意相邻两车之间的发车间隔要满足最大最小发车时间间隔约束，即： (=1，2)其中：表示相邻两车之间的最大发车间隔();表示相邻两车之间的最小发车间隔()。（2）两个相邻的发车间隔之差的约束为保证发车时刻的连续性，任意两个相邻的发车间隔之差不宜太大，即(=1，2)其中： 表示两相邻发车间隔之差的限值。5.2 模型（问题二的模型）5.2.1 确定目标函数公交司机排班是公交企业对社会的承诺，决定着为乘客服务的水平，发车间隔越小，服务水平越高，但是公交企业投入的成本越高，公交司机的排班应是在满足客流需求的前提下，尽量减少不必要的投入，这是个多目标规划问题。以一个月内总的发车次数来反映公交公司的利益，通过乘客的总的等车时间来反映乘客的利益。（1）考虑一月内总的发车次数最少： (（2）一月内乘客总的等车时间最短：=(这两个目标是相互联系矛盾的，不可能同时达到双方最小。当增大时，第一项是在减小的，而第二项是在增大的。这样就形成了一个需要寻求平衡点的问题，得到总体的最优。现在将两项加权合并为单目标函数，这里我们考虑将两项都这算为一种费用。第一项总的发车车次可折算为公交公司的运输费用。我们由公交公司的调研数据可知，平均每车公里的成本是260元，这个费用包括了司乘人员的劳动工资、车辆耗油、车辆折旧费用等等各项费用之和的折算。因此，一月内总的发车车次由价值来衡量，可以折算为：= 260()(=1，2)第二项乘客总的等车时间也可以折算为乘客等车损失的费用。根据有关资料的报道（河南省人民政府网/zwgk），许昌市2010年城镇居民的平均工资水平为1374.19元/月，按照双休日工作及法定的放假时间，现在一个月大概有天的休息时间，即有天在工作，平均每天按工作8小时计算。平均每分钟的工资为：=(元)乘客总的等车时间成本为：= (然后，通过加权系数和将价值化后的两部分合并，使得公交优化排班问题成为一个单目标优化问题。合并后的目标函数：260 ()+(；目标函数可以用乘客利益和公司利益分为两类，这两类目标是相互冲突的，两个目标函数就存在一个权值的问题，体现在目标函数中两项的加权系数的大小。在不同的线路，甚至同一线路的不同时段加权系数的最优值都是不相同的。例如：工作日的高峰正是多数乘客上班时间，也是一天中乘坐公交车人数的高峰期，所以这段时间里所需的车辆数也是最多的。从乘客的方面考虑，早上上班迟到对他的利益所示相当大，因此乘客希望等车的时间比较短，这个时候乘客等车时间的加权系数要大些。初始化时取两加权系数为0.2和0.8，然后在计算过程中根据结果逐步进行比较、调整。5.2.2 确定约束条件（1）平均满载率的约束平均满载率= =其中：表示车辆满载时的容量（人/车）；表示每车平均期望满载率()。（2）最大最小发车时间间隔约束任意相邻两车之间的发车间隔要满足最大最小发车时间间隔约束，即： (=1，2)其中：表示相邻两车之间的最大发车间隔();表示相邻两车之间的最小发车间隔()。六、模型的求解6.1 模型的求解由国家颁布的节假日安排可知，五月份的国家法定节日有五一劳动节（5月1日、2日、3日），双休日为8天，则五月份公交司机的排班需按照：节假日有11天，正常有20天。我们知道五月份排班需按照夏令（4月11月），因此该线路的开收班时间：6:2018:10。即=20，=11。则有： ( (=1，2)(=1，2)我们已经知道平时的高峰时段为（上下班）：6:008:30，11:3013:30，16:3018:00；则非高峰时段为8:3011:30，13:3016:30，18:0018:10；又知道高峰时段的发车间隔需48分钟/班，非高峰时段的发车间隔需810分钟/班。节假日的发车间隔需510分钟/班。将函数及数据带入Lingo计算，得：平时发车间隔=10（分钟/班），高峰时段发车间隔=8（分钟/班），节假日的发车间隔=10（分钟/班）；此时得的最小值为2080+1172=2392即五月份最少需2392班次。发车班次时间表五月开收班时间6:2018:10平时正常8:3011:3013:3016:3018:0018:10810分钟/班高峰6:008:3011:3013:3016:3018:0048分钟/班节假日510分钟/班发车时间节假日06:2006:3006:4006:5007:0007:1007:2007:3007:4007:5008:0008:1008:2008:3008:4008:5009:0009:1009:2009:3009:4009:5010: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发车时间平时06:2006:2806:3606:4406:5207:0007:0807:1607:2407: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:3616:4416:5217:0017:0817:1617:2417:3217:4017:4817:5618:06节假日时每天发车班次为72班平时每天发车班次为80班6.2 模型的求解本实验的数据是许昌市公交公司某线路的客流数据。客流信息如图所示： 图2 客流信息时刻分布图从上表可以看出6:008:30，11:3013:30，16:3018:00是乘客乘车的高峰时段。在满足乘客出行的前提下，根据高峰时段乘客量及发车的时间间隔来做出合理的车辆排班计划。遗传算法的参数：种群规模为48，个体选择采用适应度的轮盘赌选择法，交叉概率为0.8，变异概率为0.05，迭代次数50次。在30代完全运行完毕以后，可以得到最优的个体。根据这个最优个体，可以计算出在每个时段的发车班次如图3，并根据各个时段的发车间隔做出车辆的排班计划。图3 平时时段发车次数分布图图4 节假日发车次数分布图七、模型的扩展与评价综上可见，遗传算法应用于公交车辆排班具有很好的效果，它能够在排班优化问题的巨大搜索空间中可靠的找到最优近似解，当然本文在具体的运算过程中，对乘客流量的分布设置具有很大的假定性，同时认为公交车辆匀速行驶也不符合实际情况。但是从遗传算法的盐酸过程可以看出，算法的收敛性并不依赖于乘客的分布形式或者道路的通行状况，因此在实际应用过程中，只要乘客流量分布和道路状况能够比较准确给出，本文所涉及的遗传算法就能够得出一个相当好的结果。关于能力的分析是公路设备运输运用和服务水平确定的重要基础之一。本文结合国内外能力研究的成果，从服务质量角度提出了能力评价的理论和方法，从总体上看，这种理论的基础是突出“以人为本”的理念，论文根据公路区段、车站运输设备运用的特点，提出