校内电瓶车线路优化设计

2013年河南科技大学数学建模选拔赛承诺书我们仔细阅读了数学建模选拔赛的规则.我们完全明白，在做题期间不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人研究、讨论与选拔题有关的问题。我们知道，抄袭别人的成果是违反选拔规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守选拔规则，以保证选拔的公正、公平性。如有违反选拔规则的行为，我们将受到严肃处理。我们选择的题号是（从A/B/C中选择一项填写）：_C 队员签名： 日期：2013年8月23日2013年河南科技大学数学建模竞赛选拔编号专用页评阅编号（评阅前进行编号）：评阅记录（评阅时使用）：评阅人评分备注校内电瓶车线路优化设计摘要我校新校区占地3500余亩，较大的校区面积致使广大师生出行不便。目前为保障教师教学科研工作的正常开展以及尽量满足学生出行的需要，学校购置了电瓶车在校内运行。学校为此付出了巨大的成本，但教职员工，尤其是学生仍深感不便，尤其是在上下课高峰时。此篇论文本着方便师生出行以及电瓶车的利益对电瓶车线路进行了合理规划。关于校车站点的选择我们利用层次分析法对菁园、工科楼、公教、二号餐厅、篮球场、图书馆、文科楼、嘉园、一号餐厅、足球场、校大门根据载客量、学生对校车的需求、地理位置三个准则对这十个地点进行分析决策确定出合理的校车站点。最终确立的站点为：菁园、图书馆、嘉园、工科楼、文科楼、公教。关于校车路线的选择，我们运用Dijkstra算法求的这些地点间的最短路径并画出最短路径图。最后以确立的站点和一些道路的实际情况为一定依据并结合最短路径图取得路程相对最短但收益相对较大的合理路线。最终确定的路线为：路线1以菁园和校门口为起终点，途中经过二餐厅、公教和文科楼，全程长度为1.9km,其非最短路线系数k=1.2667<2；线路2以菁园和校门口为起终点，途中经过博园、工科楼和图书馆，全程长度2.5km，其非最短路线系数k=1.6667.关于校车运行时间的计算我们以V=20km/h运用以下公式：运行时长=线路长度运行时长=线路长度*平均速度64线路站点数每个站点数停车间隔进行计算，计算得出的运行时间为：线路1的运行时间为7.7min，路线2运行时间为9.5min。关于发车间隔的确定我们利用以下公式：p_Qi_Q.iE*CNTOC\o"1-5"\h\zi i符号说明：P为i时段内配车数、E为i时段内期望满载率、i iC为车容量、N为i时段内校车的期望占用量、Q为i时段内i i的最高断面通过量通过计算我们得到高峰期校车发车间隔为5min，非高峰期发车间隔为8min。针对策划论证，我们通过对项目的必要性进行论证、对目标的可行性进行论证、对限制性因素进行分析、对潜在问题进行分析、对预期结果进行综合效益评价这几个方面写出了我们的策划论证书。关键词：层次分析法、Dijkstra最短路法、策划论证一问题重述我校新校区占地3500余亩，较大的校区面积致使广大师生出行不便。目前为保障教师教学科研工作的正常开展以及尽量满足学生出行的需要，学校购置了电瓶车在校内运行。学校为此付出了巨大的成本，但教职员工，尤其是学生仍深感不便，尤其是在上下课高峰时。为此，学校需对电瓶车的线路进行科学规划。此题需要解决的问题有：请你的小组针对我校教职员工上班规律、同学出行的规律、现有交通等情况，根据方便师生出行、保障电瓶车的利益等原则下设计出电瓶车的路线走向、站点设置、运行时长，发车间隔等。需要充分说明你们的设计方案的科学合理性，并需为后勤公司提交一份不超过2页的策划论证。二问题分析此次论文要解决的问题是：根据方便师生出行、保障电瓶车的利益等原则对学校的校车路线进行合理的规划。谈到线路规划我们首先想到的是单纯的运用Dijkstra算法或Floyd算法求得学校菁园到校门口的最短路然后这个问题就迎刃而解了。但要考虑到方便师生出行、保障电瓶车的利益的原则下单纯用最短路算法求得的最短路并非是最优路，单纯算法求得的最短路虽然路程最短但却不一定满足师生出行、保障电瓶车利益。考虑到上述的问题，此题第一问要求根据方便师生出行、保障电瓶车的利益等原则下对电瓶车的路线走向、站点设置、运行时长、发车间隔等进行合理的规划。对于此题我们打算先利用层次分析法对菁园、工科楼、公教、二号餐厅、篮球场、图书馆、文科楼、嘉园、一号餐厅、足球场、校大门根据载客量、学生对校车的需求、地理位置三个准则对这十个地点进行分析决策确定出合理的校车站点。然后由Dijkstra算法求的这些地点间的最短路径并画出最短路径图。最后以确立的站点和一些道路的实际情况为一定依据并结合最短路径图取得路程相对最短但收益相对较大的合理路线。得到最优路线和相关路线的长度后，我们通过询问校车司机得知校车在校园里行驶的速度为20km/h左右，以该速度为校车行驶时候的恒定速度然后通过以下公式对各线路运行时长进行计算。公式如下所示：运行时长=线路长度*60+线路站点数*每个站点数停车间隔平均速度对于发车间隔的确定我们根据学生出行规律给一整天分出高峰时段和非高峰时段，然后以下公式计算时间间隔，公式如下所示：P_Q._Q.iE*CNTOC\o"1-5"\h\zi i符号说明：P为i时段内配车数、E为i时段内期望满载率、i iC为车容量、N为i时段内校车的期望占用量、Q为i时段内i i的最高断面通过量第一问解决之后我们通过对项目的必要性进行论证、对目标的可行性进行论证、对限制性因素进行分析、对潜在问题进行分析、对预期结果进行综合效益评价这几个方面写出了我们的策划论证书。

