Trilevel Memetic Algorithm for the Electric Vehicle Routing Problem

Ivan Milinovi\'c; Leon Stjepan Uroi\'c; Marko {\DJ}urasevi\'c

REVIEW 3 major objections 4 minor 19 references

Trilevel Memetic Algorithm for the Electric Vehicle Routing Problem

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A trilevel memetic algorithm splits EV routing into customer-order search, route-assignment DP, and charging-station DP, and matches best-known solutions on small WCCI2020 instances.

desk verdict A trilevel memetic decomposition with DP in the fitness loop is a real engineering idea, but the printed DP recurrences are not well-formed and the competitive claims rest on uneven comparisons and excluded instances. read the letter →

arxiv 2506.01065 v1 pith:XFHP5NRE submitted 2025-06-01 cs.NE cs.AI

Ivan Milinović , Leon Stjepan Uroić , Marko {DJ}urasević This is my paper

classification cs.NEcs.AI MSC 90B0690C3990C59

keywords ElectricVehicleRoutingProblemmemeticalgorithmgeneticdynamicprogrammingfixedroutechargingtrileveldecompositionWCCI2020benchmarkstationinsertion

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proposes a Trilevel Memetic Algorithm (TMA) for the Electric Vehicle Routing Problem, arguing that the problem splits cleanly into three stacked subproblems: a genetic algorithm that searches over customer permutations, a dynamic program that partitions each permutation into capacity-feasible routes, and a second dynamic program that inserts charging stations. The division lets the two lower layers be solved optimally (up to a battery-discretization parameter $K$), so the evolutionary search only has to find good customer orders. On the WCCI2020 benchmark, TMA matches the best-known solution values for the small instances E22, E23, E30 and E51 and comes close on E33, E76 and E101, while lagging on large instances because the charging-insertion DP is a computational bottleneck. The authors conclude that the approach is competitive for small-scale sustainable-logistics planning and that faster charging insertion would improve scalability.

What carries the argument

The central machinery is the trilevel decomposition. The top level is a memetic algorithm whose individuals are permutations of customers only; it uses rank-based selection, a distributed crossover, heuristic-swap and heuristic-move mutations, and a local search restricted to intra-route customer order. The second level is a route-assignment dynamic program that fills $dp[i][j]$---the minimal distance to serve the first $j$ customers of the permutation while ending with $i$ units of cargo capacity---using direct moves (Eq. 9) and depot detours (Eq. 10). The third level is a charging-station insertion dynamic program that extends the fixed-route charging DP of Deschênes et al. to allow multiple charging stations between customers; it discretizes battery capacity into $K$ bins, precomputes optimal paths between entry and exit stations with A* stored in table $C$, and updates via Eqs. (11) and (12). These recurrences are what turn a customer permutation into a full, feasible route plan, and their correctness is the load-bearing assumption of the whole method.

What would settle it

Run the route-assignment DP (Eqs. 9-10) on a single short customer permutation with integer demands, then compute the optimal partition by exhaustive enumeration of all depot insertions; if the DP's reported minimum differs for any demand pattern where the correct state would be $dp[Q-d_j][j]$ rather than $dp[Q-d_j-1][j]$, the lower level is not optimal and the fitness the GA maximizes is wrong. The same check can be applied to Eq. (12) for a route with two charging stations.

Watch

Extended reading notes

Core claim

The paper's central claim is that a trilevel decomposition makes the Electric Vehicle Routing Problem tractable to a memetic search: customer permutations are evolved by a genetic algorithm, and the two remaining decisions---where to insert depot visits and where to insert charging stations---are delegated to dynamic programs that are optimal for a given permutation (the charging DP optimal in the limit as the number of battery bins goes to infinity). This is presented as an improvement over previous GA-based EVRP solvers and competitive with state-of-the-art heuristics. The evidence is the WCCI2020 benchmark table, where the method's best solutions equal the best-known solutions on E22, E23, E30 and E51, its means are close on E33, E76 and E101, and its performance on large instances is limited by the slow charging-insertion routine rather than by solution quality per evaluation.

