Dynamic Vehicle Routing Problem with Prompt Confirmation of Advance Requests

Amutheezan Sivagnanam; Ayan Mukhopadhyay; Samitha Samaranayake; Abhishek Dubey; Aron Laszka

cs.AIMar 8, 2026

Dynamic Vehicle Routing Problem with Prompt Confirmation of Advance Requests

Authors: Amutheezan Sivagnanam, Ayan Mukhopadhyay, Samitha Samaranayake, Abhishek Dubey, Aron Laszka

Organizations: Department of Informatics and Intelligent Systems, Pennsylvania State University, University Park, Pennsylvania · Department of Computer Science, College of William & Mary, Williamsburg, Virginia · School of Civil and Environmental Engineering, Cornell University, Ithaca, New York · College of Connected Computing, Vanderbilt University, Nashville, Tennessee

Abstract

Transit agencies that operate on-demand transportation services have to respond to trip requests from passengers in real time, which involves solving dynamic vehicle routing problems with pick-up and drop-off constraints. Based on discussions with public transit agencies, we observe a real-world problem that is not addressed by prior work: when trips are booked in advance (e.g., trip requests arrive a few hours in advance of their requested pick-up times), the agency needs to promptly confirm whether a request can be accepted or not, and ensure that accepted requests are served as promised. State-of-the-art computational approaches either provide prompt confirmation but lack the ability to continually optimize and improve routes for accepted requests, or they provide continual optimization but cannot guarantee serving all accepted requests. To address this gap, we introduce a novel problem formulation of dynamic vehicle routing with prompt confirmation and continual optimization. We propose a novel computational approach for this vehicle routing problem, which integrates a quick insertion search for prompt confirmation with an anytime algorithm for continual optimization. To maximize the number requests served, we train a non-myopic objective function using reinforcement learning, which guides both the insertion and the anytime algorithms towards optimal, non-myopic solutions. We evaluate our computational approach on a real-world microtransit dataset from a public transit agency in the U.S., demonstrating that our proposed approach provides prompt confirmation while significantly increasing the number of requests served compared to existing approaches.

Figures & tables

Panel of Figure 1 — Fig. 1: During service, (1) requests arrive following a known distribution (e.g., based on historical data); (2) upon the arrival of each request, we decide whether to accept or reject the request given the current state of the service; (3) we promptly notify the passenger of our decision; (4) until the next request arrives, we continuously optimize route plans to better accommodate future requests. Symbols $p_{k}$ and $d_{k}$ represent the pickup and dropoff of request $k$ , respectively.

Variables
Symbol	Description
$\mathcal{T}_{t}$	Set of requests that arrived as of time $t$
$\mathcal{T}^{\textit{accept}}_{t}$	Set of requests that are part of route plans at time $t$
Constants
$\mathcal{L}$	Set of locations
$\mathcal{V}$	Set of vehicles

TABLE I: List of Symbols

Panel of Figure 3 — Fig. 2: Distribution of request rejection rates across 5 different episodes from the real-world microtransit data.

Panel of Figure 4 — Fig. 3: Distribution of request rejection rates across 5 different episodes from the NYC taxi data.

Panel of Figure 5 — Fig. 4: Distribution of rejection rates across 5 different episodes from the real-world microtransit data, with various running-time limits for the anytime algorithm (in seconds).

Appendix figures & tables20 assets

Supplementary material from the paper’s appendix.

Appendix

Neural Network Architecture: MLP
Name of the Hyperparameter	Microtransit Data	NYC Taxi Data
Number of Hidden Layers	3	2
Number of Neurons	[64, 128, 128]	[128, 128]
Dropout Rate	0.1	0.2
Neural Network Architecture: KAN
Name of the Hyperparameter	Microtransit Data	NYC Taxi Data

Appendix

TABLE II: Neural-Network Hyperparameters

Feature Selection: MLP
Name of the Parameter	Microtransit Data	NYC Taxi Data
Feature Combination	$\boldsymbol{x},\boldsymbol{x}_{a}$	$\boldsymbol{x},\boldsymbol{x}_{a}$
Grid dimension ( g )	1	3
Multiple of window ( $N_{wm}$ )	2	2
Number of subsequent intervals ( $N_{ci}$ )	1	1
Number of idle vehicle at an interval ( $N_{mv}$ )	1	1

Appendix

TABLE III: Feature Vector Combination

