1、最短路问题在城市路网中的应用摘要：为减少城市交通拥堵，提高道路通行能力，以最短交通时间为目标，根据交通状况，以时间为权值赋与每段道路，运用最短路模型，计算出道路网中两点之间最有效的路线。最终总结路网信息，指导车辆的行驶路线，缓解道路的交通压力。借此思路为城市交通管理部门提供管理新手段，在城市交通管理中具有很现实的指导意义。 关键词: 运筹学； 最短路问题； 交通；通行能力 中图分类号：0221 文献标识码：A The Application of Shortest Path Problem in urban road network JIN Yan-qing1, WANG Fei1, LAN
2、Yun-song1, YUE Guang-hua1 (1.Changan University Institute of Highway, Shanxi Xian 710064) Abstract：In order to reduce urban traffic congestion and improve road capacity, this paper uses the shortest path model to calculate the most efficient route between two points in road network. The goal is the
3、shortest travel time through assigning the road time to each weight depending on traffic conditions. At last, summing up the road network information, which can guide the vehicle driving route to ease traffic pressure of the road. Take this new idea to provide management tools for urban traffic mana
4、gement sector, which has very realistic guiding significance in urban traffic management. Key words: Operations Research; Shortest Path Problem; Traffic; Road capacity 0 引言 随着我国城市经济的快速发展，机动车拥有量迅速增加，城市交通拥堵已经成为我国许多城市的严重问题，严重影响着城市功能的发挥和城市中人们的生活质量，所以缓解交通拥堵是保障和促进经济社会发展、改善民生的必然要求。 据统计，北京市每天上路新车达 2000 多辆。2
5、014 年 2 月，北京市机动车保有量将突破 560 万辆; 与此同时，北京市区干道平均车速比 10 年前降低 50%，主要路口严重堵塞的达 60%。随着经济的快速发展，中国城市的汽车保有量逐年增长，道路堵塞严重，交通系统优化管理迫在眉睫。笔者运用运筹学最短路原理解决交通运输管理系统的问题，具有非常重要的现实意义。 根据实时交通状况，赋予城市路网中每段线路以时间权值，利用最短路原理，计算出车辆运行时间最短的路线并汇总，通过新媒体及时向广大群众发布信息，指导广大群众选择行驶路线，进一步提高现有道路通行能力，提高道路服务水平，满足现代化高速发展的需求。 一 最短交通时间模型的建立 虽然路网的优化设
6、计1在对城市交通系统管理的优化中具有重要作用，然而许薇，贾元华2通过博弈分析得出仅靠加大路网密度、扩展道路宽度等增加交通供给的手段将不能从根本上解决交通拥堵问题。邵祖峰3提出了治理交通堵塞四大原理: 交通总量削减原理、交通量均分原理、交通连续原理和交通分离原理。其中的交通量均分原理是要使交通流“均衡” 、 “分流”或“疏导” ，设法使交通量的不均匀分布变为“均匀”分布。基于此原理，韩强认为如果现行路网不会使车辆从一处顺畅地开到另一处之后因路网承载能力有限而无法顺畅返回，那么这个路网在基础设施建设方面就应是均匀的，即在来回两个方向上的承载能力相当。笔者认为车辆从一处开往另一处之后能否顺利返回与承
7、载能力有一定关系，但与返回时的交通量更有密切的关系。因此获得即时交通量，通过最短路原理进行交通量分流，是解决交通拥堵的根本措施。 基于以上分析我们需要找到一个目标函数来量化这个评价标准，笔者结合运筹学最短路问题以两目的地之间不同路线的最小运行时间作为目标函数。如图 1,所示的单行线交通网，每弧旁的数字表示通过这条单行线所要的时间。现在求从 v1 到 v8 最小行驶时间的路线。 出于以上考虑，从这个分析中引出一般的“最短路问题” ，给出一个赋时间权值有向图 D=(V,A),对每一个弧 a=(vi,vj)， 图 1 相应地有权 w(a)=wij，又给定 D 中的两个顶点 vs，vt。设 P是 D
8、中从 vs 到 vt 的一条路，定义路 P 的时间是 P 中所有弧的时间之和，记为 w(P)。 “最短路问题”就是要在所有从 vs 到 vt 的路中，求一条行驶时间最短的路，即求一条从 vs 到 vt 的路 P0，使 w(P)=min(P) 式中对 D 中所有从 vs 到 vt 的路 P 取最小，称 P0 是从 vs 到 vt 的“最短路” 。路 P0 的时间称为从 vs 到 vt 的时间，记为 d(vs,vt)。显然，d(vs,vt)与 d(vt,vs)不一定相等。 二 最短交通时间模型的计算 本算法是基于最短路问题在交通运输管理领域里的应用，由于wij0，所以目前公认最好的方法是由 Dij
9、kstra 与 1959 年提出来的。 Dijkstra.方法的基本思路是从 vs 出发，逐步的向外探寻最短路。执行过程中，与每个点对应，记录下一个数（称为这个点的标号） ，它或者表示从 vs 到该点的最短路的权（称为 P 标号） ，或者是从 vs 到该点的最短路的权的上界（称为 T 标号） ，方法的每一步是去修改 T 标号，并且把某一个具 T 标号的点改变为具 P 标号的点，从而使 D 中具 P 标号的顶点数多一个，这样，至多经过 p-1 步，就可以求出 vs 到各点的最短路。 Dijkstra 方法的具体步骤：给定赋时间有向图 D=(V,A)。 开始（i=0）令 s0=（vs）,P(vs)
10、=0, (vs)=0，对每一个vvs,令 T(v)=+，(v)=M，令 k=s。 如果 si=v，算法终止，这时，对每一个 v，d(vs,v)=P(v)：否则转入。 考察每个使(vk,vj)且 vjsi 的点 vj。 如果 T(vj)P(vk)+wkj，则把 T(vj)修改为 P(vk)+wkj，把(vj)修改为 k；否则转入。 令 T(vj)=。 如果 T()+，则把 T 标号变为 P 标号 P()= T()，令Si+1=Si，k=ji，把 i 换成 i+1，转入；否则终止，这时对每一个vSi，d(vs,v)=P(v)，而对每一个 vSi，d(vs,v)=T(v)。 现在用 Dijkstra
11、 方法求解模型中从 v1 到各个顶点的最短交通时间路线，这时 s=1。 （1）i=0 S0=，P(v1)=0，(v1)=0，T(vi)=+，(vi)=M(i=2,3,4,9)，以及 k=1。 转入，因（v1,v2）A，v2S0，P(v1)+w12T(v8)，故 T(v8)不变。 转入，在所有 T 标号中，T()=10 最小，令 P()=10，S6=，k=,6。 （7）i=6 转入，从出发没有弧指向不属于 S6 的点，故直接转入。 转入，在所有 T 标号中，T()=11 最小，于是令 P()=12，S7=，k=8。 （8）i=7 转入，这时仅有的 T 标号点为，T()=+，算法终止。 算法终止时
12、 P()=0，P()=1，P()=3，P()=5，P()=6， P()=9，P()=10，P()=11，P()=8。 ()=0，()=1，()=1，()=3，()=1， ()=5，()=5，()=5，()=5。 这样从到的最短链为（） ，总权为 11。 Dijkstra 算法只适用于所有 wij0 的情形，当赋权有向图中存在负权时，则算法失效。而对于车辆行驶时间的现实问题上，也就不存在负权值的问题，因此，最短路问题的算法可以更好地应用于城市路网中。 三 结论 从到的最短链为（） ，即从到总的交通时间最短。此算例只是对所有交通网的一个简单示例，在对一个城市的所有路线的交通组合是一个庞大的系统，需
13、要持续不断的获得即时交通量，并进行行车速度的统计及预估，最终根据统计结果，利用最短路原理找到每一段路线区间的最短交通时间，通过即时通信工具，发布这些信息，用来指导广大游客及司机朋友。 在当今城市交通日益拥挤的情况下，通过对现行路网进行科学的管理来使交通顺畅是城市管理中重要的一环。本文沿用最短路理论，在合理利用交通统计资料对每段路赋时间权值的基础上进一步讨论了最短交通时间问题，给出了其数学规划形式，其实质就是著名的最短路问题在交通运输领域里的一个实践应用。通过用户对交通信息的实时把握，对交通路线的正确选择，这对提高道路通行能力，节约能源，环境保护，提高路网通行能力有着重要的意义。尤其是在交通拥堵的当下，最短路问题在城市路网中的应用有着重要的意义。 参考文献： 1 张江华，陈克东，韩强 一种新的交通网络设计优化算法J 运筹与管理， 2007. 2 许薇，贾元华 城市道路交通拥堵问题的博弈分析J 交通科技， 2006 3 邵祖峰 城市道路交通堵塞治理研究J 城市交通， 2005
