公交车排班模型.doc

公交车排班模型中的线性规划求解问题摘要本文研究的是在满足各时段〔早顶峰、日间平峰、晚顶峰，晚平峰四个时段〕时间，公交车以一定间隔连续发车的条件下，排班的最优问题根据各小题的约束条件，用运筹学中的线性规划知识建立模型，再利用Lingo求解,分别算出所需公交车总数以及单班车、双班车各需求量，制定排班的优化方案对于题目条件，我们有三个设想，其一，根据现实生活经历可知，公交车发车间隔相对固定，方便市民安排方案候车出行；其二，从简化模型的角度考虑，每辆车的司机固定，即司机间不允许换车开车；其三，单班车一天不超过5个班次，即认定为所有单班车一天总班次相加不超过5班对于题目一，从各班次发车间隔相等这一假定条件出发，要使在早顶峰时段运行的车辆数最少，只需发车间隔尽可能大，于是我们取早的最大发车间隔5分钟来安排发车，由于该题无对单班车数量的其他要求，我们假定单班车在早顶峰时段安排2辆，同时考虑到车辆要完成一个班次的运行后才可进展下一班次，建立相关模型，用Lingo编程求解得早顶峰时段总共运行24个班次，所需的最少公交车数为16辆对于问题二，在已有模型的根底上，综合考虑全天的工作安排，发车间隔仍取每个阶段的最大发车间隔，同样的，考虑到单班车只在顶峰期运行，在早顶峰运行2到3个班次，在晚顶峰运行2到3个班次，且每天运行不超过五个班次，，根据资源利用的最大化原则，我们知道单班车数不能超过3辆，这里我们仍假设单班车数为2辆，根据题目要求，我们要使每辆公交车的工作时间和上下午司机的工作时间尽可能均匀，且要使车辆的利用率得到最大，根据以上条件建立公交车排班模型，用Lingo编程求解得全天总共运行120个班次，所需的最少公交车数为16辆。

具体公交车排班方案表见表2—1对于问题三，该题约束了单班车数量不少于3辆，由问题二的分析既得单班车数量为3辆，改变问题二模型中的相关参数，用Lingo编程求解得全天总共运行120个班次，所需的最少公交车数为16辆具体公交车排班方案表见表3—1对于问题四，进展调整后，全天共六个时段，并且增加了限制条件，根据问题二的方法，增加双班车数量、餐点和换班时间的约束，用Lingo编程求解得全天总共运行191个班次，所需的最少公交车数为22辆关键词：公交车排班线性规划 Lingo建模贝叶斯算法一、问题重述〔一〕、问题背景随着*市经济的快速开展，公交车系统对于人们的出行扮演着越来越重要的角色在公交车资源有限的情况下，合理的编排公交车的行车方案成为公交公司亟待解决的问题以下给出公交车排班问题中的局部名词说明和假设〔1〕班次：1辆公交车从起点出发到达终点停顿为1个班次〔2〕公交车公司有两种类型的班车：单班车和双班车除非特殊说明，单班车和双班车都可以用于公交车排班〔3〕单班车：由同一个驾驶员驾驶的公交车单班车通常要求在早顶峰跑2-3个班次，晚顶峰2-3个班次，一天不超过5个班次〔4〕双班车：由两个驾驶员驾驶的公交车。

