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

Demand Acceptance using Reinforcement Learning for Dynamic Vehicle Routing Problem with Emission Quota
Feb 27, 2026Farid Najar, Dominique Barth, Yann StrozeckiVehicle Routing Stochastic Optimization
1DAVID Lab, UVSQ Versailles, France
Dynamic Multi-Depot Vehicle Routing with Online Requests: Event-Driven Transformer--DRL and Rolling-Horizon Benchmarking
Aug 13, 2026Faezeh Ardali, Gerald M. KnappVehicle Routing RL for Combinatorial Optimization
Department of Industrial Engineering, Louisiana State University, Baton Rouge, LA, USA
Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency
Jul 7, 2026Manish Kolachalam, Rani MalhotraVehicle Routing Greedy Optimization
Autonomous Machines Applied Research Center Infosys Center for Imaging Technologies, Infosys Bengaluru, India

Feb 27, 2026J/K move · Enter open · S save

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

Farid Najar, Dominique Barth, Yann Strozecki

1DAVID Lab, UVSQ Versailles, France

Vehicle Routing Stochastic Optimization RL for Combinatorial Optimization

Open paper AskPDF arXiv

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.

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