Reinforcement Learning Approaches for the Orienteering Problem with Stochastic and Dynamic Release Dates

Yuanyuan Li (), Claudia Archetti () and Ivana Ljubić ()
Additional contact information
Yuanyuan Li: Department of Information Systems, Decision Sciences and Statistics, ESSEC Business School, 95021 Cergy-Pontoise Cedex, France
Claudia Archetti: Department of Information Systems, Decision Sciences and Statistics, ESSEC Business School, 95021 Cergy-Pontoise Cedex, France
Ivana Ljubić: Department of Information Systems, Decision Sciences and Statistics, ESSEC Business School, 95021 Cergy-Pontoise Cedex, France

Transportation Science, 2024, vol. 58, issue 5, 1143-1165

Abstract: 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 expected number of parcels that can be delivered during service hours. We propose two reinforcement learning (RL) approaches for solving this problem. These approaches rely on a look-ahead strategy in which future release dates are sampled in a Monte Carlo fashion, and a batch approach is used to approximate future routes. Both RL approaches are based on value function approximation: One combines it with a consensus function (VFA-CF) and the other one with a two-stage stochastic integer linear programming model (VFA-2S). VFA-CF and VFA-2S do not need extensive training as they are based on very few hyperparameters and make good use of integer linear programming (ILP) and 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 VFA-CF/VFA-2S. In an empirical study, we conduct a competitive analysis using upper bounds with perfect information. We also show that VFA-CF and VFA-2S greatly outperform alternative approaches that (1) do not rely on future information (2) are based on point estimation of future information, (3) use heuristics rather than exact methods, or (4) use exact evaluations of future rewards.

Keywords: reinforcement learning; two-stage stochastic ILP model; branch-and-cut; Markov decision process; orienteering problem (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.0366 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:58:y:2024:i:5:p:1143-1165

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().