Combinatorial Optimization Augmented Machine Learning for Dynamic Electric Autonomous Dial-a-Ride Problem
Abstract
This study introduces a decision-epoch-based dynamic electric autonomous dial-a-ride problem (Dyn-EADARP), in which incoming requests are collected and processed at periodic decision epochs. A key decision is not only how to serve requests, but also when to dispatch them. At each decision epoch, the service provider decides which requests to serve and which to postpone, while jointly determining vehicle routes, schedules, and charging decisions. Unexecuted parts of existing plans can be revised as new information becomes available. To solve this problem, we develop an ML--CO policy following the combinatorial optimization augmented machine learning (COAML) framework, which combines a statistical model with a combinatorial optimization layer for decision making. The statistical model predicts prizes for available requests, and a prize-collecting E-ADARP uses these prizes to jointly determine request selection, routing, scheduling, and charging. The statistical model is trained directly to improve the decisions produced by the optimization layer. Computational experiments on 320 test instances demonstrate the efficiency of ML--CO, which solves instances with nearly 500 requests in about 6 seconds on average. It achieves 8.7%--14.3% lower objective values than benchmark policies and an average gap of 4.8% to the anticipative reference. The results provide several managerial insights. First, serving requests immediately is not always best, as selectively postponing some requests can create better ride-sharing opportunities. Second, revising existing plans preserves operational flexibility and substantially improves solution quality. Finally, more frequent decision making does not necessarily improve performance, highlighting the importance of choosing an appropriate decision frequency.
Related
- EnerGNN: Learning Optimization-Compatible Energy Functions for Exact Constrained Combinatorial Inference
- Generic Machine Learning-Based Sparsification for Arc Flow Formulation of Combinatorial Optimization Problems
- Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon
- Learning-Augmented Optimization for Strategic Two-Echelon Spare Parts Network Design
- On Sparse Graph Limits for Neural Combinatorial Optimization
BibTeX
@misc{su2026combinatorial,
title = {{Combinatorial Optimization Augmented Machine Learning for Dynamic Electric Autonomous Dial-a-Ride Problem}},
author = {Yue Su and Léa Ricard},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.22495},
eprint = {2609.22495},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.22495},
}
RIS
TY - UNPB
TI - Combinatorial Optimization Augmented Machine Learning for Dynamic Electric Autonomous Dial-a-Ride Problem
AU - Yue Su
AU - Léa Ricard
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.22495
UR - https://arxiv.org/abs/2609.22495
AB - This study introduces a decision-epoch-based dynamic electric autonomous dial-a-ride problem (Dyn-EADARP), in which incoming requests are collected and processed at periodic decision epochs. A key decision is not only how to serve requests, but also when to dispatch them. At each decision epoch, the service provider decides which requests to serve and which to postpone, while jointly determining vehicle routes, schedules, and charging decisions. Unexecuted parts of existing plans can be revised as new information becomes available. To solve this problem, we develop an ML--CO policy following the combinatorial optimization augmented machine learning (COAML) framework, which combines a statistical model with a combinatorial optimization layer for decision making. The statistical model predicts prizes for available requests, and a prize-collecting E-ADARP uses these prizes to jointly determine request selection, routing, scheduling, and charging. The statistical model is trained directly to improve the decisions produced by the optimization layer. Computational experiments on 320 test instances demonstrate the efficiency of ML--CO, which solves instances with nearly 500 requests in about 6 seconds on average. It achieves 8.7%--14.3% lower objective values than benchmark policies and an average gap of 4.8% to the anticipative reference. The results provide several managerial insights. First, serving requests immediately is not always best, as selectively postponing some requests can create better ride-sharing opportunities. Second, revising existing plans preserves operational flexibility and substantially improves solution quality. Finally, more frequent decision making does not necessarily improve performance, highlighting the importance of choosing an appropriate decision frequency.
ER -