2011数学建模__公交司机排班方案模型__模拟

1、2010201020102010 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 承承诺诺书书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网 上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的 资料（包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正文引用处和参 考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规 则的行为，我们将受到严肃处理。 我们参赛选择的

2、题号是（从 A/B/C/D 中选择一项填写） ： 我们的参赛报名号为（如果赛区设置报名号的话） ： 所属学校（请填写完整的全名） ： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人(打印并签名)： 日期：2011年 07 月 24 日 赛区评阅编号（由赛区组委会评阅前进行编号）： 2010201020102010 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 编编 号号 专专 用用 页页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅

3、编号（由全国组委会评阅前进行编号）： 1 公交司机排班方案模型 摘要 本文就公交司机排班问题应用遗传算法和多目标规划建立数学模型。运营车辆智能 排班问题是公交车辆智能调度需要解决的典型问题之一，本文应用已有的数据，并兼顾 到乘客和公交公司的双重利益，建立起一个符合实际情况的数学模型。在此基础上引入 了遗传算法（GA） ，针对公交智能排班问题，构造了符合行车规律的编码方式、遗传算 子，并实现了程序的编码工作，最后进行了模拟实验。 问题一在一定的约束条件下，如何合理安排其组织部分（操作）所占有资源、运行 时间及先后顺序，以获得运输成本或时间最优化。在理论研究中，车辆班次问题可看做 资源分配问题。

4、问题二在保证运营效率的情况下寻求乘客等待时间最少和保证服务水平的前提下使 车队运营效率较高，基于以上的考虑行车时刻表的编制应是在满足客流需求的前提下， 尽量减少不必要的投入，这是个多目标优化问题，遗传算法是解决公交排班问题的有效 方法之一。 问题三是在一定的约束条件下，合理安排排班方案使司机总数最少，以达到资源的 合理分配。 关键词：公交智能排班；遗传算法；遗传算子 2 一、问题的重述 目前，随着某市经济进一步的发展，道路变得越来越多。公交优先，百姓优先，为 此某市公交总公司开辟了各种线路，有市内线，近郊线，远郊线，旅游线，机场线， 社 区线等 140 多条线路，以满足老百姓出行需要。而现实是

5、有的线路司机不足，常常存在 向其他车队借调司机和车辆跑班，影响其他线路的排班秩序；有的线路司机需要每天开 车 1213 小时，影响司机的休息，从而给交通留下安全隐患；有的线路因经常堵车， 打 乱了线路调度计划， 使得交接班司机和乘客怨声载道。 一般， 公交公司按月给司机排班。 下面是某条线路的基本情况（附件） ，请你根据有关数据完成下列问题。 规定： （1）司机每天上班时间不超过 8 小时； （2）司机连续开车不得超过 4 小时； （3）每名司机至少每月完成 120 班次。 问题一：根据五月份的节假日情况，求出当月最少班次总数； 问题二：阐述你对上述规定的理解，并根据你的理解建立适当的数学模型

6、，合理地 设计五月份该线路的司机排班方案； 问题三： 根据五月份该线路的司机排班方案，计算出每天需要的司机人数，假如 规定每个司机每周连续工作五天，休息两天。请你通过某周（周一至周日）需要司机人 数求出司机总数最少的排班方案。 有关的数据为： 1、该线路的开收班时间： 冬令（12 月3 月） ：6:1518:20， 夏令（4 月11 月） ：6:2018:10 2、该线路的司机人数：15 人 3、该线路排班间隔： 平时：810 分钟/班； 高峰（上下班） ：6:008:30，11:3013:30，16:3018:00：48 分钟/班 节假日：510 分钟/班 4、该线路的运行时间: 正常：80

7、85 分钟/班 高峰：100120 分钟/班 二、问题的分析 公交车排班问题是城市公交调度的核心内容，是公交调度人员、司乘人员进行工作 以及公交车辆正常运行的基本依据。 公交排班的目的是确定最优或者近似最优的运营车 辆的发车时刻表。公交车队按照时刻表发车能够达到最高的运营效率和服务水平。本题 选用某市的某条线路运营车队作为排班对象，不失一般性，只考虑上行线路，即要优化 发车时刻表。所谓排班问题就是为了某一目的面对共同使用的资源实行时间分配，通常 可表示为在等式或者不等式的约束条件下，求解目标函数的优化。城市公交车辆运输系 统是定时，定线行驶，并按客流量、流向的变化而不断调节的随机服务系统，其相

