Publication
Title
A fast solution method for the time-dependent orienteering problem
Author
Abstract
This paper introduces a fast solution procedure to solve 100-node instances of the time-dependent orienteering problem (TD-OP) within a few seconds of computation time. Orienteering problems occur in logistic situations were an optimal combination of locations needs to be selected and the routing between the selected locations needs to be optimized. In the time-dependent variant, the travel time between two locations depends on the departure time at the first location. Next to a mathematical formulation of the TD-OP, the main contribution of this paper is the design of a fast and effective algorithm to tackle this problem. This algorithm combines the principles of an ant colony system (ACS) with a time-dependent local search procedure equipped with a local evaluation metric. Additionally, realistic benchmark instances with varying size and properties are constructed. The average score gap with the known optimal solution on these test instances is only 1.4% with an average computation time of 0.5 seconds. An extensive sensitivity analysis shows that the performance of the algorithm is insensitive to small changes in its parameter settings. (c) 2013 Elsevier B.V. All rights reserved.
Language
English
Source (journal)
European journal of operational research. - Amsterdam
Publication
Amsterdam : 2014
ISSN
0377-2217
Volume/pages
236:2(2014), p. 419-432
ISI
000334143100004
Full text (Publishers DOI)
Full text (publishers version - intranet only)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Web of Science
Record
Identification
Creation 06.06.2014
Last edited 17.05.2017
To cite this reference