System-Centric Minimum-Time Paths for Battery-Powered Vehicles in Networks with Charging Nodes*

We study the routing problem for vehicle flows through a road network that includes both battery-powered Electric Vehicles (EVs) and Non-Electric Vehicles (NEVs). We seek to optimize a system-centric (as opposed to user-centric) objective aiming to minimize the total elapsed time for all vehicles to reach their destinations considering both traveling times and recharging times for EVs when the latter do not have adequate energy for the entire journey. Extending prior work where we considered only EVs entering the network, we formulate the problem by grouping all vehicles into a set of “subflows”and provide solutions based on both a Mixed Integer Non-Linear Programming (MINLP) approach and an alternative flow optimization problem. Since the problem size increases with the number of subflows, its proper selection is essential to render the problem manageable, thus reflecting a trade-off between proximity to optimality and computational effort needed to solve the problem. We propose a criterion and procedure leading to a “good” choice for the number of subflows.