基于道路交通网络的多约束最优路径算法研究
|
摘要
最短路径问题是网络优化的关键问题之一,多年来产生了大量相关领域的研究成果。在这些研究成果中,有相当一部分是针对网络弧权单一情形的。然而,在现实生活中,很多问题的弧权不是一个而是多个,而且从源节点至目标节点的最优路径对其中一个或多个弧权是有约束的,这就是有约束的最优路径问题。目前,有关QoS路由问题的多约束最优路径算法已有很多,但基于道路交通网络的多约束最优路径问题的研究成果相对较少。论文主要基于道路交通网络,对多约束最优路径问题进行研究。
论文的研究成果主要包括:
1)针对带约束的多弧权网络最优路径问题,建立了多约束最短路径模型;将经典的Dijkstra算法应用于多约束最短路径问题中,提出了D_MCSP算法。
2)D_MCSP算法是一种盲目搜索算法,在搜索过程中会扩展许多与最短路径无关的中间节点状态,影响算法的搜索效率。为此,论文将A*算法的启发式搜索思想引入多约束最短路径问题,提出了A*_MCSP算法。
3)针对D_MCSP算法和A*_MCSP算法在搜索过程中需要占用大量系统内存来存储中间节点状态的缺点,基于启发式迭代加深搜索算法IDA*,提出了IDA*_MCSP算法;针对IDA*_MCSP算法在路径搜索过程中可能出现的节点重复扩展等问题,论文又提出了一种加强存储的迭代加深启发式搜索算法(ME-IDA*_MCSP算法)。
4)对IDA*_MCSP(ME-IDA*_MCSP)算法作进一步改进,提出了一种多约束边沿搜索算——Fringe_MCSP算法,克服了原有算法每次迭代都要回到起始节点重新搜索的缺陷。
5)最后,基于南京市某区域道路信息,建立了多约束道路交通网络平台,并在该平台实现了上述四种多约束最优路径算法。试验表明:上述算法都是正确有效的,并且Fringe_MCSP算法是其中最优的一种算法。
Shortest path problem is one of the key topics in network optimization.Over the recent years,lots of related research results are proposed,In the results,quite a lot of them focus on networks with single arc weights.However,in the real life,many problems called optimal path problems with constraints,which do not just have one arc weight but many arc weights, and at least one of the arc weights of the optimal path from source node to destination node is restricted.At present,there're many multi-constraint optimal path algorithms on Quality of service(QoS for short) routing problem.Relatively,there are less research results on multi-constraint optimal path problem based on road transportation network.This dissertation is concentrated on the research of multi-constraint optimal path problem based on road transportation network.
Main contributions of the dissertation include:
1) Analyzing constraint optimal path problem based on multi-arc weights nework,a multi-constraint shortest path model is constructed.And a multi-constraint shortest path algorithm called DMCSP is proposed which is the application of classical Dijkstra algorithm in solving multi-constraint shortest path problem.
2) As D_MCSP is a blind search algorithm,it extends a lot of useless nodes for finding the shortest path while searching.And this decreases the efficiency of the search algorithm. An algorithm called A*_MCSP,which is the heuristic A* algorithm's extension used in sovling multi-constraint shortest path problem,is proposed.
3) For the demerit of D_MCSP algorithm and A*_MCSP algorithm that they needs a lot of system memory to store temporary node status,ID A*_MCSP algorithm,which is based on heuristic depth first iterative-deepening algorithm(IDA*),is proposed.However,while searching with IDA*_MCSP algorithm,nodes maybe re-extended many times.Memory enhanced IDA*_MCSP algorithm is proposed to sovle this problem.
4) A fringe search algorithm,which is called Fringe_MCSP algorithm,is proposed as an improving algorithm of IDA*_MCSP(ME-IDA*_MCSP) algorithm,which can conquer the drawback of IDA*_MCSP that restart searching from the starting node in each iteration,.
5) At last,a multi-constraint road transportation network platform based on some district's road information of Nanjing city's map is constructed.And the above four multi-constraint optimal path algorithms are implemented in this platform.And experiments are progressed to proof that all the above algorithms are correct and effective.Fringe_MCSP algorithm is the best of the four.
论文的研究成果主要包括:
1)针对带约束的多弧权网络最优路径问题,建立了多约束最短路径模型;将经典的Dijkstra算法应用于多约束最短路径问题中,提出了D_MCSP算法。
2)D_MCSP算法是一种盲目搜索算法,在搜索过程中会扩展许多与最短路径无关的中间节点状态,影响算法的搜索效率。为此,论文将A*算法的启发式搜索思想引入多约束最短路径问题,提出了A*_MCSP算法。
3)针对D_MCSP算法和A*_MCSP算法在搜索过程中需要占用大量系统内存来存储中间节点状态的缺点,基于启发式迭代加深搜索算法IDA*,提出了IDA*_MCSP算法;针对IDA*_MCSP算法在路径搜索过程中可能出现的节点重复扩展等问题,论文又提出了一种加强存储的迭代加深启发式搜索算法(ME-IDA*_MCSP算法)。
4)对IDA*_MCSP(ME-IDA*_MCSP)算法作进一步改进,提出了一种多约束边沿搜索算——Fringe_MCSP算法,克服了原有算法每次迭代都要回到起始节点重新搜索的缺陷。
5)最后,基于南京市某区域道路信息,建立了多约束道路交通网络平台,并在该平台实现了上述四种多约束最优路径算法。试验表明:上述算法都是正确有效的,并且Fringe_MCSP算法是其中最优的一种算法。
Shortest path problem is one of the key topics in network optimization.Over the recent years,lots of related research results are proposed,In the results,quite a lot of them focus on networks with single arc weights.However,in the real life,many problems called optimal path problems with constraints,which do not just have one arc weight but many arc weights, and at least one of the arc weights of the optimal path from source node to destination node is restricted.At present,there're many multi-constraint optimal path algorithms on Quality of service(QoS for short) routing problem.Relatively,there are less research results on multi-constraint optimal path problem based on road transportation network.This dissertation is concentrated on the research of multi-constraint optimal path problem based on road transportation network.
Main contributions of the dissertation include:
1) Analyzing constraint optimal path problem based on multi-arc weights nework,a multi-constraint shortest path model is constructed.And a multi-constraint shortest path algorithm called DMCSP is proposed which is the application of classical Dijkstra algorithm in solving multi-constraint shortest path problem.
2) As D_MCSP is a blind search algorithm,it extends a lot of useless nodes for finding the shortest path while searching.And this decreases the efficiency of the search algorithm. An algorithm called A*_MCSP,which is the heuristic A* algorithm's extension used in sovling multi-constraint shortest path problem,is proposed.
3) For the demerit of D_MCSP algorithm and A*_MCSP algorithm that they needs a lot of system memory to store temporary node status,ID A*_MCSP algorithm,which is based on heuristic depth first iterative-deepening algorithm(IDA*),is proposed.However,while searching with IDA*_MCSP algorithm,nodes maybe re-extended many times.Memory enhanced IDA*_MCSP algorithm is proposed to sovle this problem.
4) A fringe search algorithm,which is called Fringe_MCSP algorithm,is proposed as an improving algorithm of IDA*_MCSP(ME-IDA*_MCSP) algorithm,which can conquer the drawback of IDA*_MCSP that restart searching from the starting node in each iteration,.
5) At last,a multi-constraint road transportation network platform based on some district's road information of Nanjing city's map is constructed.And the above four multi-constraint optimal path algorithms are implemented in this platform.And experiments are progressed to proof that all the above algorithms are correct and effective.Fringe_MCSP algorithm is the best of the four.
引文
[1]刘光.地理信息系统基础篇.中国电力出版社.2002
[2]王家耀.地理信息系统的发展与发展中的地理信息系统.中国工程科学2009,11(2):10-16
[3]刘明德,林杰斌著.地理信息系统GIS理论与务实 北京:清华大学出版社,2006.12
[4]胡运权,龚强.简论GIS发展与前瞻.东北测绘,1999,22(4):3-4
[5]李连营等著.基于MapX的GIS应用开发 武汉:武汉大学出版社 2003.6
[6]乐阳,龚健雅.Dijkstra 最短路径算法的一种高效率实现.武汉:武汉测绘科技大学学报.1999.9,24(3):209-212
[7]邹永贵,魏来.带多约束条件的最优路径选择算法研究.计算机应用.2008.5,28(5):1101-1103
[8]Y.Li,J.Harms,R.Holte.Fast exact multi-constraint shortest path algorithms.IEEE Communications Society subject matter experts for publication in the ICC 2007 proceedings,123-130
[9]P.V.Mieghem,F.A.Kuipers.Concepts of exact QoS routing algorithms.IEEE/ACM transactions on networking,2004,12(5):851-864
[10]J.M.Jaffe.Algorithms for finding paths with multiple constraints.Networks,1984,14:95-116
[11]S.Chen,K.Nahrstedt.On finding multi-constrainted paths.Proc ICC'98,IEEE,1998.8,2:74-79
[12]H.De.Neve,P.Van.Mieghem.TAMCRA:a tunable accuracy multiple constraints routing algorithm.Computer Communications,2000,23:667-679
[13]P.Van.Mieghem,H.De.Neve,F.A.Kuipers.Hop-by-hop quality of service routing.Computer Networks,2001,37(3-4):407-423
[14]T.Korkmaz,M.Krunz,Multi-constrained Optimal Path Selection.Proc.INFOCOM 2001,vol.2,Anchorage,AK,IEEE,2001.4,834-43
[15]G.Liu,R.Ramakrishnam.A~* Prune:an algorithm for finding K shortest paths subject to multiple constraints.In Proceedings of INFOCOM'01,Anchorage,Alaska,2001.4,743-749
[16]T.Korkmaz,M.Krunz.A Randomized Algorithm for Finding a Path Subject to Multiple QoS Constraints.Comp.Nets.2001,36(2-3):51-68
[17]F.Kuipers,P.V.Mieghem,T.Korkmaz,M.Krunz.An Overview of Constraint-Based Path Selection Algorithms for QoS Routing.IEEE Communications Magazine.2002.12,50-54
[18]胡永良.启发式多约束路由算法研究.计算机工程与应用.2005.30:155-157
[19]国外智能交通系统介绍.http://www.police.com.cn/Article/keji/kidg/200503/134.html
[20]陆峰.最短路径算法:分类体系与研究进展.测绘学报.2001.8.30(3):209-275
[21]X.Yuan.Heuristic algorithms for multi-constrained quality-of-service routing.IEEE/ACM Transactions on Networking,2002;10(2)
[22]陈立家,周建国,江昊,晏蒲柳.QoS多约束优化路径选择算法.计算机应用.2005.4,25(4):900-902
[23]王晟,李乐民.一种改进的多约束最佳路径算法研究.电子学报.2004.4,32(4):529-535
[24]贺细平,朱幸辉,张历卓.启发式QoS路由选择算法的实现与仿真.计算机工程与设计.2007.5,28(9):2030-2033
[25]齐小刚,刘三阳.一种基于 K 最短路径的QoS路由选择算法.吉林大学学报.2005.9,35(5):526-530
[26]尹国定,于战科,倪明放.多约束QoS路由的一种启发式算法.计算机工程与科学.2004,26(2):53-55
[27]刘千里,汪泽焱,倪明放,戴浩.一种基于多条件约束的QoS路由选择优化算法.计算机研究与发展.2001.3,38(3):275-278
[28]刘山.基于多条件约束的QoS路由选择优化算法.南开大学学报.2004.6,37(2):93-96
[29]钱进,陈立家,贺贵明.一种多约束最优路径宽度优先松弛算法.计算机应用研究.2007.1:90-93,107
[30]路冉,吴巍.一种改进的多约束条件的路由算法.无线电工程.2004,34(4):19-22
[31]张琨,王珩,刘凤玉,衷宜.基于多个QoS约束的路径选择算法.计算机应用研究.2005.1:194-196,199
[32]P.S.Prakash,S.Selvan.An Efficient and Optimized Multi Constrained Path Computation for Real Time Interactive Applications in Packet Switched Networks.International Journal of Computer Science.2008,293-300
[33]M.Song,S.Sahni.Approximation Algorithms for Multiconstrained Quality-of-Service Routing.IEEE transactions on networking.2006.5,55(5):603-617
[34]G.Xue,A.Sen,W.Zhang,J.Tang,K.Thulasiraman.Finding a path subject to many additive QoS constraints.IEEE/ACM Transactions on Networking,15(1):201-211
[35]Z.Li,J.J.Garcia-Luna-Aceves.Finding multi-constrained feasible paths by using depth-first search.Wireless Network.2007,13:323-334
[36]廉师友编著.人工智能技术导论.西安:西安电子科技大学出版社.2007.5
[37]贲可荣,张彦铎编著.人工智能.北京:清华大学出版社.2006.3
[38]尹朝庆主编.人工智能方法与应用.武汉:华中科技大学出版社.2007.8
[39]谢金星,邢文训.网络优化.北京:清华大学出版社.2000.8
[40]李元臣,刘维群.基于Dijkstra 算法的网络最短路径分析.微计算机应用.2004.5,25(3):295-298
[41]张福浩,刘纪平,李青元.基于Dijkstra 算法的一种最短路径优化算法.遥感信息.2004.2.38-41
[42]P.Hart,N.Nilsson,and B.Paphael.A formal basis for the heuristic determination of minimum cost path.IEEE Transaction on Systems Science and Cybernetics,1968.4(2):100-107
[43]王海梅.基于GIS的最优路径算法研究与实现.南京:南京理工大学博士论文.2008.7.
[44]高庆吉,于咏生,胡丹丹.基于改进A~* 算法的可行性路径搜索及优化.中国民航学院学报.2005.8,23(4):42-45
[45]刘浩,鲍远律.A~* 算法在矢量地图最优路径搜索中的应用.计算机仿真.2008.4,25(4):253-257
[46]Goldburg A.V,Tarjan R.E.Expected performance of Dijkstra's Shortest Path Algorithm.Princeton:Princeton University,1996
[47]Fredman M.L,Tarjan R.E.Fibonacci heaps and their uses in improved network optimization algorithms.Journal of the Associatetion for computing machinaery.1987,34(3):596-615
[48]Ahuja R.K,Mehlhorn K,Orlin J.B,etal.Faster algorithms for shortest path problem.Journal of the association for computing machinery,1990,37(2):213-223
[49]R.Korf.Depth-first iterative-deepening:An optimal admissible tree search.Artificial Intelligence,1985,27(1):97-109
[50]Y.Bj(o|¨)rnsson,M.Enzenberger,R.Holte,and J.Schaeffer.Fringe search:beating A~* at pathfinding on game maps.In Proceedings of IEEE Symposium on Computational Intelligence and Games.Colchester,Essex,UK,April 2005.
[51]Reinefeld A,Marsland T.Enhanced iterative-deepening search.IEEE Transactions on Pattern Analysis and Machine Intelligence.1994,16:701-710
[52]荣伟.基于道路网路的最短路径算法的研究与实现.武汉:武汉理工大学硕士学位论文.2005.5
[53]熊少非,赵丕锡,李军.MapInfo 中城市道路网络拓扑结构的自动生成.兵工自动化.2005.24(3):67-68
[54]公丕波,郝金明,朱伟刚.MapX 支持下道路网络拓扑结构构建方法.测绘工程.2004.13(4):51-54
[2]王家耀.地理信息系统的发展与发展中的地理信息系统.中国工程科学2009,11(2):10-16
[3]刘明德,林杰斌著.地理信息系统GIS理论与务实 北京:清华大学出版社,2006.12
[4]胡运权,龚强.简论GIS发展与前瞻.东北测绘,1999,22(4):3-4
[5]李连营等著.基于MapX的GIS应用开发 武汉:武汉大学出版社 2003.6
[6]乐阳,龚健雅.Dijkstra 最短路径算法的一种高效率实现.武汉:武汉测绘科技大学学报.1999.9,24(3):209-212
[7]邹永贵,魏来.带多约束条件的最优路径选择算法研究.计算机应用.2008.5,28(5):1101-1103
[8]Y.Li,J.Harms,R.Holte.Fast exact multi-constraint shortest path algorithms.IEEE Communications Society subject matter experts for publication in the ICC 2007 proceedings,123-130
[9]P.V.Mieghem,F.A.Kuipers.Concepts of exact QoS routing algorithms.IEEE/ACM transactions on networking,2004,12(5):851-864
[10]J.M.Jaffe.Algorithms for finding paths with multiple constraints.Networks,1984,14:95-116
[11]S.Chen,K.Nahrstedt.On finding multi-constrainted paths.Proc ICC'98,IEEE,1998.8,2:74-79
[12]H.De.Neve,P.Van.Mieghem.TAMCRA:a tunable accuracy multiple constraints routing algorithm.Computer Communications,2000,23:667-679
[13]P.Van.Mieghem,H.De.Neve,F.A.Kuipers.Hop-by-hop quality of service routing.Computer Networks,2001,37(3-4):407-423
[14]T.Korkmaz,M.Krunz,Multi-constrained Optimal Path Selection.Proc.INFOCOM 2001,vol.2,Anchorage,AK,IEEE,2001.4,834-43
[15]G.Liu,R.Ramakrishnam.A~* Prune:an algorithm for finding K shortest paths subject to multiple constraints.In Proceedings of INFOCOM'01,Anchorage,Alaska,2001.4,743-749
[16]T.Korkmaz,M.Krunz.A Randomized Algorithm for Finding a Path Subject to Multiple QoS Constraints.Comp.Nets.2001,36(2-3):51-68
[17]F.Kuipers,P.V.Mieghem,T.Korkmaz,M.Krunz.An Overview of Constraint-Based Path Selection Algorithms for QoS Routing.IEEE Communications Magazine.2002.12,50-54
[18]胡永良.启发式多约束路由算法研究.计算机工程与应用.2005.30:155-157
[19]国外智能交通系统介绍.http://www.police.com.cn/Article/keji/kidg/200503/134.html
[20]陆峰.最短路径算法:分类体系与研究进展.测绘学报.2001.8.30(3):209-275
[21]X.Yuan.Heuristic algorithms for multi-constrained quality-of-service routing.IEEE/ACM Transactions on Networking,2002;10(2)
[22]陈立家,周建国,江昊,晏蒲柳.QoS多约束优化路径选择算法.计算机应用.2005.4,25(4):900-902
[23]王晟,李乐民.一种改进的多约束最佳路径算法研究.电子学报.2004.4,32(4):529-535
[24]贺细平,朱幸辉,张历卓.启发式QoS路由选择算法的实现与仿真.计算机工程与设计.2007.5,28(9):2030-2033
[25]齐小刚,刘三阳.一种基于 K 最短路径的QoS路由选择算法.吉林大学学报.2005.9,35(5):526-530
[26]尹国定,于战科,倪明放.多约束QoS路由的一种启发式算法.计算机工程与科学.2004,26(2):53-55
[27]刘千里,汪泽焱,倪明放,戴浩.一种基于多条件约束的QoS路由选择优化算法.计算机研究与发展.2001.3,38(3):275-278
[28]刘山.基于多条件约束的QoS路由选择优化算法.南开大学学报.2004.6,37(2):93-96
[29]钱进,陈立家,贺贵明.一种多约束最优路径宽度优先松弛算法.计算机应用研究.2007.1:90-93,107
[30]路冉,吴巍.一种改进的多约束条件的路由算法.无线电工程.2004,34(4):19-22
[31]张琨,王珩,刘凤玉,衷宜.基于多个QoS约束的路径选择算法.计算机应用研究.2005.1:194-196,199
[32]P.S.Prakash,S.Selvan.An Efficient and Optimized Multi Constrained Path Computation for Real Time Interactive Applications in Packet Switched Networks.International Journal of Computer Science.2008,293-300
[33]M.Song,S.Sahni.Approximation Algorithms for Multiconstrained Quality-of-Service Routing.IEEE transactions on networking.2006.5,55(5):603-617
[34]G.Xue,A.Sen,W.Zhang,J.Tang,K.Thulasiraman.Finding a path subject to many additive QoS constraints.IEEE/ACM Transactions on Networking,15(1):201-211
[35]Z.Li,J.J.Garcia-Luna-Aceves.Finding multi-constrained feasible paths by using depth-first search.Wireless Network.2007,13:323-334
[36]廉师友编著.人工智能技术导论.西安:西安电子科技大学出版社.2007.5
[37]贲可荣,张彦铎编著.人工智能.北京:清华大学出版社.2006.3
[38]尹朝庆主编.人工智能方法与应用.武汉:华中科技大学出版社.2007.8
[39]谢金星,邢文训.网络优化.北京:清华大学出版社.2000.8
[40]李元臣,刘维群.基于Dijkstra 算法的网络最短路径分析.微计算机应用.2004.5,25(3):295-298
[41]张福浩,刘纪平,李青元.基于Dijkstra 算法的一种最短路径优化算法.遥感信息.2004.2.38-41
[42]P.Hart,N.Nilsson,and B.Paphael.A formal basis for the heuristic determination of minimum cost path.IEEE Transaction on Systems Science and Cybernetics,1968.4(2):100-107
[43]王海梅.基于GIS的最优路径算法研究与实现.南京:南京理工大学博士论文.2008.7.
[44]高庆吉,于咏生,胡丹丹.基于改进A~* 算法的可行性路径搜索及优化.中国民航学院学报.2005.8,23(4):42-45
[45]刘浩,鲍远律.A~* 算法在矢量地图最优路径搜索中的应用.计算机仿真.2008.4,25(4):253-257
[46]Goldburg A.V,Tarjan R.E.Expected performance of Dijkstra's Shortest Path Algorithm.Princeton:Princeton University,1996
[47]Fredman M.L,Tarjan R.E.Fibonacci heaps and their uses in improved network optimization algorithms.Journal of the Associatetion for computing machinaery.1987,34(3):596-615
[48]Ahuja R.K,Mehlhorn K,Orlin J.B,etal.Faster algorithms for shortest path problem.Journal of the association for computing machinery,1990,37(2):213-223
[49]R.Korf.Depth-first iterative-deepening:An optimal admissible tree search.Artificial Intelligence,1985,27(1):97-109
[50]Y.Bj(o|¨)rnsson,M.Enzenberger,R.Holte,and J.Schaeffer.Fringe search:beating A~* at pathfinding on game maps.In Proceedings of IEEE Symposium on Computational Intelligence and Games.Colchester,Essex,UK,April 2005.
[51]Reinefeld A,Marsland T.Enhanced iterative-deepening search.IEEE Transactions on Pattern Analysis and Machine Intelligence.1994,16:701-710
[52]荣伟.基于道路网路的最短路径算法的研究与实现.武汉:武汉理工大学硕士学位论文.2005.5
[53]熊少非,赵丕锡,李军.MapInfo 中城市道路网络拓扑结构的自动生成.兵工自动化.2005.24(3):67-68
[54]公丕波,郝金明,朱伟刚.MapX 支持下道路网络拓扑结构构建方法.测绘工程.2004.13(4):51-54