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

We present an end-to-end computational framework for provably optimal route planning in orienteering races on real terrain. The framework consists of a GIS pipeline that combines International Orienteering Federation (IOF) map symbols, a digital elevation model (DEM), 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. The terrain realities captured by this pipeline lead to a new problem variant of the Orienteering Problem (OP), the Asymmetric Orienteering Problem with Fatigue (AOPF), for which we develop tailored exact solution methods. We propose two LP formulations: an MTZ-based model with McCormick linearisation and a single-commodity flow formulation. We strengthen the Branch-and-Cut solver with routing infeasibility cuts, alongside 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 for the asymmetric OP with fatigue. The flow-based B&C certifies global optimality on 11 of 14 real-terrain instances (all ≤ 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).

Article

Download

View PDF