A novel GRASP solution approach for the Orienteering Problem

The Orienteering Problem (OP) is a well-known variant of the Traveling Salesman Problem. In this paper, a novel Greedy Randomized Adaptive Search Procedure (GRASP) solution is proposed to solve the OP. The proposed method is shown to outperform state-of-the-art heuristics for the OP in producing hig...

Full description

Saved in:
Bibliographic Details
Published in:Journal of heuristics 2016-10, Vol.22 (5), p.699-726
Main Authors: Keshtkaran, Morteza, Ziarati, Koorush
Format: Article
Language:English
Subjects:
Artificial Intelligence
Calculus of Variations and Optimal Control
Optimization
Management Science
Mathematics
Mathematics and Statistics
Operations Research
Operations Research/Decision Theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Orienteering Problem (OP) is a well-known variant of the Traveling Salesman Problem. In this paper, a novel Greedy Randomized Adaptive Search Procedure (GRASP) solution is proposed to solve the OP. The proposed method is shown to outperform state-of-the-art heuristics for the OP in producing high quality solutions. In comparison with the best known solutions of standard benchmark instances, the method can find the optimal or the best known solution of about 70 % of the instances in a reasonable time, which is about 17 % better than the best known approach in the literature. Moreover, a significant improvement is achieved on the solution of two standard benchmark instances.
ISSN:1381-1231
1572-9397
DOI:10.1007/s10732-016-9316-7