A Spatio-Temporal Representation for the Orienteering Problem with
  Time-Varying Profits
  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.
