2013年河南科技大学数学建模选拔赛
承 诺 书
我们仔细阅读了数学建模选拔赛的规则.
我们完全明白，在做题期间不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人研究、讨论与选拔题有关的问题。
我们知道，抄袭别人的成果是违反选拔规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守选拔规则，以保证选拔的公正、公平性。如有违反选拔规则的行为，我们将受到严肃处理。
我们选择的题号是（从A/B/C中选择一项填写）：
队员签名 ：1.
2. 3.
日期： 年 月 日
2013年河南科技大学数学建模竞赛选拔
编 号 专 用 页
评 阅 人 评 分 备 注
评阅编号（评阅前进行编号）：
评阅记录（评阅时使用）： 校内电瓶车线路优化设计
摘要
本文针对校内电瓶车线路最优化问题，从最短路径和最大流量问题入手，通过对全体师生出行规律和校园建筑布局与道路情况的分析，设计出电瓶车的最优路线走向、站点设置、运行时长、发车间隔。
在分析学生出行规律时，本文采用抽样调查的方式，通过数据关系的处理得出在一定时间段、一定路段区间内乘坐电瓶车的人数，以此为基础建立人流量与时间的关系方程。并通过autoCAD得到各路段长度。
在设计最优路线时，针对普遍情况下和高峰情况下的最优走向，分别将之视为任意两点的最短距离问题和一个源点到任一点的问题。对于任意两点的最短距离，可以建立图论模型，采用Floyd算法，加权求和得到遍及条件下的最短距离；对于源点到任意点的问题，可以采用Dijkstra算法求解。在路线中，存在人群集中点与集中面。取人群集中点为站点，对人群集中区用采用不变量原理获取最优站点，从而可以得到各站点的位置。之后根据时间安排推导出运行时长。根据行车的最短时间与人流量的关系得到发车间隔。设计方案如下： 方案 使用时间 行车路线 发车间隔 方案一 工作日日常运行 路线1：6-9-11-10-7-1 路线2：6-9-8-5-4-1 路线3：6-3-2-1 路线1：1-4 路线2：1-5 路线3：1-10 路线1：10-7-4 路线2：8-5-4 路线：10-7-8-5-4 686s 582s 424s 无 方案二 工作日上课高峰 方案三 方案四 方案五 方案六 工作日下课高峰 工作日换课高峰 工作日晚间 无 无 520s 368s 无 路线1：6-9-8-7-1 路线2：6-5-4-1 周末、节假日、1-2-3-6 特殊天气
本文最大亮点在于采用针对不同问题采用不同模型，采用不同算法，从对结果的分析中得到最优解。在确定菁园站点时使用不变量原理，简化了大量计算与推导过程。在分析数据时充分解析其复杂性，定义了一个量并求得其一般表达式，并利用此项结果进行后续计算。在考虑高峰问题时假设拥有更多电瓶车，数量控制在两辆之内，日常调度过程中将之用于解决德园教职工上班问题，达到资源利用最大。
关键词： 最短路径 校车调度 最优化
3页 第1页，共
一、 问题重述与分析
我校新校区占地多达3500余亩，较大的面积导致广大师生的出行不便。目前为保障教师教学科研工作的正常开展以及尽量满足学生出行的需要，学校花费了大量的成本购置了电瓶车在校内运行，但教职工和学生仍深感不便，尤其是在上下课高峰时。
为此，学校需对电瓶车线路进行科学规划。
本文需要解决的问题是：针对我校教职工上班规律、同学出行规律、现有交通情况，根据方便师生出行、保障电瓶车利益的原则，设计出电瓶车的路线走向、站点设置、运行时长、发车间隔等。设计方案的学合理性需要充分说明，并为后勤公司提交一份策划论证。
针对这些问题，需要对我校教职工上班、同学上课的出行规律进行分析，出行规律直接影响到校内电瓶车的路线与时间安排问题，是决定校内电瓶车的最佳运行方案基础依据。此外，需要对我校现有交通情况进行研究，确定主要公共建筑间的可行路线与距离，了解在校师生的出行方式，以及现有电瓶车的运行模式。
在解决问题过程中需要服从的条件关系有两个：出行方便和利益保障。1出行方便问题可分为三点考虑，一是能够确定从任意点到任意点间存在校车运行，在设计电瓶车运行路线时必须以此为根据。可以视为遍及性问题。二是在人员从某个建筑内出来后，需要保证周围一定范围内有电瓶车站点，这涉及到站点设置问题。可以对公共建筑进行区域划分，从而得到一定区域范围内的最佳站点设置位置。三是等待时间必须控制在一定范围之内，过长的等待时间会令乘客感到不方便，累计效应下会选择不再等待校车，因此确定发车间隔必须考虑这一问题。这是一个等待时间满意度问题。2、利益保障需要考虑电瓶车的成本费用，运行费用，维护费用，司机费用三点，可以通过建立营业额与三项费用的差的方程，计算净利润，当净利大于零时，电瓶车利益得到保障，也在保证出行方便的前提下尽可能提高利润或尽量减小损失。
需要最终解决的问题有四个：路线走向、站点设置、运行时长、发车间隔。根据前面的分析，路线走向的前提是满足遍及性，在此基础上实现最短路径，在高峰期实现最大流量。站点设置是在将人流量集中点进行区域划分的基础上进行的，以集中点到站点距离最小为目标，建立模型给出站点位置。发车间隔可以视为到站时间间隔，即乘客可能等待的最大时间，可以通过顾客等待时间与满意度的关系求解此问题。
二、 条件假设
1、平面图与实体比例绝对精确。
2、出行的人数随时间的分布符合事物发展的普遍规律。 3、往返路段区间距离小于500m不会乘坐电瓶车。 4、校内电瓶车的行驶速度为25km/h。 5、上下车时间为零。 6、高峰期电瓶车为直达。
三、 符号说明
k dij ：i到j的只以（1?k）集合中的节点为中间节
点的最短时间
2
I D ：最短距离矩阵
D ：权重矩阵 P ：vi到vj的路
w（P） ：P的权
aij ：i车到达j站的时间 xij ：0—1变量
bij ：车辆i发车到站点j的次数
T ：i辆车完成j站所有运输任务的总时间
四、 模型建立与求解
前期准备：（1）道路情况。确定主要公共建筑间的可行路线与距离。从本校土木工程学院工程与测量实验室获取本校autoCAD平面图及相关建筑物的经纬坐标，对平面根据点坐标对近期变化情况作出修改。利用autoCAD的直观描述结合弧线上的描点法得到相邻两道路交叉口间的距离。详见[附录1]
错误！未指定书签。 （2）出行方式。借用浙江工业大学关于校内出行方式的调研结果，经分析，我校情况与之类似，可以以此描述在校学生的出行方式分布。
（3）校车现行模式概述：校车目前分成两条路线，路线一从校门经致远楼到菁园，路线二从校门经工科到菁园，但是路线二一般不会路过工科组团，导致出行不便。行驶过程中没有固定站点，根据需要任意改变路线，对其他等待校车的师生造成不便。发车
3