第34卷第2期 2011年12月
上海船舶运输科学研究所学报
JOURNAL OF SHANGHAI SHIP AND SHIPPING RESEARCH INSTITUTE
文章编号：1674-5949(2011)02-0168-04
典型高速公路路网的清分路径算法
徐青松，王力鹏，陈健华
（中海网络科技股份有限公司，上海200135）
Vol, 34 No, 2 Dec.2011
摘要：清分路径信息是高速公路联网收费清分的关键参数，传统清分计算采用预先计算设定最短路径的数据表，但清分计算的效率随着路网规模的扩大和车流量的增长而不断降低，为此，提出并实现了基于图论、结合路网结构优化的快速算法。应用结果表明，日清分耗时降低为原来的1/3，有效提高了清分效率。该算法同样适用于相似路网结构的收费清分系统
关键词：清分算法；最短路径；Dijkstra算法；同源站
中图分类号：U412.3661
文献标志码：A
ASplittingRouteAlgorithminExpressWayTollingSystem
XUQingsong，WANGLipeng，CHENJianhua
(ChinaShippingNetworkTechnologyCo.,Ltd,Shanghai200135,China)
Abstract; Splitting route information is a key parameter for toll splitting calculation in express way joint tolling system. Con ventional splitting method uses predefined shortest path table, which grows as the road system extends and does not work ef-fectively for dense traffic. A splitting route algorithm based on graph theory and optimized model is presented to improve the efficiency of toll splitting. Practice has indicated that the time consumption of daily toll splitting with new algorithm is reduced by two third.
Key words: splitting algorithm; shortest path algorithm; Dijkstra algorithm;homologous station 0前言
十多年来，随高速公路建设的发展，国内大部分省、市、自治区的高速公路已陆续实现了联网收费、统一清分。由于路网中存在二义或多义性路径，通行费的计算大多采用最小费额法，即按路网中从人入口到出口所有可能的行驶路径中取最小费额的原则计算，通行费清分时则按照最短里程路径（简称最短路径)上的各业主路段进行分配。由此，清分路径是通行费清分结算的关键参数之一，与路段业主的收益密切相关。
传统应用软件使用的清分路径通过查找数据库中预先计算设定的清分路径数据表获得，能满足早期路网结构简单、最短路径几乎不变的应用需求。随着路网的延伸，每一条高速公路的开通都可能导致大批出人口间的最短路径发生变化，需要对清分路径数据表进行调整，给清分结算的管理带来很大压力，由此，产生了采用算法获取清分路径的需求。
典型高速公路路网的清分路径算法结合国内典型的重庆市高速公路联网收费系统路网现状和项目实
施，在路网结构分析的基础上，采用图论建模，并设计准确、高效的清分算法。 1
路网的数学建模 1.1路网的拓扑结构
收稿日期：2010-03-01
作者简介：徐青松（1978-），男，浙江省新昌县人，工程师，主要从事智能交通研究。万方数据