Load-bearing premise

The load-bearing premise is that the dynamic-programming recurrences in Section IV-F and IV-G compute the true optimal route partition and charging plan for a given customer permutation, so the fitness the genetic algorithm sees is the real route cost.

Editorial extensions

If this is right

On the small instances E22, E23, E30 and E51, TMA's best solutions equal the best-known values, and on E22, E23 and E30 the mean equals the best-known value with zero standard deviation over 20 runs.
Because the lower two levels are asserted optimal (the charging level optimal as the number of bins grows), the residual gap on E33, E76 and E101 is attributed to the customer-order search and the discretization, not to the way routes are assembled or charged.
The charging-insertion DP dominates runtime with $O(n K m^2)$ complexity; the authors note TMA ran far fewer generations than the competition's evaluation limit allows, so a faster insertion routine is the stated path to matching best-known results on large instances.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper never explains the '-1' terms in the DP recurrences: Eq. (10) writes $dp[Q-d_j-1][j]$ where a natural cargo-accounting update would be $dp[Q-d_j][j]$, and Eq. (12) similarly uses $K-e_{encs}-1$; if these are off-by-one indexing errors, the lower-level 'optimal' fitness is systematically wrong, and the genetic search is optimizing a surrogate objective rather than true route cost.
A consequence the authors do not draw is that the same trilevel skeleton could be reused for EVRP variants---time windows, partial recharge, mixed fleets---by swapping only the second- and third-level dynamic programs and leaving the permutation-level genetic machinery unchanged.
If the -1 terms are genuine errors, a cheap falsification is to compare Eq. (10)'s output against exhaustive enumeration on one small permutation; if they are intentional, the paper should show the state-index derivation, since the current text gives none.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The core architecture is the genuinely new part: a memetic GA on customer permutations, with an optimal route-partition DP and a discretized charging-insertion DP called inside every fitness evaluation. That is a legitimate engineering combination, and the paper is upfront that the GA operators come from Hien et al. and the charging DP extends Deschênes et al. The decomposition into three levels is sensible, and the authors clearly state the approximation introduced by energy-binning and the computational bottleneck it creates. I credit them for that honesty.

The soft spots are real and load-bearing. The DP recurrences in Eqs. (10) and (12) are not well-formed as printed. Eq. (10) writes dp[Q-d_j-1][j] where the state invariant implies dp[Q-d_j][j], and the right-hand side uses free variable i with no quantifier. Eq. (12) has similar undefined offsets. These may be typos, but since the lower levels are claimed optimal and their output feeds every fitness evaluation, an error here means the genetic search optimizes the wrong objective. There is no correctness proof and no code to disambiguate. That alone prevents me from trusting the reported results.

On top of that, the experimental comparison is not as clean as the abstract suggests. The abstract claims matching best-known results on small-scale cases, but Table II shows exact matches only on E22, E23, E30, and E51; E33, E76, and E101 are missed. Several instances were excluded due to slow charging-insertion, and the authors admit TMA ran far fewer generations than the benchmark allowed. That does not invalidate the method, but it means the reported numbers are not yet evidence of competitiveness at an equal budget.

The citation pattern is fine: the one self-citation is not load-bearing, and the paper correctly credits prior component work. The writing is clear and the related-work section is adequate.

Who is this for? Researchers working on EVRP heuristics, especially those interested in hybrid GA+DP decompositions. They will find the trilevel idea worth discussing, and the DP issues worth dissecting. With code and corrected recurrences, this could become a useful baseline. As it stands, the central empirical claim is not secured.

My recommendation: send it to peer review, but with the clear expectation of major revision. The reviewers should ask for the code, corrected recurrences, a correctness argument for the DPs, and results on the full WCCI2020 set with a fair computational budget.

Referee Report

