Iterated local search for the team orienteering problem with time windows

作者：Vansteenwegen Pieter^*; Souffriau Wouter; Vanden Berghe Greet; Van Oudheusden Dirk

来源：Computers & Operations Research, 2009, 36(12): 3281-3290.

DOI：10.1016/j.cor.2009.03.008

• Iterated local search
• Team orienteering problem with time windows
• Meta-heuristics

A personalised electronic tourist guide assists tourists in planning and enjoying their trip. The planning problem that needs to be solved, in real-time, can be modelled as a team orienteering problem with time windows (TOPTW). In the TOPTW, a set of locations is given, each with a score, a service time and a time The goal is to maximise the sum of the collected scores by a fixed number of routes. The routes allow to visit locations at the right time and they are limited in length. The main contribution of this paper is a simple, fast and effective iterated local search meta-heuristic to solve the TOPTW. An insert step is combined with a shake step to escape from local optima. The specific shake step implementation and the fast evaluation of possible improvements, produces a heuristic that performs very well on a large and diverse set of instances. The average gap between the obtained results and the best-known solutions is only 1.8% and the average computation time is decreased with a factor of several hundreds. For 31 instances, new best solutions are computed.