  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, i.e.
allowing to delay or expedite 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, non-linear charging, and Time-of-Use energy tariffs. We propose an
exact Branch & Price algorithm, leveraging a custom branching rule and a primal
heuristic to remain efficient during the Branch & 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 non-linear 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%.
