公交司机排班方案

数学与统计学院2011-2012学年第一学期课程论文数学建模*我们选择的题号是（从A/B/C/D/E中选择一项填写）：D所属班级（请填写完整的全名）：2009级数学与应用数学（师范）2班成员（打印并签名）：1.572.773.4.日期：2011年12月30日评阅成绩：公交司机排班方案摘要本文要研究公交司机排班方案，这须考虑的制约条件很多，使其成为较为繁琐的工作。对于问题二，首先要分为节假日与非节假日进行研究。解决问题的关键在于把一天内每位司机的排班方案求出，进而可容易地得到整个五月份的排班方案。而其中非节假日分高峰时段和非高峰时段，使得情况较为复杂。要使公司的利益最大，就要求出在满足要求的情况下求出最少的司机数。本文通过寻找所有的约束条件，设置适当的目标和决策变量，并用Lingo软件解得最优排班方案。对于问题三，本文建立的数学模型为一个32X7且仅含“1”“0”元素的矩阵（“1代表司机当天工作，“0”代表休息），用其代表一周内的排班表，从而将问题简化。然后按照问题要求设计出一种算法，通过C语言程序对矩阵做一系列的变换。这样便可得到最终的排班表，整个排班过程由C语言自动完成，快速而准确。最终可得司机总数最少为23人。关键词：MATLABLIGO;多目标优化；交通运输；最优化求解一、问题重述在新的时代背景下，随着市区经济飞速发展，人们的生活和交通也有较大的改变，道路也变得越来越多。为此某市公交总公司打着“公交优先，百姓优先”，开辟了各种线路，有市内线，近郊线，远郊线，旅游线，机场线，社区线等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的分析问题一要求根据五月份的节假日情况：五月份共31个日，其中节假日11日， 非节假日20日，并按照五月份公交车的开班情况：6:20-18:10为开收班时间，排班问隔平时为8-10分钟/班，上下班为4-8分钟/班，节假日为5-10分钟/班。建立合适的线性规划模型，使得五月份的班次最小。由于非节假日分为正常时段与高峰时段，排班间隔不同，所以我们考虑把非节假日的正常工作时间分为6个时段。在每个时段按照每个时段的间隔规定，取间隔时间最大时，使得班次最小，考虑到利民的情况下，在时段交接处，如果剩余时间能按照该时间规定的间隔处理，则再出发一班车。而在节假日都按照高峰时段来看待，发车间隔时间是相同的，所以只要发车时间间隔最大，班次就最小。结合题目中的其它约束条件可分析出五月份的最少班次。（二）问题的2分析问题二的分析对于问题二，设计五月份该线路的司机排班方案，但就此排班方案过程会受到很多方面因素的影响，也就是不可能总是按照司机按点发车，准时到站，又考虑到公司要有更高的利益，每个司机每月的工资是固定的，肯定只有每个月的司机尽量的少公司才有更高的利益，那就是满足条件的情况下班次尽量的少，且我们也要让每位司机有较高的满意度，就是让他们有足够的休息时间。所以在上班的高峰期车辆间发车的间隔时间为48分钟/班，我们规定其间隔时间为8分钟；在平时车辆班次间隔规定为810分钟/班，我们取间隔时间为10分钟；要让班次尽量少，那么在非节假日规定有72个班次；在节假日规定有82个班次。结合题目中的所有约束条件，应用lingo求解五月份该路线的司机排班方案。（三）问题3的分析由于本文在问题二已经求出每天需要的司机人数，即非节假日须17人，节假日（双休日）须13人，所以问题的关键在于合理安排一周内每位司机的工作日和休息日，让他们的工作日和休息日彼此错开，在保证每天工作人数达到要求前提下，使一周内工作的司机人数最少。三、模型的假设1、假设从起始站出发到终点站，再终点站回到起点站记作一个班次；2、假设每次发车时间和运行时间都以整分钟计；3、假设某一班车在运行时只要有高峰时段就按高峰的运行时间；4、假设最后一班发车时间不是收班时间，再加发一班；5、假设各司机的身体状况基本健康稳定，公交车能车正常出行；6、假设不考虑因天气变化带来的客流量变化；7、假设即使高峰时期班次的时长也不会超过所规定时段；8、假设公交车按调度时间表准时进站和出站；9、假设车速恒定，保持匀速行驶，途中没有堵车和意外事故；10、假设各公交车为同一车辆类型；11、假设忽略个别交通事故引起的交通阻塞，和公交车因老化引起的负外效应；12、假设乘客量是均匀分布的。四、符号说明Z:五月份的总的最小班次；X Xi:五月份节假日总的最小班次；Y Yk：五月份非节假日总的最小班次3：节假日的发车时间问隔；t t2：非节假日高峰时段的发车时间问隔；t t3：非节假日正常时段的发车时间问隔；ai:非节假日一天内第i个司机工作的高峰班次数bi:非节假日一天内第i个司机工作的非高峰班次数R1:非节假日一天内需要的最少司机人数R2:节假日一天内需要的最少司机人数51 :非节假日所有汽车运行时间之和52 :节假日所有汽车运行时间之和Y代表被安排为第j种情况的司机数乂胀:第i个司机第j大的第k个班次C Cijk:第i个司机跑第j大的第k个班次所用的时间&：前后两班车次的时间问隔；Q-每个司机每天工作K:纵向不规则度R:每天规定的司机人数五、模型的建立与求解问题一模型建立：根据问题分析，可以建立如下每天的班次最少的目标函数根据附件中给的节假日、平时、高峰各个时段该线路排班间隔有如下的约束条件：模型一的求解：节假日情况：根据假设，节假日不分高峰时间段和平时间段，全天客流量可以看作是均匀分布,统一按照时间问隔：5mint5mint110min10min,则当且仅当小）=10时，达到每日班次最小五月份的运行时段是6:1518:20,共710分钟，取（t t1）maxax=10时，110+1110+1=721010考虑到公交车为两点对接，所以节假日每天的最少班次为：因此，五月节假日的最少班次总数：非节假日情况：根据问题一的分析，非节假日分为高峰时段（发车间隔 4mint4mint28min8min）和正常时段 （发车间隔 8min8min t t310min10min） 这两个时段， 显然全天的客流量不能均匀分布， 则当且仅当（t2 21 1axax=8min和（t3 31 1axax=1。min时，达到每日班次最小。由于非节假日分的时段太多，为了方便，则公交排班方案用下面的表来描述运行时间段时间问隔班次数说明6:208:30(高峰)(130min)8176:20发首班二车，以后每8min发一班。第17班次在8:28发车，2min4min,4min为最小间隔，所以在8:28后开始按平时段来进行。8:3011:30(平时)(180min)1018第18班次按照正常车次在8:38出发， 第35班次在11:28出发，2min8min,8min为最小何隔， 所以在11:28后开始按高峰时段来进行。11:3013:30(高峰)(120min)815第36班次按照高峰车次在11:36出发，每每8min发一班，第50班次在13:28出发。2min4min,4min为最小间隔，所以第51班次布将按照正常时段发车。13:3016:30(平时)(180min)1018第51班次按照正常车次在13:38出发， 每10min发一班， 第68班次在16:28出发2min82(82(j j=.31)31)i注kX XjkC Cjk+X+XijkC Cij(.240(i=1.17,j=1.240(i=1.17,j=1.31,k=1.82).31,k=1.82)约束条件：J模型的求解：3182ZZZZX Xijk之 120(i=1.17)120(i=1.17)j$y82工工X XijkC CijkW480(i=1.17,jW480(i=1.17,j=.31)31)k82工工(纯t ti)710)13,故最少司机数为13,结合第一题的结论，可得节假日一天的司机安排表如下：表四：节假日安排表一号司机11325374961二号司机21426385062三号司机31527395163四号司机41628405264五号司机51729415365六号司机61830425466七号司机71931435567八号司机82032445668九号司机92133455769十号司机102234465870L#司机112335475971十二号司机122436486072(注：其数字为班次数)问题三的模型建立：规定每个司机每周连续工作五天，休息两天，那么每个司机一个月工作的天数:312020ZZQ Qji i2323(i=117)(1)j1首先要确定五月份需要的司机人数，我们规定：1代表司机当天工作，0代表司机当天不工作； 定义一个34X7的矩阵Aj,代表每位司机(预先提供34名司机)在本周的工作表， 每一列代表一周内当天(星期一到星期日)每位司机工作的情况。现在只需把Aj各元素进行重排，满足以下两个条件的前提下，使得0元素排满某些行，这些行所代表的司机本周就无需工作了。34(1)工工Aj=Ri1(2)矩阵每行必须是【11111001111100】或是它的错位形式。为方便对模型的求解过程：将某一行的元素变为【11111001111100】。7衡量是否符合每天规定的司机人数R,K=j1把矩阵某行向左错位， 即把 【11111001111100】 变为 【11110011111001】模型的求解：根据以上要求，本文对矩阵的重排使用C语言编程实现，运行结果见附表。从程序运行结果看，矩阵下部的“1 1”被逐步消除，并且前几次重排，程序把纵向不规则度 K K保持在 2,2,至第 5 5 次以后，由于矩阵下部的“1 1”被完全消除，纵向不规则度 K K 不可避免的增大。矩阵下部全为零的各行代表该行的司机一周都不需工作，也就是说不需要这些司机了。把运行后的数据相互比较之后，发现第五次重排的数据较好，所以把第五组数据矩阵下部的0向量去除，并对最后 4 4 行稍作修整，进而可知有23种排法。34该矩阵纵向不规则度 K K 为 0,0,即工BU=R( (0j0j7)7)0 0i1每周需要的司机最少数为23人。除最后 4 4 位的司机每周仅需工作 4 4 天外，其他司机都按题设的规定作息。根据矩阵B,把最后四行与其他行交换即可排出另外三周的安排表，进而排出整个34ZAj一ii5月份的安排表。安排表如下：（“1”“0”分别代表工作和休息）每天司机数131717171717131317171717171313日期123456789101112131415总天数1号司机211111001111100112号司机211100111110011113号司机211111001111100114号司机211100111110011115号司机211001111100111116号司机221111001111100117号司机221110011111001118号司机221100111110011119号司机2211110011111001110号司机2210011111001111111号司机2210111110011111012号司机2211111001111100113号司机2211100111110011114号司机2100111100011110015号司机2101111100111110016号司机2101111100111100017号司机2101111100110110018号司机2101111100011110019号司机2101111100001110120号司机2101111000111110021号司机2101101100111110022号司机2100111100111110023号司机210001110111111001117117111171171711117773377337711181202222422627223367912358901111001I111100110 ；100111110011110011110011111001100110011I1100111100；0011111001111100111001111100111011100111111110001100111111110001111100111101100110011111011110011111110001111101111110011100111111101100100111111011110011100111100111010011111110 r111110011111011111100111110011111001111100111110 r111110011111011111110011111001111111001111100111 11111001111100111111100111110011六、模型的评价与推广1、模型的优点(1)本模型利用数学工具简化问题，简单易懂，且较直观。(2)结合权威资料，合理的分析处理数据，增加了模型的准确性。(3)题主要运用概率论与相关的数学知识建立的数学模型，进而求出来司机的排班方案，因此使题目具有其合理性。2、模型的缺点公交运营协调优化问题涵盖的内容错综复杂，且该问题涉及的不确定因素众多，还有许多问题有待进一步深入研究。(1)乘客到达可能服从其他的分布，所以应根据实际情况深入分析乘客到达分布和公交车辆到站时间之间的关系，确定不同的分布下对公交运营的影响。(2)交叉口延误时间，城市道路的交叉口是非常多的，而且城市公交车在交叉口的延误在整个公交运行时间占的比例是不小的。(3)该线路发生交通事故的情况，交通事故是时常发生的，而发生交通事故对公交车的影响是非常大的，如果公交车被挡在事故的之间，那么要等事故处理完全后才能正常运行。(4)停靠站延误时间，停靠站延误时间是指公交车由于站点的影响而花费的所有时间，包括车辆进站时间、车辆开门和关门时间、乘客上下车占用时间、车辆离站时间、车辆进出站受到干扰的时间。3、模型的推广本模型准确性较高，而且非常实用。可以应用到公司、工厂、政府等其他领域员工排班问题上。根据实际情况，具体约束条件，使得模型更加紧密实际生活，结果会得到进一步优化。七、参考文献【1】李跃鹏等，基于遗传算法的公交车辆智能排班研究J,交通运输系统工程与信息，3(1):42-43,2003年。2孙红.层次分析法在平衡记分卡中的应用及其常州电视台绩效评价系统的实现D.中国地质大学(北京),2011【3】韩中庚，数学建模方法及其应用第二版，高等教育出版社，2009.64徐小龙，王文国.遗传算法的原理与应用J,沿海企业与科技,2005,(05)八、附录1 11 11 11 11 10 01 1 1 11 19 90 01 11 11 11 11 11 11 10 00 01 1s s0 01 11 11 11 11 11 11 11 11 1 0 01 1 1 11 11 11 1n nH H1 11 10 001 11 11 11 11 11 11 1&O O0 00 01 11 11 11 11 11 11 11 10 00 0e e1 11 11 11 11 111 11 10 0e ei i1 1& &1 11 11 11 11 11 11 1o o&i ia a0 01 11 11 11 11 11 11 1M MQ Q0 01 11 11 11 11 11 11 11 10 01 1 1 1i i1 10 0a a1 11 11 11 11 11 10 00 0S Si i1 11 1i i1 11 11 11 11 11 1&0 0 1 1i i1 11 1i i1 11 11 11 11 10 01 1 1 1i i1 11 1& &0 01 11 11 11 11 1B B1 1 1 1i i1 11 10 00 01 11 11 11 11 10 01 11 11 11 11 10 00 01 11 11 11 11 1&+ +1 11 1i i1 11 1PtPt a a1 1 1 11 11 11 1o o1 1 1 1i i 1 10 00 0E)E) 0 08 80 0B B1 11 11 1 1 1i i1 11 1& &0 00 00 00 00 00 01 11 11 1 i i1 11 10 00 00&0 00 01 11 11 1 1 11 11 1& &0 0&0 00 0O O0 01.1.1 11 1 1 11 11 10 00 0时1 11 11 11 11 11 1& &0 00 00 00 01 11 10 00 00 00 01 11 10 00 00 01 11 10 0a a0 00 00 01 11 10 00 00 00 01 11 108 80 09 90 01 11 10 00 01 11 10 00 00 00 00 00 00 0&B B0 01 11 10 00 00 01 11 10 0W W0 00 00 0& &0 00 00 00 01 11 1&0 0& &0 00 00 0R RR Rflfl1 11 10 0e e0 0& &0 00 00 0B BB BS S0 00 000 00 0G G0 00 00 0& &0 00 00 00 00 00 00 00 0&0 000 00 0R R8 80 00 0&0 00 00 00 0s s0 0R R0 0Q Q0 0&0 00 00 00 00 00 00 00 00 00 00 00 00 00 0O O0000000000不规见U U度目&a&neaa11 11 1&9 9&1 1&0 01 10 01 11 11 11 11 11 1 0 00 01 11 10 0 1 11 11 11 11 1 1 11 11 11 11 1 0 00 01 11 10 0 0 01 11 11 10 0 1 11 11 11 11 1&0 0 1 11 11 1 1 11 11 11 11 1 1 11 11 10 01 1 1 10 0 0 01 1R R1 11 11 11 1 1 11 11 10 01 1 1 11 10 00 01 1 1 11 10 00 01 1 1 11 10 00 01 1 1 11 10 00 01 1 1 11 1&01 1 1 11 10 0 1 1 1 11 10 00 01 1 1 11 1&0 0 0 00 00 01 10 0 0 00 0S S0 00 0 0 00 00 05 50 0&0 00 0&0 0 0 00 00 0B B0 0 0 00 000 0B0 00 0 0 0&R R0 0 0 0 0 00 00 00 0色0 00 00 00 00 0 0 00 00 00 00 0 0 00 00 00 01 11 11 1修&01 11 11 11 11 11 11 11 11 1R Rillill1 1S S6116111 11 1时BBBB1 1111111101101661110066111001 11001001111111 11 1S S01111011111 1-rill-rillillillillillilill lillillillilli illllillillassass90U0S69090U0S69060Qfl96060Qfl9609Ga9Gaae0ae0& &80000U80000Uuu111111001uu1111110011 1111111111111111100001111Bill1111Bill11110 00 0111111111111111111111 1 的1 180000008008000000800090000n0nn090000n0nn0 00 06 60 0n0R0000000n0R00000000000000auuu0000auuu0不规则度2 2重排之前第4次重排不规则度2 2第5次重排不规则度4 4第6次重排11111 1i i1 1111111i i1 10 01 10 0iiiii11i111111i1i1i iiiii111110100 0i10ii0i10ii00 00i0i0 0ii1ii11 10 0B110111B1B110111B1o o01011111-1111-M-M-11111010000000i ii i00000 0lilll0111101111lilll011110111111111101111111110111tltl1111H0w-H0w-M-_MV-M-_MV_M_M0 01 11ii1111111111111111111111ii1111111111111111111110 0。0Id0Id11一M M0 00 0M00flM00fl111000111000111000111000111000111000111000111000111000111000(a0(a0atltl_M_atltl_M_0 000000tl_M_0tl_M_w00MH_w00MHF)000H0F)000H000000000一M_M_M_M_0 05l5lI9BM_M_I9BM_M_R R000000一M0M0不规则度1414第8次重排