8、应的 3 排班问题有如下特点： （1） M 为公交车辆集，每辆车在运输运行中只遵循一种运输方式。 （2） 每辆车按时发车，根据不同的运行时段，准时完成运输任务。 公交车辆运输排班问题是指，在固定行驶线路上，根据不同时段、依照一定的次序 关系，合理地编排运输车辆运行作业形式，以达到供需平衡，满足系统的性能指标。 本 文采用的优化指标为：在不影响乘客出行的前提下，乘客的等待时间和公司发车次数最 少，并避免出现“大间隔” 。本文采用遗产算法优化公交车辆运营排班问题。 三、模型的假设 制定公交车调度方案需要考虑的因素非常多,且很多因素都是随机的。 为了抓住重点, 简化模型建立及求解,必须作一定的简化假

9、设和设定： （1）各公交车为同一车辆类型； （2）在同一时间段内，相邻两车发车时间间隔相等； （3）公交车按调度时间表准时进站和出站，车速恒定，保持匀速行驶，途中没有堵 车和意外事故； （4）各时段以内乘客到站服从均匀分布； （5）每辆车经过各个车站时不会留有乘客； （6）在车站等待的人绝大多数不会离去； （7）以分钟作为最小的时间单位； 四、符号说明 k T 表示平时第k时段的时段长度； k t表示平时第k段时间的发车间隔； 3 T 表示节假日的时段长度； 3 t 表示节假日的发车间隔； 1k t表示第k段时间的发车间隔（包括平时和节假日） ； 1 表示某月除去节假日后总的天数； 2 表示某

10、月节假日总的天数； S表示某月发车总班次； m表示在整个调度周期内发车车次总数； n表示线路的车站总数； j r表示第j站在调度周期内随时间变化的乘客到达率（j=1，2， ，n） ； 表示目标函数中总发车车次的加权系数； 表示目标函数中乘客总的等车时间的加权系数； L表示线路总公里数； ij WT 表示所有乘客总的等车时间（min） ； 4 表示乘客总的等车时间成本（元） ； R表示公交公司的总的运行费用（元） ； 五、模型的建立 5.1 模型（问题一的模型） 5.1.1 确定目标函数 求某月最少班次就是为了某一目的面对共同使用的资源实行时间分配，可表示为在 等式或不等式的约束下，求解目标函数

11、的优化。本题采用的优化指标为：在不影响乘客 出行的前提下，使得公司发车班次最少。于是定义目标函数某一月最少的发车班次为 ： 3 3 2 1 1 T Smin tt T k k k k + = = ()2 , 1=k 排车班次受到平时时间段和节假日时段的影响， 故将排班次数分为平时时段与节假日时 段两种情况。上述目标函数中 = k k k k t T 1 1 为某月平时时段的发车总班次， 3 3 2 T t 为某月 节假日时段的发车总班次。 5.1.2 确定约束条件 （1）最大最小发车时间间隔约束 任意相邻两车之间的发车间隔要满足最大最小发车时间间隔约束，即： max1min TTtk( 1k=

12、1，2) 其中： max T表示相邻两车之间的最大发车间隔(min); min T表示相邻两车之间的最小发车 间隔(min )。 （2）两个相邻的发车间隔之差的约束 为保证发车时刻的连续性，任意两个相邻的发车间隔之差不宜太大，即 +111kk tt( 1k=1，2) 其中：表示两相邻发车间隔之差的限值。 5.2 模型（问题二的模型） 5.2.1 确定目标函数 公交司机排班是公交企业对社会的承诺，决定着为乘客服务的水平，发车间隔越小， 服 务水平越高，但是公交企业投入的成本越高，公交司机的排班应是在满足客流需求的前 提下，尽量减少不必要的投入，这是个多目标规划问题。 以一个月内总的发车次数来反映

