A swarm intelligence graph-based pathfinding algorithm (SIGPA) for multi-objective route planning

摘要

Personalized tourist route planning (TRP) and navigation are online or real-time applications whose mathematical modeling leads to complex optimization problems. These problems are usually formulated with mathematical programming and can be described as NP hard problems. Moreover, the state-of-the-art (SOA) path search algorithms do not perform efficiently in solving multi-objective optimization (MO) problems making them inappropriate for real-time processing. To address the above limitations and the need for online processing, a swarm intelligence graph-based pathfinding algorithm (SIGPA) for MO route planning was developed. SIGPA generates a population whose individuals move in a greedy approach based on A* algorithm to search the solution space from different directions. It can be used to find an optimal path for every graph-based problem under various objectives. To test SIGPA, a generic MOTRP formulation is proposed. A generic TRP formulation remains a challenge since it has not been studied thoroughly in the literature. To this end, a novel mixed binary quadratic programming model is proposed for generating personalized TRP based on multi-objective criteria and user preferences, supporting, also, electric vehicles or sensitive social groups in outdoor cultural environments. The model targets to optimize the route under various factors that the user can choose, such as travelled distance, smoothness of route without multiple deviations, safety and cultural interest. The proposed model was compared to five SOA models for addressing TRP problems in 120 various scenarios solved with CPLEX solver and SIGPA. SIGPA was also tested in real scenarios with A* algorithm. The results proved the effectiveness of our model in terms of optimality but also the efficiency of SIGPA in terms of computing time. The convergence and the fitness landscape analysis showed that SIGPA achieved quality solutions with stable convergence.