An Exact Branch-and-Cut Method for the Asymmetric Orienteering Problem with Terrain-Driven Fatigue

Preprint — under review, 2026 · Optimization Online

Orienteering is a sport where a runner must visit a set of checkpoints within a time budget. When time is limited, a selection problem arises: which checkpoints to visit and which to skip. This is the Orienteering Problem (OP). Most of the literature assumes symmetric travel costs, an assumption that breaks down on real terrain. In this paper, a GIS pipeline combines orienteering map symbols, a digital elevation model and the Minetti metabolic model into a fully asymmetric cost matrix, where directional slope costs and cumulative fatigue make travel cost depend on both direction and elapsed effort. This gives rise to a new variant of the problem, the Asymmetric Orienteering Problem with Fatigue (AOPF), for which we develop tailored exact methods: two formulations (an MTZ-based model with McCormick linearisation and a single-commodity flow formulation) and a branch-and-cut solver strengthened with routing infeasibility cuts, tightened flow-arc coupling bounds, fatigue-aware lifted covers, and directed adaptations of cycle cover and path inequalities. We validate the framework on two Spanish terrains across seven control-point distributions each, and release a parameterised benchmark suite of 66 instances. The flow-based solver certifies global optimality on 11 of 14 real-terrain instances (all with at most 40 control points) within a 15-minute time limit, with tighter LP gaps than the MTZ formulation (mean gap 11.4% vs. 20.0% on benchmark instances).