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

arXiv: https://arxiv.org/abs/2207.00885 · HTML: https://mlsanity.com/paper/2207.00885/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 63 references that are in the map.
- First posted on arXiv 2 Jul 2022.

## Builds on (most cited first, 3 of 3)

- [Deep Q-Learning for Same-Day Delivery with Vehicles and Drones](https://mlsanity.com/paper/1910.11901/) (2019)
- [Same-Day Delivery with Fairness](https://mlsanity.com/paper/2007.09541/) (2020)
- [Fighting the E-commerce Giants: Efficient Routing and Effective Consolidation for Local Delivery Platforms](https://mlsanity.com/paper/2108.12608/) (2021)

## Built on by (most cited first, 2 of 2)

- [Improving After-sales Service: Deep Reinforcement Learning for Dynamic Time Slot Assignment with Commitments and Customer Preferences](https://mlsanity.com/paper/2509.17870/) (2025)
- [GREAT-EER: Graph Edge Attention Network for Emergency Evacuation Responses](https://mlsanity.com/paper/2602.14676/) (2026)

## Abstract (arXiv)

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 hyper-parameters 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, or 2) are based on point estimation of future information, or 3) employ heuristics rather than exact methods, or 4) use exact evaluations of future rewards.