Source-linked AI summary
The Electric Two-echelon Vehicle Routing Problem
Ulrich Breunig, Roberto Baldacci, Richard F. Hartl, Thibaut Vidal
TL;DR
The paper studies how electric vehicles and charging requirements complicate two-echelon delivery routing, where existing models largely focus on simpler single-echelon networks. It introduces the E2EVRP with heuristic and exact solution methods, finding strong solution quality and measurable effects of charging-station density and battery capacity, while noting that charging-station placement remains randomized.
Problem
Electric second-echelon deliveries require routing under limited vehicle range, charging needs, and satellite decisions, while prior electric-vehicle literature mainly considered single-depot, single-echelon networks.
Method
The paper introduces the E2EVRP and solves it with an LNS metaheuristic plus an exact decomposition method using first-level route enumeration, bounds, and second-level route enumeration.
Results
All known optimal small-instance solutions were retrieved by LNS-E2E, while medium-scale instances had an average best-known upper–lower-bound gap of 3.57%.
Takeaways & Limitations
Charging-station density and battery capacity are key design factors for optimized electric two-echelon distribution networks.
Takeaways & Limitations
Charging-station locations are randomized within a fixed area rather than optimized strategically, limiting the accuracy of the sensitivity analysis.
Abstract
from arXiv · showhide
Two-echelon distribution systems are attractive from an economical standpoint and help to keep large vehicles out of city centers. Large trucks can be used to deliver goods to intermediate facilities in accessible locations, whereas smaller vehicles allow to reach the final customers. Due to their reduced size and emissions, companies consider using an electric fleet of terrestrian or aerial vehicles for last mile deliveries. Route planning in multi-tier logistics leads to notoriously difficult problems. This difficulty is accrued in the presence of an electric fleet, since each vehicle operates on a smaller range, and may require visits to charging stations. To study these challenges, we introduce the Electric Two-echelon Vehicle Routing Problem as a prototypical problem. We propose a large neighbourhood search metaheuristic as well as an exact mathematical programming algorithm, which uses decomposition techniques to enumerate promising first-level solutions, in conjunction with bounding functions and route enumeration for the second-level routes. These algorithms produce optimal or near-optimal solutions for the problem, and allow us to evaluate the impact of several defining features of optimized battery-powered distribution networks. We created representative E2EVRP benchmark instances to simulate realistic metropolitan areas. In particular, we observe that the detour miles due to recharging decrease proportionally to $1/ρ^x$ with $x \approx 5/4$ as a function of the charging stations density $ρ$; e.g., in a scenario where the density of charging stations is doubled, recharging detours are reduced by 58\%. Finally, we evaluate the trade-off between battery capacity and detour miles. This estimate is critical for strategic fleet-acquisition decisions, in a context where large batteries are generally more costly and less environment-friendly.
1. Introduction
The paper introduces the Electric Two-echelon Vehicle Routing Problem (E2EVRP) to model metropolitan delivery with conventional first-level vehicles and electric second-level vehicles. It develops heuristic and exact algorithms and studies charging-network density and battery capacity in optimized distribution networks.
- Electric vehicles create routing challenges because of limited autonomy, smaller capacity, and possible charging-station visits.
- The E2EVRP extends the 2EVRP by delivering goods from a depot to satellites conventionally and from satellites to customers using electric vehicles.
- The proposed LNS metaheuristic combines destruction and reconstruction, local search, and fast charging-location optimization.
- The exact algorithm decomposes promising first-level solutions and uses bounding functions and route enumeration for second-level routes.
- The algorithms support optimal or near-optimal solutions and enable analysis of charging-station density and vehicle battery capacity in metropolitan test datasets.
2. Related Literature
Existing research covers two-echelon routing, alternative-fuel vehicles, and en-route recharging, but the paper targets their combination in electric second-level routes within two-echelon delivery networks.
- Prior 2EVRP research developed branch-and-cut, valid-inequality, set-partitioning, and decomposition-based exact methods.
- Vehicle-routing research has addressed electric or hybrid propulsion, en-route recharging, battery swaps, time windows, and heterogeneous charging technologies.
- Related work also studies real applications such as electric buses, freight transportation, and fully electric e-commerce fleets.
- The paper identifies a gap because existing electric-vehicle literature mainly considers single-depot, single-echelon delivery networks.
- The proposed study combines electric second-level routing, satellite selection, and possible en-route recharging in a two-echelon setting.
3. Problem Description
The E2EVRP jointly designs first-level depot-to-satellite routes and second-level satellite-to-customer electric routes under capacity, battery, charging, and cost constraints.
- The network contains a depot, satellites, customers, charging stations, edges for first-level movement, and arcs for second-level movement.
- First-level vehicles travel depot-and-satellite cycles subject to vehicle capacity and satellite delivery-capacity limits.
- Second-level routes serve customers from satellites while respecting customer-demand capacity and battery-consumption constraints.
- The objective minimizes route costs while matching satellite deliveries to depot receipts and visiting every customer exactly once.
- The multigraph reformulation preserves second-level routes through a one-to-one correspondence with routes in the original graph.
- Routes may represent direct travel or travel through at most one charging station between consecutive vertices, with associated cost and consumption values.
4. Solving the E2EVRP to Optimality
The exact solution method decomposes the E2EVRP around first-level route choices, bounds candidate solutions, and solves the resulting second-level routing problems using multigraph-aware relaxations and route enumeration.
- The exact method first generates all first-level routes and computes an initial lower bound using an integer relaxation and multiple-choice knapsack problem.
- It then enumerates subsets of potentially optimal first-level routes and rejects subsets whose lower bounds cannot improve the incumbent.
- Each surviving first-level subset yields a constrained MDCVRP solved to optimality, with route generation adapted to the multigraph.
- The ng-routes relaxation and dynamic programming track customer subsets, demand, battery consumption, and the last visited customer.
- The method can solve small and medium instances to optimality and provide good lower bounds on larger instances, but it benefits strongly from a good heuristic upper bound.
5. Large Neighborhood Search
LNS-E2E repeatedly destroys and repairs routing solutions, reconstructing both echelon levels and optimally inserting charging-station visits. A dynamic-programming labeling procedure restores battery feasibility, followed by local search to improve routes.
- LNS-E2E uses ruin-and-recreate iterations that destroy parts of a solution, repair them, and apply local search.The process restarts after a prescribed number of iterations without improvement and continues until the maximum time is reached.
- The method uses a limited set of fixed-probability destroy operators, including related-node removal, random-route removal, and temporary satellite closure.Additional operators can reopen satellites or remove single-customer routes, freeing vehicles for later repair.
- Repair proceeds in three stages: reinserting customer visits into second-level routes, reconstructing first-level routes, and inserting charging-station visits.The first-level reconstruction uses known satellite quantities and permits split deliveries when necessary.
- Charging-station insertion is formulated as a shortest-path problem with resource constraints and solved by dynamic programming over a multigraph of non-dominated arc choices.The state tracks route position and battery consumption, while parallel arcs represent alternative charging-station visits.
- When no feasible battery-respecting path exists, a penalized second dynamic-programming pass permits battery excesses while prioritizing lower penalty and then shorter distance.The penalty for consumption above L is M × (w − L), with M chosen as a large constant.
- After reconstruction, local search evaluates 2-opt, 2-opt*, Relocate, Swap, and Swap2-1 moves on second-level routes while checking satellite-capacity feasibility.The 2-opt* neighborhood is restricted to routes originating from the same satellite.
6. Computational Experiments
Computational experiments evaluate the proposed exact and LNS-E2E methods on benchmark instances, integrated charging-planning benefits, operator contributions, and sensitivity to charging density and battery capacity.
- Method performance: The exact algorithm solved all small instances optimally except one, while LNS-E2E achieved an average gap of 1.18% from optimal or best-known solutions.Exact-method runtimes ranged from under one minute to six hours, whereas LNS-E2E reached final solutions in 2–132 seconds.
- Method performance: 3.57% was the average gap between LNS-E2E solutions and the lower bound on medium instances, demonstrating good accuracy for both approaches.The mathematical programming algorithm did not prove optimality within the allotted time for this group.
- Integrated planning: 2.41% was the largest improvement of LNS-E2E over LNS-2E on 200-customer instances, while 100-customer cases produced slightly lower-quality solutions.The comparison concerns average solution quality against the current state-of-the-art LNS-2E algorithm.
- Integrated planning: 3.28% was the average gain from integrated routing and charging-station planning over post-optimization, reaching 7.93% for instance 100-10-2b.The integrated approach found solutions in a similar time to LNS-2E through heuristic move filters.
- Sensitivity analysis: 5.45% versus 1.53% were the average recharging detour costs at 5 versus 15 charging stations, and detours decreased proportionally to 1/ρ^1.24.Doubling charging-station density reduced extra recharging costs by approximately 58%.
- Sensitivity analysis: 9.5 to 11.75 was the average increase in charging-station visits as the station count rose from nr = 2 to nr = 50.Dense station networks let solutions approach the battery-unrestricted 2EVRP cost because multiple charging options are available en route.
- Sensitivity analysis: Below a vehicle range of 700 distance units, most considered instances became infeasible, while ranges near the feasible limit L = 800 incurred high detour costs and station visits.The results identify battery capacity as a key factor in the viability of battery-powered delivery networks.
7. Conclusions
The paper formulates the E2EVRP and develops exact and heuristic algorithms for multi-echelon battery-powered delivery. Computational analyses assess algorithmic performance and show how charging-station density and battery capacity affect recharging costs, while highlighting remaining methodological and infrastructure-planning limitations.
- The E2EVRP extends the two-echelon vehicle routing problem with electric second-echelon vehicles, battery constraints, and charging-station visits.
- The exact algorithm enumerates candidate first-echelon solutions and uses bounding functions and route enumeration for the second echelon, while LNS-E2E provides a tailored heuristic.
- All known optimal small-instance solutions were retrieved by LNS-E2E, while medium-scale instances had an average optimality gap of 3.57%.
- Recharging detour miles decrease in O(1/ρ^x), with x ≈ 5/4, while battery capacity below 80km made electric deliveries unviable in the studied setting.
- Current methods still require improvements in accuracy, scalability, and generality for large-scale multi-echelon electric routing problems.
- Charging stations were randomized within a fixed area, whereas strategic placement may be necessary for more accurate sensitivity analysis.