Name
Abstract | ||
|---|---|---|
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 window. 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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.cor.2009.03.008 | Computers & OR |
Keywords | Field | DocType |
average gap,specific shake step implementation,shake step,time window,Iterated local search,time windows,service time,insert step,average computation time,right time,diverse set | Mathematical optimization,Orienteering,Mathematics,Iterated local search,Metaheuristic | Journal |
Volume | Issue | ISSN |
36 | 12 | Computers and Operations Research |
Citations | PageRank | References |
111 | 4.04 | 20 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pieter Vansteenwegen | 1 | 1026 | 48.63 |
| Wouter Souffriau | 2 | 750 | 28.50 |
| Greet Vanden Berghe | 3 | 1371 | 77.56 |
| Dirk Van Oudheusden | 4 | 917 | 41.64 |