Memetic Search for Green Vehicle Routing Problem with Private Capacitated Refueling Stations

• URL: http://arxiv.org/abs/2504.04527v1
• Date: Sun, 06 Apr 2025 15:52:49 GMT
• Title: Memetic Search for Green Vehicle Routing Problem with Private Capacitated Refueling Stations
• Authors: Rui Xu, Xing Fan, Shengcai Liu, Wenjie Chen, Ke Tang,
• Abstract summary: This article presents METS, a novel memetic algorithm (MA) with separate constraint-based tour segmentation (SCTS) and efficient local search (ELS) for solving GVRP-PCAFS.<n>For global search, the SCTS strategy splits giant tours to generate diverse solutions, and the search process is guided by a comprehensive fitness evaluation function.<n>For local search, ELS incorporates tailored move operators with constant-time move evaluation mechanisms, enabling efficient exploration of large solution neighborhoods.
• Score: 25.615777593601262
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The green vehicle routing problem with private capacitated alternative fuel stations (GVRP-PCAFS) extends the traditional green vehicle routing problem by considering refueling stations limited capacity, where a limited number of vehicles can refuel simultaneously with additional vehicles must wait. This feature presents new challenges for route planning, as waiting times at stations must be managed while keeping route durations within limits and reducing total travel distance. This article presents METS, a novel memetic algorithm (MA) with separate constraint-based tour segmentation (SCTS) and efficient local search (ELS) for solving GVRP-PCAFS. METS combines global and local search effectively through three novelties. For global search, the SCTS strategy splits giant tours to generate diverse solutions, and the search process is guided by a comprehensive fitness evaluation function to dynamically control feasibility and diversity to produce solutions that are both diverse and near-feasible. For local search, ELS incorporates tailored move operators with constant-time move evaluation mechanisms, enabling efficient exploration of large solution neighborhoods. Experimental results demonstrate that METS discovers 31 new best-known solutions out of 40 instances in existing benchmark sets, achieving substantial improvements over current state-of-the-art methods. Additionally, a new large-scale benchmark set based on real-world logistics data is introduced to facilitate future research.

Related papers

• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [55.78505925402658]
  Vehicle Routing Problems (VRP) are an extension of the Traveling Salesperson Problem and are a fundamental NP-hard challenge in Evolutionary optimization. We introduce a novel optimization framework that uses a reinforcement learning agent - trained on prior instances - to quickly generate initial solutions, which are then further optimized by genetic algorithms. For example, EARLI handles vehicle routing with 500 locations within 1s, 10x faster than current solvers for the same solution quality, enabling applications like real-time and interactive routing.
  arXiv  Detail & Related papers  (2025-04-08T15:21:01Z)
• SCoTT: Wireless-Aware Path Planning with Vision Language Models and Strategic Chains-of-Thought [78.53885607559958]
  A novel approach using vision language models (VLMs) is proposed for enabling path planning in complex wireless-aware environments. To this end, insights from a digital twin with real-world wireless ray tracing data are explored. Results show that SCoTT achieves very close average path gains compared to DP-WA* while at the same time yielding consistently shorter path lengths.
  arXiv  Detail & Related papers  (2024-11-27T10:45:49Z)
• Applying Neural Monte Carlo Tree Search to Unsignalized Multi-intersection Scheduling for Autonomous Vehicles [7.32653612106583]
  We introduce a transformation model that maps sequences of potentially conflicting road-space reservation requests from platoons of vehicles into a series of board-game-like problems. We use NMCTS to search for solutions representing optimal road-space allocation schedules in the context of past allocations. We show that the proposed method maintained free-flow in light traffic when all intersections are under control of PNMCTS and outperformed state-of-the-art RL-based traffic-light controllers in average travel time by 74.5% and total throughput by 16% in heavy traffic.
  arXiv  Detail & Related papers  (2024-10-24T14:37:55Z)
