Iterated local search algorithm for 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 2018
• Subjects: Orienteering problem; Iterated local search; Capacitated orienteering problem; Operations Research, Systems Engineering and Industrial Engineering; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/4373; https://ink.library.smu.edu.sg/context/sis_research/article/5376/viewcontent/CTOP.pdf
• Institution: Singapore Management University

This paper focuses on a recent variant of the Orienteering Problem (OP), namely the Capacitated Team Orienteering Problem (CTOP). 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 main objective is to find a path for each available vehicle in order to maximize the total score, without violating the capacity and time budget of each vehicle. We propose an Iterated Local Search algorithm that has been applied in solving various variants of the OP. We propose two ILS algorithms with the main difference lies on the implementation of local search operators. For solving small instances, we implement two different 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. For solving large 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 data sets illustrate the efficiency and effectiveness of the proposed approach.