Mei 2016 Efficient meta-heuristics for the multi-objective time-dependent.pdf (591.8 kB)

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

Download (591.8 kB)
journal contribution
posted on 31.03.2021, 02:39 by Yi Mei, Flora D Salim, Xiaodong Li
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/

History

Preferred citation

Mei, Y., Salim, F. D. & Li, X. (2016). Efficient meta-heuristics for the multi-objective time-dependent orienteering problem. European Journal of Operational Research, 254(2), 443-457. https://doi.org/10.1016/j.ejor.2016.03.053

Journal title

European Journal of Operational Research

Volume

254

Issue

2

Publication date

01/01/2016

Pagination

443-457

Publisher

Elsevier

Publication status

Published

Contribution type

Article

ISSN

0377-2217

eISSN

1872-6860

Article number

2

Language

en

Exports