三模型假设1•假设校园各个道路交叉口、起始点、终点以及建筑物对距离测量没有影响。2•假设地图上测得的距离真实可靠3•假设校车在校园道路行驶中以恒定速度V=20km/h行驶。4.校车道路选择中只考虑宽敞道路和交通良好的道路，忽略交通不好的道路。5•假设同学一周内出行规律基本不变。四符号说明菁园嘉园U3 公教工科楼一食堂二食堂文科楼图书馆u10u10博园A 准则层对目标层的判断矩阵A 准则层对目标层的权向量max 判断矩阵的最大特征值B 方案层对载客量这一准则的判断矩阵1B 方案层对学生对校车的需求这一准则的判断矩阵2B 方案层对地理位置这一准则层的判断矩阵3W⑶ 方案层对第k个准则的权向量kCI 矩阵的一致性指标RI 矩阵的平均随机一致指标CR 一致性比率W 各个点的带权邻接矩阵l（v） 从顶点到另一点的一条路的权Z（v） 该点的父亲点k 实际线路的非最短路线系数五模型的建立和求解问题一：1.1用层次分析法对校车站点的选择1.11关于层次分析法：层次分析法是由美国著名的运筹学专家Saaty首先提出的，它合理的将定性与定量的决策结合起来，按照思维和心理的规律将决策的过程透明化。层次结构如上所示，通过将指标两两比较的方式建立判断矩阵，通常使用9表度法（见下图表格解释）。当矩阵A为一致性矩阵时，其最大特征值所对应的特征向量归一化后即成为排序权向量表一表度法示意图含义u与u一一样重要u比u稍重要u比u重要ui比u强烈重要Ui比3极重要aj取值135792 4 6 81.12层次分析法目标层、准则层、方案层的层次关系目标层目标层淮则层方案层1.13运用层次分析法求解准则层对方案层的权向量此题为根据方便师生出行、保障电瓶车的利益等原则对学校的校车路线进行合理的规划，因此在这三个准则层中载客量以及学生对校车的需求这两个准则相对来说重要点，以此为依据我们构造准则层对目标层的判断矩阵如下：1 2 3A=1/2 1 21/31/21用MATLAB程序（见附录一）求解得出上述判断矩阵的最大特征值为：各个指标对应的权重向量是：W=【0.53960.29700.1634]A一致性检验：九一n CI一致性检验指标为CI=—（n为矩阵的阶数，此处n=5）,—致性比例CR=C|;n-1 RI当CR小于0.1时，则可以称该矩阵具有一致性。Saaty得到的平均随即一致性指标RI如下表所示：表二一致性指标RI表n1234567891011RI0.000.000.580.9021.411.451.491.51将九maX弋入检验公式得CI=0.0046,CR=0.0079<0.1,所以说矩阵A具有一致性1.14运用层次分析法求方案层对各个准则的权向量根据我们在校园生活两年的观察根据经验构造各个判断矩阵如下：方案层对载客量这一准则的判断矩阵：51213211/3531/61/211/2211/21/4431/51213211/353B=1/71/31/21/311/211/53111/61/211/2211/21/3421/51211211/3531/33435431751/91/51/41/51/31/41/51/711/3_1/71/31/31/311/21/31/531方案层对学生对校车的需求这一准则的判断矩阵

