Trip planning for visitors in a service system with capacity constraints. (December 2022)

• Record Type: Journal Article
• Authors: Luo, Xing-Gang; Liu, Xin-Rui; Ji, Peng-Li; Shang, Xuan-Zhu; Zhang, Zhong-Liang
• Is Part Of: Computers & operations research. Volume 148(2022)
• Publication Date: 2022-12
• Subjects: Trip planning -- Itinerary planning -- Orienteering problem -- Branch & bound; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105974
• Languages: English
• ISSNs: 0305-0548

Abstract

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.