A题：公交司机排班方案.doc

2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：公交司机排班方案摘要公交司机排班方案是决定交通客运健康发展前提的重要因素，合理的排班制度将直接影响社会、效益和司机的劳工权利。传统的跑班没有合理的排班安排，是以各线路的闲忙随意的掉用司机、机车跑班。这种跑班方式没有很好的体现对各方利益的照顾和社会利益的最大化。我们利用均匀分布模型分析解决以上问题，并根据模型给出最优公交司机排班方案。 本文中，我们围绕公交司机排班问题，结合我们已学的知识，与现实相结合，对问题进行层层深入的研究，最终给出了最优的公交司机排班方案。针对问题1，我们采用了分段函数分析法，得出每天的班次数与班次之间的时间间隔以及正常和高峰有着密切的关系。针对问题2，我们先利用数理统计知识分别求出每一班所用时间的期望及每天所跑班次的数的期望，在此基础上，我们建立了0,1模型。对于问题3，我们则在问题二结果的基础上建立一个新的0,1模型。、分段函数分析：由于每天的时间被分为了若干个正常和高峰，所以我们把每天按照正常和高峰分为若干段，建立一个分段函数根据题中给出的条件，在合理的假设的基础上我们的到了最少班次。、0,1模型分析：因为在问题2和3中，一个司机在第班次时只有开与不开两种选择，也就是说问题中的决策变量仅限于取0或1两个值，因此我们采用0,1模型。关键词： 排班 分段分析 0,1模型一、问题重述现代化进程是快速发展，许多城市的建设都把道路的规划放在了首要的考虑议题。这样，随着城市经济的发展，道路是越来越多。基于公交优先，百姓优先的原则，使得该公交总公司开辟了各种线路，包括市内线，近郊线，远郊线，旅游线，机场线，社区线等140多条线路，以满足老百姓出行需要。众多线路的开辟，必然会出现一些问题。据反映及相关调查，现实中有些线路司机不足，有些线路司机充足，这就导致了司机不足的线路常常要向其他线路戒掉司机和车辆跑班，从而影响了部分线路的排班秩序；而线路司机不足，却无法向其他线路借调司机和班车的就导致了这些司机每天工作时间过长，需开车12-13小时，影响司机休息，或有部分司机连续开车时间达到5、6小时，易导致工作疲劳，这样就容易给交通留下安全隐患；有的线路由于排班不当，导致在上班高峰期或节假日时段经常出现堵车现象，而正常时段确出现“空车”现象，影响公交公司收益状况及百姓乘车情绪，打乱了线路调度计划，使得交接班司机和乘客怨声载道。本文围绕如何确定最优排班，基于线路的基本情况及相关规定（1，司机每天上班时间不超过8小时；2司机连续开车不得超过4小时；3，每名司机至少每月完成120班次。），重点解决以下问题：1.根据五月份的节假日情况，给出当月最少班次总数；2.建立适当的数学模型，合理的设计该月线路的司机排班方案；3.基于2的司机排班方案，给出每天需要的司机人数；在每个司机每周连续工作五天，休息两天的前提下，通过一周需要司机人数给出司机总数最少的排班方案。二、问题分析城市城际公交拥有运量大、速度较快、污染低、安全、便宜、方便等优势，逐渐成为全国各城市客运交通系统的骨干。目前，基于节能减排新观点深入人心，我国正在大力推行城市公交系统的建设，而公交司机的排班成为了公司领导、司机、百姓最为关注的问题。随着人们时间观、舒适观、及权利的维护观相对提升，制定高效的司机排班方案越来越难，其不仅要考虑社会效益、节假日安排、乘客乘坐能力，还要考虑公交公司的收益状况、公交司机的跑班时间安排等情况。司机跑班制度安排将直接影响公交公司的利益及普通百姓的上班出行情况，不合理的排班方案会是公交资源的浪费，也会使百姓对公交怨声载道失去信心。因此，城市公交司机排班方案的制定是一项比较复杂的系统工程，并且受到政府、公交公司和百姓的热情关注。传统的排班制度的制定大多依赖于临时客运量的变化随即安排的，这种做法导致了诸多问题，如：司机过度跑班引起安全隐患、百姓等车过长或过度拥挤乘车，怨声载道这种传统的排班制度不能带来双赢甚至多赢。高效的司机排班制度要考虑到各方的利益，采取分层分段的方式进行研究，从而能达到各方利益共同兼顾的目标。三、基本假设根据不同的时间段和节假日情况建立排班模型，兼顾司机上班制度要求和当月节假日情况给出最少司机跑班次数安排制度。影响排班制度安排的主要因素有：司机身体状况、机车运行状况、百姓出行状况、其它公司的竞争、服务状况。根据这些因素我们提出以下基本假设：1.各司机的身体状况基本健康稳定。2.每天正常检车，机车正常出行。3.百姓出行状况即乘客流量保持不变。4.不考虑其它公司及私人的竞争。5.不考虑因天气变化带来的客流量变化。6.忽略个别交通事故引起的交通阻塞，和公交车因老化引起的负外效应。7.短时间内，不考虑通货膨胀和物价上涨引起的客流量变化。8.忽略因油价的变化带来的，出车频率。9. 每次发车时间和运行时间都以整分钟计。10某一班车在运行时只要有高峰时段就按高峰的运行时间。11. 最后一班发车时间不是收班时间，再加发一班。12.从起始站出发到终点站再回到起始站为一个来回，记作一个班次。 四、变量申明及符号说明符号意义单位备注 每天总班次次第时段发车间隔第时段时长第时段发车班次次节假日发车间隔节假日发车班次次总需要的司机人数个五、模型的建立与求解5.1问题一模型的建立与求解5.1.1问题一的分析 今年五月份的节假日情况是：五月份共31个日，其中节假日11日，非节假日20日。由附件，以6:20-18:10为开收班时间；排班间隔：平时为8-10分钟/班，上下班为4-8分钟/班,节假日为5-10分钟/班。由于非节假日分为正常与高峰期，排班间隔不同，所以我们考虑把非节假日的正常工作时间分为6个时段。每个时段发车班次用表示（表示当天第个时段）。用表示第个时段的发车间隔。取合适的使得的总合最小。结合题目中的其它约束条件可分析，此题符合线性规划模型。5.1.2问题一模型的建立1. 由问题一的分析可得，此问题的目标函数为每天的班次最少即：表示一天的班次总数。 2. 每个时段的发车时间不少于这个时段的时长。即： 此问题模型如下 （1） （2）节假日单日发班最少班次的数学公式为： （3）式中表示为五月份单日的上班总时间，为时间间隔，单位是分钟。5.1.3问题一模型的求解利用LINGO对（2）式编程求解，得非节假日单日单程的最少发车班次为81次。,节假日单日最少班次为72次。则由公式：，式中表示五月份非节假日公交司机跑班最少班次。，式中表示五月份节假日公交司机跑班最少班次。易知五月份总的公交司机跑班最少班次，知=2410次。非节假日和节假日公交司机跑班发车时间表如表-1-、表-2-非节假日公交司机最少跑班次数发车时间表高峰期（6:20-8:30）平时（8:30-11:30）高峰期（11:30-13:30）平时（13:30-16:30）高峰期（16:30-18:00）平时（18:00-18:10）发车时间班次发车时间班次发车时间班次发车时间班次发车时间班次发车时间班次06:20108:361811:363613:365116:366918:108106:28208:461911:443713:465216:447006:36308:562011:523813:565316:527106:44409:062112:003914:065417:007206:52509:162212:084014:165517:087307:00609:262312:164114:265617:167407:08709:362412:244214:365717:247507:16809:462512:324314:465817:327607:24909:562612:404414:565917:407707:321010:062712:484515:066017:487807:401110:162812:564615:166117:567907:481210:262913:044715:266218:048007:561310:363013:124815:366308:041410:463113:204915:466408:121510:563213:285015:566508:201611:063316:066608:281711:163416:166711:263516:2668表-1-节假日公交司机最少跑班次数发车时间表时间（6:20-18:10）发成时间班次发成时间班次发成时间班次发成时间班次发成时间班次发成时间班次06:20108:201310:202512:203714:204916:206106:30208:301410:302612:303814:305016:306206:40308:401510:402712:403914:405116:406306:50408:501610:502812:504014:505216:506407:00509:001711:002913:004115:005317:006507:10609:101811:103013:104215:105417:106607:20709:201911:203113:204315:205517:206707:30809:302011:303213:304415:305617:306807:40909:402111:403313:404515:405717:406907:501009:502211:503413:504615:505817:507008:001110:002312:003514:004716:005918:007108:101210:102412:103614:104816:106018:1072表-2-5.1.4问题一结果的分析及验证5.2问题二模型的建立与求解5.2.1问题二的分析1. 问题一中我们给出了五月份公交司机的最少跑班班次，但在现实中，司机在跑班过程中总会遇到各种因素影响由排班方案给出的跑班安排。也就是不可能的总是实现司机按点发车，准点到站，那么在问题二中，我们就有必要考虑这些因素来建立适合的数学模型。2. 发车的时间间隔是在一定范围内浮动的，不确定的。司机会根据等待人数的多少来选择间隔时间。如，高峰期，发车间隔为4-8，当等待的人数较多时，司机就会选择较短的时间间隔4发车，而较少的人数时则会选择8。在一天之内，发车的时间间隔大致服从随机均匀分布函数，运用此函数分别算出高峰期与正常期的发车时间间隔的随机均匀分布，并把数据分别保存在数组和中，以备后期计算使用。用和分别表示高峰期与正常期的发车时间间隔。5.2.2问题二模型的建立与求解1. 理的给出五月份该线路的司机排班方案，我们要计算出当月非节假日和节假日单日跑班间隔和跑班次数。我们用表示第班车的上一班车发车时间，表示这班车高峰期的发车时间,表示高峰期总的时间间隔。表示这班车正常期的发车时间，表示正常期总的时间间隔。表示一天的工作时间。表示高峰期时间间隔运用随机均匀分布产生的个数据，表示正常期运用随机均匀分布产生的个数据。表示每天发车的时间，初始值设为0。用数学式子表达如下：此式子由MATLAB编程可解出每天需要的班次数。由于每次运用随机均匀分布函数所产生的数据不同，则结果也不同。故我们采样了50个结果数据，数据如下： 999910199100981009999101979997981009910197991029798979810110099961011009896999698991029898101101989910099969910097100 为了使一天的班次数更接近现实，我们采用取平均值的方法来求出每天总的班次数为98.9，整为99。故每天的总班次数为99次。2. 为了求解需要的司机数及排班方案，我们建立如下模型：第个司机跑第天的第个班次所用的时间。：前后两班车次的时间间隔数学表达示如下：目标函数 %每天至少99班次 %司机不能连续开三班 %每个司机每月至少开120班次 %每个司机每天的工作时间不超过8小时 %不存在加班情况5.3问题三模型的建立与求解为了合理的给出五月份该线路的司机排班方案，我们要计算出当月非节假日和节假日单日跑班间隔和跑班次数。公交司机的排班的具体方法如下：1）首先根据公司的所有公交信息，将所有公交跑班编制为若干个班次串，所谓的班次串就是将本班次的起始站到终点站衔接起来，生成若干个可以由一辆班车去跑班，每一个成为“班次串”。2）针对编号的班次串计划，对每一个班次串指派班车跑班。3）对每一个班次串和跑班指派班组。这样，一辆班车就包括了班次串编制、班车指派、班组指派3个优化问题，而且它们互相影响和联系。由于班车排班问题规模大、约束条件众多，和那建立一个模型和算法来求解，一个有效的方法就是采用层次分块分别建立模型和算法，然后再综合平衡，以求最优效果。班组指派优化模型的建立 班组指派问题就是针对已经编好的班次串计划，综合考虑公司可用班车的情况，在满足班车各种条件下为每一个班次串指派班车。（4） （5） （6）（7）（8）（9）式中，为班次串数；为第个班次串内的班次数；，为班车数；为班次和班车之间的匹配差异惩罚值。目标函数（4）针对所有的班次串在指派班车的函数惩罚适应度最小，是针对批量的班车的全局优化，约束条件（5）证选择与班次串相等的执行班车数，约束条件（6）保证为每一个班次串只指派一辆班车，约束条件（7）要求为班次串指派的班车满足该班次串内的任一班车的跑班要求，约束条件（8）要求指派的班车满足该线路的乘客流量的要求。本文所建立的模型的求解属于NP-，采用数学规划等方法很难求解。本文根据模型特点构造一种自适应单亲遗传算法，算法中主要采用自然编码，以单点基因换位为主，辅以多点基因换位和基因移位的遗传算子的方法，基因换位和移位的概率自适应动态调整，同时使用专家规则进行修正。一，遗传操作算子 基因换位算子是按一定的概率交换染色体某些位置上基因的过程，被交换位置随机确定。基因换位可分为单点换位和多点换位，单点换位是一次知交换一对基因的位置；多点换位是对预先给定的证书N，取机数一次交换i对基因。本文在求解过程中以单点基因换位为主，辅以多点基因换位和单点基因移位算子。二，单点基因换位概率、多点基因换位及基因移位概率的自适应调整 本文将M.Srinivas提出的自适应遗传算法引入到单亲遗传算法中，并针对M.Srinivas算法的缺点，根据适应值的集中程度，动态调整每一代群体的单点基因换位概率pe、多点换位基因概率pm及基因移位概率ps，采用每一代群体的最大适应度值、最小适应度值、平均适应度值来作为适应值集中程度的判断标准。当时，判断为当代群体中个体趋于集中，根据集中程度自适应调整概率；否则，判断为群体中个体不趋于集中，仍维护正常情况下的单位基因换位概率pe、单点基因换位概率pm及基因移位概率ps。概率调整公式如下：式中，为初始单点基因换位概率；为初始单点基因换位概率；为初始基因移位概率。三，自适应单亲算子求解流程如下： 输入模型求解所需数据 读入要计算的合同信息。 算法参数的初始化 确定算法种群数目和结束最大循环代数，和基因单点换位、多点换位、基因移位的初始概率，然后根据种群数目给出一代初始的染色体，作为当前代染色体。 计算当前代染色体的函数适应值，记录最优个体为当前最优解，并判断是否满足结束准则，如是，则停止转。否则，进行下一步。 对当前染色体进行概率的自适应动态调整，按公式计算单点基因换位概率、单点基因换位概率及基因移位概率。 对当前染色体进行单亲遗传操作：以设定的概率，依次进行基因单点换位、多点换位和单点移位操作，最后进行选择操作，选择出一代最优的染色体。 将选出的一代染色体作为当前代染色体，转。 输出当前最优解作为算法的解。六、参考文献【1】张德喜 赵磊生主编 MATLAB语言程序设计教程（第二版）2006.6【2】韩中庚主编.实用运筹学 清华大学出版社2007.12【3】姜启源等，数学模型（第三版），高等教育出版社，2003【4】吴赣昌等，概率论与数理统计，中国统计出版社2007.11附录：model:MIN=x1+x2+x3+x4+x5+x6;x1*m1130;(x1-1)*m1310;(x2-1)*m2+x1*m1430;(x3-1)*m3+x2*m2+x1*m1610;(x4-1)*m4+x3*m3+x2*m2+x1*m1700;(x5-1)*m5+x4*m4+x3*m3+x2*m2+x1*m1710;(x6-1)*m6+x5*m5+x4*m4+x3*m3+x2*m2+x1*m1710;4m1;4m3;4m5;8m2;8m4;8m5;m18;m38;Local optimal solution found. Objective value: 80.00000 Extended solver steps: 20 Total solver iterations: 408 Variable Value Reduced Cost X1 17.00000 1.000000 X2 18.00000 1.000000 X3 15.00000 1.000000 X4 18.00000 1.000000 X5 11.00000 1.000000 X6 1.000000 1.000000 M1 8.000000 0.000000 M2 10.00000 0.000000 M3 8.000000 0.000000