Trip planning for visitors in a service system with capacity constraints. (December 2022) - Luo, Xing-Gang; Liu, Xin-Rui; Ji, Peng-Li; Shang, Xuan-Zhu; Zhang, Zhong-Liang
Abstract: The problem of optimizing trip planning for visitors in a service system with capacity constraints can be generalized as a multi-agent orienteering problem with capacity constraints (MAOPCC). The real-world applications of MAOPCCs include itinerary planning of scenic spots for tourists, trip planning for visiting attractions in a theme park, and route planning in a museum. In this research, a mixed-integer linear programming model for a MAOPCC is established that can be directly solved by CPLEX, and the NP-hard nature of MAOPCCs is proved. A branch-and-bound (B&B) algorithm is designed to solve the established model for small-scale problems. A variable neighborhood search (VNS) algorithm incorporating constructive heuristics and reward-density-based visitor-link partitioning methods is developed to solve large-scale problems. Numerical experiments show that the proposed B&B algorithm improves the results of best existing approach by 30.79%, and the developed VNS considerably outperforms the existing heuristic algorithm both on objective function value and CPU time. Highlights: A mixed-integer linear programming model for the optimization problem is established and the NP-hard nature of problem is proved. A branch-and-bound algorithm (B&B) is designed to solve small-scale problems. A variable neighborhood search (VNS) algorithm is developed to solve large-scale problems. Numerical experiments show that the proposed B&B and VNS outperform the existing algorithms.