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

开篇：润墨网以专业的文秘视角，为您筛选了一篇最短路问题在城市路网中的应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：为减少城市交通拥堵，提高道路通行能力，以最短交通时间为目标，根据交通状况，以时间为权值赋与每段道路，运用最短路模型，计算出道路网中两点之间最有效的路线。最终总结路网信息，指导车辆的行驶路线，缓解道路的交通压力。借此思路为城市交通管理部门提供管理新手段，在城市交通管理中具有很现实的指导意义。

关键词: 运筹学； 最短路问题； 交通；通行能力

中图分类号：0221 文献标识码：A

The Application of Shortest Path Problem in urban road network

JIN Yan-qing1, WANG Fei1, LAN Yun-song1, YUE Guang-hua1

(1.Chang'an University Institute of Highway, Shanxi Xi’an 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 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 management sector, which has very realistic guiding significance in urban traffic management.

Key words: Operations Research; Shortest Path Problem; Traffic; Road capacity

0引言

随着我国城市经济的快速发展，机动车拥有量迅速增加，城市交通拥堵已经成为我国许多城市的严重问题，严重影响着城市功能的发挥和城市中人们的生活质量，所以缓解交通拥堵是保障和促进经济社会发展、改善民生的必然要求。

据统计，北京市每天上路新车达2000多辆。2014年2月，北京市机动车保有量将突破560万辆; 与此同时，北京市区干道平均车速比10年前降低50%，主要路口严重堵塞的达60%。随着经济的快速发展，中国城市的汽车保有量逐年增长，道路堵塞严重，交通系统优化管理迫在眉睫。笔者运用运筹学最短路原理解决交通运输管理系统的问题，具有非常重要的现实意义。

根据实时交通状况，赋予城市路网中每段线路以时间权值，利用最短路原理，计算出车辆运行时间最短的路线并汇总，通过新媒体及时向广大群众信息，指导广大群众选择行驶路线，进一步提高现有道路通行能力，提高道路服务水平，满足现代化高速发展的需求。

一 最短交通时间模型的建立

虽然路网的优化设计[1]在对城市交通系统管理的优化中具有重要作用，然而许薇，贾元华[2]通过博弈分析得出仅靠加大路网密度、扩展道路宽度等增加交通供给的手段将不能从根本上解决交通拥堵问题。邵祖峰[3]提出了治理交通堵塞四大原理: 交通总量削减原理、交通量均分原理、交通连续原理和交通分离原理。其中的交通量均分原理是要使交通流“均衡”、“分流”或“疏导”，设法使交通量的不均匀分布变为“均匀”分布。基于此原理，韩强认为如果现行路网不会使车辆从一处顺畅地开到另一处之后因路网承载能力有限而无法顺畅返回，那么这个路网在基础设施建设方面就应是均匀的，即在来回两个方向上的承载能力相当。笔者认为车辆从一处开往另一处之后能否顺利返回与承载能力有一定关系，但与返回时的交通量更有密切的关系。因此获得即时交通量，通过最短路原理进行交通量分流，是解决交通拥堵的根本措施。

基于以上分析我们需要找到一个目标函数来量化这个评价标准，笔者结合运筹学最短路问题以两目的地之间不同路线的最小运行时间作为目标函数。如图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的路中，求一条行驶时间最短的路，即求一条从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)不一定相等。

二 最短交通时间模型的计算

本算法是基于最短路问题在交通运输管理领域里的应用，由于wij≥0，所以目前公认最好的方法是由Dijkstra与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)=0, ʎ(vs)=0，对每一个v≠vs,令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方法求解模型中从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)+w12

同理，把T(v3)修改为P(v1)+w13=3，ʎ(v3)修改为1；把T(v4)修改为P(v1)+w14=1，ʎ(v4)修改为1。

转入③，在所有的T标号中T(v4)=1最小，于是令P(v4)=1，令S1=S0=，k=4。

（2）i=1

转入②，把T(v6)修改为P(v4)+w46=11，ʎ(v6)修改为4。

转入③，在所有T标号中，T(v3)=3最小，于是令P(v3)=3,令S2=，k=3。

（3）i=2

转入②，因A，v2S2，P(v3)+w32

转入③，在所有T标号中，T()=5最小，于是令P()=5，S3=，k=2。

（4）i=3

转入②，把T()修改为P(v2)+w25=6，ʎ(v5)修改为2。

转入③，在所有T标号中，T()=1最小，于是令P()=6，S4=，k=5。

（5）i=4

转入②，把T()，T()，T()分别修改为10,9,12，把ʎ(v6)，ʎ(v7)，ʎ(v8)修改为5.

转入③，在所有T标号中，T()=9最小，于是令P()=9，S5=，k=7。

（6）i=5

转入②，A，v8S5，但因P(v7)+w73>T(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()=+∞，算法终止。

算法终止时

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算法只适用于所有wij≥0的情形，当赋权有向图中存在负权时，则算法失效。而对于车辆行驶时间的现实问题上，也就不存在负权值的问题，因此，最短路问题的算法可以更好地应用于城市路网中。

三 结论

从到的最短链为（），即从到总的交通时间最短。此算例只是对所有交通网的一个简单示例，在对一个城市的所有路线的交通组合是一个庞大的系统，需要持续不断的获得即时交通量，并进行行车速度的统计及预估，最终根据统计结果，利用最短路原理找到每一段路线区间的最短交通时间，通过即时通信工具，这些信息，用来指导广大游客及司机朋友。

在当今城市交通日益拥挤的情况下，通过对现行路网进行科学的管理来使交通顺畅是城市管理中重要的一环。本文沿用最短路理论，在合理利用交通统计资料对每段路赋时间权值的基础上进一步讨论了最短交通时间问题，给出了其数学规划形式，其实质就是著名的最短路问题在交通运输领域里的一个实践应用。通过用户对交通信息的实时把握，对交通路线的正确选择，这对提高道路通行能力，节约能源，环境保护，提高路网通行能力有着重要的意义。尤其是在交通拥堵的当下，最短路问题在城市路网中的应用有着重要的意义。

参考文献：

［1］ 张江华，陈克东，韩强． 一种新的交通网络设计优化算法［J］． 运筹与管理， 2007.

［2］ 许薇，贾元华． 城市道路交通拥堵问题的博弈分析［J］． 交通科技， 2006．

［3］ 邵祖峰． 城市道路交通堵塞治理研究［J］． 城市交通， 2005．