中国矿业大学校车调度方案

1、中国矿业大学徐海学院第七届数学建模竞赛承 诺 书我们仔细阅读了中国矿业大学徐海学院数学建模竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B中选择一项填写）： B 我们的参赛报名队号为： 201206

2、 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2012 年 11 月 18 日赛区评阅编号（由组委会评阅前进行编号）：201206中国矿业大学徐海学院第七届数学建模竞赛编 号 专 用 页评阅编号（由数学建模协会进行编号）：评阅记录（可供评阅时使用）：评阅人评分备注统一编号：中国矿业大学校车调度方案摘要 本文针对中国矿业大学校车在南湖校区和文昌校区之间运行的安排问题，通过合理的抽象假设，把校车安排问题建设成多目标模型，求解。在问题解决过程中使用了佛洛依德算法，排队论，满意度等数学模型，并利用MATLAB、Ex

3、cel对数据进行分析处理，给出了必要的图表直观的说明问题，并用C语言实现某些算法，最终得出结论。我们充分考虑现实生活中存在的一些情况，提出一些建议，以提高乘车人员的满意度，而且可以有效节省运行成本及相关费用。对于问题一，我们根据现阶段校车的运行状况，调研两个校区内停靠点处教师和学生乘车的一些数据，通过合理假设，用excel对数据处理得到图表(文中表1、表2、图1、图2)，再对图表分析分别得出了教师和学生的排队规律。利用图表直观表明影响校车调度的方案，采用排队论设计出工作日和双休日校车的调度方案（文中表3、表4）。对于问题二，建立多目标模型。目标有：校车的运行成本、经济效益、教职工和学生的满意度

4、。将校区划分为六个区域。添加满意度的约束条件Hk>h，建立车辆数模型。根据多目标函数的约束条件，既要满意度满足，又要使运营成本最低。对于问题三，根据模型一与模型二的分析，得出附件中给出的调度方案的中数据的满意度值0.7546 。又结合与问题一所得调度时间基本符合，从而得出方案合理的结论。对于问题四，根据实际的情况，分析一些具体的因素，导致影响校车的调度，一切都要从实际出发。我们结合模型对校车的安排问题提供了建议。关键词：弗洛伊德算法；总体满意度；经营者的利益；校车调度； 多目标规划； Matlab； Excel；排队论1、 问题重述中国矿业大学有南湖校区和文昌校区，现在每天都需要在两校区

5、间发不同班次的校车。作好校车的调度对于完善校区建设、改进教职工工作状况、提高学校的经济效益和创建节约型社会，都有着重要意义。如何有效安排车辆让教职工和学生尽量满意也是十分重要的问题。问题一：根据现阶段校车运营状况，调研两个校区内停靠点处教师和学生排队的规律；分析影响校车调度方案的因素，根据中国矿业大学各校区师生的实际情况，设计一个工作日和双休日校车的调度方案，方案中包含两个起点发车的数量及中间的停靠站；问题二：绘制两校区校车行车路径，考虑到校车的运行成本、经济效益以及教职工和学生的满意度等问题，试建立校车调度模型，并指出求解模型的方法。问题三：基于问题二中的调度模型，根据实际情况，试分析附件中

6、的一种校车调度方案的合理性，并给出更好的设计方案。 问题四：关于校车调度方案还有什么好的建议和考虑，请写出1000字左右的建议书，既可以提高乘车人员的满意度和节省运营的成本。2、 模型的假设1、 假设车辆均准时发车，不存在延时发出现象2、 校车只在各个点上载人，行驶途中不载人3、 假设校车均能正常运行，不存在车故障或是校车超车现象4、 假设每个乘车点的乘车人数固定不变5、 假设本文搜到的数据都是科学准确的。6、 假设等车的学生、老师均可上车7、 假设校车的最大承载量为85（人）8、 为了便于分析，把校区分为6个区域9、 假设均使用同一类型的校车 三、符号说明主要符号符号意义顾客数 乘客平均数时

