校车安排问题终极版.doc

2013高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 第27队 所属学校（请填写完整的全名）： 哈尔滨理工大学 参赛队员 (打印并签名) ：1. 梁学 2. 刘静 3. 张涵 指导教师或指导教师组负责人 (打印并签名)： 日期： 2013年 7月 27日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：摘要根据哈尔滨理工大学西、南和东校区的实际情况，每天教师和工作人员及部分学生在三个校区都有校车接送，为此建立切实可行的数学模型，根据作息时间制定校车发车时刻表，使教职员工、学生和中型客车车主以及学校的利益尽可能大。对于问题一：属于都目标规划问题，我们根据学校里教职工的总数，和教职工公寓在东、西校区分布的不同的比例，估算出每天需要跨区上课老师的数量，合理的制定了每天需要大客车10辆,发车次数为54次，又根据老师上课时间的特点，制定出高、低峰校车的运行时间表；对于中型校车，根据每天往返于各校区人数的多少，制定出相应的校车调度方案得出结论：中型客车6辆，发车次数为112次；另外，分析学生公寓的分部状况以及学校人口密集的地方，一共在西区设立五个站点，南区一个站点，东区一个站点比较适合。对于问题二：为了将这个调度问题抽象成一个明确、完整多目标规化模型，我们采用一种基于概率的算法遗传算法和仿真算法将第一个目标转化为约束条件，把乘客的满意度描述为等待时间的三角形模糊数；为了设计更好的调度方案,应该创建一个校车的调度系统来采集运营数据。 对于问题三：根据第一问和我们的计算得出校车的日均运行成本为3342元，每学期的运行成本33.66万元，我们只考虑学生教职工的满意度没有考虑节约成本。对于问题四：我们结合前三个问题提出好的建议一方面让乘车人员的满意，另一方面又可节省运行成本关键词：三角形模糊数 满意度 多目标线性规划 遗传算法 算法仿真1 问题的提出随着经济的迅速发展，校车安排问题的重要性也日益突出，它主要包括发车次数、停靠站点数、资金合理配置以及满足学生教职工的利益等等。合理的进行校车安排对于学校的发展起着重要的推动作用，因为它直接关系到学校的经济效益和长远发展战略。因此我们就需要调查相关资料，收集往年的信息，对哈尔滨理工大学的校车安排问题进行研究。二问题重述 校车安排问题哈尔滨理工大学有西校区、南校区和东校区, 现在每天都需要在三校区间对发不同班次的两种校车：定员45人的大型客车（免费）由学校负责营运和维修费用，定员25人的中型客车（收费）承包给车辆所有人由其自负盈亏。作好校车的调度对于完善校区建设、改进教职员工工作状况、提高学校的经济效益和创建节约型社会, 都具有重要意义; 如何有效地安排车辆让教职员工、学生和中型客车车主尽量满意也是个十分重要的问题。请你查询当前理工大学三校区间车辆运行时间表, 发车数量等信息, 并回答如下问题。问题一: 设计一个便于操作的全天(工作日)的校车调度方案, 包括两个起点站发车的数辆及中间停靠站; 这个方案以怎样的程度照顾到了学校、教职员工、学生和中型客车车主的利益。问题二: 如何将这个调度问题抽象成一个明确、完整的数学模型, 指出求解模型的方法; 根据实际问题的要求, 如果要设计更好的调度方案, 应如何采集运营数据。问题三: 试估计校车的日均运行成本和每学期的运行成本, 你的调度方案是否考虑了节约成本的问题。问题四: 关于校车安排问题, 你还有什么好的建议和考虑。可以提高乘车人员的满意度, 又可节省运行成本。 三、 问题分析 问题一的分析：问题一属于多目标优化问题，要求设计的方案应该考虑：（1）、 教职员工利益，工作日内所有老师及员工上下班都能及时的坐上车，保证每天最基本的通行，这要求每天上下班高峰期时，起点站能提供教职员工使用的大型校车的数量越多越好；（2）、学校的利益，在保证最基本的通行后，应尽最大可能保证学校的利益，减少不必要的浪费，这要求每天调用校车的总数尽可能的少；(3)、学生利益问题，要保证学生在上下课以及日常校区间必要的通行，都能就近找到中型校车的停靠站，这要求每天发车的频率越大越好，校园内车站数量越多越好；（4）、中型客车车主的利益，满座率越高越好。(5) 、车辆运输途中的停靠站的数量要满足同学乘车，并且要考虑学校大部分人都能就近找到乘车站。 问题二的分析：本题是将这个调度问题抽象成一个明确、完整的数学模型, 并且指出求解模型的方法; 根据实际问题的要求, 如果要设计更好的调度方案, 应如何采集运营数据。作好校车的调度对于完善校区建设、改进教职员工工作状况、提高学校的经济效益和创建节约型社会, 都具有重要意义。调度方案的合理性和实用性直接影响着其服务质量及师生的消费需求。通过分析，主要存在以下问题：师生满意度问题，资源浪费问题，调度运营管理问题，问题二基于这种情况通过对哈尔滨理工大学校车情况进行分析建立一个合理的调度系统。问题三的分析：要估计校车的日均运行成本和每学期的运行成本，并且考虑是否节约了成本。运行成本主要分为校区内的、校区间的和司机工资及其维修费用。计算校车的日均运行成本：首先来计算东西南三个校区内所花费的成本，然后算各个校区之间路途上所消耗的成本，再加上司机的日工资，最后求和。每学期的运行成本：日均运行成本X每学期天数+司机工资+维修费用问题四的分析 对于这个问题，我们要解决的是：一方面提高乘车人员的满意度另一方面要节省运行成本。即协调乘车人员的满意度和中型客车车主的利益，使其利益达到最大化 四、模型的假设1)假设校车在西南东区之间的运行路线是固定不变的（运行路线见附录1）2)假设校车在行驶过程中不会遇到红灯，不存在堵车现象，且途中无特殊事件发生3)假设乘车点均建在各区内，各个校区之间没有站点，校车在校区中途匀速行驶且不会停止4)在乘车点区内的人员乘车距离为零5)假设从学校网站找到的数据真实可靠6)假设车从始发站到达终点站后,必要时立即折回,不需要考虑掉头时间7)假设运营数据内的乘客只能乘坐校车,没有其他车可乘8)假设每位教师及工作人员均选择最短路径乘车 9)假设学生，教师及工作人员到各站点乘车的满意度只与到该站点的等待 时间有关,等待时间越短满意度越高，否则反之，司机的满意度只与坐车人数有关10)假设校车从点到点和点到点所需时间之和固定且为分钟11)假设学校校车数量不变，在一定时间内忽略校车维修费用（校车不会发生意外状况）12) 假设往返各个校区的人数相等，车辆的运行成本是固定不变的13)假设校车在每个校区之间按“按流发车”和“先进先出”原则。14)假设每学期为5个月，每月有30天，司机的日工资为100元 15)假设校车每学期维修三次，每次费用为800元 16)假设校车消耗汽油，45座客车5KM/L汽油，25座客车7KM/L汽油（油 价见附录）五、定义与符号说明W1：日均运行成本W2：每学期的运行成本W3：司机日工资W4：维修费用W5：三个校区校内的成本W6：为校区之间的费用n ：表示有n个司机n1：25座客车发车次数n2：45座大型客车发车次数MN：西区和南区的固定距离OP：南区和东区的固定距离L：校车在三个校区内每次的行驶距离a：一天里最少发车次数b：一共在学校设定b个车站s：示满意度T：示候车时间t：示全天的绝对时刻：示由第 k站到第 k+ 1站过程中车上的乘客数：型和大型校车满意度：发车时间间隔六、模型的建立与求解问题一模型的建立： （1）、根据运营时乘客流量在时间上的不均衡规律我们按时间步长法把时间划分为三个高 峰期和两个低峰期。制定发车时刻表主要目的是为了尽量方便乘客，使乘客没有车坐的可能性降到最低，尽量提高乘客的满意度。 （2）、根据时间段的不同划分为：早上教职工从西校区去往南区和东区的人数较多，达到第一个高峰；上午坐车的人不会很多，中午达到第二个高峰；考虑到下午教职工有课，放学时达到第三个高峰。 （3）、为了确定每个时间点的发车次数，我们求取一天里最少发车次数为a。（4）、为了却确保大部分人能就近找到车站，一共在学校设定b个车站。模型的改进，模型分析 建立多目标线性规划，考虑简化模型，我们将次重要的学校校车利益转化为约束条件，建立单目标线性规划。问题一模型的求解：（1）、通过调查得到学校一共有教职工3038人，专任教师1616人（方法见附录），假设每天需要坐校车跨区上课的老师占总任课教师的30%，大约400人；（2）、通过调查发现，老师的公寓分部在西区19栋，南区1栋，东区13栋（方法见附录），由此可以得出每天居住在西区需要跨区上课的老师为270人，居住在南区需要跨区上课的老师180人；(3) 、已知大校车运输能力为45人每趟，考虑到老师每天早上上课的时间都比较集中，所以早上西区一共需要6辆车，东区一共需要4辆大校车，这样才能保证一次将老师全部运送到目的地；晚上运输同样的老师需要的车数量相同，另外，考虑到有的老师上完上午第一课及下午第一节课后要返回到其它校区，所以中途又要增发一辆大校车。并且在其它时间不调度大校车这样可以使学校的利益得到最大。(4)、 通过分析学校的专业设置，得出结论学校的各个专业是分区设置，基本上跨区上课的同学不是很多，所以就确定早高峰西校区一共发中型校车12次，东校区一共发12次来满足同学的要求，这样将时间段分为高峰与低峰，并且通过调度不同数量的车来满足运输要求，可以保证中型车的满座率达到最大，并且也能满足同学们乘车的需要。最终得出具体校车的调度方案见下表：大型校车时间表：校区时间发车数量校区到达时间校区到达时间西校区7:356南校区7:45东校区7:509:3019:389:4510:00110:0810:1512:00612:0812:1513:00613:0813:1515:00115:0815:1517:10617:1817:25中型校车时间表：校区时间发车数量校区到达时间校区到达时间东校区7:354南校区7:45西校区7:509:3019:389:4510:00110:0810:1512:00412:0812:1513:00413:0813:1515:00115:0815:1517:10417:1817:25校区时间段时间发车数量（辆）发车频率（分钟/辆）西校区早高峰7:00 8:00125早低峰8:0011:401120午高峰11:4013:20910午低峰13:2016:50820晚高峰16:5018:00107晚自习18:0020:00620校区时间段时间发车数量发车频率东校区早高峰7:00 8:00125早低峰8:0011:401120午高峰11:4013:20910午低峰13:2016:50820晚高峰16:5018:00107晚自习18:0020:00620 （5）、通过分析西西区学生公寓的划分情况（见附录），所以得出结果：西校 区一共需要5个停靠站，南区和东区个需要要1个停靠站，这样能更好地满足公寓以及在主楼和一号楼上课的同学都能就近找到停靠站。（站点位置见附录） 建立模型二 将调度问题抽象成一个明确、完整的数学规划模型,建立2个多目标规化，其中目标函数有2 个，一个是关于乘客的，可取最大候车时间，平均候车时间，应取极小值. 另一个是关于学校和中型客车车主的，应是乘客和校车利益的综合，可取车辆满载率及校车辆数，应分别取极大值和取极小值.而调度问题是一个多目标优化问题，即在满足调度限制的解空间内，寻找使调度选择中提出的目标函数都满意的优化解。通过调查哈尔滨理工大学的实际日常作息时间数据，得出由西区开往东区高峰期一般出现在 7: 20 8: 00时和 16: 50 17: 30时, 东区开往西区方向高峰期也一般出现在 7: 20 8: 00时, 16: 50 17: 30时。将乘客的满意度描述为等待时间的三角形模糊数, 满意度随着等待时间的增长而减小。令s表示满意度, T表示候车时间, t表示全天的绝对时刻在早高峰期时, 有：1 0 T 2 s( t ，T ) = -T+ 210（1）在非早高峰期, 有：1 0 T 6 s( t ，T ) = -1/4T+5/2 610 （2）同理可定义每一车次的满意度函数。令表示由第 k站到第 k+ 1站过程中车上的乘客数, 则任一车次在两站之间行驶过程中的中型和大型校车满意度分别为 0.05 0 12 ()= 0.0308+0.2308 12 25 1 25 30 0.027 0 22 ()= 0.0174+0.2174 22 45 1 45 54（3）则每一车次的满意度函数 s定义为从起点至终点路上的运行过程中, 所有的站间车辆满意度之和:= （4） 由于上行方向和下行方向的运行情况相互独立, 为方便起见, 这里只对一个方向 (如上行方向 )进行描述。根据问题要求, 给该线路制定一个全天的发车时刻表, 所以变量为一个发车的时间间隔序列 (指上行方向 ): （5）其中, 为发车时间间隔。为便于公司的实际操作, 取 为正整数; 为缩小解的搜索空间, 根据实际情况, 可取 2 15。另外还应满足: = （6）其中, 最后一班车的发车时刻为 , 根据全线长和平均速度, 可取 为 17: 30时的绝对时刻,即 = ( 17. 5 - 22/3) 60 = 610(m in ), 并由实际情况, 令 = 10(m in)。公交调度所要求的目标应兼顾公司利益和乘客满意度, 所以该问题应该是一个多目标优化的问题。乘客满意度主要与候车的时间有关, 以及校车到该站的时间有关, 以 表示为在 t时刻, 在第 j站等待时间为 T 的人数, 有 （7）若 已知, 将其与满意度函数的乘积对 T积分, 然后对一天的时刻进行积分, 求出了一天内各站所有上行方向的乘客的满意度之和。但 是动态的, 无法用已知参数显式地表达出来, 需要在仿真过程中不断地予以确定。公司的总的满意度为一天内所有车次车辆满意度之和, 即 ( 8)同上面乘客的满意度计算方法一样, 各车次的满意度也需要在仿真过程中不断地予以确定。综上所述, 本模型的目标函数为m ax m ax ( 9) 考虑到哈尔滨理工大学校车发车及学校日常作息时间的实际情况以及可操作性, 多目标的处理:学校需要维持正常运转，师生对其服务质量的满意程度起着相当重要的作用，因此，顾客的满意度必须达到一定程度 即 ( 10)这样就将第一个目标转化为了约束条件, 从而简化了问题。由于该问题是离散的, 所以本文采用一种基于概率的算法遗传算法以及仿真算法。采集运营数据：首先创建一个校车的调度系统，统计每个师生的信息，对数据库进行实时的更新，对数据进行统计汇总并且根据每辆车的乘客最大人数，合理安排校车。其次是建立一个完善的调度系统，采用第三范式原则建立数据之间的联系，实用又规范。利用目前主流的Asp.Net技术进行开发；网络结构模式则采取B/S架构，程序运用三层架构，保证系统的可维护性和可扩展性。建立师生与校车座位相对应的一个关系库，通过这一系列的程序建立起一个方便快捷的预定策略，为广大师生服务。最后要由专人负责对系统进行维护，寻找一个熟练掌握数据库的人，实时的更新每一天的预定情况，并且要与校车负责人时刻保持联系。把预定的人数以及坐车时间及时的反馈给校车负责人，以便及时的安排校车发车的数量。 问题三的模型和求解MN西区和南区的固定距离1.1km如图OP南区和东区的固定距离5.09km如图日均运行成本：（以汽油为准，单价见附录）根据问题一得出25座中型客车和45座大型客车的发车次数分别为（n1=112）（n2=54）。校车在三个校区内平均每次的行驶距离为L2.8km（西区2020m+南区360m+东区420m）（根据站点的不同而改变）（测量结果如下） 西区路线及站点位置南区路线及站点位置东区路线及站点位置W5 = n1*L/7*7.22+n2*L/5*7.22W6=n1*(MN+OP)/ 7*7.22+n2*(MN+OP) /5*7.22W1= n*W3+W5+W6=3342元每学期的运行成本：W2=W1X5个月X30天+维修费用=50.37万元根据实际情况比较，我们按每个月30计算，其实45座大型客车和25座中型客车每月的运行时间只有20天（周六周日休息）每个月都多算了10天，对客车多算的工资大约是16.71万元，因此实际每学期的运行成本33.66万元，我们只是考虑了教职员工、学生和中型客车车主的利益，没有考虑节约成本。问题四的模型和求解1、根据实际情况，相比之下司机的工资远大于校车运行的成本，因此我们可以减少司机和校车的数量，增加发车的次数来节约成本。但是也要增加司机的待遇以便提高他们的积极性。2、通过对前三问结果的分析可知，在各个校区每个站点都存在空座的情况，因此在下课时间发一次车这样既可以保证在一个小的时间段里会有校车去其他校区，也保证了中型客车车主有一个相对较高的满座率。3、政府可以考虑建立校车统一管理体系，即通过公司化方式筹建校车公司，对校车及校车司机统一管理，严格把关，学校则通过购买服务的方式与校车公司签订协议。这样可以通过对校车的更有效利用，提高校车司机的待遇，并有助于管理规范。 七、对模型的评价及推广模型的优缺点分析 优点：模型结构简单，具有一定的原创性，我们对模型中涉及到的众多影响因素进行了量化分析，使得论文有说服力并且成功解决了校车调度问题，给出了较为满意的调度方案，具有一定的普适性和实用性，而且便于计算。模型能与实际紧密联系，结合实际情况对问题进行求解，可信度较高，使得模型具有很好的通用 性和推广性。 缺点：模型中 教职工和学生的流动数量全部是估计值，没有进行实际调查，模型的基本假设条件太多，影响因素过于单一化，使得结果与实际情况有些误差。比如存在车载量未满开走或车辆等候教师及工作人员而停滞的现象，未考虑到交通（堵车和红绿灯）、天气（阴雨天）及每个人的具体情况。改进方案：在上述模型中，为了简化问题的求解，我们做了好多假设，但在实际情况中，由于公路堵塞、汽车故障、自然灾害等因素的影响，这些应该被考虑进去。模型的推广：通过对题目的解读我们不难发现这是一类规划问题