A Spatio-Temporal Representation for the Orienteering Problem with Time-Varying Profits
This addresses a variant of the orienteering problem relevant for logistics and routing applications where profits are dynamic, though it is incremental as it builds on existing methods by incorporating time variations.
The paper tackles the orienteering problem with time-varying profits, where profits change arbitrarily over time, by proposing a spatio-temporal representation framework that unifies spatial and temporal aspects into a routing topology, resulting in near-optimal solutions computed efficiently with basic algorithms.
We consider an orienteering problem (OP) where an agent needs to visit a series (possibly a subset) of depots, from which the maximal accumulated profits are desired within given limited time budget. Different from most existing works where the profits are assumed to be static, in this work we investigate a variant that has arbitrary time-dependent profits. Specifically, the profits to be collected change over time and they follow different (e.g., independent) time-varying functions. The problem is of inherent nonlinearity and difficult to solve by existing methods. To tackle the challenge, we present a simple and effective framework that incorporates time-variations into the fundamental planning process. Specifically, we propose a deterministic spatio-temporal representation where both spatial description and temporal logic are unified into one routing topology. By employing existing basic sorting and searching algorithms, the routing solutions can be computed in an extremely efficient way. The proposed method is easy to implement and extensive numerical results show that our approach is time efficient and generates near-optimal solutions.