Trilevel Memetic Algorithm for the Electric Vehicle Routing Problem

• URL: http://arxiv.org/abs/2506.01065v1
• Date: Sun, 01 Jun 2025 16:08:43 GMT
• Title: Trilevel Memetic Algorithm for the Electric Vehicle Routing Problem
• Authors: Ivan Milinović, Leon Stjepan Uroić, Marko Đurasević,
• Abstract summary: This paper introduces a Trilevel Memetic Algorithm (TMA) that hierarchically optimize customer sequences, route assignments, and charging station insertions.<n> Benchmark tests on WCCI 2020 instances show competitive performance, matching best-known results for small-scale cases.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Electric Vehicle Routing Problem (EVRP) extends the capacitated vehicle routing problem by incorporating battery constraints and charging stations, posing significant optimization challenges. This paper introduces a Trilevel Memetic Algorithm (TMA) that hierarchically optimizes customer sequences, route assignments, and charging station insertions. The method combines genetic algorithms with dynamic programming, ensuring efficient and high-quality solutions. Benchmark tests on WCCI2020 instances show competitive performance, matching best-known results for small-scale cases. While computational demands limit scalability, TMA demonstrates strong potential for sustainable logistics planning.

Related papers

• Joint Optimization of Electric Vehicle Routes and Charging Locations Learning Charge Constraints Using QUBO Solver [5.616693462159185]
  We focus on the joint optimization of the location of charging stations and the routing of electric vehicles (EVs)<n>We propose a sequential optimization method utilizing the Bayesian inference and QUBO solvers, in which method the battery capacity constraints are automatically learned.<n>Applying this method to a routing problem of 20 locations, we confirmed that the learning process works well and efficient searches find good solutions.
  arXiv  Detail & Related papers  (2025-06-05T07:08:19Z)
• Dynamic Location Search for Identifying Maximum Weighted Independent Sets in Complex Networks [0.47248250311484113]
  We introduce a novel and efficient algorithm for solving the maximum weighted independent set (MWIS) problem.<n>Given the NP-hard nature of the MWIS problem, our proposed algorithm, DynLS, incorporates three key innovations to solve it effectively.<n>Our experimental results demonstrate DynLS's superior performance, consistently delivering high-quality solutions within 1000 seconds.
  arXiv  Detail & Related papers  (2025-05-07T10:35:53Z)
• Joint Resource Management for Energy-efficient UAV-assisted SWIPT-MEC: A Deep Reinforcement Learning Approach [50.52139512096988]
  6G Internet of Things (IoT) networks face challenges in remote areas and disaster scenarios where ground infrastructure is unavailable.<n>This paper proposes a novel aerial unmanned vehicle (UAV)-assisted computing (MEC) system enhanced by directional antennas to provide both computational and energy support for ground edge terminals.
  arXiv  Detail & Related papers  (2025-05-06T06:46:19Z)
• 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.<n>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.<n>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)
• Learning for Cross-Layer Resource Allocation in MEC-Aided Cell-Free Networks [71.30914500714262]
  Cross-layer resource allocation over mobile edge computing (MEC)-aided cell-free networks can sufficiently exploit the transmitting and computing resources to promote the data rate.<n>Joint subcarrier allocation and beamforming optimization are investigated for the MEC-aided cell-free network from the perspective of deep learning.
  arXiv  Detail & Related papers  (2024-12-21T10:18:55Z)
• 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)
• Hybrid Genetic Search for Dynamic Vehicle Routing with Time Windows [0.0]
  We adapt the Hybrid Genetic Search (HGS) algorithm, a successful solution for VRPTW, to the dynamic variant. Our approach modifies these components for DVRPTW, attempting to balance solution quality and constraints on future customer arrivals.
  arXiv  Detail & Related papers  (2023-07-21T11:16:49Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• Combinatorial Optimization enriched Machine Learning to solve the Dynamic Vehicle Routing Problem with Time Windows [5.4807970361321585]
  We propose a novel machine learning pipeline that incorporates an optimization layer. We apply this pipeline to a dynamic vehicle routing problem with waves, which was recently promoted in the EURO Meets NeurIPS Competition at NeurIPS 2022. Our methodology ranked first in this competition, outperforming all other approaches in solving the proposed dynamic vehicle routing problem.
  arXiv  Detail & Related papers  (2023-04-03T08:23:09Z)
• 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)
• DC3: A learning method for optimization with hard constraints [85.12291213315905]
  We present Deep Constraint Completion and Correction (DC3), an algorithm to address this challenge. DC3 implicitly completes partial solutions to satisfy equality constraints and unrolls-based corrections to satisfy inequality constraints. We demonstrate the effectiveness of DC3 in both synthetic optimization tasks and the real-world setting of AC optimal power flow.
  arXiv  Detail & Related papers  (2021-04-25T18:21:59Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

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.