数学建模：公交公司司机排班方案

-1-数模训练数模训练数模训练数模训练公交公交公交公交公司公司公司公司司机排班方案司机排班方案司机排班方案司机排班方案指导老师：陈作清组员：王青春王诗怡朱倩2011年8月23日-2-基于优化模型和计算机仿真的公交司机排班方案摘要本文建立了优化模型，并利用计算机仿真设计了公交司机排班方案，确定了2011年5月份某线路的司机排班方案。并根据排班方案优化了需要的司机人数。问题1中，以月份总班次最少为目标函数，将公司对司机的3点要求作为约束条件，建立了单目标优化模型。经计算得到最少需要2463班次，且各类别的班次如下表所示：类别天数排班间隔每天班次节假日11天10分钟每班73班次工作日高峰期20天8分钟每班48班次工作日非高峰期20天10分钟每班35班次月度总班次2463次问题2中，为了合理安排5月份司机排班方案，将司机班次的方差和工作时间的方差作为衡量合理性的标准，由于两个方差不同且难以进行归一化处理，故2者均作为目标函数；将公司对司机的3点要求作为约束条件建立了多目标规划模型，考虑到该模型约束条件的复杂性,并不直接对模型进行编程求解，而是首先设定目标函数的精度，用MATLAB对约束条件进行循环模拟排班，当排班方案对应的目标函数满足精度要求时，运算终止。经循环17次达到精度要求，此时该月共运行班次3015班，工作班次的方差为0.1961，工作时间的方差为12.62，具有较高的精度。并在附录中给出了3015班次的发车时间。问题3中，在问题2的基础上，将司机看成“乘客”进行排队上车，从而得到总共需要26名司机，又司机每连续工作5天就休息2天，故每天安排24位司机，最后给出了该月的司机排班方案。在模型改进中，进一步考虑了实际发车中可能出先的2种问题：1、某班车发车时处于正常时段，但在本班次中后处于高峰时段；2、某班车发车时处于高峰时段，但一段时间后处于正常时段；针对这2种情况，引进公交车的运行时间修正参数α，对在车上的运行时间进行修正，修正后班次的反差为0.1961，工作时间的方差为9.60，模型的精度进一步提高。问题2中将司机工作时间和工作班次的方差看作衡量合理性的标准以及在问题3中将司机看成乘客进行排班是本文最大的两个亮点。关键词：公交排班，多目标规划，计算机仿真-3-1111、问题重述随着武汉市经济进一步的发展，道路变得越来越多。公交优先，百姓优先，为此武汉市公交总公司开辟了各种线路以满足老百姓出行需要。而现实却是经常出现司机数量不足、工作时间过长、因堵车扰乱行车计划等问题。一般而言，公交公司按月给司机排班。现有某条线路基本情况如下：1、开收班时间：冬令（12月—3月）6:20—18:10；夏令（4月—11月）6:15—18:20。2、司机人数：20人。3、排班间隔：工作日：高峰期4—8分钟每班；非高峰期期8—10分钟一班；节假日：5—10分钟一班[注：高峰期为6:00—8:30，11:30—13:30，16:30—18:00]。4、运行时间：高峰期:100—120分钟每班次；非高峰期（包括节假日）：80—85分钟每班次。同时，公司对司机工作时间有如下规定：1、司机每天上班时间不超过8小时；2、司机连续开车不得超过4小时；3、每名司机每月至少完成120班次。结合上述情况，请完成如下2个问题：问题1：根据五月份的节假日情况，求出当月最少班次总数问题2：阐述你对上述规定的理解，并根据你的理解建立适当的数学模型，合理地设计五月份该线路的司机排班方案。2222、模型假设1、假设行车路上不发生任何行车时间超过题目给出的范围的事件；2、线路的排班间隔、车辆的运行时间服从均匀分布；3、工作日高峰期和非高峰期间隔是单独发车。3333、符号说明符号意义ix不同类型的时间段排班间隔（1i=表示节假日；2i=表示工作日非高峰期；3i=表示工作日高峰期）im不同类型的时间段应发车班数（i的意义同上）ijkx第i天第j班次第k号司机是否开车，0ijkx=时表示不开车；1ijkx=时表示开车（1,2,...,id=；1,2,...,ijm=；1,2,...,kn=；d表示所研究-4-的月份的总天数；im表示第i天公交班次；n表示司机的总人数）ijkc第i天第j班次第k号司机此班次所用时间（当0ijkx=时，0ijkc=；当1ijkx=时，ijkc服从均匀分布）12,σσ司机月份班次次数和月份工作时间的方差**12,σσ司机月份班次次数和月份工作时间的理想方差（精度）α公交车的运行时间修正参数4444、问题分析4.14.14.14.1问题1111的分析本问要求根据5月份节假日情况，求出当月最少班次总数。由于节假日与正常工作日发车间隔与运行时间均相互独立，所以分开考虑两种情况。当两种情况均达到最小发车次数时，总发车班次此时最小。将公交公司对司机工作时间的3条规定可以看成约束条件，总发车次数最少为目标函数，进而可建立非线性优化模型。4.24.24.24.2问题2222的分析本问要求合理设计5月份的排班方案，如何突出合理性是本文的一大关键。公交司机作为公交公司的员工，每位司机的工作班次和工作时间应该尽量相等，因此可用工作班次和工作时间的方差来衡量合理性指标，由于工作班次与工作时间的量纲差异性较大，也不宜进行归一化处理，因此可建立多目标规划模型。4.34.34.34.3问题3333的分析本问要求在问题2的基础上，计算出每天需要的司机人数，在假设每个司机每周连续工作五天，休息两天。确定使得司机总数最少的排班方案。在本文中，将司机看作特殊的乘客，让司机进行排队上车，安排司机的排班方案。5555、问题1111模型的建立与求解5.15.15.15.1问题的分析2011年5月份共包含节假日11天，正常工作日20天，以总发车次数最少为目标函数，公交公司的规定作为约束条件，建立单目标优化模型。5.25.25.25.2模型的建立5.2.15.2.15.2.15.2.1目标函数的确定1111、节假日开班次数的确定用1x表示节假日排班时间间隔，由于节假日的排班间隔为5~10分钟一班，-5-且服从均匀分布，所以1(5,10)xU∼夏令开收班时间为6:15—18:20，共725分钟，所以节假日每天开班次数117251mx⎡⎤=+⎢⎥⎣⎦其中[]x为高斯函数，表示不超过x的最大整数。2222、工作日开班次数的确定用23,xx分别表示非高峰期和高峰期排班时间间隔，均服从均匀分布，而非高峰期8~10分钟每班，高峰期4~8分钟每班，所以23(8,10)(4,8)xUxU∼∼非高峰期共包括3个时间段：8:30~11:30；13:30~16:30；18:00~18:20，共计380分钟，所以非高峰期每天开班次数223801mx⎡⎤=+⎢⎥⎣⎦高峰期共包括3个时间段：6:00~8:30；11:30~13:30；16:30~18:00，共计360分钟，然而夏令开班时间是从6:15开始，因此高峰期实际只有345分钟，所以高峰期开班次数333451mx⎡⎤=+⎢⎥⎣⎦3333、目标函数的确定总发车次数为上述3种情况的和，所以目标函数31iiiMmα==∑其中1α表示节假日的天数，23,αα表示正常工作日的天数。5.2.25.2.25.2.25.2.2约束条件的确定定义标识符ijkx，表示第i天第j班次第k号司机是否开车，其中01ijkijkxijk⎧=⎨⎩第天第班次司机开车第天第班次司机不开车用ijkc表示第i天第j班次第k号司机此班次所用时间，则(80,85)(100,120)ijkijkcUcU⎧⎪⎨⎪⎩∼∼正常高峰-6-其中1,2,...,31i=；1,2,...,ijm=；1,2,...,20k=；im表示第i天公交班次1111、司机每天上班时间不超过8888小时约束该约束等价于11480mijkijkjxc=≤∑2222、司机连续开车不超过4444小时由于每班次至少80分钟，最多120分钟，所以连续开车不超过4小时等价于不能连续开车3班次，即2,,03ijpkpx+=∑3333、司机每月至少完成120120120120班次该约束等价于311120ijkix=≥∑5.2.35.2.35.2.35.2.3模型的得到综上所述，得到总发车班次最少的优化模型13111223312,,0311min725138013451480..312001(80,85)(100,120)iiimijkijkjijpkpijkiijkijkijkMmmxmxmxxcstxxijkxijkcUcUα==+===⎧⎡⎤=+⎪⎢⎥⎣⎦⎪⎪⎡⎤⎪=+⎢⎥⎪⎣⎦⎪⎡⎤⎪=+⎢⎥⎪⎣⎦⎪⎪≤⎪⎪⎨≥⎧=⎨⎩⎧⎪⎨⎪⎩⎩∑∑∑∑∼∼第天第班次司机开车第天第班次司机不开车正常高峰⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪-7-5.35.35.35.3模型的求解考虑2011年5月份的班次，2011年5月份共有节假日11天，工作日20天，所以12311,20ααα===5.3.15.3.15.3.15.3.1模型算法复杂性分析及求解思路分析本模型直接用软件编程求解非常困难，单ijkx的取值就超过10000种情况，又ijkc服从均匀分布，取值无法确定。因此，该模型不宜直接求解。鉴于此，本文采取如下的方法进行模型求解：Step（1）：不考虑约束条件，求出无约束条件下目标函数的最大值；Step（2）：将Step（1）中的理想情况用约束条件进行检验，若满足约束条件，则计算终止，Step（1）确定的最优值即为所求；否则转Step（3）；Step（3）：剔除Step（1）最优值满足的约束条件，保留不满足的约束条件，求目标函数的次优值，转Step（2）；Step（4）：若一直存在约束条件无法满足，则该问题无解。其算法流程图如下：图1111：问题1111模型的算法流程图5.3.25.3.25.3.25.3.2模型的求解1111、无约束条件下目标函数最优解目标函数-8-1231231120()72538034511(1)12(2)Mmmmxxx=++⎡⎤⎡⎤⎡⎤=++++⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦由于ix均服从均匀分布，所以当12310,10,8xxx===时，M取最小值，且min2463M=此时的排班方案为：（1）节假日（共11天）每天开73班，每10分钟一班；（2）工作日（共20天）平时每天开班35次，每10分钟一班；（3）工作日（共20天）高峰期每天开班48次，每8分钟一班。2222、约束条件满足性验证（1111）每名司机每天工作时间不超过8888小时节假日每天开班73次，则每天工作时间介于区间[]5840,6205（单位：分钟，下同）。平时每天开班共83次，每天工作时间介于区间[]7560,8665。司机每天上班不超过8小时就是480分钟，20个司机就是9600分钟，故该约束条件可以满足。（2222）司机连续工作不能超过4444小时由于总时间充裕，所以当司机开了接近4小时的车的时候就换司机，或者没开班1次就休息一次，这样就可以满足该约束条件。（3333）每名司机每月至少完成120120120120班次平均每天至少完成3班次，每天至少要60个班次，而每天至少有73个班次，所以可以满足该约束条件。综上所述，上述模型结果可以满足约束条件。5.45.45.45.4结果分析5月份最少班次的排班方案如下表所示：表1111：5555月份总班次最少的排班方案示意表类别天数排班间隔每天班次节假日11天10分钟每班73班次工作日高峰期20天8分钟每班48班次工作日非高峰期20天10分钟每班35班次月度总班次2463次由于在发车时存在诸多不确定因素，因而仅仅考虑班数最少情况不具有一定的现实意义。因此进一步考虑5月份期望班次总数。从期望的角度讲，节假日，工作日高峰期，工作日非高峰期的排班间隔分别-9-是7.5分钟，6分钟，9分钟。从而求的5月份期望总班次的排班方案示意表如下：表2222：5555月份期望总班次的排班方案示意表类别天数排班间隔每天班次节假日11天7.5分钟每班97班次工作日高峰期20天6分钟每班64班次工作日非高峰期20天9分钟每班39班次月度总班次3127次尽管从