双班车要求上、下午各一个司机，上午和下午司机的工作时间尽可能均匀，并且都不超过8小时每辆双班车一天运行不超过10个班次〔5〕公交车运行的单程时间，已经包含乘客在各站(包括起点和终点)的上下车时间〔6〕假设每辆公交车可以运行1整天不需要加油〔7〕末班车的发车时间，可以在原有发车间隔的根底上调整2分钟〔±2分钟〕〔8〕此题以简单的环路公交路线为例，即公交车从A点出发，经过一系列站点后再次回到A点为1个班次〔9〕最短停站时间是指公交车完成1个班次之后，开场运行下一个班次之前，需要在终点停留的最短的时间在问题1-3中，每辆公交车的最短停站时间为0，即：公交车回到终点后不需要停留，可以继续进展下一班次的运行〔二〕、问题要求问题1. *市2路公交车，从*市火车站出发后经沿途站点后回到*市火车站，2路公交车行车信息如表1请建立数学模型，计算*市2路公交车，在早顶峰时段(6:00-8:00)运行所需要使用的最少公交车数量(需要给出含单班车和双班车各多少辆)问题2. 在问题1的根底上，请建立数学模型并设计相应的求解算法，给出*市2路公交车完成一整天的运行所需要最少的公交车的数量(需要给出含单班车和双班车各多少辆)，并按照表2的格式给出公交车排班方案表。

问题3. 在问题2的根底上，如果要求单班车不少于3辆，请建立数学模型并设计相应的求解算法，给出*市2路公交车完成一整天的运行所需要最少的公交车的数量(需要给出含单班车和双班车各多少辆)，并按照表2的格式给出公交车排班方案表问题4. 在公交车排班过程中，除以上要求之外，还需要考虑如下的实际因素的限制：〔a〕单班车司机不安排吃饭，所有双班车司机都安排吃饭(早餐和晚餐)，每餐饭需要20分钟用餐时间早餐8:00开场供给，10:00截止；晚餐18:00开场供给，20:00截止〔b〕限定双班车辆的数量为19辆〔c〕双班车辆运行5班次以后，上午、下午班司机进展换班，换班时间最少为20分钟(含最短停站时间)请建立数学模型并设计相应的求解算法，并以表3给出的行车信息表为例，给出*市2路公交车行车信息调整后，完成一整天的运行所需要最少的公交车的数量(需要给出含单班车和双班车各多少辆)，并按照表2的格式给出公交车排班方案表附录：表1 *市2路公交车行车信息表时段性质时段开场时间时段完毕时间单程时间(分钟)发车间隔(分钟)最短停站时间(分钟)早顶峰时段06:0008:00804.0±1.00日间平峰时段08:0016:00707.0±2.00晚顶峰时段16:0018:00804.0±2.00晚平峰时段18:0020:30754.5±2.50表2 *市2路公交车排班方案表车辆编号车辆性质(填写单班或双班)起点发车时间返回终点时间每辆车的总的班次上午司机班次(仅双班车需要填写)下午司机班次(仅双班车需要填写)12..........................................汇总信息：总车辆数( )，总双班车数量( )，总单班车数量( )，所有车的总班次数( )注：本表格可以根据需要增减行数〔第一行和最后一行不能删除〕，不能增减列数。

表3 调整后的*市2路公交车行车信息表时段性质时段开场时间时段完毕时间单程时间(分钟)发车间隔(分钟)最短停站时间(分钟)早平峰时段04:3005:00707.0±2.010早平峰时段05:0006:00704.5±1.510早顶峰时段06:0008:00753.0±1.010日间平峰时段08:0016:00754.5±1.510晚顶峰时段16:0018:00753.0±1.010晚平峰时段18:0022:15706.5±2.010二、问题分析公交车排班模型中的四个问题的处理要分两个步骤进展：第一，确定该时段时间以及发车间隔，并根据相关假设，确定约束条件；第二，在最少公交车总数已确定的条件下，算出单班车、双班车数的最优解及排班方式具体分析如下：四个问题均是典型的线性规划模型及求解的问题故该问题的求解步骤如下：首先应确定该问题的目标函数，再确定决策变量，并表示出所有的约束条件，最后用Lingo编程求解即可三、模型假设1.公交车车速恒定，平稳行驶，途中没有堵车以及意外发生；2.以分钟作为最小时间单位；3.各班次的发车间隔都相等；4.每辆车的司机固定，即司机间不允许换车行驶；5.单班车一天不超过5个班次认为所有单班车一天总班次相加不超过5班；6.在顶峰、平峰交接点临近时，假设所剩余时间已缺乏于当前时段的发车间隔，则按照下一时段的发车间隔来排班。

