Abstract
In dynamic vehicle routing (DVR), a fleet of vehicles must service demands that arrive stochastically over time and across space. While traditional models treat all demands as equal, real-world applications—ranging from emergency response to UAV-based surveillance—often involve multiple classes of service with varying levels of urgency. This paper addresses the problem of minimizing the weighted sum of expected wait times for different demand classes in a heavy-load regime. We establish a theoretical lower bound on the system's performance and propose a "Separate Queues" (SQ) policy. We prove that this policy provides a constant-factor approximation to the optimal performance, with a bound that is independent of the number of vehicles and arrival rates.
Introduction
Dynamic Vehicle Routing (DVR) problems involve a fleet of mobile agents tasked with servicing demands that appear randomly in a geographic environment. A critical gap in existing DVR literature is the treatment of heterogeneous demand classes. In many practical scenarios, some tasks are significantly more urgent than others, requiring a prioritization strategy that balances immediate needs with long-term system stability.
This research focuses on the "heavy load" regime, where the frequency of incoming requests approaches the maximum service capacity of the fleet. In such states, vehicles are almost constantly occupied, and the choice of routing policy becomes the primary determinant of system latency. The goal is to identify a policy that is not only stable—ensuring that the number of outstanding demands does not grow to infinity—but also mathematically near-optimal in minimizing the weighted wait times across all priority classes.
Methodology
Theoretical Lower Bound
The authors first establish a fundamental performance limit for any possible routing policy. This is achieved by relaxing the constraints of the original problem—specifically, by considering a scenario where a portion of the demands can be serviced without travel time. By applying the asymptotic properties of the Euclidean Traveling Salesperson Problem (TSP), they derive a mathematical "floor" for the weighted wait time that any feasible policy must respect.
The Separate Queues (SQ) Policy
To address the routing challenge, the authors propose the Separate Queues (SQ) policy. Despite its simplicity, the policy is designed to handle complex prioritization. The execution follows three primary steps:
- Environment Partitioning: The service area is divided into $n$ equal regions, with one vehicle assigned exclusively to each region.
- Class Selection: Instead of mixing priorities in a single tour, each vehicle selects a specific demand class $\alpha$ to service based on a calculated probability distribution.
- TSP Tour Execution: The vehicle forms a TSP tour consisting of all currently outstanding demands of the chosen class within its assigned region. Once the tour is completed, the vehicle selects a new class and repeats the process.
Heavy Load Analysis
The performance of the SQ policy is analyzed as the load factor ($\rho$) approaches 1. This asymptotic analysis allows the authors to characterize the policy's behavior in the most challenging operational conditions.
Key Insights
The $2m^2$ Approximation
A central finding of the paper is that the SQ policy is a $2m^2$-factor approximation of the optimal policy, where $m$ represents the number of demand classes. Remarkably, this constant factor is independent of the number of vehicles ($n$), the specific arrival rates ($\lambda$), or the service times ($s$). This suggests that the policy is highly robust across different fleet sizes and demand intensities.
Priority Labeling and Skewed Demands
The research identifies that the optimal prioritization is governed by the ratio of the cost coefficient to the arrival rate ($c_\alpha / \lambda_\alpha$). This ratio determines how the lower bound is structured and how vehicles should distribute their effort. Furthermore, the authors demonstrate that a "Merge Policy"—which treats all demands as a single class—fails significantly when priorities or arrival rates are highly skewed, whereas the SQ policy maintains its performance guarantees.
Experimental Results
Since real-world datasets for multi-class dynamic routing are scarce, the authors utilized numerical simulations to validate their theoretical framework. Using the linkern solver from the Concorde TSP package, they simulated environments with varying numbers of vehicles and demand classes.
- Practical Performance: Simulations revealed that the SQ policy often performs better than the theoretical $2m^2$ worst-case bound. The observed ratio between experimental results and the theoretical upper bound typically fell between 0.7 and 0.8.
- Scalability: The experiments confirmed that as the number of classes ($m$) increases, the performance gap grows proportionally to $m^2$, matching the theoretical predictions regarding the impact of class diversity on routing overhead.
Conclusion and Future Work
This paper provides a rigorous foundation for multi-class dynamic vehicle routing. The SQ policy demonstrates that even a strategy that avoids mixing demand classes within a single tour can achieve near-optimal performance in heavy traffic.
However, several avenues for future research remain. The authors note a persistent gap between the lower bound and the SQ policy's performance, suggesting that either the bound can be tightened or a more sophisticated policy exists. Additionally, the current model assumes a uniform distribution of demands; future iterations should account for geographic "hotspots" and the potential for multi-vehicle coordination on complex tasks. Finally, while the heavy-load regime is well-characterized here, the optimal strategy for light-load scenarios remains an open question.
Summary updated