Reward-Density heuristic for dynamic vehicle routing

Manish Kolachalam and Rani Malhotra submitted a paper on 7 Jul 2026 that introduces a reward-density approach, called the Efficiency heuristic, for dynamic multi-vehicle routing. The method aims to maximise cumulative reward within a fixed time horizon while continuously replanning as new tasks arrive, and it was evaluated on autonomous drone task allocation and urban taxi dispatch scenarios.

What is the Efficiency heuristic?

The Efficiency heuristic is a reward-density construction method for dynamic multi-vehicle assignment that chooses tasks to maximise reward per cost within a fixed horizon while replanning online. The paper frames the problem as a hybrid of the Vehicle Routing Problem and the Orienteering Problem, and the Efficiency heuristic operates as a greedy, reward-density rule applied across fleets and task streams in real time.

The authors tested the formulation across two concrete application domains: autonomous drone task allocation and urban taxi dispatch, varying fleet sizes and task scales. They compared the Efficiency heuristic under identical experimental conditions with four classical construction heuristics and three metaheuristic algorithms, showing how the approach behaves across realistic operational settings.

How does it perform against metaheuristics and classical heuristics?

Across all tested configurations, the Efficiency heuristic matched 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. The paper explicitly compares the Efficiency heuristic with three named metaheuristics: Adaptive Large Neighbourhood Search, Genetic Algorithm, and Simulated Annealing, plus four classical construction heuristics.

Kolachalam and Malhotra report that, under identical evaluation conditions, the Efficiency heuristic attains the same level of cumulative reward as the top-performing metaheuristics but at far lower computational cost. That tradeoff produces a clear outcome on the reward-versus-compute axis: the Efficiency heuristic sits on the Pareto front while the competing methods do not dominate it.

Why it matters

Real-time routing and dispatch systems must balance solution quality against planning latency. The paper supplies a concrete data point: two to three orders of magnitude less planning time for the Efficiency heuristic versus the best metaheuristics, which directly addresses the compute bottleneck in online allocation. For operators of drone fleets or taxi services, a greedy, reward-density rule that preserves reward while slashing compute can make continuous replanning feasible on constrained hardware or within tight timing windows.

The result challenges a common engineering instinct that complex search procedures are always necessary for high-quality routing under dynamics. The authors argue that carefully designed greedy heuristics can match sophisticated search at a fraction of the computational cost, making them preferable for online deployment in time-constrained environments.

What to watch

The paper is available on arXiv as arXiv:2607.06066, submitted 7 Jul 2026, and includes links to code, data, and demos under the paper's "Code, Data and Media Associated with this Article" section on the arXiv page. Watch for those artifacts and for any peer-reviewed versions that report field trials or real-world deployment results, which would validate whether the two to three orders of magnitude planning-time gains hold outside the experimental scenarios presented by the authors.

The paper also notes an arXiv-issued DOI via DataCite is pending registration, which may accompany later archival metadata or datasets linked to the project.