An improved ALNS algorithm for the Team Orienteering Problem with Time Windows

The Team Orienteering Problem with Time Windows (TOPTW) is a typical variant of the Orienteering Problem (OP) that each node can only provide one time service in a predefined time window, its objective is to maximize the total score of visiting nodes with a given number of paths. In this study we propose an improved ALNS(adaptive large neighborhood search) algorithm to solve the TOPTW problem, which clusters nodes according to their features to construct the initial solution, and design knowledge-based removal and repair operators to optimize solutions. To fully evaluate the proposed algorithm, some typical benchmark datasets are taken as the test instance suite and several state-of-the-art algorithms are chosen to compare with the proposed algorithm. Experimental results show our algorithm has satisfactory accuracy and far better performance.