四、符号说明1，：每个时段公交车发车总数，i=1,2,3,4,5,6；2，：每个时段公交车单班车发车总数，i=1,2,3,4,5,6 ；3，：每个时段公交车双班车发车总数，i=1,2,3,4,5,6；4，：全天公交车发车班次总数；5，：每个时段公交车发车班次数，i=1,2,3,4,5,6；6，：每个时段公交车发车间隔，i=1,2,3,4,5,6；7，：每个时段时长，i=1,2,3,4,5,6；五、模型的建立与求解从所要解决的的问题和对问题所做的假设出发，本文对问题一建立了模型Ⅰ，求得早顶峰时段所需的最少公交车数为16辆；对问题二建立了模型Ⅱ，求得全天所需最少公交车数为16辆；对问题三建立了模型Ⅲ，求得全天所需最少公交车数为16辆；对问题四建立了模型Ⅳ，求得全天所需最少公交车数为22辆问题一的求解：模型Ⅰ的一般表达式：此模型中，以早顶峰公交车发车总数为目标函数，以早顶峰单班车数和早顶峰双班车数为决策变量，以每车单程时间处于发车总数与发车间隔的乘积这一区间为约束条件，建立最优化模型由于早顶峰的发车间隔为41〔分钟〕，根据假设3，各班次的发车间隔都相等，因此在早顶峰的2个小时内，每辆公交车的发车间隔都一样，为3,4,5分钟中的一个，故设其为，且由题干知，单班车通常要在早顶峰时段跑2-3个班次，相对于双班车没有班次限制这一优点，单班车较浪费资源，故我们假定早顶峰时段单班车排班尽可能少，仅排2个班次，即=2。

经过上述分析，我们建立以下模型：目标函数：约束条件：模型求解：编写程序，运用Lingo求解得出，，，根据整数约束显然可知，间隔时间为5分钟，早顶峰时段所需的最少公交车数为16辆，其中单班车2辆，双班车14辆程序及运行结果见附录1问题二的求解：模型Ⅱ的一般表达式：此模型中，根据全天四个时段时长的不同，并以各班次发车间隔相等这一假定条件，以全天公交车发车班次总数为目标函数，以四个时段的发车班次为决策变量，以每个时段时长处于发车总数与发车间隔的乘积这一区间为约束条件，建立最优模型问题二建立在问题一的根底上，由于在问题一中我们已经求得早顶峰这一时段所需的最少公交车数为16辆〔其中2辆单班车，14辆双班车〕，因此，我们可以提出一可行想法：能否运用这16辆公交车合理规划，完成一天的乘客运输任务.为解决这一问题，我们先假设能够用这16辆公交车进展全天的排班，则只要能够求出各时段的班次数，进而得全天的班次数后，我们就能对全天进展排班经过上述分析，我们建立如下模型：目标函数：约束条件：模型求解：编写程序，运用Lingo求解得出早顶峰间隔时间为5分钟，早平峰间隔9分钟，晚顶峰间隔时间6分钟，晚平峰间隔7分钟，全天所需的最少公交车数为16辆，其中单班车2辆，双班车14辆，程序及运行结果见附录2。

对于lingo求解的结果进展分析，我们可以看到，最后所求得的最小班次为119班，然而，在排班的最后，我们可以发现，编号为8的公交车倒数第二个班次返回终点的时间为20:29，然而截止晚平峰截止时间为20:30，根据题干要求：末班车的发车时间，可以在原有发车间隔的根底上调整2分钟〔±2分钟〕，而晚平峰发车间隔为2-7分钟，因此，编号为8的公交车末班车在20:30分发车，因此在原有的119个班次上再加一班,为120班表2—1 *市2路公交车排班方案表车辆编号车辆性质(填写单班或双班)起点发车时间返回终点时间。