Reinforcement Learning Approaches for the Orienteering Problem with Stochastic and Dynamic Release Dates
In this paper, we study a sequential decision making problem faced by
e-commerce carriers related to when to send out a vehicle from the central
depot to serve customer requests, and in which order to provide the service,
under the assumption that the time at which parcels arrive at the depot is
stochastic and dynamic. The objective is to maximize the number of parcels that
can be delivered during the service hours. We propose two reinforcement
learning approaches for solving this problem, one based on a policy function
approximation (PFA) and the second on a value function approximation (VFA).
Both methods are combined with a look-ahead strategy, in which future release
dates are sampled in a Monte-Carlo fashion and a tailored batch approach is
used to approximate the value of future states. Our PFA and VFA make a good use
of branch-and-cut-based exact methods to improve the quality of decisions. We
also establish sufficient conditions for partial characterization of optimal
policy and integrate them into PFA/VFA. In an empirical study based on 720
benchmark instances, we conduct a competitive analysis using upper bounds with
perfect information and we show that PFA and VFA greatly outperform two
alternative myopic approaches. Overall, PFA provides best solutions, while VFA
(which benefits from a two-stage stochastic optimization model) achieves a
better tradeoff between solution quality and computing time.