Premium
A multifaceted heuristic for the orienteering problem
Author(s) -
Golden B. L.,
Wang Qiwen,
Liu Li
Publication year - 1988
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(198806)35:3<359::aid-nav3220350305>3.0.co;2-h
Subject(s) - orienteering , heuristics , heuristic , mathematical optimization , selection (genetic algorithm) , computer science , randomness , path (computing) , mathematics , artificial intelligence , statistics , programming language
The orienteering problem involves the selection of a path between an origin and a destination which maximizes total score subject to a time restriction. In previous work we presented an effective heuristic for this NP‐hard problem that outperformed other heuristics from the literature. In this article we describe and test a significantly improved procedure. The new procedure is based on four concepts—center of gravity, randomness, subgravity, and learning. These concepts combine to yield a procedure which is much faster and which results in more nearly optimal solutions than previous procedures.