The capacitated team orienteering problem

• Main Authors: GUNAWAN, Aldy, NG, Kien Ming, YU, Vincent F., ADIPRASETYO, Gordy, LAU, Hoong Chuin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2019
• Subjects: Orienteering Problem; Iterated Local Search; Capacitated Team Orienteering Problem; Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/4328; https://ink.library.smu.edu.sg/context/sis_research/article/5331/viewcontent/The_Capacitated_Team_Orienteering_Problem.pdf
• Institution: Singapore Management University

This paper focuses on a recent variant of the Orienteering Problem (OP), namely the Capacitated Team OP (CTOP) which arises in the logistics industry. In this problem, each node is associated with a demand that needs to be satisfied and a score that need to be collected. Given a set of homogeneous fleet of vehicles, the objective is to find a path for each vehicle in order to maximize the total collected score, without violating the capacity and time budget. We propose an Iterated Local Search (ILS) algorithm for solving the CTOP. Two strategies, either accepting a new solution as long as it improves the quality of the solutions or accepting a new solution as long as there is no constraint violation, are implemented. For solving difficult instances, we simplify the move operator of local search in order to reduce the computational time. Instead of exploring all possible nodes in all paths to be moved, we only focus on nodes in the path with the least remaining amount of time. Computational experiments on benchmark instances illustrate that the algorithm can generate solutions within 1% and 4% from the current best known solution for small and large instances, respectively.