﻿ 改进的A*算法在定制公交路径规划中的应用 Application of Improved A* Algorithm in Customized Bus Path Planning

Computer Science and Application
Vol. 10  No. 01 ( 2020 ), Article ID: 33820 , 8 pages
10.12677/CSA.2020.101003

Application of Improved A* Algorithm in Customized Bus Path Planning

Yuekun Liu, Xiuyan Liu*

School of Information and Control Engineering, Qingdao University of Technology, Qingdao Shandong

Received: Dec. 12th, 2019; accepted: Dec. 30th, 2019; published: Jan. 6th, 2020

ABSTRACT

Path search is the core problem in intelligent transportation technology. Customized bus routes need to consider factors such as convenient travel, operating costs, and distance traveled. Traditional A* algorithms are generally used to solve the shortest path between two points. The algorithm has many problems such that the search time is long with low efficiency and the searched path is not necessarily the shortest. Therefore, this paper proposes a dynamic path planning measure based on the improved A* algorithm. The bus station is used as a point for customizing the bus, and the estimated number of passengers is combined with the valuation function. Not only is the cost factor considered, but also the intersection is taken as the nodes of the path plan pruning the path direction to improve the search efficiency. This paper conducts experiments on the improved A* algorithm and compares it with the traditional A* algorithm. The experimental results show that the improved A* algorithm reduces the number of route searches, improves the efficiency of route planning, and reduces the operating costs of bus companies for the purpose of dynamic and real-time path planning.

Keywords:Path Planning, Improved A* Algorithm, Customized Bus, Valuation Function

Copyright © 2020 by author(s) and Hans Publishers Inc.

1. 引言

2. 定制公交路径规划算法

2.1. 启发式搜索算法

2.2. A*算法

A*算法是一种典型的启发式搜索算法，建立在Dijkstra算法的基础之上，广泛应用于游戏地图、现实世界中，用来寻找两点之间的最短路径 [10]。A*算法是一种静态路网中求解最短路径最有效的直接搜索方法，A*算法能够高效地找到两点之间的最优路径。但在A*算法中，往往通过一个函数来计算每个节点的权值，而这个函数，则决定算法的搜索效率。

2.3. A*算法存在的问题

A*算法广泛应用于各种路径搜索问题，虽然A*算法优势比较明显，寻路过程中可以更智能地分析最优路径并减少搜索的冗余节点。但是，A*算法在路径规划应用中经常用来求解最短路径 [7] [10] [11]，而定制公交运行中既需要考虑距离、时间因素，又需要考虑乘客乘车便捷、运营公司的经济效益，所以求得最短路径不一定是最优的路径。

Figure 1. A* algorithm path planning

3. 改进的A*算法

3.1. 路网结构

Figure 2. Road Structure

3.2. 估价函数

1) 依次搜索n节点相邻节点，计算邻接点与n组成的向量和n与终点组成的向量的夹角，如果夹角大于90度，说明远离终点而去，则不进行搜索；

2) 对于符合条件的邻接点，计算邻接点到终点的欧几里得距离，得到h(n)。

1) 搜索n节点的有效邻接点，统计n与人员乘车终点向量和n与终点向量夹角；

2) 如果向量夹角小于45度，则统计该乘车人，否则不统计；

3) 统计各方向预计乘车人数x。

g(n) = g(v) + α*vn + (β/(1 + x))*vn

3.3. 改进后的A*算法

(1) open={},close={},path={}

(2) open←src,g(src)=0，f(src)

(3) while(open<>null){

(4) v=f_min(open) //取open表中最小f值的节点

(5) if(v==dst) break

(6) close←v，open→v

(9) if(angle( , )<=90){

(10) x=person( )//计算vm路段乘车人数

(11) g(m)= g(v)+vm+(1+x)*vm

(12) h(m)=dist( ) //m到dst的欧几里得距离

(13) f(m)=g(m)+h(m) //计算m点的f值

(14) if(m not in open and m not in close)

(15) set_father(m)←v

(16) open←m

(17) else

(18) if( m in open and g(m)

(19) g_old(m)=g(m)

(20) set_father(m)←v

(21) if( m in close and g(m)

(22) g_old(m)=g(m)

(23) set_father(m)←v

(24) open←m

(25) close→m }

(26) } //adjvex(v) 循环结束

(27) } //open<>null循环结束

(28) if(v==dst)

(29) path←v,m=v

(30) while((m<>src){

(31) m= get_father(m)

(32) path←m}

(33) print path

(34) else

(35)print搜索失败

4. 改进后的A*算法与传统A*算法的对比

Figure 3. Test example 1 road network structure model

Table 1. Test example 1 algorithm comparison table

Figure 4. Test example 2 road network structure model

Table 2. Test example 2 algorithm comparison table

Figure 5. Test example 3 road network structure model

Table 3. Test example 3 algorithm comparison table

5. 结束语

Application of Improved A* Algorithm in Customized Bus Path Planning[J]. 计算机科学与应用, 2020, 10(01): 21-28. https://doi.org/10.12677/CSA.2020.101003

1. 1. 郭嫚. 基于多点对多点开行模式的定制公交线路规划研究[D]: [硕士学位论文]. 成都: 西南交通大学, 2018.

2. 2. 胡郁葱, 陈栩, 罗嘉陵. 多起终点多车型混载的定制公交线路规划模型[J]. 广西师范大学学报(自然科学版), 2018, 36(4): 1-10.

3. 3. 王俊培. 大城市定制公交服务体系研究[D]: [硕士学位论文]. 西安: 长安大学, 2015.

4. 4. 马继辉, 王飞, 王娇, 等. 定制公交站点和线路规划研究[J]. 城市交通, 2017(2): 21-25.

5. 5. 陆乾杰, 陈志平, 张林佳, 等. 基于蚁群算法多起点多终点社区公交路径规划[J]. 杭州电子科技大学学报(自然科学版), 2016, 36(3): 84-88.

6. 6. Zhang, S.J. and Zhang, Y. (2018) A Hybrid Genetic and Ant Colony Algorithm for Finding the Shortest Path in Dynamic Traffic Networks. Automatic Control and Computer Sciences, 52, 67-76. https://doi.org/10.3103/S014641161801008X

7. 7. 李少伟, 曹成涛. 基于A*算法的复杂交通环境下出行者最优路径分析研究[J]. 软件工程, 2019, 22(6): 29-32.

8. 8. Huo, E.-Z., Miao, R. and Luan, S. (2019) Research on the Location Selection of Customized Shuttle Bus Stations Based on the MassData of Online Taxi-hailing Service. Abstract Proceedings of the 2019 World Transport Convention, Beijing, 2019, 33.

9. 9. Liu, K. and Liu, C. (2019) The Study of Customized Bus Site and Route Planning Based on Site Segmentation Clustering Algorithm. Abstract Proceedings of the 2019 World Transport Convention (Cross-Cutting), Beijing, 2019, 110.

10. 10. 冯来春, 梁华为, 杜明博, 等. 基于A*引导域的RRT智能车辆路径规划算法[J]. 计算机系统应用, 2017, 26(8): 127-133.

11. 11. 彭澎. 基于A*算法的路径规划算法研究[D]: [硕士学位论文]. 马鞍山: 安徽工业大学, 2017.