_1354874397一1/31326521751/51/311/2431/21/3531/41/2215411/264B=1/81/61/41/511/21/51/621/221/71/51/31/4211/41/5311/41/2215411/2641/31326521751/91/71/51/61/21/31/61/711/3一1/71/51/31/4211/41/531方案层对地理位置这一准则的判断矩阵:"1633545298一1/611/41/41/21/31/21/5431/34113231/2761/34113231/276B=1/521/31/311/211/45431/431/21/22121/3651/521/31/311/211/4541/25224341871/91/41/71/71/51/61/51/811/21/81/31/61/61/41/51/41/721运用MATLAB程序求解如下：w（3）=（0.3445,0.0897,0.0584,0.0897,0.0399,0.0563,0.0820,0.1905,0.0182,0.0346”1九=10.3747maxCI=0.0416CR=0.0279<0.1该矩阵具有一致性w（3）=（0.0309,0.1560,0.0687,0.1019,0.0230,0.0332,0.1019,0.1560,0.0171,0.0332）t2九=10.3753max

CI=0.0417CR=0.0280<0.1该矩阵具有一致性w(3)=(0.2730,0.0374,0.1279,0.1279,0.0671,0.0843,0.0551,0.1916,0.0155,0.0203”3九=10.6156maxCI=0.0684CR=0.0459<0.1该矩阵具有一致性1.15求取方案层对对目标层的重要程度即权数由(W(3),W(3),W(3))*W计算得各个方案层对目标层的重要程度即权向量如下所1 2 3 A示：(0.3223,0.1011,0.0707,0.0996,0.0393,0.0540,0.0835,0.1804,0.0174,0.0318”1.16校车站点的选择根据上面所求权数大小对各个地点进行排名得到：菁园〉图书馆〉嘉园〉工科楼>文科楼〉公教〉二食堂>一食堂〉博园〉足球场根根据权重大小以及校园大小关系我们决定选取六个站点，它们分别是：菁园、图书馆、嘉园、工科楼、文科楼、公教。1.2最优线路的选择1.21关于Dijkstra算法此算法为求赋权有向图或无向图中从顶点到其余点的最短路，对每个顶点，定义两个标记(l(v),z(v)),其中了l(v)表示从顶点到另一点的一条路的权；z(v)表示V的父亲点，用以确定最短路线。算法的过程就是在每一步改进这两个标记，使最终l(v)为从顶点到另一点的最短路的权。1.22各个地点邻接关系的确立通过查地图我们画出来学校的整体简化图，这样方便我们更好的确定路线，学校的整体简化图如下所示：图一学校整体简化图餐厅1西大门新大门籍园科博园OWT"公教餐厅1西大门新大门籍园科博园OWT"公教接下来我们给一些重要的地点进行标号然后画出根据实际道路连接情况建立起了邻接关系图，各个地点编号：(1菁园—2工科楼一3公教—4■二号餐厅5篮球场6图书馆7文科楼8嘉园9一号餐厅10足球场11校大门)。

则各个地点的邻接关系图如图二所示：图二邻接关系图根据邻接关系图确定带权邻接矩阵如下:013001100792750gggggg130001100gg952865gggg110011000196ggg536ggg792g1960100ggg280gg750gg1000ggg440300gg952ggg0637ggg326g865ggg6370400gg370gg536ggg400096g360ggg280440gg960100ggggg300ggg1000500ggggg326370360g5000运用MATLAB程序（见附录二）求的结果如下：表三Dijkstra算法求解结果l(u)il(u)1l(u)2l(u)3l(u)4l(u)5l(u)6l(u)7l(u)8l(u)9l(u)10l(u)11

l(v)01300982792750185415681168107210501528z(v)114111189458对结果进行分析得到从菁园到各个地点的最短路，菁园到各个地点的最短路径走法以及距离如图三所示：1.22非最短路线系数对于关于线路的选择我们特别定义一个非最短路线系数k。k= （D实际路线的路长，d为最短路线长度）d minmin路线的非最短路线系数k反映了路线的优化程度,该系数是一个不小于1的常数。系数的大小能够说明实际路线与最短路线距离之间的比例关系，数值越小说明这条路线的距离与最短路之间的距离差距越小，说明此条路线绕远程度小。我们规定在考虑司机成本时候当1<k<2时候线路才能称得上最优路。1.23最优线路的选择由算法得到的解可知由菁园到校门口及图书馆的最短路径是1—4—9—8—11，该路径是以菁园和校门口为起终点，途中经过二餐厅、一餐厅和嘉园，考虑到选择的校车站点为菁园、图书馆、嘉园、工科楼、文科楼、公教。这几个站点在最短路线中都没有经过，更重要的是二餐厅到一餐厅到嘉园的道路还狭窄拥堵，如果校车在这里行驶容易发生交通事故且很有可能因为人多路窄而造成行驶缓慢。所以我们打算最优路线不选择最短路线而选择1—4—3—7—11，这样路线经过菁园、二食堂、公教、文科楼等几个重要地点满足了载客量达到最大从而达到校车利益较大的原则；有了此条线路但却没连接到工科楼和图书馆为此我们又选择了第二条线路：1—2—6—11.，这条路线经过了工科楼和图书馆等站点满足了学生的需求。下面我们跟据非最短路线系数对这两条线路进行了验证：线路1：D=1.9km1,D1.9 [ ck=i= =1.2667<2id1.5min由此得线路1为最优路线选择线路2：D=2.5km2,D2.5 ]ck=亠= =1.6667<22d1.5min由此可知线路2也为最优线路选择由此为依据我们对校车路线优化给出两种路线：线路1和线路2,路线具体走法如图四所示：图四优化线路图示校门口北门场工科楼博园亠二密厅公教楼10工稷训選中心5km校门口北门场工科楼博园亠二密厅公教楼10工稷训選中心5kmraw1.3对校车运行时间的解决校车在校园里行驶要注意安全，校园里学生师生众多且道路也没足够宽敞因此校车在校园里行驶一定要以一合适的速度行驶。在此问计算小车运行时间时我们假设校车在校园中以恒定速度V=20km/h进行计算。下面我们对同学们出行规律进行了统计总结，具体规律如表四所示：运行时长=线路长度平均速度运行时长=线路长度平均速度*60+线路站点数*每个站点数停车间隔表四学生出行规律表出行高峰时段A学生出行规律B学生出行规律上午7:30-8:00宿舍-餐厅-教学区9:40-10:00教学区-宿舍11:40—12:10教学区-餐厅-宿舍休息时间下午2:00-2:30宿舍-教学区4:05-4:25教学区到宿舍、教学区到校门口6:05-6:45教学区-餐厅6:45-7:30餐厅到宿舍或教学区晚上7:00-7:30教学区图书馆足球场9:10-10:30回宿舍通过对学生出行规律的观察我们发现在高峰期公教、工科楼以及菁园等各个站点的压力很大，但考虑到大学各个专业的上课时间不一定，各个学生的出行规律也不一定，为了方便计算我们给出每个站点的平均停车间隔为lmin.计算运行时长的公式如下所示：对于线路1（站点为公教、文科楼两个）:D=1.9kmV=20km/h1则行驶时间t=D则行驶时间t=D1=19=0.095h=5.7min20运行时长T=t+2*l=7.7min1对于线路2：D=2.5kmV=20km/h2一 D25则行驶时间t=2= =0.125h=7.5minV20运行时长T二t+2*1=9.5min21.4发车间隔的确定发车间隔确定的基本公式：p_Qi_QiiE*CNTOC\o"1-5"\h\zl l符号说明：P为i时段内配车数、E为i时段内期望满载率、i iC为车容量、N为i时段内校车的期望占用量、Q为i时段内i i的最高断面通过量下面我们以早上7:00—8:00这个高峰期以菁园为例来求的发车间隔，据统计菁园大概住有5500人，我们根据对自己身边的人进行抽样统计发现每10个人有8个人有自行车，也就是说菁园有1100人没有自行车。假设这1100人中有一半人在这个时段内出行，那么设个时段的出行人数为550人。假设这550人中有一半出行坐校车，则坐校车人数为275人，将这些人平分到两条线路中，即每条线在。这段时间内的最高断面通过量为137.5，即：Q—137.5。由于这段时间内出行i高峰期，则假设在7:00—8:00这一时段内N—11。由以上公式得:ip—Q—1375—12.5辆/小时iN11i则该时段内的发车间隔H-—4.8min〜5min012.5以上求得高峰时段的发车间隔为5min，对于非高峰时段我们可以适当增加发车间隔，定义非高峰时段发车间隔为8min。问题二：策划论证—项目的必要性我校新校区占地3500余亩，较大的校区面积致使广大师生出行不便，学校购置了电瓶车在校内运行，学校为此付出了巨大的成本。但是学生仍深感不便，尤其是在上下课高峰时人流量大路途远时间有限学生出行很不方便。为缓解学生保证校车的利益我们必须合理的设置交通路线站点校车的运行时长发车间隔等问题解决学生出行不便。二目标的可行性要解决学生出行不便保证校车的利益，设置交通路线站点校车的运行时长发车间隔必须找这些问题的限制因素解决这些因素。我们可以统计分析学生的出行规律、现有的交通等分析。对于交通路线设置通过统计学生出行规律找出哪些地方的人流量大，和两地点间的最短路建立模型。站点设置从统计的人流量和地理位置见找关系。运行时长可问卷调查校车司机平均运行速度每站停留时间综合设计出的路线求解。时间间隔：调查校车数根据统计的学生出行规律分别求出高峰期和平常时间，在方便出行保证校车利益找时间T的函数关系。通过调查统计找函数关系我们可以解决目标。三对限制因素进行分析1、路线选择：限制因素有人流量和最短路人流量和最短路线是无关联的。选择最优路线既要保证路线过人流量大的地方方便学生出行，又要保障校车的利益走最短的路线。两者的比重系数人流量大于最短路，我们用Dijkstra算法求的这些地点间的最短路径并画出最短路径图，然后统计出人流量大的10个地点。由于这10个地点比较分散我们设置了两条路线，规定每条路线的地点大于3。

定义一个非最短比例系数K(1<K>2)K最小过的地点最多的最优解为最优路线。2、站点选择：限制因素有人流量地理位置，人流量大设站点方便学生地理位置又与道路的宽度对交通的影响等有关，我们用层次分析法用人流量大的10个地点作为方案层，评价10个地点可做站点的权重。3运行时长：我们询问校车司机平均运行速度大概是20km/h，每个站点的停留时间1min。运用公式运行时长=线路长度平均速度运行时长=线路长度平均速度*60+线路站点数*每个站点数停车间隔，求出两条路线的运行时长。4校车停留间隔：通过统计分析我们分了高峰期和正常时段，确定每时段路线上的断面通过量Q，计算出该时段小车的期望占有量N。我们定义单i i位时间的配车数p，利用公式P二QN求出p。发车间隔H二60P。i ill i i四对潜在问题的分析1由于我们选择的路线经过一些人流量大的路考虑到人流量多对车速的影响。在校车做满的情况下我们可以允许校车更改路线避开交通拥堵。2、在人流量的情况下一辆校车乘载不完，我们可以两量车同时出发。五对于其结果进行综合评价线路我们选择了2条每条线路过了4个站点，路线一总长1.9公里路线二总长2.5公里最短路线总长1.5公里线路一运行时长7.7min人步行要30min线路二运行时长9.5min人步行要40min。综合以上数据对线路问题我们做优化，能缓解学生出行问题。六模型优化与评价针对校车站点的选择我们采用了综合分析法对菁园、工科楼、公教、二号餐厅、篮球场、图书馆、文科楼、嘉园、一号餐厅、足球场、校大门根据载客量、学生对校车的需求、地理位置三个准则对这十个地点进行分析决策确定出合理的校车站点。对校车站点给出了合理的选择，比较有合理可行性。但模型的缺点是权重对于影响因素的权重值运用综合评价的方法对其赋权定义由人为评定的，建立层次结构图到给出两两比较矩阵，人的主观因素作用很大，使决策结果较大程度地依赖于决策人的主观意志，可能难以为众人所接受导致权值的赋予偏于主观性这一不足之处针对最优线路的选择我们通过Dijkstra算法求的这些地点间的最短路径并画出最短路径图。最后以确立的站点和一些道路的实际情况为一定依据并结合最短路径图取得路程相对最短但收益相对较大的合理路线。这比单纯用Dijkstra算法求校车线路有很大可行性。针对校车运行时间和发车间隔我们运用一些数学公式给出了计算结果，结果也相对合理。但在此计算中我们的数据具有一定的不准确性导致结果的真实性。在时间允许的情况下，如果能运用调查统计的方法给出数据那么我们的模型将更有说服力、准确性。七参考文献姜启源，数学模型(第二版)，北京：高等教育出版社，1992刘承平，数学建模方法，北京：高等教育出版社，2002.7百度地图，/,2013.8.21张智星，MATLAB程序设计与应用，北京：清华大学出版社，2002.4金孟合、王慧，基于蚁群算法的公交路线走向模型及其求解，/p-531635002.html,2013.8.21孙芙灵，公交调度中发车间隔的确定方法的探讨，/view/dee47b9851e79b8968022691.html,2013.8.23八附录附录1层次分析法MATLAB程序disp('请输入判断矩阵A(n阶)');A=input('A二')；[n,n]二size(A);x=ones(n,100);y=ones(n,100);m=zeros(1,100);m(1)=max(x(:,1));y(:,l)=x(:,l);x(:,2)=A*y(:,1);m(2)=max(x(:,2));y(:,2)=x(:,2)/m⑵;p=0.0001;i=2;k=abs(m(2)-m(1));whilek>pi=i+1;x(:,i)=A*y(:,iT);m(i)=max(x(:,i));y(:,i)=