Efficient meta-heuristics for the Multi-Objective Time-Dependent OrienteeringProblem

Publication Year: 2016 Publication Type : JournalArticle


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 nd 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 ecacy of adopting the memetic algorithm framework to solve MOTDOP.


    author = {Yi Mei and Flora D. Salim and Xiaodong Li},
    bibsource = {dblp computer science bibliography, https://dblp.org},
    biburl = {https://dblp.org/rec/journals/eor/MeiSL16.bib},
    doi = {10.1016/j.ejor.2016.03.053},
    journal = {Eur. J. Oper. Res.},
    number = {2},
    pages = {443--457},
    timestamp = {Fri, 21 Feb 2020 00:00:00 +0100},
    title = {Efficient meta-heuristics for the Multi-Objective Time-Dependent Orienteering Problem},
    url = {https://doi.org/10.1016/j.ejor.2016.03.053},
    volume = {254},
    year = {2016}


Related Publications

RUP: Large Room Utilisation Prediction with carbon dioxide sensor
Type : JournalArticle
Show More
A Scalable Room Occupancy Prediction with Transferable Time Series Decomposition of CO 2 Sensor Data
Type : JournalArticle
Show More
Topical Event Detection on Twitter
Type : ConferenceProceeding
Show More

© 2021 Flora Salim - CRUISE Research Group.