Panel of Figure 8 — Fig. 5: Distribution of rejection rates for the trained policy $\pi^{*}$ with neural-network architectures based on MLP ( $\blacksquare$ ), KAN ( $\blacksquare$ ), and CNN ( $\blacksquare$ ), across 5 different episodes from the microtransit data .

Panel of Figure 9 — Fig. 6: Distribution of rejection rates for the trained policy $\pi^{*}$ with neural-network architectures based on MLP ( $\blacksquare$ ), KAN ( $\blacksquare$ ), and CNN ( $\blacksquare$ ), across 5 different episodes from the NYC taxi data .

Panel of Figure 10 — Fig. 7: Distribution of rejection rates for various running-time limits on the anytime algorithm (in seconds, horizontal axis) with trained policies $\pi^{*}$ based on MLP ( $\blacksquare$ ), KAN ( $\blacksquare$ ), and CNN ( $\blacksquare$ ), across 5 different episodes from the microtransit data .

Panel of Figure 11 — Fig. 8: Distribution of rejection rates for various running-time limits on the anytime algorithm (in seconds, horizontal axis) with trained policies $\pi^{*}$ based on MLP ( $\blacksquare$ ), KAN ( $\blacksquare$ ), and CNN ( $\blacksquare$ ), across 5 different episodes from the NYC taxi data .

Settings	Insertion Decision	Acceptance Decision	Anytime Optimization	Service Rate
A	$\pi^{0}$	Always Accept ( $\pi^{0}$ )	$\pi^{0}$	98.64
B	$\pi^{0}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{*}$	98.83
C	$\pi^{*}$	Always Accept ( $\pi^{*}$ )	$\pi^{0}$	98.70
D	$\pi^{*}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{0}$	98.86
E	$\pi^{*}$	Always Accept ( $\pi^{*}$ )	$\pi^{*}$	99.06
Our	$\pi^{*}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{*}$	98.83

Appendix

TABLE IV: Average service rate across 5 different episodes from microtransit data evaluated using the decision making choices while using learned

Q

-function using MLP based architecture.

Settings	Insertion Decision	Acceptance Decision	Anytime Optimization	Service Rate
A	$\pi^{0}$	Always Accept ( $\pi^{0}$ )	$\pi^{0}$	98.64
B	$\pi^{0}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{*}$	98.25
C	$\pi^{*}$	Always Accept ( $\pi^{*}$ )	$\pi^{0}$	98.67
D	$\pi^{*}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{0}$	98.80
E	$\pi^{*}$	Always Accept ( $\pi^{*}$ )	$\pi^{*}$	98.67
Our	$\pi^{*}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{*}$	98.77

Appendix

TABLE V: Average service rate across 5 different episodes from microtransit data evaluated using the decision making choices while using learned

Q

-function using CNN based architecture.

Settings	Insertion Decision	Acceptance Decision	Anytime Optimization	Service Rate
A	$\pi^{0}$	Always Accept ( $\pi^{0}$ )	$\pi^{0}$	98.64
B	$\pi^{0}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{*}$	98.44
C	$\pi^{*}$	Always Accept ( $\pi^{*}$ )	$\pi^{0}$	98.57
D	$\pi^{*}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{0}$	98.80
E	$\pi^{*}$	Always Accept ( $\pi^{*}$ )	$\pi^{*}$	98.83
Our	$\pi^{*}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{*}$	98.99

Appendix

TABLE VI: Average service rate across 5 different episodes from microtransit data evaluated using the decision making choices while using learned

Q

-function using KAN based architecture.

Settings	Insertion Decision	Acceptance Decision	Anytime Optimization	Service Rate
A	$\pi^{0}$	Always Accept ( $\pi^{0}$ )	$\pi^{0}$	98.70
B	$\pi^{0}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{*}$	98.95
C	$\pi^{*}$	Always Accept ( $\pi^{*}$ )	$\pi^{0}$	99.00
D	$\pi^{*}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{0}$	99.29
E	$\pi^{*}$	Always Accept ( $\pi^{*}$ )	$\pi^{*}$	98.84
Our	$\pi^{*}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{*}$	98.93

Appendix

TABLE VII: Average service rate across 5 different episodes from NYC taxi data evaluated using the decision making choices while using learned

Q

-function using MLP based architecture.