7、间内到达的乘客平均数乘客的平均队长平均等待队长平均逗留时间平均等待时间图的距离矩阵 总满意度平均满意度第i个区域到第j个区域之间的距离第i个区域到达第j个区域所要经过点的记录四、问题的分析与建模思路图4.1问题分析4.1.1研究意义中国矿业大学有南湖校区和文昌校区，现在每天都需要在两校区间发不同班次的校车。作好校车的调度对于完善校区建设、改进教职工工作状况、提高学校的经济效益和创建节约型社会，都有着重要意义。4.1.2研究现状中国矿业大学有南湖校区和文昌校区，受教育资源的限制，两校区的老师及同学需要乘坐校车去另一个校区教学或上课，现在每天都需要在两校区间发不同班次的校车。南湖校区附近没有大的商

8、务区，南湖校区的学生喜欢乘车到文昌校区附近买东西。4.1.3存在问题如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。由于受到车辆数目的限制，即车辆花费的限制。还有乘车点的限制。我们只能在现有的条件下合理的安排乘车点和乘车数目使教师和工作人员尽量满意。4.1.4分析问题1： 根据矿大现阶段校车运营情况，矿大文昌校区公交起点站在教师宿舍区，离教学区较远，假设学生不会去起点站坐车，所以就只分析教师在起点站坐车，学生在教学区附近的两个乘车点（主楼北站点与主楼东站点）乘车。学生在两站点坐车的人数用概率计算。南湖校区共有六个站台，主要也是学生坐车。 4.1.5分析问题2： 要求在教师和工作

9、人员的满意度最大为前提条件下选出最佳乘车点。为此需要建立关于满意度的函数，然后以平均满意度最高为目标函数建立模型，并对设立2个和3个乘车点时的校车安排问题进行求解。4.1.6分析问题3： 基于对问题一和对问题二的求解，得到影响调度的主要因素，以及运营商的成本（运行的最短距离）、人们的满意度等因素，对表中的一个数据进行分析，并给出建议。4.1.7分析问题4： 基于前三问，以及根据现实中的实际情况，给出合理的建议及考虑。4.2建模思路图 根据问题一的题设，建立排队论，建立模型，得到主要的影响排队的因素由观察、记录最近几天的实际情况得到数据并作出其大致图像根据现实情况分析影响校车调度方案的因素基于题

10、设一的结果，建立多目标模型，满意度，运用Floyd算法，得到满意度主成分排队论，Floyd算法,多目标模型，满意度等模型的建立基于对问题的调查所得的规律建立调度体系综合考虑各因素，给出总体意见及考虑，来提高人们的满意度和节省运营商利益对现有的一种方案进行分析，并提出建议五、模型的建立与解析5.1 问题一的解答5.1.1问题一中的排队规律表一：同一时间在该站点乘车的人数占本校区总乘车人数的比例校区站点排队乘车人数南湖校区站点1（始/终）0%站点210%站点3（图书馆站点）60%站点410%站点510%站点610%文昌校区站点7（主楼北站点）20%站点8（主楼东站点）60%站点9（终/始）20%（

11、以教师为主）注：由于文昌校区的始（终）点站在教师宿舍区，所以假设教师只在始（终）点站坐车表二：同一站台（以文昌校区主楼东站点为参考点）不同时间的等待乘车的平均人数即到达车站的速率时间段工作日双休日周一至周四周五周六周日到达速率（人/min)到达速率（人/min)到达速率（人/min)到达速率（人/min)07：00-07：30 30 2 30 21015107：30-08:00 603 6033028108：00-09:40 151 1511015109：40-10:20 402 4022016110:20-11：45 151 1511015111:45-12:30 704 654302202