• FH-DRL: Exponential-Hyperbolic Frontier Heuristics with DRL for accelerated Exploration in Unknown Environments [1.8749305679160366]
  This paper introduces FH-DRL, a novel framework that integrates a customizable function for frontier detection with a Twin Delayed DDPG (TD3) agent for continuous, high-speed local navigation.<n>We thoroughly evaluate FH-DRL across multiple simulated and real-world scenarios, demonstrating clear improvements in travel distance and completion time.<n>The results highlight FH-DRL as an efficient and general approach for frontier-based exploration in large or partially known environments.
  arXiv  Detail & Related papers  (2024-07-26T17:42:18Z)
• Using Reinforcement Learning for the Three-Dimensional Loading Capacitated Vehicle Routing Problem [40.50169360761464]
  Collaborative vehicle routing has been proposed as a solution to increase efficiency. Current operations research methods suffer from non-linear scaling with increasing problem size. We develop a reinforcement learning model to solve the three-dimensional loading capacitated vehicle routing problem in approximately linear time.
  arXiv  Detail & Related papers  (2023-07-22T18:05:28Z)
• DenseLight: Efficient Control for Large-scale Traffic Signals with Dense Feedback [109.84667902348498]
  Traffic Signal Control (TSC) aims to reduce the average travel time of vehicles in a road network. Most prior TSC methods leverage deep reinforcement learning to search for a control policy. We propose DenseLight, a novel RL-based TSC method that employs an unbiased reward function to provide dense feedback on policy effectiveness.
  arXiv  Detail & Related papers  (2023-06-13T05:58:57Z)
• Multi-Start Team Orienteering Problem for UAS Mission Re-Planning with Data-Efficient Deep Reinforcement Learning [9.877261093287304]
  We study a mission re-planning problem where vehicles are initially located away from the depot and have different amounts of fuel. We develop a policy network with self-attention on each partial tour and encoder-decoder attention between the partial tour and the remaining nodes. We propose a modified REINFORCE algorithm where the greedy rollout baseline is replaced by a local mini-batch baseline based on multiple, possibly non-duplicate sample rollouts.
  arXiv  Detail & Related papers  (2023-03-02T15:15:56Z)
• SRRT: Exploring Search Region Regulation for Visual Object Tracking [58.68120400180216]
  We propose a novel tracking paradigm, called Search Region Regulation Tracking (SRRT) SRRT applies a proposed search region regulator to estimate an optimal search region dynamically for each frame. On the large-scale LaSOT benchmark, SRRT improves SiamRPN++ and TransT with absolute gains of 4.6% and 3.1% in terms of AUC.
  arXiv  Detail & Related papers  (2022-07-10T11:18:26Z)
• On the Role of Multi-Objective Optimization to the Transit Network Design Problem [0.7734726150561088]
  This work shows that single and multi objective stances can be synergistically combined to better answer the transit network design problem (TNDP) As a guiding case study, the solution is applied to the multimodal public transport network in the city of Lisbon, Portugal. The proposed TNDP optimization proved to improve results, with reductions in objective functions of up to 28.3%.
  arXiv  Detail & Related papers  (2022-01-27T16:22:07Z)
• Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem [13.389057146418056]
  Vehicles in real-world scenarios are likely to be heterogeneous with different characteristics that affect their capacity (or travel speed) We propose a DRL method based on the attention mechanism with a vehicle selection decoder accounting for the heterogeneous fleet constraint and a node selection decoder accounting for the route construction, which learns to construct a solution by automatically selecting both a vehicle and a node for this vehicle at each step.
  arXiv  Detail & Related papers  (2021-10-06T10:05:19Z)
• Flatland Competition 2020: MAPF and MARL for Efficient Train Coordination on a Grid World [49.80905654161763]
  The Flatland competition aimed at finding novel approaches to solve the vehicle re-scheduling problem (VRSP) The VRSP is concerned with scheduling trips in traffic networks and the re-scheduling of vehicles when disruptions occur. The ever-growing complexity of modern railway networks makes dynamic real-time scheduling of traffic virtually impossible.
  arXiv  Detail & Related papers  (2021-03-30T17:13:29Z)
• 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.