校车调度问题

《校车调度问题》由会员分享，可在线阅读，更多相关《校车调度问题（21页珍藏版）》请在金锄头文库上搜索。

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

2、 月 日2013 年河南科技大学数学建模竞赛选拔年河南科技大学数学建模竞赛选拔编编 号号 专专 用用 页页评阅编号（评阅前进行编号）：评阅记录（评阅时使用）：评 阅 人评 分备 注第 0 页，共 21 页校内电瓶车线路优化设计校内电瓶车线路优化设计摘要摘要本文针对校内电瓶车线路最优化问题，从最短路径和最大流量问题入手，通过对 全体师生出行规律和校园建筑布局与道路情况的分析，设计出电瓶车的最优路线走向、 站点设置、运行时长、发车间隔。 在分析学生出行规律时，本文采用抽样调查的方式，通过数据关系的处理得出在 一定时间段、一定路段区间内乘坐电瓶车的人数，以此为基础建立人流量与时间的关 系方程。并通过

3、 autoCAD 得到各路段长度。 在设计最优路线时，针对普遍情况下和高峰情况下的最优走向，分别将之视为任 意两点的最短距离问题和一个源点到任一点的问题。对于任意两点的最短距离，可以 建立图论模型，采用 Floyd 算法，加权求和得到遍及条件下的最短距离；对于源点到 任意点的问题，可以采用 Dijkstra 算法求解。在路线中，存在人群集中点与集中面。取 人群集中点为站点，对人群集中区用采用不变量原理获取最优站点，从而可以得到各 站点的位置。之后根据时间安排推导出运行时长。根据行车的最短时间与人流量的关 系得到发车间隔。设计方案如下： 方案使用时间行车路线发车间隔方案一工作日日常运行路线 1：

4、6-9-11-10-7-1 路线 2：6-9-8-5-4-1 路线 3：6-3-2-1686s 582s 424s 方案二工作日上课高峰路线 1：1-4 路线 2：1-5 路线 3：1-10无方案三工作日下课高峰路线 1：10-7-4 路线 2：8-5-4无方案四工作日换课高峰路线：10-7-8-5-4无方案五工作日晚间路线 1：6-9-8-7-1 路线 2：6-5-4-1520s 368s 方案六周末、节假日、 特殊天气1-2-3-6无本文最大亮点在于采用针对不同问题采用不同模型，采用不同算法，从对结果的分 析中得到最优解。在确定菁园站点时使用不变量原理，简化了大量计算与推导过程。 在分析数

5、据时充分解析其复杂性，定义了一个量并求得其一般表达式，并利用此项结 果进行后续计算。在考虑高峰问题时假设拥有更多电瓶车，数量控制在两辆之内，日 常调度过程中将之用于解决德园教职工上班问题，达到资源利用最大。关键词：关键词： 最短路径 校车调度 最优化 1一、一、 问题重述与分析问题重述与分析我校新校区占地多达 3500 余亩，较大的面积导致广大师生的出行不便。目前为 保障教师教学科研工作的正常开展以及尽量满足学生出行的需要，学校花费了大量的 成本购置了电瓶车在校内运行，但教职工和学生仍深感不便，尤其是在上下课高峰时。为此，学校需对电瓶车线路进行科学规划。 本文需要解决的问题是：针对我校教职工上

6、班规律、同学出行规律、现有交通情 况，根据方便师生出行、保障电瓶车利益的原则，设计出电瓶车的路线走向、站点设 置、运行时长、发车间隔等。设计方案的学合理性需要充分说明，并为后勤公司提交 一份策划论证。 针对这些问题，需要对我校教职工上班、同学上课的出行规律进行分析，出行规 律直接影响到校内电瓶车的路线与时间安排问题，是决定校内电瓶车的最佳运行方案 基础依据。此外，需要对我校现有交通情况进行研究，确定主要公共建筑间的可行路 线与距离，了解在校师生的出行方式，以及现有电瓶车的运行模式。 在解决问题过程中需要服从的条件关系有两个：出行方便和利益保障。1 出行方便 问题可分为三点考虑，一是能够确定从任

