Electric Arc Routing
Elena Fernández  1@  , Markus Leitner  2@  , Ivana Ljubic  3@  , Mario Ruthmair  4, *@  
1 : Barcelona Tech-UPC, Department of statistics and operations research  (BcnTech-UPC EIO)  -  Website
C/ Jordi Girona 1-3, 08034 Barcelona -  Spain
2 : VU University Amsterdam  -  Website
De Boelelaan 1105, 1081 HV Amsterdam -  Netherlands
3 : ESSEC Business School  -  Website
ESSEC Business School
3 Avenue Bernard Hirsch, 95021 Cergy-Pontoise -  France
4 : University of Vienna  -  Website
Oskar-Morgenstern-Platz 1, 1090 Vienna -  Austria
* : Corresponding author

In company fleets (battery) electric vehicles (EVs) impose additional challenges due to their limited range enforcing time-demanding charging breaks during service in case of long trips and since their energy consumption heavily depends on the driving speed (among other factors).
We study the use of EVs in the context of arc routing. Given a street network including a set of required arcs, the electric arc routing problem (eARP) proposed in this work asks for a set of energy-feasible routes that visit all required arcs with minimal total travel time. While the use of EVs in arc routing has not been studied before, related works in node routing with EVs typically use several simplifying assumptions with respect to the energy consumption and / or charging functions. We address several of these shortcomings by considering speed dependent energy consumption values and nonlinear charging functions that depend on the battery state and the charging time. Additionally, we study the possibility of inductive (wireless) charging along roads while driving. We introduce the new problem and describe an integer linear programming formulation with an exponential number of constraints solved by a branch-and-cut algorithm. Furthermore, several heuristics based on a labeling algorithm are presented. In a computational study we analyze the performance of the algorithms and compare the solutions for different battery sizes, speed and charging options.

Online user: 1 RSS Feed