基于改进A*算法的高速公路选线决策辅助模型

doi:10.3969/j.issn.1674-0696.2024.09.01

摘要/Abstract

摘要： 为提高山区高速公路选线的智能化水平，基于改进A*算法对高速公路选线决策辅助模型进行了分析。提出了高速公路选线的平面约束指标和纵断面约束指标；根据山区高速公路选线实际情况，从估价函数、搜索范围、搜索方向、数据结构、优化方法等方面对传统A*算法进行了改进，建立高速公路选线决策辅助模型；并通过实际案例验证了该模型的有效性。研究结果表明：与传统A*算法相比，改进A*算法在搜索时间、搜索次数、搜索节点数方面分别降低了约75%、48%、44%；路线优化后的总转折角度和长度分别降低了约83%和17%；高速公路选线决策辅助模型能有效地处理自然环境复杂条件下的选线问题，具有较高的实用价值。

关键词: 道路工程；高速公路选线决策辅助模型；改进A*算法；山区选线；选线约束指标

Abstract: In order to improve the intelligence level of route selection of mountainous highway, the analysis on highway route selection decision auxiliary model was conducted on the basis of the improved A* algorithm. Firstly, the plane constraint indexes and vertical cross-section constraint indexes for highway route selection were proposed. Then, according to the actual situation of mountainous highway route selection, the traditional A* algorithm was improved in terms of valuation function, search range, search direction, data structure, optimization methods, etc., and the highway route selection decision auxiliary model was established. Finally, the validity of the proposed model was confirmed through case study. Research results show that compared with the traditional A* algorithm, the improved A* algorithm reduces search time by about 75%, search iterations by about 48%, and the number of search nodes by about 44%. The total turning angle and length of the route after optimization are reduced by about 83% and 17%, respectively. The highway route selection decision auxiliary model is capable of effectively addressing the route selection problem in complex natural environmental conditions and possesses high practical value.

Key words: highway engineering; highway route selection decision auxiliary model; improved A* algorithm; mountain route selection; route selection constraint index

中图分类号:

U412.3

陈雨人，黎东丰，余博，高健强. 基于改进A*算法的高速公路选线决策辅助模型[J]. 重庆交通大学学报（自然科学版）, 2024, 43(9): 1-8.

CHEN Yuren, LI Dongfeng, YU Bo, GAO Jianqiang. Highway Route Selection Decision Auxiliary Model Based on Improved A* Algorithm[J]. Journal of Chongqing Jiaotong University(Natural Science), 2024, 43(9): 1-8.

参考文献

