Branch-and-Price for the electric vehicle charge schedulingproblem with flexible service operations
P. S. Kleina,∗ , M. Schiffera,ba School of Management & b Munich Data Science Institute,

Technical University of Munich, Munich, Germany
patrick.sean.klein@tum.de
schiffer@tum.de∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

January 15, 2022
Keywords: charge scheduling; branch and price; electric vehicles

1

Introduction

Increasing societal and political environmental awareness, resulting from climate change, as well
as local and global emission problems, call for a paradigm change towards sustainable transportation systems. Herein, electric commercial vehicles (ECVs) are seen as a viable option thatpromise up to 20% reduction in life-cycle greenhouse-gas emissions compared to internal combustion engine vehicles (ICEVs) while also lowering operational costs.
However, large-scale fleet electrification raises a new and unresolved planning problem: ECVs
require time-intensive charging which needs to be scheduled efficiently to guarantee the costcompetitiveness of electrified fleets. Specifically, operators face the following challenges whenscheduling charging operations: first, the number of chargers available remains limited by grid
capacity constraints and high investment costs. Second, suboptimal charging patterns with deep
(dis-)charging cycles accelerate battery degradation and thus require earlier battery replacements,
which affect the cost-competitiveness of ECVs (cf. Taefi, 2016). Third, energy suppliers often
bill industrial customers according to time-of-use (TOU) energy tariffs, i.e., they charge varying
electricity prices depending on the time of consumption. With such pricing schemes, it can beworthwhile to incur accelerated battery degradation by sub-optimal charging patterns if the costsavings obtained through off-peak energy prices outweigh degradation related costs (cf. Pelletier
et al., 2018). Fourth, operators who want to utilize this trade-off need to consider an accurate
model of the (non-linear) recharging process in their planning problem, because the error causedby over or under-estimating the charging rate may superpose attainable cost savings (Montoya
et al., 2017, Pelletier et al., 2018). Fifth, suboptimal service schedules may limit the impact
of charge-scheduling, such that operators who wish to remain cost-competitive should design
vehicle schedules with charge schedules in mind and vice versa.
Addressing this joint planning problem requires an integrated planning approach which combines vehicle scheduling problems (VSPs) with charge-scheduling. So far, publications dealing
with VSPs have either focused on conventional vehicles and did not account for charging-related
concerns, such as battery health, station capacity, and variable energy prices (Adler & Mirchandani, 2016, Yao et al., 2020, Parmentier et al., 2021), or remain computationally intractable forproblem sizes relevant in practice (van Kooten Niekerk et al., 2017). Publications focusing on(depot) charge-scheduling problems have been limited in a similar fashion, either assuming a
TRISTAN XI Symposium

Original abstract submittal

P. S. Klein and M. Schiffer2

simplified model of the charging process (Sassi & Oulamara, 2014, 2016) or proposing algorithms
that do not scale to problem sizes encountered in practice (Pelletier et al., 2018).
We close this research gap by developing an exact branch and price (B&P) algorithm for
an integrated charge and service operation scheduling problem, considering battery degradation,
TOU energy prices, limited availability of charging infrastructure, and non-linear battery behavior. An efficient branching rule, a state-of-the-art primal heuristic, and a novel label-setting
algorithm based on a continuous label representation with set-based dominance rules allow tosolve instances with fleet sizes of 68 vehicles and planning horizons of five days within one hour.
Our case study shows that integrated charge and service operation scheduling lowers the amountof charging infrastructure required by up to 57% and yields operational cost savings of up to 5%
in a city logistics context.

2

Problem Setting

We consider an electrified fleet of vehicles K that needs to perform a set of operations over agiven planning horizon, e.g., delivery tours in the context of (city) logistics or servicing customer
requests in passenger transportation. We assume that the assignment of operations to vehicles
is fixed but that servicing an operation can be shifted in time subject to an operation-specifictime window. Vehicles can be recharged using a set of (heterogeneous) charging stations locatedat the depot. For this purpose, each station f ∈ F is equipped with Cf chargers that allow forparallel charging. Charging incurs costs according to the battery degradation caused and theenergy price at the time of charging. In this problem setting, an operator aims to find a costminimal schedule of charging- and service-operations for each vehicle k ∈ K such that i) battery
capacity constraints are respected, ii) each tour is serviced by its assigned vehicle, iii) departuretime windows are met, and iv) charger capacity is not violated.
To model this optimization problem, we discretize the planning horizon into a set of equidistant periods p ∈ P such that charger to vehicle allocation and energy prices remain fixed withineach period. To avoid charging more energy than necessary, we allow partial charging operations
independent of the time discretization, such that charging may be started and interrupted at
any point in time. We model non-linear charging behavior with charger-specific recharging functions which capture a vehicle’s state of charge (SoC)-evolution over time when charging with an
initially empty battery and quantify the charging cost attributed to battery deterioration basedon a so-called wear density function (cf. Han et al., 2014). This function is non-linear such that
we consider its piecewise linear approximation in our planning problem.
We propose a set-covering based integer programming formulation where each column models
a feasible vehicle schedule ω ∈ Ak for each vehicle k ∈ K to express our planning problem:
X X
zM P = minxkω c(ω)(1a)
k∈K ω∈Ak

