Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

8-2018

Abstract

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.

Keywords

Orienteering problem, Iterated local search, Capacitated orienteering problem

Discipline

Operations Research, Systems Engineering and Industrial Engineering | Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the 12th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2018), Vienna, Austria, August 28-31

First Page

493

Last Page

496

ISBN

9780992998424

Publisher

PATAT

City or Country

Vienna

Download

Share

COinS