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

• URL: http://arxiv.org/abs/2607.06066v1
• Date: Tue, 07 Jul 2026 09:37:46 GMT
• Title: Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency
• Abstract summary: We address a dynamic, online variant combining elements of the Vehicle Problem (VRP) and the Orienteering Problem (OP)<n>We propose and evaluate a reward-density for dynamic multi-vehicle assignment, referred to as the Efficiency Routing.<n>Across all tested configurations, the Efficiency matches the solution quality of the best metaheuristic algorithms while requiring two to three orders of magnitude less planning time.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• HAD: Combining Hierarchical Diffusion with Metric-Decoupled RL for End-to-End Driving [51.268878540511054]
  We propose HAD, an end-to-end planning framework with a Hierarchical Diffusion Policy.<n>We show that HAD achieves new state-of-the-art performance on both NAVSIM and HUGSIM.
  arXiv  Detail & Related papers  (2026-04-04T04:12:47Z)
• Experience-Guided Reflective Co-Evolution of Prompts and Heuristics for Automatic Algorithm Design [124.54166764570972]
  Combinatorial optimization problems are traditionally tackled with handcrafted algorithms.<n>Recent progress has highlighted the potential of automatics design powered by large language models.<n>We propose the Experience-Evolution Reflective Co-Guided of Prompt and Heuristics (EvoPH) for automatic algorithm design.
  arXiv  Detail & Related papers  (2025-09-29T09:24:09Z)
• Dynamic Location Search for Identifying Maximum Weighted Independent Sets in Complex Networks [0.47248250311484113]
  We introduce a novel and efficient algorithm for solving the maximum weighted independent set (MWIS) problem.<n>Given the NP-hard nature of the MWIS problem, our proposed algorithm, DynLS, incorporates three key innovations to solve it effectively.<n>Our experimental results demonstrate DynLS's superior performance, consistently delivering high-quality solutions within 1000 seconds.
  arXiv  Detail & Related papers  (2025-05-07T10:35:53Z)
• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
  Vehicle Routing Problems (VRP) are a fundamental NP-hard challenge in Evolutionary optimization.<n>We introduce an optimization framework where a reinforcement learning agent is trained on prior instances and quickly generates initial solutions.<n>This framework consistently outperforms current state-of-the-art solvers across various time budgets.
  arXiv  Detail & Related papers  (2025-04-08T15:21:01Z)
• A Coalition Game for On-demand Multi-modal 3D Automated Delivery System [4.378407481656902]
  We introduce a coalition game for a fleet of UAVs and ADRs operating in two overlaying networks to address last-mile delivery in urban environments.<n>We investigate cooperation structures among the modes to capture how strategic collaboration can improve overall routing efficiency.<n>Several numerical experiments on last-mile delivery applications have been conducted, showing the results from the case study in the city of Mississauga.
  arXiv  Detail & Related papers  (2024-12-23T03:50:29Z)
• Learn to Solve Vehicle Routing Problems ASAP: A Neural Optimization Approach for Time-Constrained Vehicle Routing Problems with Finite Vehicle Fleet [0.0]
  We propose an NCO approach to solve a time-constrained capacitated VRP with a finite vehicle fleet size. The method is able to find adequate and cost-efficient solutions, showing both flexibility and robust generalizations.
  arXiv  Detail & Related papers  (2024-11-07T15:16:36Z)
• Combinatorial Optimization enriched Machine Learning to solve the Dynamic Vehicle Routing Problem with Time Windows [5.4807970361321585]
  We propose a novel machine learning pipeline that incorporates an optimization layer. We apply this pipeline to a dynamic vehicle routing problem with waves, which was recently promoted in the EURO Meets NeurIPS Competition at NeurIPS 2022. Our methodology ranked first in this competition, outperforming all other approaches in solving the proposed dynamic vehicle routing problem.
  arXiv  Detail & Related papers  (2023-04-03T08:23:09Z)
• Controllable Dynamic Multi-Task Architectures [92.74372912009127]
  We propose a controllable multi-task network that dynamically adjusts its architecture and weights to match the desired task preference as well as the resource constraints. We propose a disentangled training of two hypernetworks, by exploiting task affinity and a novel branching regularized loss, to take input preferences and accordingly predict tree-structured models with adapted weights.
  arXiv  Detail & Related papers  (2022-03-28T17:56:40Z)
• Value Function is All You Need: A Unified Learning Framework for Ride Hailing Platforms [57.21078336887961]
  Large ride-hailing platforms, such as DiDi, Uber and Lyft, connect tens of thousands of vehicles in a city to millions of ride demands throughout the day. We propose a unified value-based dynamic learning framework (V1D3) for tackling both tasks.
  arXiv  Detail & Related papers  (2021-05-18T19:22:24Z)
• Integrated Decision and Control: Towards Interpretable and Efficient Driving Intelligence [13.589285628074542]
  We present an interpretable and efficient decision and control framework for automated vehicles. It decomposes the driving task into multi-path planning and optimal tracking that are structured hierarchically. Results show that our method has better online computing efficiency and driving performance including traffic efficiency and safety.
  arXiv  Detail & Related papers  (2021-03-18T14:43:31Z)
• NOMA in UAV-aided cellular offloading: A machine learning approach [59.32570888309133]
  A novel framework is proposed for cellular offloading with the aid of multiple unmanned aerial vehicles (UAVs) Non-orthogonal multiple access (NOMA) technique is employed at each UAV to further improve the spectrum efficiency of the wireless network. A mutual deep Q-network (MDQN) algorithm is proposed to jointly determine the optimal 3D trajectory and power allocation of UAVs.
  arXiv  Detail & Related papers  (2020-10-18T17:38:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.