Trilevel Memetic Algorithm for the Electric Vehicle Routing Problem
1 st Ivan Milinović, 2 nd Leon Stjepan Uroić, 3 rd Marko Đurasević · 2025
Read Trilevel Memetic Algorithm for the Electric Vehicle Routing Problem by 1 st Ivan Milinović, 2 nd Leon Stjepan Uroić, 3 rd Marko Đurasević (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01065.txt.
Introduction
Ivan Milinović, Leon Stjepan Uroić, and Marko Đurasević plan routes for electric delivery vans in a 2025 computing paper. Electric fleets add battery limits and charging stops to the classic routing puzzle. Their method works on three stacked levels: the order of stops, the split of stops among vans, and where charging fits in. A genetic search supplies variety, while exact dynamic programming polishes each piece.
On standard contest cases, the method matched the best known answers for small problems. Larger cases strain its computing budget, which the authors state plainly. The layered design still shows promise for green logistics planning. Delivery firms facing city emission rules need such tools that respect real battery limits.
Catalog record
| CREATOR | 1 st Ivan Milinović, 2 nd Leon Stjepan Uroić, 3 rd Marko Đurasević |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-01065
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Trilevel Memetic Algorithm for the Electric Vehicle Routing Problem 1 st Ivan Milinović, 2 nd Leon Stjepan Uroić, 3 rd Marko Đurasević 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. I Introduction The increasing demand for sustainable transportation has positioned electric vehicles (EVs) as a viable alternative to internal combustion engine vehicles. Governments around the world are promoting EV adoption through policy incentives and environmental regulations to mitigate greenhouse gas emissions and reduce dependence on fossil fuels [ 1 ] . As a result, electric vehicles are becoming more prevalent in both public and commercial transportation sectors. Despite their benefits such as zero tailpipe emissions, lower operating costs, and reduced noise pollution, EVs present unique operational challenges. Chief among these are limited driving range, long charging times, and a sparse distribution of charging infrastructure. These factors complicate traditional vehicle routing, especially for logistics operations that require timely and energy-efficient deliveries. Consequently, the Electric Vehicle Routing Problem (EVRP) has emerged as an important variant of the classical Vehicle Routing Problem (VRP), incorporating energy constraints and charging station decisions into the optimization process. Solving the EVRP is computationally difficult due to its combinatorial nature and the additional layer of complexity introduced by battery management. As exact methods often become impractical for large-scale instances, heuristic and metaheuristic approaches have gained popularity. Among these, Genetic Algorithms (GAs) have proven effective for solving a variety of routing and scheduling problems, thanks to their flexibility, global search capability, and robustness against local optima. In this study, we propose a GA-based method to solve the EVRP. The main contributions of this paper are described below: • An improved memetic algorithm for finding customer permutations • Trilevel solver structure • Optimal 1 1 1 For route assignment and charging station insertion as the number of bins approaches infinity. route assignment and charging station insertion in the optimization loop. The results demonstrate that genetic algorithms can provide high-quality solutions within reasonable computational times, offering a practical tool for companies transitioning to sustainable transportation models. Our method improves on the previously proposed solutions based on genetic algorithms and achieves results on par with other state of the art methods. II Problem Statement The Electric Vehicle Routing Problem (EVRP) seeks to find optimal routes for a fleet of homogeneous electric vehicles, minimizing the total distance traveled subject to the following constraints: • Every route must start and end at the depot. • Each customer must be visited exactly once. • The total demand of customers on a given route cannot exceed the vehicle’s maximum cargo capacity. • Vehicles must maintain sufficient battery energy throughout the route. Formally, the problem is defined on a weighted, fully connected graph G=(V,E) . The vertex set V=\{\bar{d}\}\cup V_{c}\cup\hat{V_{s}} includes a single depot node d , a set of customer nodes V_{c}=\{c_{1},c_{2},...,c_{n}\} , and an expanded set of charging stations \hat{V_{s}} . The latter consists of \beta_{i} copies of each original charging station s_{i} for i=1,2,...,m , ensuring sufficient representation for multiple visits. The edge set E=\{(i,j),\forall i,j\in V,i\neq j\} connects all vertices, with each edge (i,j) weighted by the Euclidean distance d_{ij} . When a vehicle traverses edge (i,j) , it consumes h\cdot d_{ij} units of battery energy, where h\in\mathbb{R}^{+} denotes the battery consumption rate. All vehicles are identical, sharing the same cargo capacity Q and battery capacity B . The EVRP can be formulated mathematically as follows: \displaystyle min\hskip 10.00002ptf(x)=\sum_{i\in V,j\in V,i\neq j}d_{ij}x_{ij}\quad\quad\quad s.t. (1) \displaystyle\sum_{j\in V,i\neq j}x_{ij}=1,\forall i\in V_{c} (2) \displaystyle\sum_{j\in V,i\neq j}x_{ij}\leq 1\quad\forall i\in\hat{V_{s}} (3) \displaystyle\sum_{j\in V}x_{ij}-\sum_{j\in V}x_{ji}=0\quad\forall i\in V (4) \displaystyle y_{j}\leq y_{i}-hd_{ij}x_{ij}+B(1-x_{ij})\quad\forall i\in V_{c},\forall j\in V,i\neq j (5) \displaystyle y_{j}\leq B-hd_{ij}x_{ij}\quad\forall i\in\hat{V_{s}}\cup\{d\},\forall j\in V,i\neq j (6) \displaystyle q_{j}\leq q_{i}-d_{i}x_{ij}+Q(1-x_{ij})\quad\forall(i,j)\in V,i\neq j (7) \displaystyle x_{ij}\in\{0,1\},\quad\forall i\in V,\forall j\in V,i\neq j (8) If the edge (i,j) is traversed by an electric vehicle, the binary variable x_{ij} equals one; otherwise, it is set to zero. Equation 1 defines the EVRP’s objective of minimizing the total distance traveled by all EVs. The remaining equations specify the constraints that a feasible solution must satisfy. Constraint 2 ensures that each customer node is visited exactly once. Similarly, Constraint 3 requires that each copy of a charging station is visited at most once. Constraint 4 guarantees flow conservation at every node, meaning the number of incoming edges equals the number of outgoing edges. This prevents route discontinuities (i.e., vehicles cannot "teleport" between nodes). In Constraints 5 and 6 , y_{i} represents the remaining battery charge level of an EV at node i . The former constraint governs battery consumption when traveling between customer nodes, while the latter applies when departing from a charging station or the depot. Finally, Constraint ( 7 ) tracks the remaining cargo capacity q_{i} at node i , enforcing that the total demand on a route cannot exceed the vehicle’s capacity Q and that the remaining cargo decreases after visiting a customer. III Related Work The Electric Vehicle Routing Problem (EVRP) extends the classical capacitated VRP by incorporating electric vehicles limited battery range and the need to visit charging stations. Its first variant was introduced by Erdoğan and Miller-Hooks [ 2 ] as the Green Vehicle Routing Problem. Afterwards many electric vehicle specific problem variants came about such as making the time it takes to recharge the vehicle a non-linear function. These extra constraints make EVRP harder than the standard VRP and have motivated numerous studies of EVRP variants (see, e.g., [ 3 ] for a survey). In this work we focus on the basic EVRP without any additional constraints. Many exact approaches model EVRP as a 0-1 mixed-integer linear program (MILP). For example, Keskin and Catay [ 4 ] extend VRP with time windows (VRPTW) formulations to EVRPTW by including battery energy consumption and allowing partial recharge. Generally, MILP formulations can be solved optimally only on very small problem instances [ 5 ] . Heuristic and metaheuristic methods are prevalent for EVRP [ 3 ] . Ant Colony Optimization (ACO) has been adapted in several studies. For instance, Mavrovouniotis et al. [ 6 ] incorporate a look-ahead feasibility check in ACO so that each EV can always reach a charging station. Jia et al. [ 7 ] propose a bilevel ACO that splits the problem into capacitated VRP (upper level) and fixed route vehicle charging problem (lower level). Similarly, large-neighborhood search methods have been developed. Keskin and Catay [ 4 ] design an adaptive large neighborhood search (ALNS) with new destroy-and-repair operators tailored to EV constraints, allowing partial recharging and yielding high-quality solutions. They further combine ALNS with CPLEX to tackle medium-size instances [ 8 ] . Schneider et al [ 5 ] proposed a hyhrid heuristic that combines VNS with tabu search for EVRPTW. Deep reinforcement learning (DRL) has also emerged as a promising approach to