Spatial-Aware Deep Reinforcement Learning for the Traveling Officer
  Problem
Niklas Strauß Matthias Schubert
The traveling officer problem (TOP) is a challenging stochastic optimization
task. In this problem, a parking officer is guided through a city equipped with
parking sensors to fine as many parking offenders as possible. A major
challenge in TOP is the dynamic nature of parking offenses, which randomly
appear and disappear after some time, regardless of whether they have been
fined. Thus, solutions need to dynamically adjust to currently fineable parking
offenses while also planning ahead to increase the likelihood that the officer
arrives during the offense taking place. Though various solutions exist, these
methods often struggle to take the implications of actions on the ability to
fine future parking violations into account. This paper proposes SATOP, a novel
spatial-aware deep reinforcement learning approach for TOP. Our novel state
encoder creates a representation of each action, leveraging the spatial
relationships between parking spots, the agent, and the action. Furthermore, we
propose a novel message-passing module for learning future inter-action
correlations in the given environment. Thus, the agent can estimate the
potential to fine further parking violations after executing an action. We
evaluate our method using an environment based on real-world data from
Melbourne. Our results show that SATOP consistently outperforms
state-of-the-art TOP agents and is able to fine up to 22% more parking
offenses.