An evolution strategy approach to the team orienteering problem with time windows

Abstract

The team orienteering problem with time windows (TOPTW) is a highly constrained NP-hard problem having many practical applications in vehicle routing and production scheduling. The TOPTW is an extended variant of the Orienteering Problem (OP) where each node has a predefined time window during which the service has to be started. The aim is to maximize the total collected score by visiting a set of nodes with a limited number of tours since the given distance budget is limited. We propose an evolution strategy (ES) together with an effective constructive heuristic for solving the TOPTW. The main feature of the ES is to generate an offspring solution through ruin and recreate (RR) heuristic where a number of nodes are removed from the incumbent solution and then they are reinserted into tours until a complete solution is obtained. The ES is hybridized with an efficient random local search to enhance solution quality. For survivor selection we use a goodness of scores approach to determine and diversify the population for the next generation. Parameters of the ES are determined through the design of experiment approach to tune them. The computational results show that the constructive heuristic is slightly better than existing heuristics in the literature. Furthermore the detailed computation results on the benchmark suite from the literature confirm the effectiveness of the evolution strategy. Ultimately the evolution strategy obtains new best-known solutions for 7 benchmark problem instances.