［1］许金良. 道路勘测设计［M］. 5版. 北京: 人民交通出版社, 2018.
XU Jinliang. Road Survey and Design［M］. 5th ed. Beijing: China Communications Press, 2018.
［2］李源. 生态脆弱地质复杂山区高速公路态势性选线方法［D］. 昆明: 昆明理工大学, 2023.
LI Yuan. Situational Route Selection Method of Expressway in Ecolo-gically Fragile and Geologically Complex Mountainous Areas［D］.Kun-ming: Kunming University of Science and Technology, 2023.
［3］郑洪, 谢浩, 姚洪锡, 等. 陆路交通基础设施智能化勘察设计研究综述［J］. 铁道工程学报, 2023, 40(8): 1-11.
ZHENG Hong, XIE Hao, YAO Hongxi, et al. Review on intelligent surveyand design of land transportation infrastructure［J］. Journal of Railway Engineering Society, 2023, 40(8): 1-11.
［4］ HOLLAND J H. Genetic algorithms［J］. Scientific American, 1992, 267(1): 66-72.
［5］ DORIGO M, DI CARO G, GAMBARDELLA L M. Ant algorithms for discrete optimization［J］. Artificial Life, 1999, 5(2): 137-172.
［6］ DIJKSTRA E W. A note on two problems in connexion with graphs［J］. Numerische Mathematik, 1959, 1(1): 269-271.
［7］ HART P E, NILSSON N J, RAPHAEL B. A formal basis for the heuri-stic determination of minimum cost paths［J］. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.
［8］朱雷鹏, 张贵阳, 张志清. 基于遗传算法的公路自动选线与安全评价方法［J］. 科学技术与工程, 2023, 23(29): 12672-12678.
ZHU Leipeng, ZHANG Guiyang, ZHANG Zhiqing. Automatic highway alignment selection and safety evaluation method based on genetic algorithm［J］. Science Technology and Engineering, 2023, 23(29): 12672-12678.
［9］ AL-HADAD B M, NADIR W H, ALI M J G. Intelligent optimization of highway alignments: A novel approach integrating geographic information system and genetic algorithms［J］. Engineering Applications of Artificial Intelligence, 2024, 133: 108037.
［10］曹祥红, 李欣妍, 魏晓鸽, 等. 基于Dijkstra-ACO混合算法的应急疏散路径动态规划［J］. 电子与信息学报, 2020, 42(6): 1502-1509.
CAO Xianghong, LI Xinyan, WEI Xiaoge, et al. Dynamic programming of emergency evacuation path based on Dijkstra-ACO hybrid algorithm［J］. Journal of Electronics & Information Technology, 2020, 42(6): 1502-1509.
［11］夏沁雪. 水电站进场道路智能选线算法及方案比选方法研究［D］. 武汉: 华中科技大学, 2022.
XIA Qinxue. Research on Intelligent Route Selection Algorithm and Scheme Comparison Method for Approach Road of Hydropower Station［D］.Wuhan: Huazhong University of Science and Technology, 2022.
［12］ PUSHAK Y, HARE W, LUCET Y. Multiple-path selection for new highway alignments using discrete algorithms［J］. European Journal of Operational Research, 2016, 248(2): 415-427.
［13］张今尧. 基于改进A*算法的车间物料配送路径规划研究［D］. 长春: 长春工业大学, 2022.
ZHANG Jinyao. Research on Workshop Material Distribution Path Plan-ning Based on Improved A* Algorithm［D］.Changchun: Changchun University of Technology, 2022.
［14］王月爽. 基于改进A*算法的山地风电场道路智能选线方法研究［D］. 石家庄: 石家庄铁道大学, 2021.
WANG Yueshuang. Intelligent Route Selection Method of Wind Farm Road in the Mountain Based on Improved A* Algorithm［D］.Shijia-zhuang: Shijiazhuang Tiedao University, 2021.
［15］代奇峰. 水电站道路成本指数模型及智能选线方法研究［D］. 武汉: 华中科技大学, 2022.
DAI Qifeng. Research on Road Cost Index Model and Intelligent Road Selection Method for Hydropower Station［D］.Wuhan: Huazhong University of Science and Technology, 2022.
［16］中华人民共和国交通运输部. 公路路线设计规范: JTG D20—2017［S］. 北京: 人民交通出版社, 2017.
Ministry of Transport of the Peooles Republic of China. Design Speci-fication for Highway Alignment: JTG D20—2017［S］. Beijing: China Communications Press, 2017.
［17］卫彦, 晋芳, 董凯锋, 等. 基于节点优化的改进全局路径规划A*算法［J］. 计算机测量与控制, 2023, 31(6): 143-148.
WEI Yan, JIN Fang, DONG Kaifeng, et al. Improved global path plan-ning A* algorithm based on node optimization［J］. Computer Measure-ment & Control, 2023, 31(6): 143-148.
［18］吴飞龙, 郭世永. 融合改进A*和动态窗口法的AGV动态路径规划［J］. 科学技术与工程, 2020, 20(30): 12452-12459.
WU Feilong, GUO Shiyong. Dynamic path planning of AGV based on fusion of improved A* and dynamic window approach［J］. Science Technology and Engineering, 2020, 20(30): 12452-12459.
［19］张航, 韦金君, 张肖磊. 道路平面线形拟合方法比较研究［J］. 武汉理工大学学报(交通科学与工程版), 2018, 42(4): 594-598.
ZHANG Hang, WEI Jinjun, ZHANG Xiaolei. Comparative study on road plane alignment fitting methods［J］. Journal of Wuhan University of Technology (Transportation Science & Engineering), 2018, 42(4): 594-598.
［20］张驰, 王茜茹, 向宇杰, 等. 基于平纵组合的山区高速公路连续下坡路段行车安全评价方法［J］. 重庆交通大学学报(自然科学版), 2024, 43(5): 78-90.
ZHANG Chi, WANG Xiru, XIANG Yujie, et al. Driving safety evalua-tion method for continuous downhill section of mountainous expressway based on longitudinal-transverse combination［J］. Journal of Chongqing Jiaotong University (Natural Science), 2024, 43(5): 78-90.

