一种基于 Google Earth 的新型动态路径诱导算法及其实现.pdf

一种基于 Google Earth 的新型动态路径诱导算法及其实现
A Google Earth-Based Dynamic Route Guidance Algorithm and
Its Application

参赛选手
王顺智,高逸涵
辅导教师
胡坚明,徐文兵
学校
清华大学附属中学

摘要:随着城市中私家车数目日益增多、交通拥堵现象日益严重,更合理地利用现有路网资源、
提高道路运输效率是当今学术界的一个研究热点。针对这一问题,本研究以北京的环路交通体系
为模型,提出了一种新的动态路径诱导算法,为出行者提供人性化的“最优路径”。算法以路网
(ρ-ρ0)
的图论模型为平台,提出顺畅度函数σ=Vf/[k×(t+m )]为道路动态赋权,并通过经典Dijkstra
算法实时计算最优路径。同时,研究基于环路交通城市的特殊性,提高了环路节点在Dijkstra算
法中的计算优先度,算法时间复杂性约为传统Dijkstra算法的 1/(16k2)(k为路网中的环路数),并
且控制中、长距离路径诱导时额外里程小于 5%,有效提升了算法在大型环路路网中的实用性。
此外,基于北京实际路网和Google Earth的地理信息平台,本研究以C语言实现了算法程序的测试
和演示,设计了人性化、易于操作的车载人机界面。
关键词:动态路径诱导,人性化择路,环路优先算法,Dijkstra 算法

Abstract: Since the traffic jams e more and more serious in modern society due to the sharp
increasing of private cars, how to improve the transportation efficiency and utilize the current road
network more effectively has e a crucial issue. In this paper, the authors designed a new dynamic
route guidance algorithm in order to provide travelers humanized “optimal route” and alleviate the loss
caused by traffic jams. The study built a graph theory model for Beijing’s ring road transportation
(ρ-ρ0)
system, with proposed evaluation function σ=Vf/[k×(t+m )] describing the real plex
traffic flow, and realizing the route searching by timed putation of classic Dijkstra algorithm.
Meanwhile, the study investigates the special feature of ring roads, improves the priority of ring road
nodes during the searching process. Comparing with Dijkstra algorithm, the plexity of this
new algorithm decreases to 1/16k2 (k equals to the amount of ring road in the work), at the
costs of extra miles less than 5% of the total distance, which match large scale ring-works. The
study piles the algorithm into a testing program with C language, connecting to Google Earth’s
map database, and designed an easy-operate Human-Machine Interface. (The operation of the
algorithm program performs in the appended video)
Keywords: Dynamic route guidance, huma