Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems

• URL: http://arxiv.org/abs/2310.14157v4
• Date: Sat, 7 Sep 2024 13:41:29 GMT
• Title: Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems
• Authors: Abhay Sobhanan, Junyoung Park, Jinkyoo Park, Changhyun Kwon,
• Abstract summary: When vehicle routing decisions are intertwined with higher-level decisions, the resulting optimization problems pose significant challenges for computation. We propose a novel deep-learning-based approach called Genetic Algorithm with Neural Cost Predictor (GANCP) to tackle the challenge. In particular, our proposed neural network learns the objective values of the HGS-CVRP open-source package that solves capacitated vehicle routing problems.
• Score: 20.684353068460375
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: When vehicle routing decisions are intertwined with higher-level decisions, the resulting optimization problems pose significant challenges for computation. Examples are the multi-depot vehicle routing problem (MDVRP), where customers are assigned to depots before delivery, and the capacitated location routing problem (CLRP), where the locations of depots should be determined first. A simple and straightforward approach for such hierarchical problems would be to separate the higher-level decisions from the complicated vehicle routing decisions. For each higher-level decision candidate, we may evaluate the underlying vehicle routing problems to assess the candidate. As this approach requires solving vehicle routing problems multiple times, it has been regarded as impractical in most cases. We propose a novel deep-learning-based approach called Genetic Algorithm with Neural Cost Predictor (GANCP) to tackle the challenge and simplify algorithm developments. For each higher-level decision candidate, we predict the objective function values of the underlying vehicle routing problems using a pre-trained graph neural network without actually solving the routing problems. In particular, our proposed neural network learns the objective values of the HGS-CVRP open-source package that solves capacitated vehicle routing problems. Our numerical experiments show that this simplified approach is effective and efficient in generating high-quality solutions for both MDVRP and CLRP and has the potential to expedite algorithm developments for complicated hierarchical problems. We provide computational results evaluated in the standard benchmark instances used in the literature.

Related papers

• 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)
• 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)
• 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)
• Dynamic Origin-Destination Matrix Estimation in Urban Traffic Networks [0.05735035463793007]
  We model the problem as a bi-level optimization problem. In the inner level, given a tentative travel demand, we solve a dynamic traffic assignment problem to decide the routing of the users between their origins and destinations. In the outer level, we adjust the number of trips and their origins and destinations, aiming at minimizing the discrepancy between the counters generated in the inner level and the given vehicle counts measured by sensors in the traffic network.
  arXiv  Detail & Related papers  (2022-01-31T21:33:46Z)
• Fidelity-Guarantee Entanglement Routing in Quantum Networks [64.49733801962198]
  Entanglement routing establishes remote entanglement connection between two arbitrary nodes. We propose purification-enabled entanglement routing designs to provide fidelity guarantee for multiple Source-Destination (SD) pairs in quantum networks.
  arXiv  Detail & Related papers  (2021-11-15T14:07:22Z)
• Ranking Cost: Building An Efficient and Scalable Circuit Routing Planner with Evolution-Based Optimization [49.207538634692916]
  We propose a new algorithm for circuit routing, named Ranking Cost, to form an efficient and trainable router. In our method, we introduce a new set of variables called cost maps, which can help the A* router to find out proper paths. Our algorithm is trained in an end-to-end manner and does not use any artificial data or human demonstration.
  arXiv  Detail & Related papers  (2021-10-08T07:22:45Z)
• 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)
• Learning (Re-)Starting Solutions for Vehicle Routing Problems [14.509927512118544]
  A key challenge in solving a optimization problem is how to guide the agent (i.e., solver) to efficiently explore the enormous search space. In this paper, we show it is possible to use machine learning to speedup the exploration.
  arXiv  Detail & Related papers  (2020-08-08T02:53:09Z)
• Learning High-Level Policies for Model Predictive Control [54.00297896763184]
  Model Predictive Control (MPC) provides robust solutions to robot control tasks. We propose a self-supervised learning algorithm for learning a neural network high-level policy. We show that our approach can handle situations that are difficult for standard MPC.
  arXiv  Detail & Related papers  (2020-07-20T17:12:34Z)
• 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.