过必经点集且具有额外硬约束的最短路径算法

doi:10.3778/j.issn.1002-8331.2102-0338

摘要/Abstract

摘要： 求解过必经点集的最短路径问题已有多种算法，但其应用到在具有额外硬约束限定条件的场景时存在不足。针对此类问题，提出一种基于深度优先搜索发展的随机搜索算法，由使用者依据现场情况给出数学描述，建模抽象为无向带权图表示；依据路径规划要求定义相关变量，包括路径规划的起点、终点、必经点集以及额外硬约束条件，图信息和节点信息以邻接矩阵的形式保存；搜索过程中对路径的可行性加入额外硬约束条件进行实时判定，最终获得最短路径解。实验仿真和实测结果表明，该算法能有效规避额外硬约束条件下的中间路径，生成合理的最短路径，改善相关问题的可求解性。

关键词: 深度优先搜索, 随机搜索, 最短路径, 必经点集, 额外硬约束

Abstract: There have been many algorithms for solving the shortest path problems through necessary nodes set, but most of them are insufficient when applied to the circumstances with extra hard constraints. To solve this problem, this paper puts forward a random search algorithm based on depth first search mechanism. The mathematical models are provided by users according to actual situation, and they are abstracted as undirected weighted graphs. Some related variables such as the beginning node, the end node, necessary nodes and extra hard constraints are defined by path planning requirements, and they are saved as adjacency matrix. In the searching process, the feasibility of the path is determined in real time to meet the requirements of extra hard constraints. Finally, the optimal shortest path solution is obtained. Simulation and actual results show that the algorithm effectively avoids the influence of intermediate path under extra hard constraints and generate a shortest path, which means that this algorithm can greatly improve problem solvability.

Key words: depth-first search, random search, shortest path, passing necessary nodes, extra hard constraints

郭展羽, 张志明, 贺兰山, 郑家齐, 赵师兵, 康琦. 过必经点集且具有额外硬约束的最短路径算法[J]. 计算机工程与应用, 2022, 58(18): 297-303.

GUO Zhanyu, ZHANG Zhiming, HE Lanshan, ZHENG Jiaqi, ZHAO Shibing, KANG Qi. Shortest Path Algorithm Through Necessary Nodes with Extra Hard Constraints[J]. Computer Engineering and Applications, 2022, 58(18): 297-303.

参考文献

[1] BERTSEKAS D P.Robust shortest path planning and semicontractive dynamic programming[J].Naval Research Logistics，2016，66（1）：15-37.
[2] GUSFIELD D，LANDAU G M，SCHIEBER B.An efficient algorithm for the all pairs suffix-prefix problem[J].Information Processing Letters，1992，41（4）：181-185.
[3] RAJA P，PUGAZHENTHI S.Optimal path planning of mobile robots：a review[J].International Journal of Physical Sciences，2012，7（9）：1314-1320.
[4] 张波良，张瑞昌，关佶红.道路网上最短路径算法综述[J].计算机应用与软件，2014，31（10）：1-9.
ZHANG B L，ZHANG R C，GUAN J H.A survey on shortest path algorithms in road networks[J].Computer Applications and Software，2014，31（10）：1-9.
[5] MASOUDI N，FADEL G M，WIECEK M M.Planning the shortest path in cluttered environments：a review and a planar convex Hull-based approach[J].Journal of Computing and Information Science in Engineering，2019，19（4）：041011.
[6] KIM G，ONG Y，HENG C K，et al.City vehicle routing problem（City VRP）：a review[J].IEEE Transactions on Intelligent Transportation Systems，2015，16（4）：1654-1666.
[7] DIJKSTRA E W.A note on two problems in connexion with graphs[J].Numerische Mathematik，1959，1：269-271.
[8] HART P E，NILSSON N J，RAPHAEL B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions on Systems Science and Cybernetics，1968，4（2）：100-107.
[9] 康文雄，许耀钊.节点约束型最短路径的分层Dijkstra算法[J].华南理工大学学报（自然科学版），2017，45（1）：66-73.
KANG W X，XU Y Z.A hierarchical Dijkstra algorithm for solving shortest path from constrained nodes[J].Journal of South China University of Technology（Natural Science Edition），2017，45（1）：66-73.
[10] DANIELE F，PAOLA F，FRANCESCA G.An efficient exact approach for the constrained shortest path tour problem[J].Optimization Methods and Software，2020，35（1）：1-20.
[11] CHE G F，LIU L J，YU Z.An improved ant colony optimization algorithm based on particle swarm optimization algorithm for path planning of autonomous underwater vehicle[J].Journal of Ambient Intelligence and Humanized Computing，2020，11（8）：3349-3354.
[12] PATLE B K，PARHI D R K，JAGADEESH A，et al.Matrix-binary codes based genetic algorithm for path planning of mobile robot[J].Computers & Electrical Engineering，2018，67：708-728.
[13] 杨志勇，叶冯彬，冯艳辉，等.有向非负权图中经过必经节点集最短路径算法[J].电子设计工程，2017，25（16）：32-36.
YANG Z Y，YE F B，FENG Y H，et al.Algorithm for finding shortest path which contains a necessary set of nodes in directed and non-negative weighted graph[J].Electronic Design Engineering，2017，25（16）：32-36.
[14] 王磊，孙力帆.引入必经点约束的路径规划算法研究[J].计算机工程与应用，2020，56（21）：25-29.
WANG L，SUN L F.Research on path planning algorithm with obligatory node constraint[J].Computer Engineering and Applications，2020，56（21）：25-29.
[15] 李东，严义，王丹东，等.必经节点集约束型无环最短路径算法研究[J].杭州电子科技大学学报（自然科学版），2017，37（5）：44-50.
LI D，YAN Y，WANG D D，et al.Research on the loop-free shortest path algorithm with necessary nodes constraint[J].Journal of Hangzhou Dianzi University（Natural Sciences），2017，37（5）：44-50.
[16] SU Z，ZHANG J，Lü Z.A multi-stage metaheuristic algorithm for shortest simple path problem with must-pass nodes[J].IEEE Access，2019，7：52142-52154.
[17] 全国大学生智能汽车竞赛组委会.第十五届全国大学生智能汽车竞赛室外光电组全国总决赛方案[EB/OL].（2020-08-19）[2020-09-11].https：//blog.csdn.net/zhuoqingjoking97298/article/details/107901873.
Committee of national college students’ intelligent car competition.Finals plan of the 15th national college students’ intelligent car competition[EB/OL].（2020-08-19）[2020-09-11].https：//blog.csdn.net/zhuoqingjoking97298/article/details/107901873.
[18] 姚明海，王娜，赵连朋.改进的模拟退火和遗传算法求解TSP问题[J].计算机工程与应用，2013，49（14）：60-65.
YAO M H，WANG N，ZHAO L P，et al.Improved simulated annealing algorithm and genetic algorithm for TSP[J].Computer Engineering and Applications，2013，49（14）：60-65.