7、意点到任意点间存在校车运行，在设计电瓶 车运行路线时必须以此为根据。可以视为遍及性问题。二是在人员从某个建筑内出来 后，需要保证周围一定范围内有电瓶车站点，这涉及到站点设置问题。可以对公共建 筑进行区域划分，从而得到一定区域范围内的最佳站点设置位置。三是等待时间必须 控制在一定范围之内，过长的等待时间会令乘客感到不方便，累计效应下会选择不再 等待校车，因此确定发车间隔必须考虑这一问题。这是一个等待时间满意度问题。2、 利益保障需要考虑电瓶车的成本费用，运行费用，维护费用，司机费用三点，可以通 过建立营业额与三项费用的差的方程，计算净利润，当净利大于零时，电瓶车利益得 到保障，也在保证出行方便的

8、前提下尽可能提高利润或尽量减小损失。 需要最终解决的问题有四个：路线走向、站点设置、运行时长、发车间隔。根据 前面的分析，路线走向的前提是满足遍及性，在此基础上实现最短路径，在高峰期实 现最大流量。站点设置是在将人流量集中点进行区域划分的基础上进行的，以集中点 到站点距离最小为目标，建立模型给出站点位置。发车间隔可以视为到站时间间隔， 即乘客可能等待的最大时间，可以通过顾客等待时间与满意度的关系求解此问题。二、二、 条件假设条件假设1、平面图与实体比例绝对精确。 2、出行的人数随时间的分布符合事物发展的普遍规律。 3、往返路段区间距离小于 500m 不会乘坐电瓶车。 4、校内电瓶车的行驶速度为

9、 25km/h。 5、上下车时间为零。 6、高峰期电瓶车为直达。三、三、 符号说明符号说明：i 到 j 的只以（1k）集合中的节点为中间节 k ijdL2点的最短时间 ID：最短距离矩阵D ：权重矩阵P ：到的路ivjvw（P） ：P 的权：i 车到达 j 站的时间ija：01 变量ijx：车辆 i 发车到站点 j 的次数ijbT ：i 辆车完成 j 站所有运输任务的总时间四、四、 模型建立与求解模型建立与求解前期准备：前期准备：（1）道路情况。确定主要公共建筑间的可行路线与距离。从本校土木 工程学院工程与测量实验室获取本校 autoCAD 平面图及相关建筑物的经纬坐标，对平 面根据点坐标对近

10、期变化情况作出修改。利用 autoCAD 的直观描述结合弧线上的描点 法得到相邻两道路交叉口间的距离。详见附录 1后勤服务中心学生公寓组团2开666666水上舞台音乐广场N食堂学生公寓学生公寓水上舞台浴室食堂多媒体公共教学中心学生公寓学生公寓3（2）出行方式。借用浙江工业大学关于校内出行方式的调研结果，经分析，我校 情况与之类似，可以以此描述在校学生的出行方式分布。（3）校车现行模式概述：校车目前分成两条路线，路线一从校门经致远楼到菁园， 路线二从校门经工科到菁园，但是路线二一般不会路过工科组团，导致出行不便。行 驶过程中没有固定站点，根据需要任意改变路线，对其他等待校车的师生造成不便。 发车

11、时间不定，仅遵守“坐满就走”和司机的主观意愿，使乘客没有“等车”概念。（4）出行时间规律。校园作为一个小型的综合功能区，其对交通的需求有着自身 的特点，如学生出行时间比较集中，出行高峰主要集中在早中晚，周末出行已于平时。 以往文献对此研究内容较少。1对我校师生出行的一般规律进行分析。为获得第一手数据，通过设计调查问的形 式详见附录2，在学院11级及专业四个年级，对学生在一定时间段、一定建 筑物间是否会乘坐校车进行调查，以此反映本校实际情况，并结合查阅其他院校对相 关情况的调查结果，得出教职工及学生出行的规律。根据调查结果，学生日常出行的高峰值在上下课时间和两大节之间需要换教学区 上课的情况，晚

