贪心与回溯算法在城市马拉松路线规划中的实践

针对目前城市马拉松路线人工规划效率低下的问题, 本文采用贪心和回溯算法进行城市马拉松路线智能规划, 具体方法是: 通过城市路网信息构建由经纬度坐标点拓扑关系连接而成的路网, 采用贪心和回溯算法对坐标点进行遍历搜索, 结合城市马拉松路线特殊要求, 运用直接逼近、启发式远离、启发式靠近和方向预估等策略实现路线的智能规划. 在此基础上, 提出一种综合POI热度值、道路宽度适宜度、路线畅通指数、过弯舒适度以及POI密集度5个维度的马拉松路线评估方法. 最后, 开展了北京、合肥马拉松人工和智能规划路线对比分析, 结果表明所采用的方法可快速高效实现马拉松路线规划.

Practice of Greedy and Backtracking Algorithm in City Marathon Route Planning

Manual planning of city marathon routes has low efficiency. In view of this, this study adopts a greedy and backtracking algorithm to carry out intelligent planning of a city marathon route. The specific method is described as follows. A road network connected by the topological relationship of longitude and latitude coordinate points is built through the urban road network information, and a traversal search is performed by the greedy and backtracking algorithm on the coordinate points. In addition, according to the special requirements of the city marathon route, strategies are adopted, such as direct approximation, heuristic distance, heuristic approach, and direction estimation, so as to realize the intelligent planning of the route. On this basis, a marathon route evaluation method is proposed, which integrates five dimensions including POI heat value, road width suitability, route smoothness index, comfort for turning, and POI density. Finally, a comparative analysis of artificial and intelligent route planning for Beijing and Hefei marathons is carried out. The results show that the proposed method can realize fast and efficient marathon route planning.