  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.