12、12:30-13:30 101 2011014113:30-14:00 604 50440310114:00-15:40 151 20110130215:40-16:10 403 45320220216:10-17:45 151 10110110117:45-19:00 704 75430240319:00-20:20 10120-22:05 704 754503654 根据表一和表二的数据分析得出，南湖校区站点2、4、5、6和文昌校区站点7排队等待乘车规律大致相同，南湖校区站点3和文昌校区站点8排队等待乘车规律大致相同，故在此仅以文昌校区学生、老师等车规律为例，列表

13、与图进行说明。图一：发车前不同时刻到站台乘车的平均人数 图二：发车前不同站台的等待人数维修费5.1.2 影响校车调度的因素乘车人员的等待时间班车次 运行商受对利益的驱使 乘车人员的满意度乘车人员的舒适度 满座率 车辆行驶时的路况 车辆数5.1.3 设计一个工作日和双休日的调度方案 等待制模型该模型中顾客到达规律服从参数为的Poisson分布，在 时间内到达的顾客数 服从的分布为： （1）其单位时间到达的乘客平均数为，时间内到达的乘客平均数为。乘客接受服务（即乘客上车）的时间服从负指数分布，单位时间服务的乘客（即乘客上车）平均数为，服务时间的分布为： （2）每个乘客接受服务的平均时间为。下面分别

14、给出S=1的情形，即服务台个数仅为1 可以计算出稳定状态下系统有个乘客的概率： （3）其中称为系统的服务强度。则系统没有乘客的概率为：系统中乘客的平均队长为： （4）系统中乘客的平均等待队长为： （5）系统中乘客的平均逗留时间为： （6）系统中乘客的平均等待时间为： （7）从(4)(6)式可以看出： ， （8）或 ， （9）该公式称为Little公式。在其它排队论模型中依然适用。Little公式的直观意义：表明排队系统的队长等于一个乘客平均逗留时间内到达的乘客数。表明排队系统的等待队长等于一个乘客平均等待时间内到达的乘客数。 下面分别将表2 的数据带入上面的算式，可得下表，即平均的等待时间（参

