Conference Proceeding Article
The Orienteering Problem with Time Windows (OPTW) is a variant of the Orienteering Problem (OP). Given a set of nodes including their scores, service times and time windows, the goal is to maximize the total of scores collected by a particular route considering a predefined time window during which the service has to start. We propose an Iterated Local Search (ILS) algorithm to solve the OPTW, which is based on several LocalSearch operations, such as swap, 2-opt, insert and replace. We also implement the combination between AcceptanceCriterion and Perturbation mechanisms to control the balance between diversification and intensification of the search. In Perturbation, Shake strategy is introduced. The computational results obtained by our proposed algorithm are compared against optimal solutions or best known solution values obtained by state-of-the-art algorithms. We show experimentally that our proposed algorithm is effective on well-known benchmark instances available in the literature. It is also able to improve the best known solution of some benchmark instances.
Orienteering problem, Time windows, Iterated local search
Operations Research, Systems Engineering and Industrial Engineering | Theory and Algorithms
Intelligent Systems and Decision Analytics
Evolutionary Computation in Combinatorial Optimization: 15th European Conference, EvoCOP 2015, Copenhagen, Denmark, April 8-10, 2015, Proceedings
City or Country
GUNAWAN, Aldy; LAU, Hoong Chuin; and LU, Kun.
An iterated local search algorithm for solving the Orienteering Problem with Time Windows. (2015). Evolutionary Computation in Combinatorial Optimization: 15th European Conference, EvoCOP 2015, Copenhagen, Denmark, April 8-10, 2015, Proceedings. 61-73. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/2794
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.