MINLP-Based Routing for Electric Vehicles with Velocity Control in Networks with Inhomogeneous Charging Stations

Battery electric vehicles (BEVs) are playing an increasingly important role in personal mobility due to the wish to counteract climate change and political regulations concerning carbon dioxide emissions. Nevertheless, there are obstacles that need to be overcome. Especially long-distance journeys are problematic due to long charging stops and range anxiety It is a driver's wish to fulfill a given driving task in a time-optimal way. But in the BEV case, driving faster does not necessarily lead to a decreased total travel time. The vehicle routing and charging problem is formulated as a mixed-integer nonlinear program (MINLP) and solved using mathematical optimization methods. First, time-minimizing vehicle routing with charging stations providing different power levels is discussed. The program returning the exact result is significantly faster than previous ones. Afterwards, the model is extended: Driving speed becomes adjustable. A combined time minimal optimization of which route to take, how fast to drive, where and how much to recharge is the result. The combination of these four parameters has never been studied before. It is shown that up to 14.48% of driving time can be saved in our examples by incorporating the choice of a driving speed.