×

The orienteering problem. (English) Zbl 0647.90099

Summary: Orienteering is a sport in which start and end points are specified along with other locations. These other locations have associated scores. Competitors seek to visit, in a fixed amount of time, a subset of these locations on the way from the start point to the end point in order to maximize the total score. An effective center-of-gravity heuristic is presented that outperforms heuristics from the literature.

MSC:

90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
90C10 Integer programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] and , Computers and Intractability, Freeman, San Francisco, 1979.
[2] Golden, Large Scale Systems 7 pp 181– (1984)
[3] Golden, OMEGA 9 pp 439– (1981)
[4] Tsiligirides, Journal of the Operational Research Society 35 pp 797– (1984)
[5] Wren, Operational Research Quarterly 23 pp 333– (1972)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.