15、数中，上车的速率大约是18人/min)表三：乘客不同时间段的平均等待时间(min）时间段工作日双休日周一至周四周五周六周日07：00-07：308 8 141407：30-08:00 667708：00-09:4019 19 191909：40-10:2012 12131310:20-11：4528 28 202011:45-12:3012 12 151512:30-13:3038 40 414113:30-14:006 6 7714:00-15:4014 15 151515:40-16:108 9 91016:10-17:4512 12 131317:45-19:0013 14 171219

16、:00-20:2023 24 201820:20-22:0520 22 2317根据上表，可建立以下的发车方案 表四：发车数量（时间间隔为表三中的等待时间）时间段工作日双休日周一至周四周五周六周日07：00-07：302 2 2207：30-08:00 665508：00-09:405 5 4409：40-10:204 44410:20-11：453 3 2211:45-12:303 3 2212:30-13:302 2 2213:30-14:006 6 5514:00-15:405 4 4315:40-16:103 3 3316:10-17:454 4 4417:45-19:005 6 45

17、19:00-20:203 4 4520:20-22:056 6 56 注:停靠站以文昌校区的主东站点和南湖校区的图书馆站点为基准，因为这两个站点为上车和下车人次较多。5.2 问题二的解答5.2.1两校区校车行车路径 5.2.2 校车调度模型及其求解方法此问题以运营成本和总体满意度为双目标函数；最短乘车距离模型：Floyd算法简介Floyd算法是弗洛伊德（floyd）提出的一种解决每对节点之间最短路径问题的的算法。算法的基本思想：直接在图的带权邻接矩阵中，用插入顶点的方法依次构造出v个矩阵D(1)、D(2)、D(v),使最后得到的矩阵D(v)为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最

18、短路径。1.在邻接矩阵G中表示第i个区域到第j个区域之间的距离；2.用矩阵R来记录插入点的信息，其中表示第i个区域到达第j个区域所要经过点的记录，把各个区域插入图中，比较插入区域后的距离与原来的距离，如果的距离变小，则=k，并把最短距离记录在矩阵D中。算法完成后则R中包含了最短通路的信息，中包含了最短路径的信息。关于本文具体问题的算法（算法程序见程序1）如下：1.先根据题目所给的各个连通区域之间距离的数据为初始矩阵赋值，其中没有给出距离的赋给无穷大，其中B(i,j)=0(i=j)。2.进行迭代计算。对任意两点，若存在，使，则更新。3.直到所有点的距离不再更新停止计算,则得到最短路距离矩阵B*(

19、i,j)。模型数据处理依据模型，利用MATLAB软件(程序见附录)求得结果如下当时：乘车点设立在2区4区，各个区域到各自最近乘车点的最短距离之和为Z=1449米。当时：乘车点设立在1区3区和6区，各个区域到各自最近乘车点的最短距离之和Z=1266米。 由结果可看出当乘车点越多时，Z值越小。满意度模型的建立如果车站就建在自己的区，则乘客就非常的满意，如果离自己区最近的车站比较远，则乘客就不满意。乘客对车站点的满意度取决于自己区到最近乘车点的距离。为此我们建立满意度函数其中,为第k个区离本区最远区的距离，为第k个区离本区最近区的距离，当然离自己区的距离最近，即。化简得 （2）k的值越大，满意度就越

20、大。如果乘车点就建在自己的区,则d=0, k=1,该区的乘客非常满意；如果让乘客去距离本区最远的区乘车，则k=0,为极度不满意。结合满意度函数，建立最高满意度乘车点选择模型，由于每个乘车点的乘客的满意度不同，乘车点的人数也不同，我们不可能使乘车点的乘客的满意度都最大，因此我们关注的是全体乘客的平均满意度为使教师和学生的满意度最大，为此我们将全体人的平均满意度作为目标函数 2. 满意度函数的求解依据模型二，利用MATLAB软件求得结果如下（程序见附录附录中程序3）：当时:选择的2个乘车点为区域2和区域4，平均满意度为0.7239。选区域有1、2、3、4、5、6当时：选择的三个乘车点为区域1、3、

21、6选区域有1、2、3、4、5、6由计算结果可看出，建立车站数越多，乘客的平均满意度越高。5.3 问题三的解答 基于问题2，在模型1的基础之上，判断时间的合理性，取得最短时间及路径。依据模型二，利用MATLAB软件求得满意度约为0.7546，目前的校车点安排较为合理，以及排队论所求得的时间，可得目前的校车调度较为合理。 5.4 问题四的解答 此前为了建立模型的方便， 在本文假设使用同一型号的校车。但是在现实的情况下，在不同的时间段里校车的满座率不同。在繁忙期间，等待校车的人或许上不了车，在不繁忙的时间段里校车里还有空座，所以可以考虑使用小型的校车，小型校车不仅节约购买成本，而且耗油量少，这样就可

22、以获得更大的利润。当然不能仅使用小车，因为在繁忙的时刻小车使用量大，反而增大了成本，所以我们建议采取组合的形式，使用大车小车相结合的方案。繁忙时刻存在使用两辆大型校车做不满，两辆小型校车做不下的情况，此时就可以使用一辆小型一辆大型相结合的方案。在这里只是举出一个例子帮助表达理解，可以根据具体的问题具体分析，选出最佳的搭配方案。繁忙的时候还可以加派校车，这样就可以节省大家的等待时间，但是有考虑到运行成本的问题，在繁忙的时候可适当增加收费1-2角（校园实行一卡通，坐校车可以使用校园卡，这使少量的增加收费成为一种可能，也不费时），此方案不仅可以减少运行成本，而且可以让在繁忙时间没有重大时间需要乘车的

23、人避开高峰期。购买两辆车作为备用车。现实生活存在各种情况。情况一：校车抛锚，为了不耽误乘客的行程，此时需要使用备用车辆解决这个问题。情况二：雨雪天气。路上可见性小，交通也可能堵塞，此时为了安全起见，校车行驶速度减少了，此时就会出现发车延迟的现象。此种现象会影响的乘客的行程安排，增加等车时间，满意度大大降低。如果有备用保证准时发车，那么乘客的满意度会大大提升。情况三：大学有老师常常会因公出差，有时候人多，需要租车出行，学校可以提供这样的服务，不仅方便教师出行，而且可以增加收入。情况四：校车行驶到一定的路程就需要保养，在一般车保养期间，就可以使用备用车保证校车系统正常运行。综上论述，准备备用校车是

24、必须的。分析现实情况大部分教师居住于风华园，大部分老师有自己的车，乘坐校车的教师少，而且只在上下班的时间。所以建议在上下班期间开通一辆小校车往返风华园于学校之间。这样平时的校车就不需要在风华园停车了，在节约时间的基础上增加了学生的满意度。适当增加乘车点数能增加教师和工作人员的总体满意度。而减少校车数量与增加总体满意度相矛盾。因此，在校车安排时应综合考虑教师的满意度和增加校车与乘车点的成本问题，在条件允许的范围内尽量增加乘车点以提高总体满意度。六、模型的评价本文的优点如下:1) 通过调研的具体数据，使用Excel工具作出函数图像，从而得到教师与学生的排队规律，清晰明了。2) 运用排队论，Floy

