Algorithm Selection for the Team Orienteering Problem

This work utilizes Algorithm Selection for solving the Team Orienteering Problem (TOP). The TOP is an NP-hard combinatorial optimization problem in the routing domain. This problem has been modelled with various extensions to address different real-world problems like tourist trip planning. The complexity of the problem motivated to devise new algorithms. However, none of the existing algorithms came with the best performance across all the widely used benchmark instances. This fact suggests that there is a performance gap to fill. This gap can be targeted by developing more new algorithms as attempted by many researchers before. An alternative strategy is performing Algorithm Selection that will automatically choose the most appropriate algorithm for a given problem instance. This study considers the existing algorithms for the Team Orienteering Problem as the candidate method set. For matching the best algorithm with each problem instance, the specific instance characteristics are used as the instance features. An algorithm Selection approach, namely ALORS, is used to conduct the selection mission. The computational analysis based on 157 instances showed that Algorithm Selection outperforms the state-of-the-art algorithms despite the simplicity of the Algorithm Selection setting. Further analysis illustrates the match between certain algorithms and certain instances. Additional analysis showed that the time budget significantly affects the algorithms’ performance.

Duke Scholars

Author Mustafa Misir DKU Faculty