A Deep Reinforcement Learning Approach for Online Parcel Assignment
This work addresses a stochastic logistics optimization problem for parcel delivery companies, offering an incremental improvement over existing methods.
The paper tackles the online parcel assignment problem by proposing a deep reinforcement learning algorithm (PPO-OPA) that models it as a Markov Decision Process, achieving lower total cost and reduced constraint violations compared to traditional proportional assignment methods, with performance comparable to a primal-dual algorithm that requires unrealistic prior knowledge.
In this paper, we investigate the online parcel assignment (OPA) problem, in which each stochastically generated parcel needs to be assigned to a candidate route for delivery to minimize the total cost subject to certain business constraints. The OPA problem is challenging due to its stochastic nature: each parcel's candidate routes, which depends on the parcel's origin, destination, weight, etc., are unknown until its order is placed, and the total parcel volume is uncertain in advance. To tackle this challenge, we propose the PPO-OPA algorithm based on deep reinforcement learning that shows competitive performance. More specifically, we introduce a novel Markov Decision Process (MDP) framework to model the OPA problem, and develop a policy gradient algorithm that adopts attention networks for policy evaluation. By designing a dedicated reward function, our proposed algorithm can achieve a lower total cost with smaller violation of constraints, comparing to the traditional method which assigns parcels to candidate routes proportionally. In addition, the performances of our proposed algorithm and the Primal-Dual algorithm are comparable, while the later assumes a known total parcel volume in advance, which is unrealistic in practice.