X X

xkω · Aωp,f ≤ Cf

f ∈ F, p ∈ P (1b)k∈K ω∈Ak

X

xkω ≥ 1k ∈ K (1c)ω∈Akxkω ∈ {0, 1}
ω ∈ Ak (1d)Here, Aω is a binary matrix that indicates whether a vehicle uses period p to charge at chargerf (Aω = 1) or remains idle, charges at a different charger f 0 ∈ F \ {f }, or provides service(Aω = 0). Binary variables xkω indicate the inclusion of a schedule in the final solution (xkω = 1).
Objective (1a) minimizes overall scheduling costs. Linking Constraints (1b) enforce charger
capacity limitations, while convexity Constraints (1c) ensure that a schedule is picked for eachvehicle. Finally, Constraints (1d) state our decision variables’ domain.
TRISTAN XI Symposium

Original abstract submittal

P. S. Klein and M. Schiffer

33

Methodology

We propose a B&P-based approach to solve IP 1: we solve an LP relaxation of IP 1, the socalled master problem, using a column-generation procedure at each node of the branch andbound (B&B) tree. Specifically, we limit IP 1 to a small subset of schedules A, which we
generate iteratively. At each iteration, we solve a linear relaxation of IP 1 to then generate new(1b)schedules ω ∈ Ak based on the dual variables of Constraints (1b) and (1c), denoted πp,f and
(1c)

πk

respectively, in the so-called pricing problem:
XX
(1c)
(1b)
yω,p,f · πp,f .
min c(ω) − πk −k∈K,ω∈Ak(2)

p∈P f ∈F

The procedure terminates when (2) is positive, i.e., when the basis of IP 1 is optimal. We
express our pricing problem as a shortest path problem with resource constraints (SPPRC)
over a time-expanded network, which we solve by using a problem-specific labeling algorithm.
Here, a canonical label respresentation which tracks each resource as a scalar value remains
computationally intractable as each charging decision constitutes a trade-off between cost and
SoC, such that time-continuous recharging requires to create an unbounded number of labels at
each charging station. We address this issue with a novel label representation which capturescharging trade-offs in so-called cost profiles. These state the maximum SoC reachable at the endof a (partial) path ρ when spending a total of c along ρ, potentially replenishing additional energy
at f . This allows delaying the decision on how much to charge at f until another station or the
network sink is reached. Here, the trade-off becomes explicit and a finite subset of non-dominatedcharging decisions at f can be identified. A novel set-based dominance criterion ensures that
this function-based label representation remains computationally tractable.
As column generation deals with the Linear Program (LP) relaxation of the master problem(MP) it may not terminate with an integral solution. In such cases, we resort to B&B toestablish integrality. Specifically, we observe that in each fractional solution of the restricted
master problem (RMP) at least two schedules compete for a charger that is already at capacity
and hence create branches based on charger allocation. We enforce any added cuts in our pricing
problems to avoid additional dual variables.
We present various speedup techniques to further accelerate our B&P algorithm: we use
a primal heuristic to quickly find upper bounds, thus speeding up the solution procedure byallowing to prune nodes of the B&B tree early. To this end, we use a diving heuristic that
explores an auxiliary branch-and-bound tree, which branches on the variables of the extensive
formulation xkω , in a depth-first fashion. We rely on strong branching to boost the success rateand solution quality of the diving algorithm. Here, we consider only a subset of columns, which
we select according to a roulette wheel criterion based on dissimilarity and quality, to speed up
the procedure.

4

Numerical Experiments