3 major / 4 minor

Summary. The paper proposes a Trilevel Memetic Algorithm (TMA) for the Electric Vehicle Routing Problem. The upper level evolves customer permutations with a genetic algorithm; the middle level partitions a permutation into routes by inserting depot visits via dynamic programming; the lower level inserts charging stations using a discretized DP for the Fixed-Route EV Charging Problem. The authors evaluate TMA on WCCI2020 benchmark instances and report that it matches best-known solutions on small instances, with larger instances showing larger gaps. The manuscript also acknowledges two limitations: some instances were excluded because the charging-station DP was too slow, and TMA was run for fewer evaluations than allowed by the competition protocol.

Significance. If the two dynamic programs are correct, the trilevel decomposition is a sensible and potentially useful design: it gives a polynomial-time optimal subroutine for route partitioning (for integer demands) and an asymptotically convergent approximation for charging insertion. The paper is also candid about discretization error and computational bottlenecks, which is helpful. However, the printed recurrences are not well-formed, the comparison protocol is not head-to-head, and the abstract overstates the small-instance result; these issues currently prevent the reader from attributing the reported numbers to the described algorithm.

major comments (3)

[Section IV-F, Eq. (10)] The route-assignment DP is the fitness evaluator for every individual in the genetic search, yet Eq. (10) as printed is not a computable recurrence. Under the stated invariant, dp[i][j] is the minimal distance after serving the first j customers with i units of cargo left; a depot insertion before customer j resets cargo to Q and then consumes demand d_j, so the destination row should be Q-d_j, not Q-d_j-1. In addition, the right-hand side reads dp[i][j-1] with no quantifier over i, and the depot distances are not minimized over the previous cargo level. Please correct the recurrence, give the base case and backtracking rule, and provide a proof (or a precise reference) that it returns an optimal route partition for every permutation.
[Section IV-G, Eq. (12)] The charging-insertion DP has the same well-formedness problem. Eq. (12) writes dp[K-e_encs-1][j] and dp[K-e_ecs-1][j] without defining e_encs or e_ecs, and the '-1' offset is unexplained; it also leaves the previous-state index i free. Eq. (11) appears to contain a subscript typo (dp[i+e_j,j-1][j-1] instead of an index depending on e_{j-1}). Because this DP is the second half of the fitness evaluation, the reported solution qualities cannot be reproduced from the text alone. Please define the discretization, all variables, and the full DP including how C[encs][excs] is precomputed, and release pseudocode or code.
[Section V-B, V-C, Table II] The experimental comparison is not yet evidence for the abstract's claim. Section V-B states that 'a few problem instances with a lot of charging stations were excluded' without naming them, and Section V-C admits that TMA ran for 'substantially fewer iterations than the maximum allowed by the benchmark rules'; Table II then compares TMA minima with competitors that, for at least some rows, used the full protocol. Moreover, the exact-match claim in the abstract holds for only four of the seven small instances: TMA matches BKS on E22, E23, E30, and E51, but misses on E33, E76, and E101. Please re-run under a truly equal evaluation budget, report all WCCI2020 instances, list any exclusions, and soften or qualify the abstract. It should also be stated whether the listed competitor numbers are taken from the literature or produced with the same code/validation harness.

minor comments (4)

[Algorithm 1] The loop bounds in Algorithm 1 appear inconsistent with the textual description; 'for i←l to k−1' and 'for j←i+1 to l' do not clearly range over the segment from c_k to c_l, and the variable l is not defined in the loop header. Please rewrite the pseudocode so that the indices are unambiguous.
[Table II] The min/mean/std rows are not labeled for every column, and the X214 mean for TMA is printed as '121842' without a decimal point; several competitor entries are missing standard deviations (e.g., GA for X1001). Please reformat the table so each row and entry is unambiguous.
[Table I] Table I lists hyperparameters but not the number of energy-discretization bins K used during optimization, apart from the 'Energy repair bin count while opt.' value of 151. Since K controls the approximation quality of the lower-level DP, please state K explicitly for both the optimization and repair phases and describe how it was chosen.
[References] The sentence describing reference [13] reads 'perform 20%-37% worse to the best known results'; please rephrase to 'worse than the best-known results' and add a citation or table if the comparison is quantitative.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central claim is benchmarked against external WCCI2020 instances, and the lower-level DPs are not fitted to the target results.

