Conference Proceeding Article
This paper presents a generalization of the Orienteering Problem, the Time-Dependent Orienteering Problem (TDOP) which is based on the real-life application of providing automatic tour guidance to a large leisure facility such as a theme park. In this problem, the travel time between two nodes depends on the time when the trip starts. We formulate the problem as an integer linear programming (ILP) model. We then develop various heuristics in a step by step fashion: greedy construction, local search and variable neighborhood descent, and two versions of iterated local search. The proposed metaheuristics were tested on modified benchmark instances, randomly generated problem instances, and two real world problem instances extracted from two popular theme parks in Asia. Experimental results confirm the effectiveness of the developed metaheuristic approaches, especially an iterated local search with adaptive perturbation size and probabilistic intensified restart mechanism. It finds within an acceptably short computation time, the optimal or near optimal solutions for TDOP instances of realistic size as in our target application.
Time-Dependent Orienteering Problem, Integer Linear Programming, Metaheuristics, Iterated Local Search
Artificial Intelligence and Robotics | Numerical Analysis and Scientific Computing | Operations Research, Systems Engineering and Industrial Engineering
Intelligent Systems and Decision Analytics
PATAT 2014: Proceedings of the 10th International Conference of the Practice and Theory of Automated Timetabling, 26-29 August 2014
City or Country
GUNAWAN, Aldy; YUAN, Zhi; and LAU, Hoong Chuin.
A mathematical model and metaheuristics for Time Dependent Orienteering Problem. (2014). PATAT 2014: Proceedings of the 10th International Conference of the Practice and Theory of Automated Timetabling, 26-29 August 2014. 202-217. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/2669
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.