  Same-Day Delivery services are becoming increasingly popular in recent years.
These have been usually modelled by previous studies as a certain class of
Dynamic Vehicle Routing Problem (DVRP) where goods must be delivered from a
depot to a set of customers in the same day that the orders were placed.
Adaptive exact solution methods for DVRPs can become intractable even for small
problem instances. In this paper, we formulate the SDDP as a Markov Decision
Process (MDP) and solve it using a parameter-sharing Deep Q-Network, which
corresponds to a decentralised Multi-Agent Reinforcement Learning (MARL)
approach. For this, we create a multi-agent grid-based SDD environment,
consisting of multiple vehicles, a central depot and dynamic order generation.
In addition, we introduce zone-specific order generation and reward
probabilities. We compare the performance of our proposed MARL approach against
a Mixed Inter Programming (MIP) solution. Results show that our proposed MARL
framework performs on par with MIP-based policy when the number of orders is
relatively low. For problem instances with higher order arrival rates,
computational results show that the MARL approach underperforms the MIP by up
to 30%. The performance gap between both methods becomes smaller when
zone-specific parameters are employed. The gap is reduced from 30% to 3% for a
5x5 grid scenario with 30 orders. Execution time results indicate that the MARL
approach is, on average, 65 times faster than the MIP-based policy, and
therefore may be more advantageous for real-time control, at least for
small-sized instances.