Settings	Insertion Decision	Acceptance Decision	Anytime Optimization	Service Rate
A	$\pi^{0}$	Always Accept ( $\pi^{0}$ )	$\pi^{0}$	98.70
B	$\pi^{0}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{*}$	98.47
C	$\pi^{*}$	Always Accept ( $\pi^{*}$ )	$\pi^{0}$	98.95
D	$\pi^{*}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{0}$	99.02
E	$\pi^{*}$	Always Accept ( $\pi^{*}$ )	$\pi^{*}$	98.35
Our	$\pi^{*}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{*}$	98.26

Appendix

TABLE VIII: Average service rate across 5 different episodes from NYC taxi data evaluated using the decision making choices while using learned

Q

-function using CNN based architecture.

Settings	Insertion Decision	Acceptance Decision	Anytime Optimization	Service Rate
A	$\pi^{0}$	Always Accept ( $\pi^{0}$ )	$\pi^{0}$	98.70
B	$\pi^{0}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{*}$	98.72
C	$\pi^{*}$	Always Accept ( $\pi^{*}$ )	$\pi^{0}$	99.00
D	$\pi^{*}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{0}$	99.00
E	$\pi^{*}$	Always Accept ( $\pi^{*}$ )	$\pi^{*}$	98.84
Our	$\pi^{*}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{*}$	99.05

Appendix

TABLE IX: Average service rate across 5 different episodes from NYC taxi data evaluated using the decision making choices while using learned

Q

-function using KAN based architecture.

Settings	Insertion Decision	Acceptance Decision	Anytime Optimization	Service Rate
A	$\pi^{0}$	Always Accept ( $\pi^{0}$ )	$\pi^{0}$	56.67
B	$\pi^{0}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{*}$	57.91
C	$\pi^{*}$	Always Accept ( $\pi^{*}$ )	$\pi^{0}$	57.17
D	$\pi^{*}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{0}$	56.83
E	$\pi^{*}$	Always Accept ( $\pi^{*}$ )	$\pi^{*}$	58.17
Our	$\pi^{*}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{*}$	58.33

Appendix

TABLE X: Average service rate across 5 different episodes from abstract environment evaluated using the decision making choices while using learned Q function using MLP based architecture.

Settings	Insertion Decision	Acceptance Decision	Anytime Optimization	Service Rate
A	$\pi^{0}$	Always Accept ( $\pi^{0}$ )	$\pi^{0}$	56.67
B	$\pi^{0}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{*}$	59.08
C	$\pi^{*}$	Always Accept ( $\pi^{*}$ )	$\pi^{0}$	56.84
D	$\pi^{*}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{0}$	57.92
E	$\pi^{*}$	Always Accept ( $\pi^{*}$ )	$\pi^{*}$	58.00
Our	$\pi^{*}$	Accept/Reject ( $\pi^{*}$ )	$\pi^{*}$	59.17

Appendix

TABLE XI: Average service rate across 5 different episodes from abstract environment evaluated using the decision making choices while using learned Q function using CNN based architecture.

Panel of Figure 20 — Fig. 9: Distribution of rejection rates when using MC VRP as the dynamic VRP solver with different running times per decision epoch, across 5 different episodes from the microtransit data .

Panel of Figure 21 — Fig. 10: Distribution of rejection rates when using MC VRP as the dynamic VRP solver with different running times per decision epoch, across 5 different episodes from the NYC taxi data .

Panel of Figure 22 — Fig. 11: Distribution of rejection rates when using Rolling Horizon solver at each decision epoch with rolling-horizon factors RH1 ( $\blacksquare$ ) and RH2 ( $\blacksquare$ ), across 5 different episodes from the microtransit data .

Panel of Figure 23 — Fig. 12: Distribution of average computation time for each decision epoch when using Rolling Horizon solver with rolling-horizon factors RH1 ( $\blacksquare$ ) and RH2 ( $\blacksquare$ ), across 5 different episodes from the microtransit data .

Panel of Figure 24 — Fig. 13: Distribution of rejection rates when using Rolling Horizon solver at each decision epoch with rolling-horizon factors RH1 ( $\blacksquare$ ) and RH2 ( $\blacksquare$ ), across 5 different episodes from the NYC taxi data .

Panel of Figure 25 — Fig. 14: Distribution of average computation time for each decision epoch when using Rolling Horizon solver with rolling-horizon factors RH1 ( $\blacksquare$ ) and RH2 ( $\blacksquare$ ), across 5 different episodes from the NYC taxi data .

Vehicle Routing

Vehicle routing studies how to assign and sequence trips for fleets while meeting capacity, time, energy, and service constraints.

