Vehicle Routing Optimization Methods

Derniers papiers

• Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon

  Johannes F. Loevenich, Thies Moehlenhof, Laurin Holz, Maxime Schwarzer, Tobias Huerten, Roberto Rigolin F. Lopes · 2 octobre 2026

  Neural combinatorial optimization typically assumes a centralized solver that reads the whole instance. We study the opposite: combinatorial optimization under a hard information horizon, where every node commits to its share of a global solution seeing only its $k$-hop neighborhood, and those commi…

• Sequence Variables: A Constraint Programming Computational Domain for Routing and Sequencing

  Augustin Delecluse, Pierre Schaus, Pascal Van Hentenryck · 30 septembre 2026

  Constraint Programming (CP) offers an intuitive, declarative framework for modeling Vehicle Routing Problems (VRP). While classical successor-based CP models can be adapted to handle optional visits or insertion-based heuristics, sequence variables provide a significantly more natural and elegant fo…

• Understanding Decision-Making Mechanisms in Neural Routing Solvers

  Fatemeh Askari, Mazdak Teymourian, Mohammad Izadi, Mahdieh Soleymani Baghshah · 30 septembre 2026

  Neural Combinatorial Optimization (NCO) has achieved strong empirical success, yet the internal mechanisms driving model decisions remain largely unexplored. In this paper, we investigate three representative autoregressive NCO models spanning two encoder-decoder configurations: AM and POMO (heavy-e…

• Just Initialize: A Training-Free Initialization Component for Large-Scale Routing Optimization

  Jiale Zhao, Sirui Mao, Zimu Chen, Wentao Yang, Zihan Wang, Xuefeng Huang, Junji Cheng, Liyuanjun Lai · 29 septembre 2026

  Large-scale routing problems are difficult to solve efficiently as their search spaces grow rapidly with problem size. Existing approaches primarily improve the optimization procedure itself, often at increasing computational cost. We instead shift the focus to a useful initialization that can be re…

• JAMPR+/L2D: scalable neural heuristic for constrained vehicle routing problems in dynamic environment

  Andrew Soroka, Alex Meshcheryakov · 23 septembre 2026

  The vehicle routing problems with real-world constraints (we consider vehicles capacity limits, time windows constrains, pickup-and-delivery multi-depo --- CPDPTW) pose significant computational challenges. While classical exact and heuristic methods remain effective to solve problems of small/mediu…

• Dual-GNN Multilevel Coarsening for Maximum Independent Set

  Tianfeng Chen, Xianyue Li · 23 septembre 2026

  Solving large-scale instances of the Traveling Salesman Problem (TSP) exactly is computationally expensive. Researchers often employ graph sparsification methods to improve computational efficiency. Traditional sparsification methods typically rely on fixed heuristics and fail to fully exploit insta…

• COMPASS: Ordered Clustered Routing at 100K Scale

  Ido Greenberg, Hugo Linsenmaier, Piotr Sielski, Shie Mannor, Alex Fender, Gal Chechik, Eli Meirom · 18 septembre 2026

  Large-scale routing often requires visiting clusters of nodes in a prescribed order, giving rise to the Ordered Clustered Traveling Salesman Problem (OCTSP). Optimizing each cluster independently seems natural, but misses non-local dependencies. We introduce the COMPASS algorithm for OCTSP, which co…

• GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer

  Youssef Kamel Rezk, Pawe{\l} Gora · 7 septembre 2026

  Graph coarsening reduces the large Quadratic Unconstrained Binary Optimization (QUBO) formulations arising when vehicle-routing problems are solved by quantum annealing. Nearby customers with compatible time windows are merged into super-nodes, the reduced problem is solved, and the solution is expa…

• Learning Constraints-Based Adaptive Hypergraph Neural Networks for Solving Vehicle Routing Problems

  Zhenwei Wang, Tiehua Zhang, Jing Liu, Heng Yu, Kaizhu Huang, Ruibin Bai · 4 septembre 2026

  The application of learning based methods to vehicle routing problems has emerged as a pivotal area of research in combinatorial optimization. These problems are characterized by vast solution spaces and intricate constraints, making traditional approaches such as exact mathematical models or heuris…

• A hybrid quantum-classical neural network for learning to route

  Marcus Rolf Peter Ritt, Alexsandro Santos da Rosa J\'unior, Marcos Vinicius Reballo, Cesar Augusto do Amaral, Fernando Augusto Caletti de Barros · 2 septembre 2026

  This work studies hybrid quantum-classical neural networks for learning routing heuristics. Specifically, this paper asks whether small quantum neural networks can replace parameter-heavy modules inside a competitive attention-based routing model while maintaining solution quality. For the capacitat…

• GeoPAR: Large-Scale Multi-Agent Combinatorial Optimization with Geometry-Guided Parallel Autoregressive Learning

  Wenjian Wu, Zesheng Jia, Jiaying Tang, Benyuan Yang, Jin Wang · 2 septembre 2026

  Multi-agent combinatorial optimization problems are notoriously challenging due to their NP-hard nature. Recent parallel autoregressive neural solvers improve inference efficiency by allowing agents to make decisions simultaneously, but their performance often degrades on large-scale instances. This…

• Reinforcement Learning Enhanced LLM Agents for Complex Vehicle Routing Problems

  Yi Chen, Zikang Yu, Jiahai Wang, Jinbiao Chen, Jianpeng Zhou, Zizhen Zhang · 2 septembre 2026

  Vehicle Routing Problems (VRPs) are fundamental combinatorial optimization problems with widespread applications in various scenarios. The advanced optimization solvers can effectively solve such problems. However, modeling complex VRP variants for solvers often requires substantial domain expertise…

• Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglement

  Arthur Corr\^ea, Paulo Nascimento, Samuel Moniz · 26 août 2026

  Multi-task vehicle routing problem (VRP) solvers seek to handle multiple VRP variants within a single unified model, avoiding the need to train a separate model for every variant. In spite of recent progress, current approaches remain limited on two fronts. On the training side, reinforcement learni…

• The canonical facets of multi-separator polytopes

  Bjoern Andres, Silvia Di Gregorio, Jannik Irmai, Lucas Fabian Naumann, Shengxian Zhao · 18 août 2026

  We initiate a polyhedral study of the graph multi-separator problem proposed by Irmai et al. (2024) as an alternative to the lifted multicut problem for application to the task of image segmentation. Starting with an integer linear program (ILP) formulation and the multi-separator polytope spanned b…

• Drive, Pack, Fly: The Travelling Thief Problem with Drone

  Kabir Murjani, Abhay Sobhanan · 18 août 2026

  In collection operations, accumulating payload progressively slows the vehicle, imposing a cumulative penalty on routing efficiency. An onboard drone can offset this penalty by retrieving outlying items, thereby shortening the makespan and increasing operational profit. However, travel time remains …

• Deep Reinforcement Learning solution for pickup and delivery routing problems with time window and capacity constraints

  Andrew Soroka, Alex Meshcheryakov, Sergey Gerasimov · 17 août 2026

  The task of constructing vehicles optimal routes for pickup and delivery of goods is one of most promising tasks in the context of global urban population growth. Although this kind of problems with small size can be solved by various classical approaches, a fast (or realtime) route optimizer under …

• Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints

  Andrew Soroka, German Mikhelson, Alexander Mescheryakov, Sergey Gerasimov · 17 août 2026

  The problem of route optimization with realistic constraints is becoming extremely relevant in the face of global urban population growth. While we are aware of approaches that theoretically provide an exact optimal solution, their application becomes challenging as the problem size increases becaus…

• Dynamic Multi-Depot Vehicle Routing with Online Requests: Event-Driven Transformer--DRL and Rolling-Horizon Benchmarking

  Faezeh Ardali, Gerald M. Knapp · 17 août 2026

  This paper presents an event-driven learning and benchmarking framework for the Dynamic Multi-Depot Vehicle Routing Problem with progressively revealed requests and evolving vehicle states. Masked MLP and Transformer policies are trained through behavior cloning and proximal policy optimization. Det…

• A Graph Neural Network--Guided Genetic Algorithm for Physical Internet Supply Chain Optimization under Cost Uncertainty

  Faezeh Ardali, Gerald M. Knapp · 12 août 2026

  Inventory and distribution planning in Physical Internet networks requires coordinating factory-hub assignments, factory supply, lateral transshipment among collaborative hubs, retailer deliveries, and shortages. The problem combines discrete assignment decisions with interdependent continuous flows…

• Rural School Bus Routing and Scheduling

  Prabhat Hegde, Vikrant Vaze · 12 août 2026

  Long school bus rides adversely affect student performance and well-being. Rural school bus rides are particularly long, incentivizing parents to drive their children to school rather than to opt for the school bus. This in turn exacerbates the traffic congestion around schools, further compounding …

• DualCert: A Solver for the Traveling Salesman Problem with Constraint-Coupled Learning

  Yancheng Song, Yongzhi Qi, Wei Qi, Zuo-Jun Max Shen · 11 août 2026

  Large traveling salesman problem (TSP) instances require a solver to allocate limited computation while preserving the validity of its outputs. Existing neural--operations-research (OR) hybrids predict guidance without requiring learned transitions to satisfy constraints discovered during search. Du…

• Vehicle routing problem using deep reinforcement learning - A case study about truck planning in the industry

  Siliang Lu, Dan Hu, Lili Wu · 10 août 2026

  As an important component of the supply chain industry, transportation has experienced rapid development in the past decade with the assistance of digital platforms and intelligent algorithms. Within the field of transportation research, Vehicle Routing Problem (VRP) has remained a persistent and en…

• Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization

  David Aguado, Daniel Fuertes, Carlos R. del-Blanco, Fernando Jaureguizar · 4 août 2026

  Neural Combinatorial Optimization (NCO) techniques have emerged as a highly efficient alternative to traditional exact algorithms for solving routing problems such as the Traveling Salesman Problem (TSP). However, the generalization capabilities of these Reinforcement Learning-based models are sever…

• Learning to Optimize: Joint Routing and Flow Allocation on Sparse Non-Euclidean Networks

  Haomiao Sun, Fang He, Congyuan Ji, Xindi Tang · 28 juillet 2026

  We study an integrated pickup-and-delivery problem on sparse, non-Euclidean networks that jointly optimizes cyclic routing, cargo flow allocation, and cross-cycle service. The tight coupling of these operational constraints creates a complex discrete-continuous decision space with highly restricted …

• Integrated Order Dispatching and Routing for Last-Mile Pickup via Deep Reinforcement Learning

  Yida Xu, Zhaofang Mao, Yuheng Miao, Jiaxin Zhang, Yiting Sun · 27 juillet 2026

  In recent years, the growing complexity of last-mile pickup operations has increased the need for fast and accurate decision-making on logistics platforms. This challenge is fundamentally driven by two key and tightly coupled decision-making processes: order dispatching and routing. Solving them sep…