Title: A fast solution method for the time-dependent orienteering problem
Authors: Verbeeck, Cedric ×
Sörensen, Kenneth
Aghezzaf, El-Houssaine
Vansteenwegen, Pieter #
Issue Date: 2014
Publisher: Elsevier
Series Title: European Journal of Operational Research vol:236 pages:419-432
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.
ISSN: 0377-2217
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Centre for Industrial Management / Traffic & Infrastructure
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
A fast solution method for the time-dependent orienteering problem_.pdf Published 439KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science