[1]	潘兵宏1，2，任卉2，单慧敏1，霍永富1. 客货分离整体式路基互通出口同分带开口长度研究[J]. 重庆交通大学学报（自然科学版）, 2021, 40(04): 83-90.
[2]	彭金栓，朱科，张应旗，邵毅明，徐磊. 山区高速爬坡路段重载车辆运行速度仿真分析[J]. 重庆交通大学学报（自然科学版）, 2020, 39(05): 123-129.
[3]	朱家松，陈思渊. 考虑交叉口上自行车冲突的改进社会力模型[J]. 重庆交通大学学报（自然科学版）, 2019, 38(12): 18-25.
[4]	杨少伟1,2，陈浩1，潘兵宏1,2，赖泓志1，赵亚茹1. 高速公路共用段最小长度研究[J]. 重庆交通大学学报（自然科学版）, 2019, 38(11): 111-117.
[5]	刘唐志1，白婧荣2，聂舒磊3，盛启锦2，刘飞1. 基于熵权物元的互通立交出口匝道安全评价研究[J]. 重庆交通大学学报（自然科学版）, 2019, 38(10): 95-101.
[6]	束海波1,2，邵毅明2. 高速公路上坡路段半挂汽车列车行驶速度特性试验研究[J]. 重庆交通大学学报（自然科学版）, 2019, 38(09): 128-132.
[7]	陈芳1，张浩月2，胡晓红1，刘煌1. 基于暴雨洪水管理模型的海绵型高速公路服务区低影响开发研究[J]. 重庆交通大学学报（自然科学版）, 2019, 38(07): 54-59.
[8]	陈柳晓1, 唐伯明1, 张勃2, 向浩1. “二十四道拐”盘山公路车辆行驶轨迹研究[J]. 重庆交通大学学报（自然科学版）, 2019, 38(04): 47-54.
[9]	胡川，邓明镜，赵立都. 非线性总体最小二乘反演道路圆曲线参数算法[J]. 重庆交通大学学报（自然科学版）, 2019, 38(03): 27-31.
[10]	潘兵宏1, 2，倪旭1，唐力焦1，赵亚茹1，余英杰1. B型喇叭式立交环圈出口匝道运行速度过渡段长度研究[J]. 重庆交通大学学报（自然科学版）, 2019, 38(03): 32-37.
[11]	陈柳晓1，张勃2，唐伯明1，向浩1，戴广雷1. “二十四道拐”盘山公路事故预测分析[J]. 重庆交通大学学报（自然科学版）, 2019, 38(03): 83-90.
[12]	乔建刚1，田亚磊1，陈罗刚1，戴长永2. 基于最大熵的城郊公路接入口间距研究[J]. 重庆交通大学学报（自然科学版）, 2018, 37(03): 88-91.
[13]	姬杨蓓蓓，周金凤. 基于成本分析的高速公路收费站车道配置研究[J]. 重庆交通大学学报（自然科学版）, 2018, 37(1): 85-91.
[14]	刘浪1，白彬2，燕南3，高建平3. 基于驾驶员视认性的山区双车道公路交叉口停车视距计算[J]. 重庆交通大学学报（自然科学版）, 2017, 36(5): 98-103.
[15]	顾欢达，李翠，薛国强. MSWI混合土在动力荷载作用下的变形特性试验研究[J]. 重庆交通大学学报（自然科学版）, 2016, 35(3): 38-42.