full rationale

The paper's central claim is that TMA matches best-known results on WCCI2020 instances. These instances and their best-known solution values come from the external WCCI2020 competition suite [16], not from the paper's own outputs, so the comparison is not self-referential. The lower-level dynamic programs in Sections IV-F and IV-G define the fitness evaluator for a given customer permutation; while their correctness is asserted rather than proven and the printed recurrences contain apparent indexing issues, that is a correctness risk, not circularity. The objective being minimized is the externally defined EVRP distance of Eq. (1), and no parameter is fitted to the reported best-known values. The only author self-citation ([13], Gil-Gala et al.) appears in related work to describe another method's performance and is not load-bearing for TMA. No fitted input is renamed as a prediction, and no uniqueness result from the authors' prior work is invoked to force the design. The derivation chain therefore has no circular step.

Assumptions & free parameters 6 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the correctness of two dynamic programs, on standard EVRP modeling assumptions, and on a set of hand-chosen hyperparameters. The paper supplies no proof of DP optimality and no code to check the implementation.

free parameters (6)

Energy discretization bins K during optimization = 151
Hand-chosen discretization; the claimed optimality of charging insertion only holds in the limit K to infinity, and the search uses a finite K.
Final energy repair bin count = 100001
Chosen for post-processing; affects final solution cost and is not derived from any principle.
Population size = 200
Algorithm hyperparameter chosen by hand, listed in Table I, directly affecting search behavior.
Selection pressure = 1.6
Algorithm hyperparameter chosen by hand, listed in Table I.
Number of elite individuals = 30
Algorithm hyperparameter chosen by hand, listed in Table I.
Stochastic nearest-neighbour candidates = 3
Algorithm hyperparameter chosen by hand, listed in Table I.

assumptions (4)

domain assumption The DP recurrences in Equations (9) to (12) correctly compute optimal route partitions and charging plans.
Assumed throughout Sections IV-F and IV-G, but no correctness proof is given and Equations (10) and (12) contain unexplained -1 index terms.
domain assumption Battery recharge is full and instantaneous at charging stations.
Equation (12) resets residual energy to K-e_encs-1 after charging, which implies full recharge, but the problem statement in Section II does not explicitly state this modeling choice.
domain assumption Battery consumption is linear in distance with a fixed rate h.
Section II defines consumption as h times d_ij, which is the standard basic EVRP model but restricts generality.
domain assumption The best-known solutions (BKS) in Table II are reliable and representative.
Table II reports BKS values without citing their source, so the comparison targets cannot be independently verified.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Trilevel Memetic Algorithm for the Electric Vehicle Routing Problem." pith.science (2026). https://pith.science/paper/XFHP5NRE

@misc{pith2026250601065,
  author       = {Pith},
  title        = {Pith review of: Trilevel Memetic Algorithm for the Electric Vehicle Routing Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XFHP5NRE}},
  note         = {Machine review of arXiv:2506.01065}
}

read the original 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.

Figures

Figures reproduced from arXiv: 2506.01065 by the authors.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

19 extracted references · 12 canonical work pages

[1]

Global ev outlook 2023,

I. E. Agency, “Global ev outlook 2023,” 2023. [Online]. Available: https://www.iea.org/reports/global-ev-outlook-2023

work page 2023
[2]

A green vehicle routing problem,

S. Erdo ˘gan and E. Miller-Hooks, “A green vehicle routing problem,” Transportation research part E: logistics and transportation review, vol. 48, no. 1, pp. 100–114, 2012

