Road Transport Network-based Multi-constrained Optimal Path Algorithm Research

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.