Publication Type

Journal Article

Version

publishedVersion

Publication Date

6-2017

Abstract

The Team Orienteering Problem with Time Windows (TOPTW) is the extension of the Orienteering Problem (OP) where each node is limited by a predefined time window during which the service has to start. The objective of the TOPTW is to maximize the total collected score by visiting a set of nodes with a limited number of paths. We propose two algorithms, Iterated Local Search and a hybridization of Simulated Annealing and Iterated Local Search (SAILS), to solve the TOPTW. As indicated in multiple research works on algorithms for the OP and its variants, determining appropriate parameter values in a statistical way remains a challenge. We apply Design of Experiments, namely factorial experimental design, to screen and rank all the parameters thereby allowing us to focus on the parameter search space of the important parameters. The proposed algorithms are tested on benchmark TOPTW instances. We demonstrate that well-tuned ILS and SAILS lead to improvements in terms of the quality of the solutions. More precisely, we are able to improve 50 best known solution values on the available benchmark instances.

Keywords

Orienteering Problem, Time windows, Iterated Local Search, Simulated Annealing, Hybrid algorithm

Discipline

Databases and Information Systems

Research Areas

Intelligent Systems and Optimization

Publication

Journal of the Operational Research Society

Volume

68

Issue

8

First Page

861

Last Page

876

ISSN

0160-5682

Identifier

10.1057/s41274-017-0244-1

Publisher

Taylor & Francis: STM, Behavioural Science and Public Health Titles

Additional URL

https://doi.org/10.1057/s41274-017-0244-1

Download

Share

COinS