  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/\rho^x$ with $x
\approx 5/4$ as a function of the charging stations density $\rho$; 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.
