Electric Vehicle Charge Scheduling with Flexible Service Operations

Operators who deploy large fleets of electric vehicles often face a challenging charge scheduling problem. Specifically, time-ineffective recharging operations limit the profitability of charging during service operations such that operators recharge vehicles off duty at a central depot. Here, high investment cost and grid capacity limit available charging infrastructure such that operators need to schedule charging operations to keep the fleet operational. In this context, flexible service operations, that is, allowing delayed or expedited vehicle departures, can potentially increase charger utilization. Beyond this, jointly scheduling charging and service operations promises operational cost savings through better utilization of time-of-use energy tariffs and carefully crafted charging schedules designed to minimize battery wear. Against this background, we study the resulting joint charging and service operations scheduling problem accounting for battery degradation, nonlinear charging, and time-of-use energy tariffs. We propose an exact branch-and-price algorithm, leveraging a custom branching rule and a primal heuristic to remain efficient during the branch-and-bound phase. Moreover, we develop an exact labeling algorithm for our pricing problem, constituting a resource-constrained shortest path problem that considers variable energy prices and nonlinear charging operations. We benchmark our algorithm in a comprehensive numerical study and show that it can solve problem instances of realistic size with computational times below one hour, thus enabling its application in practice. Additionally, we analyze the benefit of jointly scheduling charging and service operations. We find that our integrated approach lowers the amount of charging infrastructure required by up to 57% besides enabling operational cost savings of up to 5%.