校车调度

1对学校两校区工作班车的调度问题的研究摘要基于本题为带单边时间窗的单线路单车型的班车调度问题，本文研究了如何合理安排车辆并让教师和工作人员满意的问题。本文根据所给的客流量、运营情况以及反映客运公司和师生的利益的多个指标，包括运客能力与运输需求(实际客运量)的匹配程度、等待时间、总车辆数、发车次数等，应用数值计算软件建立了校车安排方案的优化数学模型，依据题目中所给条件分别建立多目标规划模型来求解。对于问题1，我们根据学校班车车次表给出的每个时刻的发车辆数，建立空趟总次数函数，然后以空趟总次数最小为目标函数建立单目标规划模型，并依据模型借助Matlab软件求出一大早本部和江宁存放车的辆数的最优解，再依照“按流开车”和“先进先出”的原则，安排出具体的班车调度方案。对于问题2，我们根据两站每个时刻的实际需乘车人数，设立各发车时刻的供求匹配比限制和两校区全天发车的总辆数约束，添加约束条件k≤βi，βj≤1+k和NA=MB，建立车辆数多目标规划模型。应用Matlab软件结合各营运指标筛选出恰当的k值，再借助Lingo软件确定每个时刻的发车辆数。以此为基础，运用问题1中的但目标规划模型，求出一大早本部和江宁存放车的辆数的最优解，再同问题1一样依照“按流开车”和“先进先出”的原则，安排出具体的班车调度方案。对于问题3，根据题目的要求，为了进一步满足教师上课、上班的条件，可在问题二的基础上，再添加约束条件，使上课、上班的发车时刻的教师滞留人数为零，运用和问题二相同的方法安排出具体的班车调度方案。关键字：班车调度；多目标规划；单边时间窗；Matlab；Lingo21问题重述两校区工作班车承担了两校区教学，接送师生等服务保障运输任务，附录中给出了新旧班车时刻表以及每个发车时刻需要乘坐的师生的人数统计表，请结合数据进行分析，给出师生坐班车的规律，建立数学模型，具体要求如下：问题1：对于目前的班车时刻表，如何考虑班车的调度，尽量减少空趟运输。（班车调度中，可以自己设置初始条件，即一大早本部停放车辆数以及江宁停放车辆数）问题2：根据调查数据，在满足师生需求的条件下，调整班车时刻表（只调整车辆数，不能调整发车时刻），并基于调整后的班车时刻表，给出调度方案。问题3：进一步考虑，在满足师生需求的条件下，并且保证教师上课、上班的条件下（如：保证老师准时上课，江宁院行政人员9：00上班，本部行政人员8：00上班），给出班车调整方案（包括车辆数以及发车时刻）。（学校目前是12辆校车，调度方案中要给出哪辆校车发哪个班次，如果考虑驾驶员的休息时间，如何进行调整。）（可有车辆闲置）2问题分析由附表中的各调研数据以及新旧班车时刻表，不难发现原班车时刻表存在一些缺陷。比如：对“明故宫——将军路”的校车，整个星期，7：20、9：20班次过多，且9：20空趟较多；工作日时，8：30、13：20班次过多，且8：30空趟较多。对“将军路——明故宫”的校车，整个星期，8：10班次过少；双休日时，12：15、17：00班次过多。对于第（1）问，发空车是为了返程调度，欲减少空趟运输，就应合理调整一大早本部停放车辆数以及江宁停放车辆数以及闲置的车辆数。对于第（2）问，基于原班车时刻表，调整其车辆数，但不调整其发车时刻，从而满足运客能力与运输需求(实际客运量)达到最优匹配、乘坐率较优、总车辆数较少、发车次数最少。对于第（3）问，调整车辆数，使得满足运客能力与运输需求(实际客运量)达到最优匹配、乘坐率较优、总车辆数较少、发车次数最少；调整发车时刻，来保证教师上课、上班的条件。3模型的基本假设与说明制定班车调度方案需要考虑的因素很多，且很多因素都是随机的。为了抓住重点,简化模型建立及求解,必须作一定的简化假设和设定。1)在8:00前和18：30之后发车的校车从起点站发车后,都能在额定的20分钟内到达终点站，其余时刻发车的校车需30分钟；2）师生的满意程度以他是否能在所需的时刻上车以及等待时间来衡量；3）在候车室等待的人绝大多数不会离去，即在某个发车时刻滞留的师生在下一个发车3时刻均能上车且校车最终可以运走所有的师生；4)两校区站点确定，行驶路线相同；5）车辆到达终点时，所有的乘客必须下车；6)从周一至周日，两校区所发班车乘车总人次（包含教工和学生）具有一定稳定性；7）对同一发车时刻，各辆需发出的班车准时同时发出，不考虑延时；8)校车单辆乘客座位数为45，在本次建模中不考虑人员站立情况；9）仅明故宫和将军路两个上车地点；10）当出现一次空趟时，仅调度一辆校车便可解决问题；11）产生空趟仅仅是由于某个发车站的某个发车时刻规定发出的车辆数小于此发车站库存的车辆数；12）当“滞留情况”为“多”时，可认为滞留了20人，为“少”时，可认为滞留了5人，为“无”或无标注时可认为没有滞留。44符号说明βi=Vi/(c×Ni)βj=Wj/(c×Mj)c=45人/车次Vi=Xi+Yi,其中，Xi={Vi，Vi=Ni*c符号表示意义A本部的发车时刻总数目B江宁的发车时刻总数目Ni本部第i发车时刻的发车辆数Mj江宁第j发车时刻的发车辆数Vi本部第i发车时刻的需要运客量（人）Wj江宁第j发车时刻的需要运客量（人）i本部第i发车时刻的供求匹配比j江宁第j发车时刻的供求匹配比Xi本部第i发车时刻的上车总人数Yi本部第i发车时刻的滞留总人数Xj江宁第j发车时间的上车总人数Yj江宁第i发车时刻的滞留总人数NA本部全天发车的总辆数MB江宁全天发车的总辆数k控制参数Na0一大早本部停放车辆数Mb0一大早江宁停放车辆数Nai第i发车时刻，本部车场内存放的车辆数目Mbj第j发车时刻，江宁车场内存放的车辆数目N1本部出现的空趟次数，即NaiNi的总次数（i=1,2,3,.....A)M2江宁出现的空趟次数，即MbjMj的总次数（j=1,2,3,.....B)01从本部出发的班车的平均乘坐率02从江宁出发的班车的平均乘坐率T1本部滞留的乘客的平均候车时间T2江宁滞留的乘客的平均候车时间T(i,1)本部第i发车时刻的车全部离开时候车室内的滞留者的滞留时间T(j,2)江宁第j发车时刻的车全部离开时候车室内的滞留者的滞留时间5Ni*c，ViNi*cWj=Xj+Yj其中，Xj={Wj，Wj=Mj*cMj*c，WjMj*c01/iicNAX02/jjcNBX5模型的建立与求解5.1问题1的模型建立与求解5.1.1模型一的建立要求确定一大早本部停放车辆数Na0以及江宁停放车辆数Mb0(Na0+Mb0=12），欲尽可能减少空趟次数，应建立如下的单目标规划模型：目标函数全天的空趟次数最少min（N1+M2)约束条件实际运营时内在满足条件Nai=Ni时，有Na(i+1)=-Ni+∑Mbji,NaiNi时，江宁车场存车数量少一辆且Na(i+1)=∑Mbji,bji为ii~i(i+1)之间的jMbj=Mj时，有Mb(j+1)=Mbj-Mj+∑Naij,MbjMj时，本部车场存车数量少一辆且Mb(j+1)=∑Naij,aij为jj~j(j+1)之间的i令i1,i2,i3,....iA表示本部发车的具体时刻，j1,j2,j3,......jB表示江宁发车的具体时刻。5.1.2模型一的求解(1)思路：○1根据附录一中的现有班车表中分别排出工作日和节假日的Ni和Mj的具体值○2因工作日班车发车时刻较多，故，针对工作日的Ni和Mj的具体值，基于变量Na0、Mb0，使用matlab得出每对Na0、Nb0对应的Nai、Ni、Mbj、Mj的关系○3仍使用matlab计算出每对Na0、Mb0对应的N1+M2（即需要空趟行驶的总次数）的值，并筛选出使N1+M2最小的Na0、Nb0○4对于工作日和节假日，分别给所有班车依次编号，认为在该路线上运行的总车数固定不变，形成序贯流动的车流，依照“按流开车”和“先进先出”的原则,按发车时刻表发车。6(2)利用MATLAB软件(程序见附录五)求得结果如表5.1所示。表5.1工作日时，两校区在每个发车时刻的存放车辆数Na0Na1Na2Na3Na4Na5Na6Na7Na8Na9Na10Na11Na12Na13Na14Na15Na16Na17Na18Na19109965431254368871091010Mb0Mb1Mb2Mb3Mb4Mb5Mb6Mb7Mb8Mb9Mb10Mb11Mb12Mb13Mb14Mb15Mb16Mb17Mb18Mb19226121110109799863254432说明：Na19+Mb19≠12,是因为江宁的那辆末班车不能在本部最后的发车时刻赶到，但仍满足每天一大早两校区起始停车辆数相等------本部停放10辆，江宁停放2辆。给12辆校车依次编号○1～○12，经计算分析，得出具体的校车调度方案（见附录六）。5.2问题2的模型建立与求解5.2.1模型二的建立只调整发车辆数，不调整发车时刻，为兼顾师生与班车公司双方的利益，分别对从本部出发和从江宁出发的班车建立如下的多目标规划模型：目标函数两校区全天发车的总车次数最少minNA，minMB约束条件①各发车时刻的供求匹配比限制k≤βi，βj≤1+k②两校区全天发车的总辆数约束NAMB目标函数说明：目标函数使两校区全天发车的最多总车次数，在满足约束条件下尽可能少，以使总共需要的车辆数较少。约束条件说明：条件①是限制各发车时刻的供求匹配比在常熟k和1+k之间，根据参数k的变动量分别进行模拟，从而筛选最恰当的k值。条件②是总发车次数与总收车次数相等，保证了始发站车场的每天起始时刻的车辆数保持不变。5.2.2模型二的求解（1）思路：此题需要人为输入的数据量很庞大，故考虑，○1先由工作日时输入的某站某发车时刻需要乘车的人数，采用matlab软件对各个参变量k来模拟，根据定量的运营指标来筛选出最恰当的k值,同时工作日的各个Ni、7Mj也确定下来，接着，采用Lingo软件确定节假日时的Ni、Mj○2结合新表的发车时刻表，列出每个时刻的发车辆数○3针对工作日的Ni、Mj，基于变量Na0、Mb0，使用matlab得出每对Na0、Mb0对应的Nai、Ni、Mbj、Mj的关系○4仍使用matlab计算出每对Na0、Mb0对应的N1+M2（即需要空趟行驶的总次数）的值,并筛选出使N1+M2最小的Na0、Mb0○5对于工作日和节假日，分别给所有班车依次编号，认为在该路线上运行的总车数固定不变，形成序贯流动的车流，依照“按流开车”和“先进先出”的原则，按发车时刻表发车。（2）筛选出恰当的k值选取参数k采用等步长法来进行循环模拟运行，求解过程及程序见附录七：（对模型二的目标函数进行线性规划）因各个Ni,Mj为正整数，故，经整理如表5.2所示。表5.2不同的k值对应的本部每个时刻该发的车辆数kN1N2N3N4N5N6N7N8N9N10N11N12N13N14N15N16N17N18N190.112311111111211111110.212311111111211111110.25123111111112111111180.311211111111211111110.3511211111111211111110.41121111111111111111M1M2M3M4M5M6M7M8M9M10M11M12M13M14M15M16M17M18M19NAMB1221111121122111111232412211111211121111112323122121111111211111123231221111111112111111212291221111111112111111212211211111111121111112021所得结论如表5.3（表中只给出本部发车的值）：表5.3模拟本部发车所得营运指标值参数k平均乘坐率β01平均候车时间T1(min)总发车次数N10.1085.1%1.76230.2085.1%1.76230.2585.1%1.76230.3088.1%3.26210.3588.1%3,262