2012
[3]

A survey on the electric vehicle routing problem: variants and solution approaches,

T. Erdeli ´c and T. Cari ´c, “A survey on the electric vehicle routing problem: variants and solution approaches,”Journal of Advanced Trans- portation, vol. 2019, no. 1, p. 5075671, 2019

work page 2019
[4]

Partial recharge strategies for the electric vehicle routing problem with time windows,

M. Keskin and B. Çatay, “Partial recharge strategies for the electric vehicle routing problem with time windows,”Transportation research part C: emerging technologies, vol. 65, pp. 111–127, 2016

work page 2016
[5]

The electric vehicle-routing problem with time windows and recharging stations,

M. Schneider, A. Stenger, and D. Goeke, “The electric vehicle-routing problem with time windows and recharging stations,”Transportation science, vol. 48, no. 4, pp. 500–520, 2014

2014
[6]

Ant colony op- timization for the electric vehicle routing problem,

M. Mavrovouniotis, G. Ellinas, and M. Polycarpou, “Ant colony op- timization for the electric vehicle routing problem,” in2018 IEEE Symposium series on computational intelligence (SSCI). IEEE, 2018, pp. 1234–1241

work page 2018
[7]

A bilevel ant colony optimization algorithm for capacitated electric vehicle routing problem,

Y .-H. Jia, Y . Mei, and M. Zhang, “A bilevel ant colony optimization algorithm for capacitated electric vehicle routing problem,”IEEE Trans- actions on Cybernetics, vol. 52, no. 10, pp. 10 855–10 868, 2022

work page 2022
[8]

A matheuristic method for the electric vehicle routing problem with time windows and fast chargers,

M. Keskin and B. Çatay, “A matheuristic method for the electric vehicle routing problem with time windows and fast chargers,”Computers & operations research, vol. 100, pp. 172–188, 2018

work page 2018

Show all 19 references

[9]

Deep reinforcement learning for the electric vehicle routing problem with time windows,

B. Lin, B. Ghaddar, and J. Nathwani, “Deep reinforcement learning for the electric vehicle routing problem with time windows,”IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 8, pp. 11 528–11 538, 2021

2021
[10]

An end-to-end deep reinforcement learning framework for electric vehicle routing problem,

M. Wang, Y . Wei, X. Huang, and S. Gao, “An end-to-end deep reinforcement learning framework for electric vehicle routing problem,” IEEE Internet of Things Journal, 2024

2024
[11]

A greedy search based evolutionary algorithm for electric vehicle routing problem,

V . Q. Hien, T. C. Dao, and H. T. T. Binh, “A greedy search based evolutionary algorithm for electric vehicle routing problem,”Applied Intelligence, vol. 53, no. 3, pp. 2908–2922, 2023

2023
[12]

Coordinated charging scheduling of electric vehicles: a mixed-variable differential evolution approach,

W.-L. Liu, Y .-J. Gong, W.-N. Chen, Z. Liu, H. Wang, and J. Zhang, “Coordinated charging scheduling of electric vehicles: a mixed-variable differential evolution approach,”IEEE Transactions on Intelligent Trans- portation Systems, vol. 21, no. 12, pp. 5094–5109, 2019

2019
[13]

Evolving routing policies for electric vehicles by means of genetic programming,

F. J. Gil-Gala, M. Ðurasevi ´c, and D. Jakobovi ´c, “Evolving routing policies for electric vehicles by means of genetic programming,”Applied Intelligence, vol. 54, no. 23, pp. 12 391–12 419, 2024

2024
[14]

Computers and intractability: a guide to the theory of np-completeness (michael r. garey and david s. johnson),

J. Hartmanis, “Computers and intractability: a guide to the theory of np-completeness (michael r. garey and david s. johnson),”Siam Review, vol. 24, no. 1, p. 90, 1982

1982
[15]

Dynamic program- ming for the fixed route electric vehicle charging problem with nonlinear energy management,

