A reinforcement learning guided hybrid evolutionary algorithm for the latency location routing problem

• URL: http://arxiv.org/abs/2403.14405v1
• Date: Thu, 21 Mar 2024 13:54:03 GMT
• Title: A reinforcement learning guided hybrid evolutionary algorithm for the latency location routing problem
• Authors: Yuji Zou, Jin-Kao Hao, Qinghua Wu,
• Abstract summary: The latency location routing problem integrates the facility location problem and the cumulative capacitated vehicle routing problem. This problem involves making simultaneous decisions about depot locations and vehicle routes to serve customers. We propose a reinforcement learning guided hybrid evolutionary algorithm following the framework of the memetic algorithm.
• Score: 14.9829752183927
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The latency location routing problem integrates the facility location problem and the multi-depot cumulative capacitated vehicle routing problem. This problem involves making simultaneous decisions about depot locations and vehicle routes to serve customers while aiming to minimize the sum of waiting (arriving) times for all customers. To address this computationally challenging problem, we propose a reinforcement learning guided hybrid evolutionary algorithm following the framework of the memetic algorithm. The proposed algorithm relies on a diversity-enhanced multi-parent edge assembly crossover to build promising offspring and a reinforcement learning guided variable neighborhood descent to determine the exploration order of multiple neighborhoods. Additionally, strategic oscillation is used to achieve a balanced exploration of both feasible and infeasible solutions. The competitiveness of the algorithm against state-of-the-art methods is demonstrated by experimental results on the three sets of 76 popular instances, including 51 improved best solutions (new upper bounds) for the 59 instances with unknown optima and equal best results for the remaining instances. We also conduct additional experiments to shed light on the key components of the algorithm.

Related papers

• A Multi-population Integrated Approach for Capacitated Location Routing [14.897794986447474]
  This paper presents a multi-population integrated framework for the capacitated location-routing problem. It includes an effective neighborhood-based local search, a feasibility-restoring procedure and a diversification-oriented mutation. Experiments on 281 benchmark instances from the literature show that the algorithm performs remarkably well.
  arXiv  Detail & Related papers  (2024-03-14T13:11:30Z)
• Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
  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.
  arXiv  Detail & Related papers  (2023-10-22T02:46:37Z)
• Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving [73.58829980121767]
  We present a novel method for solving square jigsaw puzzles based on global optimization. The method is fully automatic, assumes no prior information, and can handle puzzles with known or unknown piece orientation.
  arXiv  Detail & Related papers  (2023-03-26T18:53:51Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• 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)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Distributed Multi-agent Meta Learning for Trajectory Design in Wireless Drone Networks [151.27147513363502]
  This paper studies the problem of the trajectory design for a group of energyconstrained drones operating in dynamic wireless network environments. A value based reinforcement learning (VDRL) solution and a metatraining mechanism is proposed.
  arXiv  Detail & Related papers  (2020-12-06T01:30:12Z)
• 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)
• A Hybrid Multi-Objective Carpool Route Optimization Technique using Genetic Algorithm and A* Algorithm [0.0]
  This work presents a hybrid GA-A* algorithm to obtain optimal routes for the carpooling problem. The routes obtained maximize the profit of the service provider by minimizing the travel and detour distance as well as pick-up/drop costs. The proposed algorithm has been implemented over the Salt Lake area of Kolkata.
  arXiv  Detail & Related papers  (2020-07-11T14:13:20Z)
• 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.