高速公路联网收费多义性路径问题及解决方案研究
|
摘要
多义性路径问题是联网收费区域路网内由于环状路网结构,存在两条或多条可选择的行驶路径,若无法唯一确定行驶路径,则不能精确进行通行费征收和拆分、结算。解决高速公路多义性问题总体分为精确识别法和概率分配法两种。精确识别法是对车辆行驶路径精确标识,获得车辆行驶的准确路径,具有精确度高及可信度高等特点,但是设施设备建设及后期运营维护费用投入大,实施的难度大,而且影响道路通行效率。概率分配法,在精确度方面不如精确识别法,但它的准确度能够基本满足业主的需求,具有投资及运营成本小,不影响车辆通行效率等特点。
交通分配法是解决多义性路径问题的有效方法之一。它以交通流分布理论为基础,通过确定车辆行驶路径选择的概率,确定通行费的收取和拆分结算。Bechmann提出的交通分配模型,是一种满足Wardrop均衡原理的数学优化模型,Frank-wolf算法是经典的求解交通分配问题算法,后续应用于解决多义性路径问题的交通分配法包括最短路径法、基于路段及基于路径等方法。
随着广东省高速公路的发展和联网收费工作的推进,高速公路路网范围和密度增大,现行的标识站精确标识路径在复杂路网环境下将难以继续实施,需要更为合理和准确的方法来解决这一问题。本文拟在分析交通分配用户均衡模型、非均衡模型及其求解算法的基础上,构建适用于高速公路路网特征和交通流特征的实用模型,并运用Frank-wolf算法、基于起点算法以及Logit模型算法,求解高速公路多义性路径分配的问题,通过不同算法模型求解相应的路径交通量及路径流量比,对实际数据及各种算法的计算结果进行比较分析,检验基于起点算法相关特性,评价该模型实际运用于高速公路多义性问题的可行性,研究基于起点分配法对通行费进行拆分的意义,并将提出运用该交通分配模型解决联网收费多义性路径问题的技术路线。本研究不仅检验基于交通分配模型解决联网收费多义性路径问题的可行性,还对进一步完善基于路径交通量求解算法,具有较为重要的理论和实际意义。
The path ambiguity problem is due to the union-toll regional road network within the ring ruonaidq uneeltyw doertke rsmtruincetudr,teh, et htoerlle caorell etwctoio onr ,m spolriet aalntder sneatttilveem teranvt ecla pna ntho.t bIfe tahcec turraavteell yp awtho riks sn.Iont general there are two ways to solving Highway ambiguity problem, the accurate identification method and the probability distribution method. Accurate identification method is to accurately identify the vehicle path, can get the exact path of vehicles, so precise identification with high accuracy and high reliability features, However, the need for accurate identification method identifies infrastructure operation and maintenance of pre-and post-investment requires a lot of capital investment, and the stop sign reducing road capacity. Probability distribution method, although the accuracy is less than accurate identification method, but it also has a certain accuracy and Can meet the basically requirements of the corresponding owners, And has a small initial investment and post-investment operation and maintenance of small, no parking is conducive to high-speed passage of vehicles and so on.
Traffic assignment method to solve the problem of ambiguous path Interconnection charges the effective probability distribution methods. It based on the distribution theory of traffic flow, by determining the ambiguous path chosen a path of vehicles to determine the probability that the rate of the vehicle and split the fees generated by the vehicle tolls, with a small investment, does not affect road capacity and so on. On the traffic assignment model first proposed initially by Bechmann , Satisfy the principle of Wardrop equilibrium is a mathematical optimization model, the distribution of follow-up most of the subsequent models are based on the model be extended, Frank-wolf algorithm which is used to solve the traffic problems are most common algorithm, based on this study, follow-up research and application of research to solve the interconnection charges more ambiguous path traffic assignment problem of law and the law, including the shortest path based on link and path-based and other methods.
With the expressway development and promotion of toll collection network in Guangdong Province, expressway network range and density, it would be difficult to implement using accurate identification method in a complex network environment,it need to find a more reasonable and accurate way to solve this problem. The project intends to user equilibrium and non-equilibrium in traffic assignment model and solution algorithm based on network construction for highway traffic flow characteristics and features of the utility model, and the use the Frank-wolf algorithm, Origin-Based Traffic assignment algorithm and Logit assignment algorithm, to solve ambiguity highway path allocation problem by solving the corresponding path algorithm model and the path of traffic flow ratio, the Origin-Based Traffic assignment algorithm on actual data and comparative analysis of the algorithm model, the starting point algorithm based on correlation test, and evaluate the model using more than the actual meaning of the highway feasibility issues, and research point allocation method based on the split of the significance of the toll, in addition, the project will make use of this method to resolve ambiguous path interconnection charges the technical route. Research projects can not only test the Feasibility of Origin-Based traffic assignment model to resolve the ambiguity interconnection charges problem, but also can improve the awareness of Origin-Based Traffic assignment algorithm, is of great theoretical and practical significance.
交通分配法是解决多义性路径问题的有效方法之一。它以交通流分布理论为基础,通过确定车辆行驶路径选择的概率,确定通行费的收取和拆分结算。Bechmann提出的交通分配模型,是一种满足Wardrop均衡原理的数学优化模型,Frank-wolf算法是经典的求解交通分配问题算法,后续应用于解决多义性路径问题的交通分配法包括最短路径法、基于路段及基于路径等方法。
随着广东省高速公路的发展和联网收费工作的推进,高速公路路网范围和密度增大,现行的标识站精确标识路径在复杂路网环境下将难以继续实施,需要更为合理和准确的方法来解决这一问题。本文拟在分析交通分配用户均衡模型、非均衡模型及其求解算法的基础上,构建适用于高速公路路网特征和交通流特征的实用模型,并运用Frank-wolf算法、基于起点算法以及Logit模型算法,求解高速公路多义性路径分配的问题,通过不同算法模型求解相应的路径交通量及路径流量比,对实际数据及各种算法的计算结果进行比较分析,检验基于起点算法相关特性,评价该模型实际运用于高速公路多义性问题的可行性,研究基于起点分配法对通行费进行拆分的意义,并将提出运用该交通分配模型解决联网收费多义性路径问题的技术路线。本研究不仅检验基于交通分配模型解决联网收费多义性路径问题的可行性,还对进一步完善基于路径交通量求解算法,具有较为重要的理论和实际意义。
The path ambiguity problem is due to the union-toll regional road network within the ring ruonaidq uneeltyw doertke rsmtruincetudr,teh, et htoerlle caorell etwctoio onr ,m spolriet aalntder sneatttilveem teranvt ecla pna ntho.t bIfe tahcec turraavteell yp awtho riks sn.Iont general there are two ways to solving Highway ambiguity problem, the accurate identification method and the probability distribution method. Accurate identification method is to accurately identify the vehicle path, can get the exact path of vehicles, so precise identification with high accuracy and high reliability features, However, the need for accurate identification method identifies infrastructure operation and maintenance of pre-and post-investment requires a lot of capital investment, and the stop sign reducing road capacity. Probability distribution method, although the accuracy is less than accurate identification method, but it also has a certain accuracy and Can meet the basically requirements of the corresponding owners, And has a small initial investment and post-investment operation and maintenance of small, no parking is conducive to high-speed passage of vehicles and so on.
Traffic assignment method to solve the problem of ambiguous path Interconnection charges the effective probability distribution methods. It based on the distribution theory of traffic flow, by determining the ambiguous path chosen a path of vehicles to determine the probability that the rate of the vehicle and split the fees generated by the vehicle tolls, with a small investment, does not affect road capacity and so on. On the traffic assignment model first proposed initially by Bechmann , Satisfy the principle of Wardrop equilibrium is a mathematical optimization model, the distribution of follow-up most of the subsequent models are based on the model be extended, Frank-wolf algorithm which is used to solve the traffic problems are most common algorithm, based on this study, follow-up research and application of research to solve the interconnection charges more ambiguous path traffic assignment problem of law and the law, including the shortest path based on link and path-based and other methods.
With the expressway development and promotion of toll collection network in Guangdong Province, expressway network range and density, it would be difficult to implement using accurate identification method in a complex network environment,it need to find a more reasonable and accurate way to solve this problem. The project intends to user equilibrium and non-equilibrium in traffic assignment model and solution algorithm based on network construction for highway traffic flow characteristics and features of the utility model, and the use the Frank-wolf algorithm, Origin-Based Traffic assignment algorithm and Logit assignment algorithm, to solve ambiguity highway path allocation problem by solving the corresponding path algorithm model and the path of traffic flow ratio, the Origin-Based Traffic assignment algorithm on actual data and comparative analysis of the algorithm model, the starting point algorithm based on correlation test, and evaluate the model using more than the actual meaning of the highway feasibility issues, and research point allocation method based on the split of the significance of the toll, in addition, the project will make use of this method to resolve ambiguous path interconnection charges the technical route. Research projects can not only test the Feasibility of Origin-Based traffic assignment model to resolve the ambiguity interconnection charges problem, but also can improve the awareness of Origin-Based Traffic assignment algorithm, is of great theoretical and practical significance.
引文
[1]广东联合电子收费股份有限公司.广东省高速公路联网收费路径识别技术比选研究报告[R].广州,广东联合电子收费股份有限公司,2010
[2]王占宇,关强.高速公路收费站区空气污染特征分析与数值模拟[J].公路交通科技,2009,26(4):154-158
[3]倪艳明.高速公路收费站车辆能耗[J].研究科技广场,2010,138-140
[4]张昊.基于RFID的浙江省高速公路联网收费多义性路径识别研究[D].长春.吉林大学,2009.6
[5]陈旻瑞.基于车牌识别法的高速公路联网收费路径识别技术的研究[D].南昌.华东交通大学,2010.4
[6]耿驰远,左建勋.关于高速公路多义性路径精确识别的思考[J].天津.中国交通信息产业,2009,03:29-38
[7]张健.高速公路联网收费多路径判断技术方法研究[D].西安.长安大学,2008.4
[8]赵克程.高速公路路径识别问题研究[D].西安.长安大学,2005.4
[9]刘海涛.公路联网收费的缴费方式选择与路径识别模型研究[D].武汉.华中科技大学2005.11
[10]郝国昌.高速公路区域联网收费系统的研究[D].西安.长安大学,2002
[11] Wardrop J G.Some theoretical aspects of road traffic research[J].Proceedings of the Institute of Civil Engineers,PartⅡ,1952,325-378
[12] Beckmann M,Mcguire C B, Winster C B.Studies in the Economics of Transportation [M ]. NewHeaven (CT):Yale University Press, 1956
[13]王炜,陈学武.交通规划[M].北京:人民交通出版社,2007:85-96
[14] Leblanc L J, Morlok E K, Pierskalla W.An Efficient Approach to Solving the Road Network Equi-librium Traffic Assignment Problem[J].Transportation Research,1975,9: 309-318
[15]陈森发,周晶,朱玉全.城市交通均衡流分配的多模式模型及算法[J].南京.自动化学报,1993,3:190-196
[16]安梅,高自友.求解交通均衡配流问题的新算法[J].北京.系统科学与数学,2000,7:367-375
[17]徐猛,屈云超,高自友.Frank-Wolfe算法求解交通分配问题:比较不同流量更新策略和线搜索技术[J].交通运输系统工程与信息,2008,8(3):14-22
[18] Larsson T,Patriksson M.Simplicial decomposition with disaggregated representation for the traffic assignment problem.Transportation Science,1992,26(1):4-17
[19] Bertsekas D.On the Goldstein-Levitin-Polyak gradient projectciton method.IEEE Transation on Automatic Control,1976,21(2):174-183
[20] Jayakrishnan R,Tsai W K,Prashker J N.Faster path-based algorithm for traffic assignment.Transporttation Research Record,1994,1443(1):75-83
[21] Lee D H,Yu N,Chen A.A conjugate gradient projection algorithm for the traffic assignment problem.Mathematical and Computer Modeling,2003,37(7/8):863-878
[22]李峰,王书宁.基于Frank-Wolfe算法的路径交通量求解方法[J].吉林大学学报(工学版),2005,35(6):632-636
[23]李曙光,巨永峰,姬建岗.路径流量估计方法在高速公路收费分配中的应用[J].西安.北京工业大学学报,2009,35(8):1027-1032
[24]陈洪星,孙洋.改进的布瑞尔交通分配模型在高速公路路径识别问题中的应用[J].交通与运输,2008,37-40
[25]程琳,朱志坚,许项东,邱松林.交通分配起点算法的实证研究[J].应用基础与工程科学学报,2009,17(6):950-957
[26] Hillel Bar-Gera.Origin-Based Algorithm for the Traf?c Assignment Problem [J].Transportation Science,2002,36(4):398-417
[27]王建伟,付鑫,马暕.复杂路网条件下高速公路收费费率计算方法[J].中国公路学报,2010,23(1):105-110
[28]刘涛.高速公路联网收费系统中的多义性路径识别[J].机械管理开发,2009,24(5):154-155
[29]李俊峰.城市交通规划模型研究模型参数的标定[D].大连.大连理工大学2002,6
[30]吴先宇,袁振洲,李艳红,曹守华,用户平衡算法中目标函数值与迭代次数关系研究[J].交通与计算机,2007,25(6):8-12
[31]周刚,车卓君.静态多路径交通分配法在公路网规划中的应用[J].广东公路交通,1995,(2):30-34
[32]陈树伟,李光远,王杰.一种基于Dijkstra的实用多路径求解算法[J].煤炭技术,2011,30(1):41-43
[33]颜佑启,欧阳建湘.最短路-最大流交通分配法[J].中国公路学报,2005,18(4):91-95
[34]孟祥云.最短路径及其求法[J].唐山高等专科学校学报,2002,15(2):51-53
[35]郑远,李江,施丽娟,孙立军.车牌识别技术在多义性路径问题中的应用[J].交通与计算机,2007,25(3):121-127
[36]李兆庆.高速公路联网收费模型、算法和应用[D].山东.山东科技大学,2005.10
[37]赵芳.高速公路联网收费资金拆分模型研究[J].陕西国防工业职业技术学院学报,2005,(2):16-19
[38]张好智,高自友.交通配流问题路径解唯一性的探讨[J].交通运输系统工程与信息,2003,3(1):38-40
[39]李峰,王书宁.基于终点的路径交通量求解方法[J].清华人学学报(自然科学版)2006 46(1):149-152
[40]张欢,史峰.基于流量预测的高速公路收费员动态配置模型[J].交通运输系统工程与信息2009,9(5):72-76
[41]刘灿齐.现代交通规划学[M].北京.人民交通出版社,2001:150-165
[42] Hillel Bar-Gera.Primal Method for Determining the Most Likely Route Flows in Large Road Networks [J].Transportation Science,2006,40(3):269-286
[43] Yu Nie,H.M. Zhang, Der-Horng Lee.Models and algorithms for the traffic assignment problem with link capacity constraints[J].Transportation Research Part B,2004,38:285-312
[44] Yu (Marco) Nie.A class of bush-based algorithms for the traf?c assignment problem [J].Transportation Research Part B (2010) 44:73-89
[45] David Boyce,M.ASCE,Biljana Ralevic-Dekic,Hillel Bar-Gera.Convergence of Traf?c Assignments:How Much is Enough [J].Journal of Transportation Engnieering ? ASCE, 2004:49-55
[46] DB44/127-2003,广东省高速公路联网收费系统[S].广东:广东省质量技术监督局,2003
[2]王占宇,关强.高速公路收费站区空气污染特征分析与数值模拟[J].公路交通科技,2009,26(4):154-158
[3]倪艳明.高速公路收费站车辆能耗[J].研究科技广场,2010,138-140
[4]张昊.基于RFID的浙江省高速公路联网收费多义性路径识别研究[D].长春.吉林大学,2009.6
[5]陈旻瑞.基于车牌识别法的高速公路联网收费路径识别技术的研究[D].南昌.华东交通大学,2010.4
[6]耿驰远,左建勋.关于高速公路多义性路径精确识别的思考[J].天津.中国交通信息产业,2009,03:29-38
[7]张健.高速公路联网收费多路径判断技术方法研究[D].西安.长安大学,2008.4
[8]赵克程.高速公路路径识别问题研究[D].西安.长安大学,2005.4
[9]刘海涛.公路联网收费的缴费方式选择与路径识别模型研究[D].武汉.华中科技大学2005.11
[10]郝国昌.高速公路区域联网收费系统的研究[D].西安.长安大学,2002
[11] Wardrop J G.Some theoretical aspects of road traffic research[J].Proceedings of the Institute of Civil Engineers,PartⅡ,1952,325-378
[12] Beckmann M,Mcguire C B, Winster C B.Studies in the Economics of Transportation [M ]. NewHeaven (CT):Yale University Press, 1956
[13]王炜,陈学武.交通规划[M].北京:人民交通出版社,2007:85-96
[14] Leblanc L J, Morlok E K, Pierskalla W.An Efficient Approach to Solving the Road Network Equi-librium Traffic Assignment Problem[J].Transportation Research,1975,9: 309-318
[15]陈森发,周晶,朱玉全.城市交通均衡流分配的多模式模型及算法[J].南京.自动化学报,1993,3:190-196
[16]安梅,高自友.求解交通均衡配流问题的新算法[J].北京.系统科学与数学,2000,7:367-375
[17]徐猛,屈云超,高自友.Frank-Wolfe算法求解交通分配问题:比较不同流量更新策略和线搜索技术[J].交通运输系统工程与信息,2008,8(3):14-22
[18] Larsson T,Patriksson M.Simplicial decomposition with disaggregated representation for the traffic assignment problem.Transportation Science,1992,26(1):4-17
[19] Bertsekas D.On the Goldstein-Levitin-Polyak gradient projectciton method.IEEE Transation on Automatic Control,1976,21(2):174-183
[20] Jayakrishnan R,Tsai W K,Prashker J N.Faster path-based algorithm for traffic assignment.Transporttation Research Record,1994,1443(1):75-83
[21] Lee D H,Yu N,Chen A.A conjugate gradient projection algorithm for the traffic assignment problem.Mathematical and Computer Modeling,2003,37(7/8):863-878
[22]李峰,王书宁.基于Frank-Wolfe算法的路径交通量求解方法[J].吉林大学学报(工学版),2005,35(6):632-636
[23]李曙光,巨永峰,姬建岗.路径流量估计方法在高速公路收费分配中的应用[J].西安.北京工业大学学报,2009,35(8):1027-1032
[24]陈洪星,孙洋.改进的布瑞尔交通分配模型在高速公路路径识别问题中的应用[J].交通与运输,2008,37-40
[25]程琳,朱志坚,许项东,邱松林.交通分配起点算法的实证研究[J].应用基础与工程科学学报,2009,17(6):950-957
[26] Hillel Bar-Gera.Origin-Based Algorithm for the Traf?c Assignment Problem [J].Transportation Science,2002,36(4):398-417
[27]王建伟,付鑫,马暕.复杂路网条件下高速公路收费费率计算方法[J].中国公路学报,2010,23(1):105-110
[28]刘涛.高速公路联网收费系统中的多义性路径识别[J].机械管理开发,2009,24(5):154-155
[29]李俊峰.城市交通规划模型研究模型参数的标定[D].大连.大连理工大学2002,6
[30]吴先宇,袁振洲,李艳红,曹守华,用户平衡算法中目标函数值与迭代次数关系研究[J].交通与计算机,2007,25(6):8-12
[31]周刚,车卓君.静态多路径交通分配法在公路网规划中的应用[J].广东公路交通,1995,(2):30-34
[32]陈树伟,李光远,王杰.一种基于Dijkstra的实用多路径求解算法[J].煤炭技术,2011,30(1):41-43
[33]颜佑启,欧阳建湘.最短路-最大流交通分配法[J].中国公路学报,2005,18(4):91-95
[34]孟祥云.最短路径及其求法[J].唐山高等专科学校学报,2002,15(2):51-53
[35]郑远,李江,施丽娟,孙立军.车牌识别技术在多义性路径问题中的应用[J].交通与计算机,2007,25(3):121-127
[36]李兆庆.高速公路联网收费模型、算法和应用[D].山东.山东科技大学,2005.10
[37]赵芳.高速公路联网收费资金拆分模型研究[J].陕西国防工业职业技术学院学报,2005,(2):16-19
[38]张好智,高自友.交通配流问题路径解唯一性的探讨[J].交通运输系统工程与信息,2003,3(1):38-40
[39]李峰,王书宁.基于终点的路径交通量求解方法[J].清华人学学报(自然科学版)2006 46(1):149-152
[40]张欢,史峰.基于流量预测的高速公路收费员动态配置模型[J].交通运输系统工程与信息2009,9(5):72-76
[41]刘灿齐.现代交通规划学[M].北京.人民交通出版社,2001:150-165
[42] Hillel Bar-Gera.Primal Method for Determining the Most Likely Route Flows in Large Road Networks [J].Transportation Science,2006,40(3):269-286
[43] Yu Nie,H.M. Zhang, Der-Horng Lee.Models and algorithms for the traffic assignment problem with link capacity constraints[J].Transportation Research Part B,2004,38:285-312
[44] Yu (Marco) Nie.A class of bush-based algorithms for the traf?c assignment problem [J].Transportation Research Part B (2010) 44:73-89
[45] David Boyce,M.ASCE,Biljana Ralevic-Dekic,Hillel Bar-Gera.Convergence of Traf?c Assignments:How Much is Enough [J].Journal of Transportation Engnieering ? ASCE, 2004:49-55
[46] DB44/127-2003,广东省高速公路联网收费系统[S].广东:广东省质量技术监督局,2003