最短路问题在城市路网中应用

《最短路问题在城市路网中应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、最短路问题在城市路网中应用　　摘要：为减少城市交通拥堵，提高道路通行能力，以最短交通时间为目标，根据交通状况，以时间为权值赋与每段道路，运用最短路模型，计算出道路网中两点之间最有效的路线。最终总结路网信息，指导车辆的行驶路线，缓解道路的交通压力。借此思路为城市交通管理部门提供管理新手段，在城市交通管理中具有很现实的指导意义。关键词:运筹学；最短路问题；交通；通行能力中图分类号：0221文献标识码：ATheApplicationofShortestPathProbleminurbanroadnetwork

2、JINYan-qing1,WANGFei1,LANYun-song1,YUEGuang-hua1(1.Chang’anUniversityInstituteofHighway,ShanxiXi’an710064)Abstract：Inordertoreduceurbantrafficcongestionandimproveroadcapacity,thispaperusestheshortestpathmodeltocalculatethemostefficientroutebetweentwopoin

3、tsinroadnetwork.Thegoalistheshortesttraveltimethroughassigningtheroadtimetoeachweightdependingon8trafficconditions.Atlast,summinguptheroadnetworkinformation,whichcanguidethevehicledrivingroutetoeasetrafficpressureoftheroad.Takethisnewideatoprovidemanagem

4、enttoolsforurbantrafficmanagementsector,whichhasveryrealisticguidingsignificanceinurbantrafficmanagement.Keywords:OperationsResearch;ShortestPathProblem;Traffic;Roadcapacity0引言随着我国城市经济的快速发展，机动车拥有量迅速增加，城市交通拥堵已经成为我国许多城市的严重问题，严重影响着城市功能的发挥和城市中人们的生活质量，所以缓解交通拥

5、堵是保障和促进经济社会发展、改善民生的必然要求。据统计，北京市每天上路新车达2000多辆。2014年2月，北京市机动车保有量将突破560万辆;与此同时，北京市区干道平均车速比10年前降低50%，主要路口严重堵塞的达60%。随着经济的快速发展，中国城市的汽车保有量逐年增长，道路堵塞严重，交通系统优化管理迫在眉睫。笔者运用运筹学最短路原理解决交通运输管理系统的问题，具有非常重要的现实意义。8根据实时交通状况，赋予城市路网中每段线路以时间权值，利用最短路原理，计算出车辆运行时间最短的路线并汇总，通过新媒体及时

6、向广大群众发布信息，指导广大群众选择行驶路线，进一步提高现有道路通行能力，提高道路服务水平，满足现代化高速发展的需求。一最短交通时间模型的建立虽然路网的优化设计[1]在对城市交通系统管理的优化中具有重要作用，然而许薇，贾元华[2]通过博弈分析得出仅靠加大路网密度、扩展道路宽度等增加交通供给的手段将不能从根本上解决交通拥堵问题。邵祖峰[3]提出了治理交通堵塞四大原理:交通总量削减原理、交通量均分原理、交通连续原理和交通分离原理。其中的交通量均分原理是要使交通流“均衡”、“分流”或“疏导”，设法使交通量的不

7、均匀分布变为“均匀”分布。基于此原理，韩强认为如果现行路网不会使车辆从一处顺畅地开到另一处之后因路网承载能力有限而无法顺畅返回，那么这个路网在基础设施建设方面就应是均匀的，即在来回两个方向上的承载能力相当。笔者认为车辆从一处开往另一处之后能否顺利返回与承载能力有一定关系，但与返回时的交通量更有密切的关系。因此获得即时交通量，通过最短路原理进行交通量分流，是解决交通拥堵的根本措施。8基于以上分析我们需要找到一个目标函数来量化这个评价标准，笔者结合运筹学最短路问题以两目的地之间不同路线的最小运行时间作为目标

8、函数。如图1,所示的单行线交通网，每弧旁的数字表示通过这条单行线所要的时间。现在求从v1到v8最小行驶时间的路线。出于以上考虑，从这个分析中引出一般的“最短路问题”，给出一个赋时间权值有向图D=(V,A),对每一个弧a=(vi,vj)，图1相应地有权w(a)=wij，又给定D中的两个顶点vs，vt。设P是D中从vs到vt的一条路，定义路P的时间是P中所有弧的时间之和，记为w(P)。“最短路问题”就是要在所有从vs到vt的路中，求一条行驶时间