See all 135 papers

Feb 27, 2026

Demand Acceptance using Reinforcement Learning for Dynamic Vehicle Routing Problem with Emission Quota

This paper introduces and formalizes the Dynamic and Stochastic Vehicle Routing Problem with Emission Quota (DS-QVRP-RR), a novel routing problems that integrates dynamic demand acceptance and routing with a global emission constraint. A key contribution is a two-layer optimization framework designed to facilitate anticipatory rejections of demands and generation of new routes. To solve this, we develop hybrid algorithms that combine reinforcement learning with combinatorial optimization techniques. We present a comprehensive computational study that compares our approach against traditional methods. Our findings demonstrate the relevance of our approach for different types of inputs, even when the horizon of the problem is uncertain.

Farid Najar, Dominique Barth, Yann Strozecki

1DAVID Lab, UVSQ Versailles, France

Vehicle Routing Stochastic Optimization RL for Combinatorial Optimization

Ask PDF

Aug 13, 2026

Dynamic Multi-Depot Vehicle Routing with Online Requests: Event-Driven Transformer--DRL and Rolling-Horizon Benchmarking

This paper presents an event-driven learning and benchmarking framework for the Dynamic Multi-Depot Vehicle Routing Problem with progressively revealed requests and evolving vehicle states. Masked MLP and Transformer policies are trained through behavior cloning and proximal policy optimization. Deterministic feasibility masking prevents invalid vehicle--request assignments, while fixed-prefix/flexible-suffix route commitments protect completed, active, and near-term decisions and separately measure vehicle reassignment and resequencing. The learned policies are compared with dynamic insertion heuristics and time-limited rolling-horizon optimization. In a 20-scenario policy benchmark, all methods completed every request without invalid actions, but nearest feasible achieved the lowest mean objective and outperformed the learned policies in routing quality, waiting time, stability, makespan, and runtime. Across five independent training runs, PPO had little average effect on the MLP and improved the Transformer on average, although with greater seed variability. Under the common protocol, nearest feasible achieved the lowest combined objective and route disruption, whereas rolling horizon achieved the lowest waiting times and makespan at substantially higher computational cost. The learned policies retained millisecond-level decisions and transferred to instances with up to 80 requests without retraining, but did not outperform the strongest heuristic. No single method was best across routing efficiency, service responsiveness, stability, and online computation.

Faezeh Ardali, Gerald M. Knapp

Department of Industrial Engineering, Louisiana State University, Baton Rouge, LA, USA

Vehicle Routing RL for Combinatorial Optimization Transformer-Based RL

Ask PDF

Jul 7, 2026

Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency

The Vehicle Routing Problem (VRP) and its variants represent some of the most practically consequential optimization challenges in modern logistics and urban mobility. In this study, we address a dynamic, online variant combining elements of the VRP and the Orienteering Problem (OP), in which a fleet of vehicles must maximise cumulative reward collected within a fixed time horizon while continuously replanning as new tasks arrive. We propose and evaluate a reward-density heuristic for dynamic multi-vehicle assignment, referred to as the Efficiency heuristic. We evaluate this formulation across two application domains: autonomous drone task allocation and urban taxi dispatch, across multiple fleet sizes and task scales. The proposed method is compared with four classical construction heuristics and three metaheuristic algorithms (Adaptive Large Neighbourhood Search, Genetic Algorithm, and Simulated Annealing), all evaluated under identical conditions. Across all tested configurations, the Efficiency heuristic matches the solution quality of the best metaheuristic algorithms while requiring two to three orders of magnitude less planning time, establishing Pareto dominance over all competing methods on the reward-versus-compute frontier. These findings suggest a practical design principle for real-time allocation and dispatch systems: in dynamic, time-constrained routing environments, carefully designed greedy heuristics can match the output of sophisticated search procedures at a fraction of the computational cost, making them preferable for online deployment.

Manish Kolachalam, Rani Malhotra

Autonomous Machines Applied Research Center Infosys Center for Imaging Technologies, Infosys Bengaluru, India

Vehicle Routing Greedy Optimization

Ask PDF

Abstract

Vehicle Routing

Explore similar work

Demand Acceptance using Reinforcement Learning for Dynamic Vehicle Routing Problem with Emission Quota

Dynamic Multi-Depot Vehicle Routing with Online Requests: Event-Driven Transformer--DRL and Rolling-Horizon Benchmarking

Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency