Edge-Selector Model Applied for Local Search Neighborhood for Solving Vehicle Routing Problems

• URL: http://arxiv.org/abs/2508.14071v1
• Date: Tue, 12 Aug 2025 05:28:26 GMT
• Title: Edge-Selector Model Applied for Local Search Neighborhood for Solving Vehicle Routing Problems
• Authors: Bachtiar Herdianto, Romain Billot, Flavien Lucas, Marc Sevaux, Daniele Vigo,
• Abstract summary: This research proposes a hybrid Machine Learning and metaheuristic mechanism that is designed to solve Vehicle Routing Problems (VRPs)<n>The main of our method is an edge solution selector model, which classifies solution edges to identify prohibited moves during the local search.<n>Our method demonstrates both scalability and generalizability, achieving performance improvements across different baseline metaheuristics.
• Score: 1.9573380763700716
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: This research proposes a hybrid Machine Learning and metaheuristic mechanism that is designed to solve Vehicle Routing Problems (VRPs). The main of our method is an edge solution selector model, which classifies solution edges to identify prohibited moves during the local search, hence guiding the search process within metaheuristic baselines. Two learning-based mechanisms are used to develop the edge selector: a simple tabular binary classifier and a Graph Neural Network (GNN). The tabular classifier employs Gradient Boosting Trees and Feedforward Neural Network as the baseline algorithms. Adjustments to the decision threshold are also applied to handle the class imbalance in the problem instance. An alternative mechanism employs the GNN to utilize graph structure for direct solution edge prediction, with the objective of guiding local search by predicting prohibited moves. These hybrid mechanisms are then applied in state-fo-the-art metaheuristic baselines. Our method demonstrates both scalability and generalizability, achieving performance improvements across different baseline metaheuristics, various problem sizes and variants, including the Capacitated Vehicle Routing Problem (CVRP) and CVRP with Time Windows (CVRPTW). Experimental evaluations on benchmark datasets up to 30,000 customer nodes, supported by pair-wise statistical analysis, verify the observed improvements.

Related papers

• Bundle Network: a Machine Learning-Based Bundle Method [5.611428210450043]
  This paper presents Bundle Network, a learning-based algorithm inspired by the Bundle Method for convex non-smooth problems.<n>By leveraging the unrolled graph of computation, our Bundle Network can be trained end-to-end via automatic differentiation.
  arXiv  Detail & Related papers  (2025-09-29T12:59:49Z)
• Hybrid Node-Destroyer Model with Large Neighborhood Search for Solving the Capacitated Vehicle Routing Problem [1.9573380763700716]
  We propose an iterative learning hybrid optimization solver to strengthen the performance of metaheuristic algorithms.<n>The proposed approach reduces operational complexity and scales down the search space involved in the optimization process.
  arXiv  Detail & Related papers  (2025-08-12T05:56:13Z)
• Adaptive and Robust DBSCAN with Multi-agent Reinforcement Learning [53.527506374566485]
  We propose a novel Adaptive and Robust DBSCAN with Multi-agent Reinforcement Learning cluster framework, namely AR-DBSCAN.<n>We show that AR-DBSCAN not only improves clustering accuracy by up to 144.1% and 175.3% in the NMI and ARI metrics, respectively, but also is capable of robustly finding dominant parameters.
  arXiv  Detail & Related papers  (2025-05-07T11:37:23Z)
• GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems [6.084414764415137]
  We propose an adaptive Graph Attention Sampling with the Edges Fusion framework to solve vehicle routing problems. Our proposed model outperforms the existing methods by 2.08%-6.23% and shows stronger generalization ability.
  arXiv  Detail & Related papers  (2024-05-21T03:33:07Z)
• Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows [0.0]
  We propose a decompose-route-improve (DRI) framework that groups customers using clustering. Its similarity metric incorporates customers' spatial, temporal, and demand data. We apply pruned local search (LS) between solved subproblems to improve the overall solution.
  arXiv  Detail & Related papers  (2024-01-20T06:06:01Z)
• A hybrid deep-learning-metaheuristic framework for bi-level network design problems [2.741266294612776]
  This study proposes a hybrid deep-learning-metaheuristic framework with a bi-level architecture for road network design problems (NDPs) We train a graph neural network (GNN) to approximate the solution of the user equilibrium (UE) traffic assignment problem. We use inferences made by the trained model to calculate fitness function evaluations of a genetic algorithm (GA) to approximate solutions for NDPs.
  arXiv  Detail & Related papers  (2023-03-10T16:23:56Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  We study the OOD generalization of neural algorithmic reasoning tasks. The goal is to learn an algorithm from input-output pairs using deep neural networks.
  arXiv  Detail & Related papers  (2022-11-01T18:33:20Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  We introduce a novel Neural Improvement (NI) model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each.
  arXiv  Detail & Related papers  (2022-06-01T10:35:29Z)
• Semi-supervised Domain Adaptive Structure Learning [72.01544419893628]
  Semi-supervised domain adaptation (SSDA) is a challenging problem requiring methods to overcome both 1) overfitting towards poorly annotated data and 2) distribution shift across domains. We introduce an adaptive structure learning method to regularize the cooperation of SSL and DA.
  arXiv  Detail & Related papers  (2021-12-12T06:11:16Z)
• Enhanced Exploration in Neural Feature Selection for Deep Click-Through Rate Prediction Models via Ensemble of Gating Layers [7.381829794276824]
  The goal of neural feature selection (NFS) is to choose a relatively small subset of features with the best explanatory power. Gating approach inserts a set of differentiable binary gates to drop less informative features. To improve the exploration capacity of gradient-based solutions, we propose a simple but effective ensemble learning approach.
  arXiv  Detail & Related papers  (2021-12-07T04:37:05Z)
• Reconfigurable Intelligent Surface Assisted Mobile Edge Computing with Heterogeneous Learning Tasks [53.1636151439562]
  Mobile edge computing (MEC) provides a natural platform for AI applications. We present an infrastructure to perform machine learning tasks at an MEC with the assistance of a reconfigurable intelligent surface (RIS) Specifically, we minimize the learning error of all participating users by jointly optimizing transmit power of mobile users, beamforming vectors of the base station, and the phase-shift matrix of the RIS.
  arXiv  Detail & Related papers  (2020-12-25T07:08:50Z)
• DAIS: Automatic Channel Pruning via Differentiable Annealing Indicator Search [55.164053971213576]
  convolutional neural network has achieved great success in fulfilling computer vision tasks despite large computation overhead. Structured (channel) pruning is usually applied to reduce the model redundancy while preserving the network structure. Existing structured pruning methods require hand-crafted rules which may lead to tremendous pruning space.
  arXiv  Detail & Related papers  (2020-11-04T07:43:01Z)
• Contradictory Structure Learning for Semi-supervised Domain Adaptation [67.89665267469053]
  Current adversarial adaptation methods attempt to align the cross-domain features. Two challenges remain unsolved: 1) the conditional distribution mismatch and 2) the bias of the decision boundary towards the source domain. We propose a novel framework for semi-supervised domain adaptation by unifying the learning of opposite structures.
  arXiv  Detail & Related papers  (2020-02-06T22:58:20Z)

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.