Dynamic Vehicle Routing Problem with Prompt Confirmation of Advance Requests

📌 Key Contributions

• Identified a real-world gap in on-demand microtransit services: existing approaches either provide prompt confirmation or continual route optimization, but not both simultaneously
• Introduced a novel problem formulation — Dynamic Vehicle Routing with Prompt Confirmation and Continual Optimization — that guarantees prompt acceptance/rejection decisions while enabling ongoing improvement of vehicle manifests
• Developed a quick insertion algorithm that confirms or rejects each incoming trip request within a fraction of a second, with O(|T|²) worst-case complexity that is fast in practice
• Designed a simulated-annealing anytime algorithm that continuously optimizes route plans between request arrivals, exploiting idle compute time to improve service rates
• Trained a non-myopic objective function (action-value function Q) using reinforcement learning, guiding both the insertion and anytime algorithms toward long-term optimal solutions
• Evaluated across MLP, KAN, and CNN neural network architectures; MLP and KAN achieved the best performance in terms of rejection rate
• Demonstrated on a real-world microtransit dataset that the proposed approach reduces rejection rates to ~1%, significantly outperforming Google OR-Tools, Rolling Horizon, and Monte Carlo VRP baselines — while maintaining sub-second confirmation times

High-Level Overview of the Solution Approach

sequenceDiagram
    participant ENV as Environment<br/>(call center)
    participant INS as Exhaustive Search Insertion<br/>(DRL Agent)
    participant SOLV as Anytime VRP Solver<br/>(DRL Agent)
    participant DB as Requests & Routes

    Note over ENV: New Ride Request received
    ENV->>SOLV: 1. Interrupt anytime solver
    SOLV->>DB: 2. Store improved solution
    ENV->>INS: 3. Send new request
    DB->>INS: 4. Load latest solution
    INS->>ENV: 5. Accept / reject decision
    ENV->>DB: 6. Add request if accepted
    ENV->>SOLV: 7. Trigger anytime solver
    DB->>SOLV: 8. Load latest solution

📝 Publication

This research has been published in: Proceedings of the 17th ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS 2026)
“Dynamic Vehicle Routing Problem with Prompt Confirmation of Advance Requests” [ArXiv]

💻 Code & Data

The source code, simulation environment, and microtransit dataset used in this work are publicly available: [Code & Data]