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

• Bi-level RL-Heuristic Optimization for Real-world Winter Road Maintenance [3.7856931422411346]
  Winter road maintenance is critical for ensuring public safety and reducing environmental impacts.<n>Existing methods struggle to manage large-scale routing problems effectively and mostly reply on human decision.<n>This study presents a novel, scalable bi-level optimization framework, validated on real operational data on UK strategic road networks.
  arXiv  Detail & Related papers  (2026-02-27T15:37:35Z)
• Scalable Transit Delay Prediction at City Scale: A Systematic Approach with Multi-Resolution Feature Engineering and Deep Learning [1.065661841579261]
  Most existing delay prediction systems handle only a few routes, depend on hand-crafted features, and offer little guidance on how to design a reusable architecture.<n>We present a city-scale prediction pipeline that combines multi-resolution feature engineering, dimensionality reduction, and deep learning.<n>A global LSTM with cluster-aware features achieves the best trade-off between accuracy and efficiency, outperforming transformer models by 18 52% to 52%.
  arXiv  Detail & Related papers  (2026-01-26T14:30:50Z)
• Rich Vehicle Routing Problem in Disaster Management enabling Temporally-causal Transhipments across Multi-Modal Transportation Network [1.1470070927586018]
  A rich vehicle routing problem is considered, allowing multiple trips of heterogeneous vehicles stationed at geographically distributed vehicle depots having access to different modes of transportation.<n>The problem arises from the real-world requirement of optimizing the disaster response time by minimizing the makespan of vehicular routes.<n>The superiority of the proposed cascaded minimization approach is demonstrated through our developed Mixed-Integer Linear Programming formulation.
  arXiv  Detail & Related papers  (2025-09-16T16:37:18Z)
• 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)
• Scalable Ride-Sourcing Vehicle Rebalancing with Service Accessibility Guarantee: A Constrained Mean-Field Reinforcement Learning Approach [42.070187224580344]
  We introduce continuous-state mean-field control (MFC) and mean-field reinforcement learning (MFRL) models that employ continuous vehicle repositioning actions.<n>MFC and MFRL offer scalable solutions by modeling each vehicle's behavior through interaction with the vehicle distribution, rather than with individual vehicles.<n>Our approach scales to tens of thousands of vehicles, with training times comparable to the decision time of a single linear programming rebalancing.
  arXiv  Detail & Related papers  (2025-03-31T15:00:11Z)
• Towards Intelligent Transportation with Pedestrians and Vehicles In-the-Loop: A Surveillance Video-Assisted Federated Digital Twin Framework [62.47416496137193]
  We propose a surveillance video assisted federated digital twin (SV-FDT) framework to empower ITSs with pedestrians and vehicles in-the-loop.<n>The architecture consists of three layers: (i) the end layer, which collects traffic surveillance videos from multiple sources; (ii) the edge layer, responsible for semantic segmentation-based visual understanding, twin agent-based interaction modeling, and local digital twin system (LDTS) creation in local regions; and (iii) the cloud layer, which integrates LDTSs across different regions to construct a global DT model in realtime.
  arXiv  Detail & Related papers  (2025-03-06T07:36:06Z)
• 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)
• TOP-Former: A Multi-Agent Transformer Approach for the Team Orienteering Problem [47.40841984849682]
  Route planning for a fleet of vehicles is an important task in applications such as package delivery, surveillance, or transportation.<n>We introduce TOP-Former, a multi-agent route planning neural network designed to efficiently and accurately solve the Team Orienteering Problem.
  arXiv  Detail & Related papers  (2023-11-30T16:10:35Z)
• 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.