A Neural Column Generation Approach to the Vehicle Routing Problem with Two-Dimensional Loading and Last-In-First-Out Constraints

• URL: http://arxiv.org/abs/2406.12454v1
• Date: Tue, 18 Jun 2024 09:58:29 GMT
• Title: A Neural Column Generation Approach to the Vehicle Routing Problem with Two-Dimensional Loading and Last-In-First-Out Constraints
• Authors: Yifan Xia, Xiangyi Zhang,
• Abstract summary: A vehicle routing problem with two-dimensional loading constraints (2L-CVRP) presents significant practical and algorithmic challenges. This article presents an exact algorithm that integrates advanced machine learning techniques, specifically a novel combination of attention and recurrence mechanisms. The proposed algorithm successfully resolves an open instance in the standard test-bed, demonstrating significant improvements brought about by the incorporation of machine learning models.
• Score: 3.9594431485015096
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The vehicle routing problem with two-dimensional loading constraints (2L-CVRP) and the last-in-first-out (LIFO) rule presents significant practical and algorithmic challenges. While numerous heuristic approaches have been proposed to address its complexity, stemming from two NP-hard problems: the vehicle routing problem (VRP) and the two-dimensional bin packing problem (2D-BPP), less attention has been paid to developing exact algorithms. Bridging this gap, this article presents an exact algorithm that integrates advanced machine learning techniques, specifically a novel combination of attention and recurrence mechanisms. This integration accelerates the state-of-the-art exact algorithm by a median of 29.79% across various problem instances. Moreover, the proposed algorithm successfully resolves an open instance in the standard test-bed, demonstrating significant improvements brought about by the incorporation of machine learning models. Code is available at https://github.com/xyfffff/NCG-for-2L-CVRP.

Related papers

• Two-Timescale Model Caching and Resource Allocation for Edge-Enabled AI-Generated Content Services [55.0337199834612]
  Generative AI (GenAI) has emerged as a transformative technology, enabling customized and personalized AI-generated content (AIGC) services. These services require executing GenAI models with billions of parameters, posing significant obstacles to resource-limited wireless edge. We introduce the formulation of joint model caching and resource allocation for AIGC services to balance a trade-off between AIGC quality and latency metrics.
  arXiv  Detail & Related papers  (2024-11-03T07:01:13Z)
• Multiobjective Vehicle Routing Optimization with Time Windows: A Hybrid Approach Using Deep Reinforcement Learning and NSGA-II [52.083337333478674]
  This paper proposes a weight-aware deep reinforcement learning (WADRL) approach designed to address the multiobjective vehicle routing problem with time windows (MOVRPTW) The Non-dominated sorting genetic algorithm-II (NSGA-II) method is then employed to optimize the outcomes produced by the WADRL.
  arXiv  Detail & Related papers  (2024-07-18T02:46:06Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  This paper presents a novel form of the PSO methodology that uses the Roulette Wheel Method (RWPSO) Experiments using the Solomon VRPTW benchmark datasets on the RWPSO demonstrate that RWPSO is competitive with other state-of-the-art algorithms from the literature.
  arXiv  Detail & Related papers  (2023-06-04T09:18:02Z)
• Combining Constructive and Perturbative Deep Learning Algorithms for the Capacitated Vehicle Routing Problem [0.0]
  The Capacitated Vehicle Routing Problem is a well-known NP-hard problem that poses the challenge of finding the optimal route of a vehicle delivering products to multiple locations. Recently, new efforts have emerged to create constructive and perturbative Deep Learning-based algorithms to tackle this problem. We propose a Combined Deep Constructor and Perturbator, which combines two powerful constructive and perturbative Deep Learning-based algorithms.
  arXiv  Detail & Related papers  (2022-11-25T06:20:11Z)
• Solving the vehicle routing problem with deep reinforcement learning [0.0]
  This paper focuses on the application of RL for the Vehicle Routing Problem (VRP), a famous problem that belongs to the class of NP-Hard problems. In a second phase, the neural architecture behind the Actor and Critic has been established, choosing to adopt a neural architecture based on the Convolutional neural networks. Experiments performed on a wide range of instances show that the algorithm has good generalization capabilities and can reach good solutions in a short time.
  arXiv  Detail & Related papers  (2022-07-30T12:34:26Z)
• Capacitated Vehicle Routing Problem Using Conventional and Approximation Method [0.0]
  This paper attempts to solve the famous Vehicle Routing Problem by considering multiple constraints including capacitated vehicles, single depot, and distance. For clustering the nodes, we have adopted the DBSCAN algorithm, and the routing is done using the approximation algorithm, Christofide's algorithm. The solution generated can be employed for solving real-life situations, like delivery systems consisting of various demand nodes.
  arXiv  Detail & Related papers  (2022-07-29T19:25:39Z)
• A Case Study of Vehicle Route Optimization [2.2101681534594237]
  In this work, we incorporate the main relevant real-world constraints and requirements. We propose a two-stage strategy and a Timeline algorithm for time windows and pause times. Our evaluation of eight different problem instances against four state-of-the-art algorithms shows that our approach handles all given constraints in a reasonable time.
  arXiv  Detail & Related papers  (2021-11-17T13:10:55Z)
• Applying quantum approximate optimization to the heterogeneous vehicle routing problem [0.7503129292751939]
  We investigate the potential use of a quantum computer to find approximate solutions to the heterogeneous vehicle routing problem. We find that the number of qubits needed for this mapping scales quadratically with the number of customers.
  arXiv  Detail & Related papers  (2021-10-13T15:38:25Z)
• An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problem [49.04543375851723]
  Vehicle routing problem (VRP) is a typical discrete optimization problem. Many studies consider learning-based optimization algorithms to solve VRP. This paper reviews recent advances in this field and divides relevant approaches into end-to-end approaches and step-by-step approaches.
  arXiv  Detail & Related papers  (2021-07-15T02:13:03Z)
• 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)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  This paper investigates the problem of vehicle-cell association in millimeter wave (mmWave) communication networks. We first formulate the user state (VU) problem as a discrete non-vehicle association optimization problem. The proposed solution achieves up to 15% gains in terms sum of user complexity and 20% reduction in VUE compared to several baseline designs.
  arXiv  Detail & Related papers  (2020-01-22T08:51:05Z)

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.