Large Neighborhood Search based on Neural Construction Heuristics

• URL: http://arxiv.org/abs/2205.00772v1
• Date: Mon, 2 May 2022 09:38:19 GMT
• Title: Large Neighborhood Search based on Neural Construction Heuristics
• Authors: Jonas K. Falkner, Daniela Thyssens, Lars Schmidt-Thieme
• Abstract summary: We propose a learned construction based on neural networks as repair operator to solve the vehicle routing problem with time windows. Our method uses graph neural networks to encode the problem and auto-regressively decodes a solution.
• Score: 5.210197476419621
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We propose a Large Neighborhood Search (LNS) approach utilizing a learned construction heuristic based on neural networks as repair operator to solve the vehicle routing problem with time windows (VRPTW). Our method uses graph neural networks to encode the problem and auto-regressively decodes a solution and is trained with reinforcement learning on the construction task without requiring any labels for supervision. The neural repair operator is combined with a local search routine, heuristic destruction operators and a selection procedure applied to a small population to arrive at a sophisticated solution approach. The key idea is to use the learned model to re-construct the partially destructed solution and to introduce randomness via the destruction heuristics (or the stochastic policy itself) to effectively explore a large neighborhood.

Related papers

• Neural Networks for Vehicle Routing Problem [0.0]
  Route optimization can be viewed as a new challenge for neural networks. Recent developments in machine learning provide a new toolset, for tackling complex problems. The main area of application of neural networks is the area of classification and regression.
  arXiv  Detail & Related papers  (2024-09-17T15:45:30Z)
• Robotic warehousing operations: a learn-then-optimize approach to large-scale neighborhood search [84.39855372157616]
  This paper supports robotic parts-to-picker operations in warehousing by optimizing order-workstation assignments, item-pod assignments and the schedule of order fulfillment at workstations. We solve it via large-scale neighborhood search, with a novel learn-then-optimize approach to subproblem generation. In collaboration with Amazon Robotics, we show that our model and algorithm generate much stronger solutions for practical problems than state-of-the-art approaches.
  arXiv  Detail & Related papers  (2024-08-29T20:22:22Z)
• Deep Reinforcement Learning for Picker Routing Problem in Warehousing [0.6562256987706128]
  We introduce an attention based neural network for modeling picker tours, which is trained using Reinforcement Learning. A key advantage of our proposed method is its ability to offer an option to reduce the perceived complexity of routes.
  arXiv  Detail & Related papers  (2024-02-05T21:25:45Z)
• Too Big, so Fail? -- Enabling Neural Construction Methods to Solve Large-Scale Routing Problems [10.832715681422842]
  We show that even state-of-the-art neural construction methods are outperformed by simple iterations. We propose to use the ruin recreate principle that alternates between completely destroying a localized part of the solution and then recreating an improved variant.
  arXiv  Detail & Related papers  (2023-09-29T09:36:37Z)
• The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks [59.26515696183751]
  We show that algorithm discovery in neural networks is sometimes more complex. We show that even simple learning problems can admit a surprising diversity of solutions.
  arXiv  Detail & Related papers  (2023-06-30T17:59:13Z)
• Graph Neural Networks for Decentralized Multi-Agent Perimeter Defense [111.9039128130633]
  We develop an imitation learning framework that learns a mapping from defenders' local perceptions and their communication graph to their actions. We run perimeter defense games in scenarios with different team sizes and configurations to demonstrate the performance of the learned network.
  arXiv  Detail & Related papers  (2023-01-23T19:35:59Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  We propose Deep Policy Dynamic Programming (D PDP) to combine the strengths of learned neurals with those of dynamic programming algorithms. D PDP prioritizes and restricts the DP state space using a policy derived from a deep neural network, which is trained to predict edges from example solutions. We evaluate our framework on the travelling salesman problem (TSP) and the vehicle routing problem (VRP) and show that the neural policy improves the performance of (restricted) DP algorithms.
  arXiv  Detail & Related papers  (2021-02-23T15:33:57Z)
• Automated Search for Resource-Efficient Branched Multi-Task Networks [81.48051635183916]
  We propose a principled approach, rooted in differentiable neural architecture search, to automatically define branching structures in a multi-task neural network. We show that our approach consistently finds high-performing branching structures within limited resource budgets.
  arXiv  Detail & Related papers  (2020-08-24T09:49:19Z)
• Learn to Design the Heuristics for Vehicle Routing Problem [5.37343672465706]
  This paper presents an approach to learn the local-searchs that iteratively improves the solution of Vehicle Problem (VRP) A local-searchs is composed of a destroy operator that destructs a candidate solution, and a following repair operator that rebuilds the destructed one into a new one. The proposed neural network, as trained through actor-critic framework, consists of an encoder in form of a modified version of Graph Attention Network.
  arXiv  Detail & Related papers  (2020-02-20T02:39:02Z)
• Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach [9.717648122961483]
  Multi-vehicle routing problem with soft time windows (MVRPSTW) is an indispensable constituent in urban logistics systems. Traditional methods incur the dilemma between computational efficiency and solution quality. We propose a novel reinforcement learning algorithm called the Multi-Agent Attention Model that can solve routing problem instantly benefit from lengthy offline training.
  arXiv  Detail & Related papers  (2020-02-13T14:26:27Z)

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.