Accepted Paper at SIAM SDM 2024

Authors

Niklas Strauß and Matthias Schubert

SIAM International Conference on Data Mining (SDM 2024),
18–20 April 2024, Houston, Texas, USA

Abstract

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 vari- ous solutions exist, these methods often struggle to take the implications of actions on the ability to fine future park- ing 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 vi- olations after executing an action. We evaluate our method using an environment based on real-world data from Mel- bourne. Our results show that SATOP consistently outperforms state-of-the-art TOP agents and is able to fine up to 22% more parking offenses.