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

K Karabulut, MF Tasgetiren - Computers & Industrial Engineering, 2020 - Elsevier
Computers & Industrial Engineering, 2020Elsevier
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 …
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.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果