13、公交公司的利益，通过乘客的总的等车时间来反映 乘客的利益。 （1）考虑一月内总的发车次数最少： 5 3 3 2 1 1 T Smin tt T k k k k + = = ()2 , 1=k （2）一月内乘客总的等车时间最短： ij WTmin= 2 )( 2 1 1 k n j j t rS = (）， 3,211=k 这两个目标是相互联系矛盾的，不可能同时达到双方最小。当 1k t增大时，第一项 是在减小的，而第二项是在增大的。这样就形成了一个需要寻求平衡点的问题，得到总 体的最优。 现在将两项加权合并为单目标函数， 这里我们考虑将两项都这算为一种费用。 第一项总的发车车次可折算为公交公司

14、的运输费用。我们由公交公司的调研数据可 知，平均每车公里的成本是 260 元，这个费用包括了司乘人员的劳动工资、车辆耗油、 车辆折旧费用等等各项费用之和的折算。因此，一月内总的发车车次由价值来衡量， 可 以折算为： R = 260L( k k k k k t T t T + = 3 2 1 1 )(k=1，2) 第二项乘客总的等车时间也可以折算为乘客等车损失的费用。根据有关资料的报道 （河南省人民政府网 ， 许昌市 2010 年城镇居民的平均 工资水平为 1374.19 元/月， 按照双休日工作及法定的放假时间， 现在一个月大概有 2 天 的休息时间，即有 1 天在工作，平均每天按工作 8 小

15、时计算。 平均每分钟的工资为： 608 1374.19 1 = 1 863 . 2 (元) 乘客总的等车时间成本为： = 1 863 . 2 2 )( 2 1 1 k n j j t rS = (）， 3,211=k 然后，通过加权系数和将价值化后的两部分合并，使得公交优化排班问题成为 一个单目标优化问题。合并后的目标函数： 260L( k k k k k t T t T + = 3 2 1 1 )+ 1 863. 2 2 )( 2 1 1 k n j j t rS = (2 , 1=k；）， 3,211=k 目标函数可以用乘客利益和公司利益分为两类，这两类目标是相互冲突的，两个目 标函数就存

16、在一个权值的问题，体现在目标函数中两项的加权系数的大小。在不同的线 路，甚至同一线路的不同时段加权系数的最优值都是不相同的。例如：工作日的高峰正 是多数乘客上班时间，也是一天中乘坐公交车人数的高峰期，所以这段时间里所需的车 辆数也是最多的。从乘客的方面考虑，早上上班迟到对他的利益所示相当大，因此乘客 希望等车的时间比较短，这个时候乘客等车时间的加权系数要大些。初始化时取两加权 系数为 0.2 和 0.8，然后在计算过程中根据结果逐步进行比较、调整。 5.2.2 确定约束条件 6 （1）平均满载率的约束 平均满载率=%100 车次车型定员 客运量 = = %100 111 mQ tr m i n

17、 j t tt j i i 车容量 其中： 车容量 Q表示车辆满载时的容量（人/车） ；表示每车平均期望满载率 (%1000)。 （2）最大最小发车时间间隔约束 任意相邻两车之间的发车间隔要满足最大最小发车时间间隔约束，即： max1min TTtk(1k=1，2) 其中： max T表示相邻两车之间的最大发车间隔(min); min T表示相邻两车之间的最小发车 间隔(min)。 六、模型的求解 6.1 模型的求解 由国家颁布的节假日安排可知，五月份的国家法定节日有五一劳动节（5 月 1 日、2 日、3 日） ，双休日为 8 天，则五月份公交司机的排班需按照：节假日有 11 天，正常有 20

18、 天。 我们知道五月份排班需按照夏令 （4 月11 月） ， 因此该线路的开收班时间： 6:20 18:10。 即 1 =20， 2 =11。 则有： 3 3 1 T 1120Smin tt T k k k k + = = ()2 , 1=k . .ts max1min TTtk(1k=1，2) +111kk tt(1k=1，2) 我们已经知道平时的高峰时段为（上下班） ：6:008:30，11:3013:30，16:30 18:00；则非高峰时段为 8:3011:30，13:3016:30，18:0018:10；又知道高峰时段 的发车间隔需 48 分钟/班，非高峰时段的发车间隔需 810 分

19、钟/班。节假日的发车 间隔需 510 分钟/班。 7 将函数及数据带入 Lingo 计算，得： 平时发车间隔 1 t =10（分钟/班） ， 高峰时段发车间隔 2 t=8（分钟/班） ， 节假日的发车间隔 3 t =10（分钟/班） ； 此时得S的最小值为 2080+1172=2392 即五月份最少需 2392 班次。 发车班次时间表 五月五月开收班时间开收班时间6:2018:106:2018:10 平时正常8:3011:3013:3016:3018:0018:10810 分钟/班 高峰6:008:3011:3013:3016:3018:0048 分钟/班 节假日510 分钟/班 发车时间发车

20、时间 节假日06:2006:3006:4006:5007:0007:10 07:2007:3007:4007:5008:0008:10 08:2008:3008:4008:5009:0009:10 09:2009:3009:4009:5010:0010:10 10:2010:3010:4010:5011:0011:10 11:2011:3011:4011:5012:0012:10 12:2012:3012:4012:5013:0013:10 13:2013:3013:4013:5014:0014:10 14:2014:3014:4014:5015:0015:10 15:2015:3015:40

21、15:5016:0016:10 16:2016:3016:4016:5017:0017:10 17:2017:3017:4017:5018:0018:10 发车时间发车时间 平时06:2006:2806:3606:4406:5207:00 07:0807:1607:2407:3207:4007:48 07:5608:0408:1208:2008:2808:38 08:4808:5809:0809:1809:2809:38 09:4809:5810:0810:1810:2810:38 10:4810:5811:0811:1811:2811:36 11:4411:5212:0012:0812:16

22、12:24 12:3212:4012:4812:5613:0413:12 13:2013:2813:3813:4813:5814:08 14:1814:2814:3814:4814:5815:08 15:1815:2815:3815:4815:5816:08 16:1816:2816:3616:4416:5217:00 17:0817:1617:2417:3217:4017:48 17:5618:06 8 节假日时每天发车班次为 72 班 平时每天发车班次为 80 班 6.2 模型的求解 本实验的数据是许昌市公交公司某线路的客流数据。客流信息如图所示： 客流信息表 0 10 20 30 40

23、50 60 6:007:00 7:008:01 8:009:00 9:0010:00 10:0011:00 11:0012:00 12:0013:00 13:0014:00 14:0015:00 15:0016:00 16:0017:00 17:0018:00 18:0019:00 时间段 乘客到站人数 乘客到站人数 图 2客流信息时刻分布图 从上表可以看出 6:008:30， 11:3013:30， 16:3018:00 是乘客乘车的高峰时段。 在满足乘客出行的前提下， 根据高峰时段乘客量及发车的时间间隔来做出合理的车辆排 班计划。 遗传算法的参数：种群规模为 48，个体选择采用适应度的轮盘

24、赌选择法，交叉概率 为 0.8，变异概率为 0.05，迭代次数 50 次。 在 30 代完全运行完毕以后，可以得到最优的个体。根据这个最优个体，可以计算出 在每个时段的发车班次如图 3，并根据各个时段的发车间隔做出车辆的排班计划。 发车次数表 0 1 2 3 4 5 6 7 8 6:007:00 7:008:01 8:009:00 9:0010:00 10:0011:00 11:0012:00 12:0013:00 13:0014:00 14:0015:00 15:0016:00 16:0017:00 17:0018:00 18:0019:00 时间段 发车班次 发车次数 图 3平时时段发车次

25、数分布图 9 节假日发车次数表 0 1 2 3 4 5 6 7 6:007:00 7:008:01 8:009:00 9:0010:00 10:0011:00 11:0012:00 12:0013:00 13:0014:00 14:0015:00 15:0016:00 16:0017:00 17:0018:00 18:0019:00 时间段 节假日发车班次 发车次数 图 4节假日发车次数分布图 七、模型的扩展与评价 综上可见，遗传算法应用于公交车辆排班具有很好的效果，它能够在排班优化问题 的巨大搜索空间中可靠的找到最优近似解，当然本文在具体的运算过程中，对乘客流量 的分布设置具有很大的假定性，同时认为公交车辆匀速行驶也不符合实际情况。但是从 遗传算法的盐酸过程可以看出， 算法的收敛性并不依赖于乘客的分布形式或者道路的通 行状况，因此在实际应用过程中，只要乘客流量分布和道路状况能够比较准确给出， 本 文所涉及的遗传算法就