Efficient meta-heuristics for the multi-objective time-dependent orienteering problem

In this paper, the Multi-Objective Time-Dependent Orienteering Problem (MOTDOP) is investigated. Time-dependent travel time and multiple preferences are two of the most important factors in practice, and have been handled separately in previous work. However, no attempts have been made so far to consider these two factors together. Handling both multiple preferences and time-dependent travel time simultaneously poses a challenging optimization task in this NP-hard problem. In this study, two meta-heuristic methods are proposed for solving MOTDOP: a Multi-Objective Memetic Algorithm (MOMA) and a Multi-objective Ant Colony System (MACS). Two sets of benchmark instances were generated to evaluate the proposed algorithms. The experimental studies show that both MOMA and MACS managed to find better solutions than an existing multi-objective evolutionary algorithm (FMOEA). Additionally, MOMA achieved better performance than MACS in a shorter time, and is less sensitive to the parameter setting. Given that MACS inherits promising features of P-ACO, which is a state-of-the-art algorithm for multi-objective orienteering problem, the advantage of MOMA over MACS and FMOEA demonstrates the efficacy of adopting the memetic algorithm framework to solve MOTDOP. Graphical Abstract https://ars.els-cdn.com/content/image/1-s2.0-S0377221716301990-fx1_lrg.jpg © This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/