Solving large-scale dynamic vehicle routing problems with stochastic requests
From MaRDI portal
Publication:6106486
Abstract: Dynamic vehicle routing problems (DVRPs) arise in several applications such as technician routing, meal delivery, and parcel shipping. We consider the DVRP with stochastic customer requests (DVRPSR), in which vehicles must be routed dynamically with the goal of maximizing the number of served requests. We model the DVRPSR as a multi-stage optimization problem, where the first-stage decision defines route plans for serving scheduled requests. Our main contributions are knapsack-based linear models to approximate accurately the expected reward-to-go, measured as the number of accepted requests, at any state of the stochastic system. These approximations are based on representing each vehicle as a knapsack with a capacity given by the remaining service time available along the vehicle's route. We combine these approximations with optimal acceptance and assignment decision rules and derive efficient and high-performing online scheduling policies. We further leverage good predictions of the expected reward-to-go to design initial route plans that facilitate serving dynamic requests. Computational experiments on very large instances based on a real street network demonstrate the effectiveness of the proposed methods in prescribing high-quality offline route plans and online scheduling decisions.
Recommendations
- Vehicle Routing with Stochastic Demands: Properties and Solution Frameworks
- An approximate dynamic programming approach for the vehicle routing problem with stochastic demands
- Vehicle routing problem with stochastic demand
- A Vehicle Routing Problem with Stochastic Demand
- Dynamic vehicle routing with priority classes of stochastic demands
- The stochastic vehicle routing problem revisited
- AN EFFICIENTLY NOVEL MODEL FOR VEHICLE ROUTING PROBLEMS WITH STOCHASTIC DEMANDS
- A new approach to partial constraint satisfaction problems
- Reoptimization Approaches for the Vehicle-Routing Problem with Stochastic Demands
Cites work
- A dynamic vehicle routing problem with multiple delivery routes
- A review of dynamic vehicle routing problems
- A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane
- Adaptive Routing on the Plane
- Approximate dynamic programming. Solving the curses of dimensionality
- Branch-and-price: Column generation for solving huge integer programs
- scientific article; zbMATH DE number 1321699 (Why is no real title available?)
- Meso-parametric value function approximation for dynamic customer acceptances in delivery routing
- New route relaxation and pricing strategies for the vehicle routing problem
- Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching
- Partially dynamic vehicle routing—models and algorithms
- Pro-active real-time routing in applications with multiple request patterns
- Same-day delivery with pickup stations and autonomous vehicles
- Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers
- Stochastic dynamic vehicle routing in the light of prescriptive analytics: a review
- The dynamic dispatch waves problem for same-day delivery
- The vehicle routing problem
- Value function approximation for dynamic multi-period vehicle routing
Cited in
(15)- Maximizing the number of served requests in an online shared transport system by solving a dynamic DARP
- Time-dependent stochastic vehicle routing problem with random requests: application to online police patrol management in Brussels
- Optimizing large on-demand transportation systems through stochastic conic programming
- Horizontal combinations of online and offline approximate dynamic programming for stochastic dynamic vehicle routing
- Off-line approximate dynamic programming for the vehicle routing problem with a highly variable customer basis and stochastic demands
- Dynamic parcel pick-up routing problem with prioritized customers and constrained capacity via lower-bound-based rollout approach
- Dynamic priority rules for combining on-demand passenger transportation and transportation of goods
- An online reinforcement learning approach to charging and order-dispatching optimization for an e-hailing electric vehicle fleet
- Balancing resources for dynamic vehicle routing with stochastic customer requests
- Dynamic migratory beekeeping route recommendation based on spatio-temporal distribution of nectar sources
- Dynamic crowdsourcing problem in urban-rural distribution using the learning-based approach
- Knowledge-guided hybrid deep reinforcement learning for the dynamic multi-depot electric vehicle routing problem
- Deep reinforcement learning for solving the stochastic e-waste collection problem
- Emerging optimization problems for distribution in same-day delivery
- Meal delivery routing problem with stochastic meal preparation times and customer locations
This page was built for publication: Solving large-scale dynamic vehicle routing problems with stochastic requests
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6106486)