12、上出行几率大于白天。这是一次取样调查，样本容量 ，愿意乘坐校 车人数为 y，定义乘坐比例 b，则b=y/。 由于调查对象为某工科学院的一个年级的 7 个专业和某工科专业四个年级，其上 课情况不同导致往返教学区的情况不同，所以需要分别分析。通过对菁园居住学生的 了解可知菁园学生的院系分布为：理科两个（数统、物理，约 1200 人） ，工科三个 （建工、生物、材料，约 6800 人） ，艺术学院（约 1800 人） ，体育学院（约 400 人） ， 少量文科学院大三大四年级（约 500 人） ，部分研究生。为防止实际人数偏少导致车辆 空载，对总人数进行保守估计为 10000。 在全部人中，有自行车

13、的学生一般不会选择坐校车，可以忽略。根据前文，结合 我校实际情况，假定我校 70%学生有自行车。 根据情况不同取不同的学生群体为研究对象，设研究对象数量为 N，设在该时间段4往返于所述区间的天数占工作日的比例为频率 f。定义一个量为 m（作为乘客来源的） 目标人数，可根据概率知识推导出：30%mNf早高峰流量从 7:00 开始，人流量增加，增加幅度随时间延续递增；至 8:55 开始 下降，下降幅度随时间延续递减。其中，菁园-公教（公共基础课）取研究对象为菁园 全体学生，频率为每周三次。菁园-工科（工科专业课）主要针对理工科学院大三大四 学生，频率为每周一次。菁园-文科（英语课、文科专业课）主要

14、针对菁园所有大一大 二年级学生及文科学院大三大四学生，频率为每周一次。 课间高峰流量从 9:40-10:00，是由上课地点在不同教学区造成的，针对所有专业 大二大三学生及教师。 午高峰流量从 11:00-12:20，主要针对理工科学院和文科学院高年级学生从工科- 食堂，文科-食堂。 下午高峰流量与上午类似。由于上课时间充裕，上课高峰流量有所下降；由于课 间时间较短，课间流量上升；由于晚上选择区校外吃饭的人较多，下课高峰流量有所 上升。 菁园所有学生在一定时间一定区间乘坐校车的人数为： n=mb. 由此可得在一定时间段往返一定区间人数，将其分为早高峰、课间高峰、下课高峰三 类，分别求和，获得范围

15、内乘车人数。在一定时间段往返一定区间人数统计 往返地点乘坐比例b目标人数 m乘车人数 n合计菁园-公教0.0971800175菁园-工科0.32524078早 高 峰 期菁园-文科0.343330113366公教-工科0.04124010公教-文科0.09733032课 间 高 峰工科-文科0.0822402062工科-食堂0.21624051文科-食堂0.1753358下 课 高 峰工科-校门0.041240101195路线走向：路线走向：根据上文对校师生出行的一般规律进行分析，将校车一天内运行时间 根据乘客数量分类。1、平稳期。此时各点间人员流动视为均衡的，因此可以将之近似看做针对任意两 点间的最短路线问题，根据“交通情况”中建立的各个定点，通过 Excel 软件对任意 两点间最短道路长度与该路段平均速度作比，得到对应路段的平均行驶时间，即任意 到达任意两点间的最短时间，并以此为基础利用 Floyd 算法，以行驶时间为权重，建 立各点对应的权重矩阵 D，即D=1112111212111111121111dddddddd LOLMMOML081810 LOLM LOML其中表示点 i 到 j 的时间。当=时，表示 i 点与 j 点不直接相通。以此为基础ijdijd建立