Multi-Constrained Shortest Path Model and Solution with Improved Ant Colony Algorithm

How to provide a route to meet the driver's multiple psychological expectations is the key problem of a navigation system. Essentially, this problem is a resource constrained shortest path problem (RCSP), which belongs to NP hard problems and can not be solved with the traditional shortest path algorithm. A multi-constrained shortest path mathematical model is presented in this paper and solved with an improved ant colony algorithm. The pheromone update rule and heuristic factor are redesigned in the algorithm. Results show that the improved optimization algorithm has a good ability to accurately determine the multi-constrained shortest path in the road network.