# Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency Source: [Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency]() Collection index: [llms.txt]() Data updated: 2026-07-09T05:00:01.225Z Authors: Manish Kolachalam, Rani Malhotra Published: 2026-07-07T09:37:46.000Z ## Abstract The Vehicle Routing Problem (VRP) and its variants represent some of the most practically consequential optimization challenges in modern logistics and urban mobility. In this study, we address a dynamic, online variant combining elements of the VRP and the Orienteering Problem (OP), in which a fleet of vehicles must maximise cumulative reward collected within a fixed time horizon while continuously replanning as new tasks arrive. We propose and evaluate a reward-density heuristic for dynamic multi-vehicle assignment, referred to as the Efficiency heuristic. We evaluate this formulation across two application domains: autonomous drone task allocation and urban taxi dispatch, across multiple fleet sizes and task scales. The proposed method is compared with four classical construction heuristics and three metaheuristic algorithms (Adaptive Large Neighbourhood Search, Genetic Algorithm, and Simulated Annealing), all evaluated under identical conditions. Across all tested configurations, the Efficiency heuristic matches 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. These findings suggest a practical design principle for real-time allocation and dispatch systems: in dynamic, time-constrained routing environments, carefully designed greedy heuristics can match the output of sophisticated search procedures at a fraction of the computational cost, making them preferable for online deployment. ## Recorded benchmark results A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage. - [Drone Dispatching on Drone Dispatch Synthetic 12 Drones 50 Targets 1.0 (test)](): Drone Dispatching; Drone Dispatch Synthetic 12 Drones 50 Targets 1.0 (test); Reward: 1850. - [Drone Dispatching on Drone Dispatch Synthetic 20 Drones / 100 Targets 1.0 (test)](): Drone Dispatching; Drone Dispatch Synthetic 20 Drones / 100 Targets 1.0 (test); Reward: 3585. - [Taxi Dispatch on NYC TLC Yellow Cab 50 taxis fleet 2024](): Taxi Dispatch; NYC TLC Yellow Cab 50 taxis fleet 2024; Revenue: 6938. - [Taxi Dispatch on NYC TLC Yellow Cab 2024 (200 taxis fleet)](): Taxi Dispatch; NYC TLC Yellow Cab 2024 (200 taxis fleet); Revenue: 23826. - [Drone Dispatching on Drone Dispatch Synthetic 50 Drones 200 Targets 1.0 (test)](): Drone Dispatching; Drone Dispatch Synthetic 50 Drones 200 Targets 1.0 (test); Reward: 8308. ## Original sources and implementation [Original paper]() [PDF]()