A. Deschênes, J. Gaudreault, and C.-G. Quimper, “Dynamic program- ming for the fixed route electric vehicle charging problem with nonlinear energy management,” in2022 IEEE 25th International Conference on Intelligent Transportation Systems (ITSC). IEEE, 2022, pp. 3956–3962

2022
[16]

A benchmark test suite for the electric capacitated vehicle routing problem,

M. Mavrovouniotis, C. Menelaou, S. Timotheou, G. Ellinas, C. Panayiotou, and M. Polycarpou, “A benchmark test suite for the electric capacitated vehicle routing problem,” in2020 IEEE Congress on evolutionary computation (CEC). IEEE, 2020, pp. 1–8

2020
[17]

An algorithm for the vehicle-dispatching problem,

N. Christofides and S. Eilon, “An algorithm for the vehicle-dispatching problem,”Journal of the Operational Research Society, vol. 20, no. 3, pp. 309–318, 1969

1969
[18]

New benchmark instances for the capacitated vehicle routing problem,

E. Uchoa, D. Pecin, A. Pessoa, M. Poggi, T. Vidal, and A. Subramanian, “New benchmark instances for the capacitated vehicle routing problem,” European Journal of Operational Research, vol. 257, no. 3, pp. 845–858, 2017

2017
[19]

The electric vehicle routing problem with nonlinear charging functions,

Y . Liang, S. Dabia, and Z. Luo, “The electric vehicle routing problem with nonlinear charging functions,”arXiv preprint arXiv:2108.01273, 2021

2021 arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Global ev outlook 2023,

I. E. Agency, “Global ev outlook 2023,” 2023. [Online]. Available: https://www.iea.org/reports/global-ev-outlook-2023

work page 2023

[2] [2]

A green vehicle routing problem,

S. Erdo ˘gan and E. Miller-Hooks, “A green vehicle routing problem,” Transportation research part E: logistics and transportation review, vol. 48, no. 1, pp. 100–114, 2012

2012

[3] [3]

A survey on the electric vehicle routing problem: variants and solution approaches,

T. Erdeli ´c and T. Cari ´c, “A survey on the electric vehicle routing problem: variants and solution approaches,”Journal of Advanced Trans- portation, vol. 2019, no. 1, p. 5075671, 2019

work page 2019

[4] [4]

Partial recharge strategies for the electric vehicle routing problem with time windows,

M. Keskin and B. Çatay, “Partial recharge strategies for the electric vehicle routing problem with time windows,”Transportation research part C: emerging technologies, vol. 65, pp. 111–127, 2016

work page 2016

[5] [5]

The electric vehicle-routing problem with time windows and recharging stations,

M. Schneider, A. Stenger, and D. Goeke, “The electric vehicle-routing problem with time windows and recharging stations,”Transportation science, vol. 48, no. 4, pp. 500–520, 2014

2014

[6] [6]

Ant colony op- timization for the electric vehicle routing problem,

M. Mavrovouniotis, G. Ellinas, and M. Polycarpou, “Ant colony op- timization for the electric vehicle routing problem,” in2018 IEEE Symposium series on computational intelligence (SSCI). IEEE, 2018, pp. 1234–1241

work page 2018

[7] [7]

A bilevel ant colony optimization algorithm for capacitated electric vehicle routing problem,

Y .-H. Jia, Y . Mei, and M. Zhang, “A bilevel ant colony optimization algorithm for capacitated electric vehicle routing problem,”IEEE Trans- actions on Cybernetics, vol. 52, no. 10, pp. 10 855–10 868, 2022

work page 2022

[8] [8]

A matheuristic method for the electric vehicle routing problem with time windows and fast chargers,

M. Keskin and B. Çatay, “A matheuristic method for the electric vehicle routing problem with time windows and fast chargers,”Computers & operations research, vol. 100, pp. 172–188, 2018

work page 2018