Deep Learning--Accelerated Multi-Start Large Neighborhood Search for Real-time Freight Bundling

• URL: http://arxiv.org/abs/2512.11187v1
• Date: Fri, 12 Dec 2025 00:29:37 GMT
• Title: Deep Learning--Accelerated Multi-Start Large Neighborhood Search for Real-time Freight Bundling
• Authors: Haohui Zhang, Wouter van Heeswijk, Xinyu Hu, Neil Yorke-Smith, Martijn Mes,
• Abstract summary: We model the OFEX bundling problem as a multi-commodity one-to-one pickup-and-delivery selective traveling salesperson problem (m1-PDSTSP)<n>Key challenge is to couple bundle selection with pickup-and-delivery routing under sub-second.<n>We propose a learning-accelerated hybrid search pipeline that pairs a Transformer Neural Network-based constructive policy with an innovative Multi-Start Large Neighborhood Search (LNMSS) metaheuristic within a rolling-horizon scheme.
• Score: 10.477771954122625
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online Freight Exchange Systems (OFEX) play a crucial role in modern freight logistics by facilitating real-time matching between shippers and carrier. However, efficient combinatorial bundling of transporation jobs remains a bottleneck. We model the OFEX combinatorial bundling problem as a multi-commodity one-to-one pickup-and-delivery selective traveling salesperson problem (m1-PDSTSP), which optimizes revenue-driven freight bundling under capacity, precedence, and route-length constraints. The key challenge is to couple combinatorial bundle selection with pickup-and-delivery routing under sub-second latency. We propose a learning--accelerated hybrid search pipeline that pairs a Transformer Neural Network-based constructive policy with an innovative Multi-Start Large Neighborhood Search (MSLNS) metaheuristic within a rolling-horizon scheme in which the platform repeatedly freezes the current marketplace into a static snapshot and solves it under a short time budget. This pairing leverages the low-latency, high-quality inference of the learning-based constructor alongside the robustness of improvement search; the multi-start design and plausible seeds help LNS to explore the solution space more efficiently. Across benchmarks, our method outperforms state-of-the-art neural combinatorial optimization and metaheuristic baselines in solution quality with comparable time, achieving an optimality gap of less than 2\% in total revenue relative to the best available exact baseline method. To our knowledge, this is the first work to establish that a Deep Neural Network-based constructor can reliably provide high-quality seeds for (multi-start) improvement heuristics, with applicability beyond the \textit{m1-PDSTSP} to a broad class of selective traveling salesperson problems and pickup and delivery problems.

Related papers

• FastLane: Efficient Routed Systems for Late-Interaction Retrieval [58.060096779432094]
  FastLane is a novel retrieval framework that dynamically routes queries to their most informative representations.<n>By bridging late-interaction models with Approximate Nearest Neighbor Search (ANNS), FastLane enables scalable, low-latency retrieval.
  arXiv  Detail & Related papers  (2026-01-10T02:22:01Z)
• Solving the Min-Max Multiple Traveling Salesmen Problem via Learning-Based Path Generation and Optimal Splitting [8.941535841606584]
  Min-Max Multiple Traveling Salesmen Problem aims to coordinate tours for multiple salesmen so that the length of the longest tour is minimized.<n>Due to its NP-hard nature, exact solvers become impractical under the assumption that $P ne NP$.<n>We propose a novel two-stage framework named textbfGenerate-and-Split (GaS), which integrates reinforcement learning with an optimal splitting algorithm in a joint training process.
  arXiv  Detail & Related papers  (2025-08-23T17:00:57Z)
• Pinet: Optimizing hard-constrained neural networks with orthogonal projection layers [5.227723778971733]
  We introduce an output layer for networks that ensures satisfaction of convex constraints.<n>Our approach, $Pi$net, leverages operator splitting for rapid and reliable projections in the forward pass.
  arXiv  Detail & Related papers  (2025-08-14T09:32:09Z)
• How to Train Your LLM Web Agent: A Statistical Diagnosis [96.86317871461834]
  We present the first statistically grounded study on compute allocation for LLM web-agent post-training.<n>Our approach uses a two-stage pipeline, training a Llama 3.1 8B student to imitate a Llama 3.3 70B teacher via supervised fine-tuning (SFT) and on-policy reinforcement learning.<n>Our results show that combining SFT with on-policy RL consistently outperforms either approach alone on both WorkArena and MiniWob++.
  arXiv  Detail & Related papers  (2025-07-05T17:12:33Z)
• 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)
• Learning to Solve the Min-Max Mixed-Shelves Picker-Routing Problem via Hierarchical and Parallel Decoding [0.3867363075280544]
  The Mixed-Shelves Picker Routing Problem (MSPRP) is a fundamental challenge in logistics, where pickers must navigate a mixed-shelves environment to retrieve SKUs efficiently.<n>We propose a novel hierarchical and parallel decoding approach for solving the min-max variant of the MSPRP via multi-agent reinforcement learning.<n> Experiments show state-of-the-art performance in both solution quality and inference speed, particularly for large-scale and out-of-distribution instances.
  arXiv  Detail & Related papers  (2025-02-14T15:42:30Z)
• Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization [83.65278205301576]
  We propose to learn direct mappings from different noise levels to the optimal solution for a given instance, facilitating high-quality generation with minimal shots.<n>This is achieved through an optimization consistency training protocol, which minimizes the difference among samples.<n>Experiments on two popular tasks, the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS), demonstrate the superiority of Fast T2T regarding both solution quality and efficiency.
  arXiv  Detail & Related papers  (2025-02-05T07:13:43Z)
• Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learning [29.551883712536295]
  Existing neural methods for the Travelling Salesman Problem (TSP) mostly aim at finding a single optimal solution.<n>We propose a novel deep reinforcement learning based neural solver, which is primarily featured by an encoder-decoder structured policy.
  arXiv  Detail & Related papers  (2025-01-01T16:08:40Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  We introduce an NN-based solver to significantly narrow the gap with advanced metaheuristics. First, we propose direction-aware facilitating attention model (DaAM) to incorporate directionality into the embedding process. Second, we design a supervised reinforcement learning scheme that involves supervised pre-training to establish a robust initial policy.
  arXiv  Detail & Related papers  (2024-03-11T02:17:42Z)
• Low-Latency Federated Learning over Wireless Channels with Differential Privacy [142.5983499872664]
  In federated learning (FL), model training is distributed over clients and local models are aggregated by a central server. In this paper, we aim to minimize FL training delay over wireless channels, constrained by overall training performance as well as each client's differential privacy (DP) requirement.
  arXiv  Detail & Related papers  (2021-06-20T13:51:18Z)
• Deep Reinforcement Learning for Resource Constrained Multiclass Scheduling in Wireless Networks [0.0]
  In our setup, the available limited bandwidth resources are allocated in order to serve randomly arriving service demands. We propose a distributional Deep Deterministic Policy Gradient (DDPG) algorithm combined with Deep Sets to tackle the problem. Our proposed algorithm is tested on both synthetic and real data, showing consistent gains against state-of-the-art conventional methods.
  arXiv  Detail & Related papers  (2020-11-27T09:49:38Z)

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.