Scientific Program > Talks by Speaker > Ruthmair Mario

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.