A Greedy Constructive Heuristic for Solving the Team Orienteering Problem with Variable Time Windows

Abstract

Orienteering problems are a subclass of routing problems, in which a selection of the set of nodes should be made for visiting, due to route length restrictions. These nodes can also impose time-window constraints, which can be variable if they are defined by a spread process, which behavior can be modified. The problem including all these features is the Team Orienteering Problem with Variable Time Windows (TOPVTW). In this paper, deterministic and randomized greedy constructive heuristic schemes are developed for solving the problem, along with the definition of some metrics that guide the constructive processes. One of the heuristics is combined with an existing exact mixed integer programming model to improve the outputs. All the solving strategies proposed are tested with instances representing the spread of a wildfire in a landscape, demonstrating improvements in performance when compared with existing exact solving methodologies.