Our computational study comprises two experiments: first, we validate the correctness, investigate the performance, and analyze the scalability of our B&P algorithm. For this purpose, webenchmark our algorithm against an equivalent mixed integer program (MIP) based formulation
on a set of small, randomly generated, instances. We further test our algorithm on a set of larger
instances, where we additionally vary several instance parameters. Second, we assess the impact
of integrated service and charging operation scheduling in a potential real-world scenario for anelectrified fleet. Specifically, we analyze the overall benefit of flexible service operations, theimpact of schedule flexibility on the amount of charging infrastructure required, and the impact
of energy price distribution on the cost savings obtainable through integrated charge and service
operation scheduling. Table 1 shows the results of our benchmark on the small instances. As
TRISTAN XI Symposium

Original abstract submittal

P. S. Klein and M. Schiffer

4

Table 1 – Results of our experiments on small instances.
Avg. t[s]Avg. obj

Avg. LB

Avg. #nodes#optimal#without solution#total0.85
3600.00

396.56397.46396.56114.74

4.98
2183022.26

50
1

0
2

50
50

Algorithm
Branch-and-Price
MIP

Note. All instances were solved on a Intel(R) i9-9900, 3.1 GHz CPU with 16 GB of RAM using a single thread.

can be seen, our algorithm outperforms the MIP formulation on all instance types. Our computational study on large instances shows that our algorithm scales to a fleet size of 68 vehicles
and manages to solve instances spanning up to 5 days within the hour, allowing for day-ahead
planning in practice.
Concerning our managerial study, we disseminate the following findings:
1. flexible service operations have an overall positive impact on the objective value. Specifically, higher schedule flexibility allows utilizing periods with energy prices cheap enoughto outweigh additional battery degradation costs caused by cycling the battery at higher
SoC levels, such that energy costs decrease and battery degradation costs increase.
2. integrated planning of charge and service operations reduces the amount of charging infrastructure required for fleet operation but shows decreasing marginal benefits: time windows
of one hour reduce the number of chargers required by 14%, three hours by 43%, and six
hours by 57%.
3. the mean energy price offsets total cost. Concerning energy price variance, integrated
scheduling of charge and service operations provides the largest savings in scenarios withhighly varying energy prices. Specifically, doubling and quadrupling the energy price variance roughly doubles and triples relative savings.
Acknowledgements: This work was supported by the German Federal Ministry for Economic
Affairs and Energy within the project MILAS (01MV21020B).

References
Adler, J.D., & Mirchandani, P. B. 2016. The Vehicle Scheduling Problem for Fleets with Alternative-Fuel
Vehicles. Transportation Science, 51(2), 441–456.
Han, S., Han, S., & Aki, H. 2014. A practical battery wear model for electric vehicle charging applications.
Applied Energy, 113(113), 1100–1108.
Montoya, A., Guéret, C., Mendoza, J., & Villegas, J. 2017. The electric vehicle routing problem withnonlinear charging function. Transportation Research Part B: Methodological, 103(103), 87–110.
Parmentier, A., Martinelli, R., & Vidal, T. 2021. Mobility-on-Demand with Electric Vehicles: Scalable
Route and Recharging Planning through Column Generation. arXiv: 2104.03823 [math.OC].
Pelletier, S., Jabali, O., & Laporte, G. 2018. Charge scheduling for electric freight vehicles. Transportation
Research Part B: Methodological, 115(115), 246–269.
Sassi, O., & Oulamara, A. 2014. Simultaneous Electric Vehicles Scheduling and Optimal Charging in theBusiness Context: Case Study. Pages 6.3–6.3(1) of: IET Conference Proceedings, vol. 5. Institutionof Engineering and Technology.
Sassi, Ons, & Oulamara, Ammar. 2016. Electric vehicle scheduling and optimal charging problem:
complexity, exact and heuristic approaches. International Journal of Production Research, 55(2),519–535.
Taefi, T. T. 2016. Viability of electric vehicles in combined day and night delivery: a total cost ofownership example in Germany. European Journal of Transport & Infrastructure Research, 16(4),512–553.
van Kooten Niekerk, M. E., van den Akker, J. M., & Hoogeveen, J. A. 2017. Scheduling electric vehicles.
Public Transport, 9(1), 155–176.
Yao, E., Liu, T., Lu, T., & Yang, Y. 2020. Optimization of electric vehicle scheduling with multiple
vehicle types in public transport. Sustainable Cities and Society, 52(Jan.).

TRISTAN XI Symposium

Original abstract submittal