Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency

Technical Summary: Reward-Density Heuristic for Dynamic Multi-Vehicle Routing

Problem Definition
The paper addresses a dynamic, online variant of the Vehicle Routing Problem (VRP) that integrates elements of the Orienteering Problem (OP). In this formulation, a fleet of vehicles operates within a fixed time horizon to maximize cumulative reward. Unlike static VRP variants, tasks arrive dynamically (online), necessitating continuous replanning. The problem is constrained by a time budget per vehicle, where a vehicle can only be assigned a task if the sum of travel time and service time does not exceed its remaining budget. This structure models real-world scenarios such as autonomous drone task allocation and urban taxi dispatch, where assignment decisions must be made within milliseconds as new requests emerge.

Methodology
The authors propose and evaluate a "Reward-Density Heuristic" (termed the Efficiency heuristic) against four construction heuristics and three metaheuristic algorithms.

1. Proposed Approach (Efficiency Heuristic):
   The core of the method is a scoring function based on reward density, defined as the ratio of a task's reward ($R$) to its total time cost (travel time $d$ + service time $s$):
   $$\eta(\tau) = \frac{R(\tau)}{d(v, \tau) + s(\tau)}$$
   Two instantiations are tested:

   • Greedy-Efficiency: Assigns each available vehicle to the highest-scoring unclaimed feasible target sequentially.
   • Hungarian-Efficiency: Formulates the assignment as a Linear Assignment Problem (LAP) using the negative reward density ($-\eta$) as the cost matrix, solved optimally via the Hungarian algorithm.

2. Comparative Baselines:

   • Construction Heuristics: Greedy-Nearest (minimizes distance), Greedy-Reward (maximizes raw reward), Hungarian-Time (minimizes travel time), and Hungarian-Reward (maximizes raw reward via LAP).
   • Metaheuristics: Adaptive Large Neighborhood Search (ALNS), Genetic Algorithm (GA), and Simulated Annealing (SA). These are reinitialized at every replanning event to adapt to the changing landscape.

3. Experimental Setup:
   The study utilizes an event-driven simulator where replanning triggers upon task completion. Evaluations are conducted across two domains:

   • Synthetic Drone Environment: 12, 20, and 50 drones operating on a $5000 \times 5000$ map with 50–200 targets.
   • Real-World Taxi Dispatch: 50 and 200 taxis operating over 120 minutes against ~7,600 tasks derived from the NYC TLC Yellow Cab 2024 dataset.
     Performance is measured by cumulative reward (or revenue) and planning time (computational cost).

Key Results
The experiments demonstrate a clear Pareto dominance of the Efficiency heuristics over all competing methods:

• Solution Quality: The Efficiency heuristics (both Greedy and Hungarian variants) achieve solution quality statistically indistinguishable from the best-performing metaheuristics (ALNS, GA, SA) across all fleet sizes and domains. In contrast, simpler heuristics (Greedy-Nearest, Greedy-Reward, Hungarian-Time, Hungarian-Reward) consistently underperform with statistically significant deficits in reward/revenue.
• Computational Efficiency: The Efficiency heuristics require two to three orders of magnitude less planning time than the metaheuristics.
  • In the 50-drone scenario, Hungarian-Efficiency required ~128 ms, whereas GA required ~1.1 million ms, ALNS ~42,654 ms, and SA ~5,247 ms.
  • In the 200-taxi scenario, Hungarian-Efficiency required ~363 ms, while GA required ~4.58 million ms.
• Greedy vs. Global Optimality: The study found that the computationally cheaper Greedy-Efficiency approach yields statistically equivalent results to the globally optimal Hungarian-Efficiency approach, suggesting that the global optimality guarantee of the Hungarian algorithm confers limited practical benefit in these dynamic, high-frequency settings.

Significance and Claims
The paper claims that the choice of the optimization criterion (reward density/efficiency) is more impactful than the sophistication of the assignment mechanism.

• Structural Advantage: The success of the Efficiency heuristic suggests that in dynamic reward-maximizing routing, the ratio of reward to cost (efficiency) is a superior proxy for fleet-level value generation compared to optimizing for raw reward or travel time alone.
• Practical Viability: The metaheuristics, while capable of reaching similar solution quality ceilings, incur planning times that render them impractical for real-time dispatch. A planning cycle taking minutes is described as "actively harmful" in live operations because the environment changes materially before a solution is produced.
• Pareto Dominance: The Efficiency heuristics establish Pareto dominance on the reward-versus-compute frontier, offering near-optimal performance with minimal computational overhead.

The authors conclude that for real-time fleet dispatch, careful objective function design (specifically reward-density scoring) outweighs algorithmic complexity, making the Efficiency heuristic a robust candidate for operational systems where planning time is a binding constraint. The study acknowledges limitations regarding the simulation-based nature of the experiments and the focus on revenue as a single objective, noting that future work should explore multi-objective constraints and non-stationary demand.