25、d算法，多目标规划，满意度等模型，对各个问题进行合情的分析与计算，并结合实际情况提出一些合理化意见与建议。本文的缺点是:1) 本文中有些假设并不合乎实际情况，因而在分析计算时与生活中的实际情况可能有着一些偏差。2) 时间复杂度比较高，不适合计算大量数据。 3) 模型的基本假设条件有点简单 4) 没有很好地把握论文的重心，让人感觉论文有点散。 5) 由于是第一次参赛，模型建立不够成熟和专业 七、模型的改进及其推广改进方案：本文模型适合于乘车人数基本稳定、行驶时间基本不变的情况，当有较大变动的时候，模型的误差变大，所以我们考虑到， 1、 更进一步分化每个时间段的校车行驶时间； 2、增加能反应有关需

26、乘人数、滞留人数的统计数据。 八、参考文献1 张磊，毕靖，郭莲英.MATLAB实用教程.北京：人民邮电出版社，2008，55752赵静，但琦.数学建模与数学实验.北京：高等教育出版社，2003，822，38603姜启源 谢金星 叶俊，数学模型，高等教育出版社，2003年8月4李得宜 李明，数学建模，科学出版社，2009年5月5孙祥 徐流美 吴清 Matlab7.0基础教程 清华大学出版社。6 刘卫国.MATLAB程序设计与应用.北京：高等教育出版社，20067 邬学军，周凯.数学建模竞赛铺导教程.杭州：浙江大学出版社，2009附录表六 各区距离表区域号区域号距离(m)1240013550247

27、0034630451140区域人数区域人数116542162167519431426218表七 各区人员分布Matlab程序：程序1：clear;clc;n=6;a=zeros(n);a(1,2)=400;a(1,3)=550;a(2,4)=700;a(3,4)=630;a(4,5)=1140a=a+a'M=max(max(a)*n2;a=a+(a=0)-eye(n)*M;path=zeros(n);for k=1:n for i=1:n for j=1:n if a(i,j)>a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); path(i,j)=k; en

28、d end endenda;程序2：sl=inf;for b=1:n for c=1:n for d=1:n if a(b,d)<a(c,d) l(d)=a(b,d); else l(d)=a(c,d); end end L=sum(l); if sl>L sl=L;p1=b;p2=c; end endendsl,p1,p2for i=1:n if a(i,p1)<=a(i,p2) qulu(1,i)=p1; else qulu(1,i)=p2; endendqulu程序3：q=sum(ren);sl=0; A=max(a);for b=1:n for c=1:n for d=1:n for e=1:n mm=a(b,e),a(c,e),a(d,e); l(e)=min(mm); lren(e)=(A(e)-