Keywords

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, ECVs are seen as a viable option that promise up to 20% reduction in life-cycle greenhouse-gas emissions compared to internal combustion engine vehicles (ICEVs) while also lowering operational costs. Launching and operating ECV fleets however, bears a new and unresolved planning problem. Long recharging times and limited availability of public recharging infrastructure often require investments into private, on-premise recharging stations. As these remain costly, the number of chargers available generally remains limited such that charging bottlenecks arise and day-ahead planning of charging operations is necessary. Moreover, accelerated battery degradation, caused by, high-voltage (fast) charging, may offset the otherwise lower operational costs of ECVs such that sub-optimal charging patterns need to be avoided when scheduling charging operations. Many operators are billed according to time-of-use (TOU) energy tariffs, which charge varying electricity rates depending on the time of consumption. In such scenarios, it becomes necessary to schedule charging operations accordingly as this leads to a non-trivial trade-off between incurring accelerated battery degradation and profiting from periods with low energy prices. Clearly, the impact of charge-scheduling is limited by the service schedules, 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 combining vehicle scheduling problems (VSPs) with charge-scheduling. However, 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 and Mirchandani 2017; Yao et al. 2020), or remain computationally intractable for problem 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 simplified model of the charging process (Sassi and Oulamara 2014, 2017), remaining heuristic, or proposing algorithms that do not scale to problem sizes encountered in practice (Pelletier et al. 2018). This work aims to close this gap by developing an exact branch and price (B &P) algorithm for an integrated charge- and service operation scheduling problem, accounting for battery degradation, TOU energy prices, limited availability of charging infrastructure, and non-linear battery behavior. For this purpose, Sect. 2 outlines the problem setting and develops a set-covering based formulation. Section 3 then summarizes our approach to solve this problem, followed by an evaluation of the algorithm’s computational performance in Sect. 4. Finally, Sect. 5 concludes this article.

2 Problem Setting

We consider a (depot) charge scheduling problem faced by logistics service providers (LSPs) in the context of electric vehicle routing. Here, an electrified fleet of vehicles \(\mathcal {K}\) needs to service a set of customers over a planning horizon of several days. We assume that routes have been pre-computed for each vehicle such that tour assignment, consumption, and duration are known in advance. Departure times are subject to scheduling, i.e., may be shifted in time, but must be completed within a certain, tour-specific, time window. Vehicles may be recharged at the depot using a set of (heterogeneous) charging stations. For this purpose, each station \(f\in \mathcal {F}\) is equipped with \(C_{f}\) chargers for parallel charging. Charging incurs costs according to the battery degradation caused and the energy price at the time of charging. In this problem setting, the LSP’s aim is to find a cost-minimal schedule of charging- and service-operations for each vehicle \(k\in \mathcal {K}\) such that i) battery capacity constraints are respected, ii) each tour is serviced by its assigned vehicle, iii) departure time windows are met, and iv) charger capacity is not violated. We model this optimization problem using a set-covering formulation over the set of vehicle schedules. For this purpose, we discretize the planning horizon into a set of equidistant periods \(p\in \mathcal {P}\). To ensure the feasibility of the original problem, we pursue a conservative discretization approach for tour departure time windows and charging operations. More precisely, tour departure and arrival are shifted to the beginning and end of their respective periods, and vehicles occupy chargers for entire periods at a time. To maintain accuracy, we still allow time-continuous charging such that vehicles may spend only a fraction of a period charging. We denote the set of all feasible vehicle schedules for vehicle \(k\in \mathcal {K}\) as \(\mathcal {A}_{k}\) and let \(\mathcal {A}= \cup _{k\in \mathcal {K}} \mathcal {A}_{k}\) be the set of all schedules. This distinction is necessary as charging schedules may not be compatible with every vehicle due to different tour assignments. We further use binary parameters \(y_{\omega , p, f}\) to indicate if \(\omega \in \mathcal {A}\) schedules a charging operation at \(f\in \mathcal {F}\) in period \(p\in \mathcal {P}\). Finally, binary variables \(x^{k}_{\omega }\) assign schedules to vehicles. We obtain the following optimization problem:

$$\begin{aligned}&\qquad \qquad \qquad \quad z_{MP}= \min \sum _{k \in \mathcal {K}} \sum _{\omega \in \mathcal {A}_{k}} x^{k}_{\omega } c(\omega ) \end{aligned}$$
(1a)
$$\begin{aligned}&\sum _{k \in \mathcal {K}} \sum _{\omega \in \mathcal {A}_{k}} x^{k}_{\omega } \cdot y_{\omega , p, f}\le C_{f}\qquad \qquad \qquad \qquad \qquad f\in \mathcal {F}, p\in \mathcal {P} \end{aligned}$$
(1b)
$$\begin{aligned}&\,\, \sum _{\omega \in \mathcal {A}_{k}} x^{k}_{\omega } = 1 \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad k \in \mathcal {K} \end{aligned}$$
(1c)
$$\begin{aligned}&\, x^{k}_{\omega } \in \{0, 1\} \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \omega \in \mathcal {A}_{k} \end{aligned}$$
(1d)

MIP 1 assembles a fleet schedule of minimal cost from the set of feasible vehicle schedules \(\mathcal {A}_{k}\) according to two sets of constraints. First, capacity constraints (1b) enforce charger capacity limitations. Second, covering constraints (1c) ensure that exactly one schedule is assigned to each vehicle. Constraints (1d) state the decision variables’ domain.

3 Methodology

As \(\mathcal {A}\) is huge for instances of reasonable size, solving MIP 1 using conventional, i.e., LP-based, branch and bound (B &B) remains computationally intractable. As a mitigation, we propose a B &P-based approach. Our algorithm essentially solves a LP relaxation of MIP 1, the so-called master problem, using a column-generation procedure at each node of the B &B tree. This procedure is outlined in Sect. 3.1. We propose a problem-specific branching rule to ensure a balanced B &B tree, detailed in Sect. 3.2. Finally, we utilize a primal heuristic, summarized in Sect. 3.3, to find good upper bounds early during the search.

3.1 Column Generation

The fundamental idea of column generation is to approach MIP 1 with only a small subset of schedules \(\mathcal {A}\), generated iteratively. For this purpose, each iteration first solves a linear relaxation of MIP 1 to then generate a new schedule \(\omega \in \mathcal {A}_{k}\) based on the dual variables of Constraints (1b) and (1c), denoted \(\pi ^{(1)}_{p, f}\) and \(\pi ^{(2)}_{k}\), respectively. This corresponds to solving the so-called pricing problem (Eq. 2), which seeks to generate schedules with negative reduced costs, i.e., schedules which would enter the basis of MIP 1 in the next iteration.

$$\begin{aligned} \min _{k\in \mathcal {K}, \omega \in \mathcal {A}_{k}} c(\omega ) - \pi ^{(2)}_{k}- \sum _{p\in \mathcal {P}} \sum _{f\in \mathcal {F}} y_{\omega , p, f}\cdot \pi ^{(1)}_{p, f}. \end{aligned}$$
(2)

The procedure terminates when (2) is positive, i.e., when the basis of MIP 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, we address non-linear charging, battery degradation, and variable energy prices with a novel label representation: instead of considering every reachable state of charge (SoC) when charging at some charger \(f\in \mathcal {F}\), our labels capture charging trade-offs in so-called cost profiles. These state the maximum SoC reachable at the end of a (partial) path \(\rho \) when spending a total of c along \(\rho \), potentially replenishing additional energy at \(f\). This allows to delay 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-dominated charging decisions at \(f\) can be identified.

3.2 Branching

Column generation deals with the linear relaxation of MIP 1 and thus may terminate with a fractional solution. We mitigate this issue by embedding our column generation procedure into a B &B algorithm. Here, our branching rule bases on the following observation: In every fractional solution of MIP 1 it holds that \(\exists (p, f) \in \mathcal {P}\times \mathcal {F}\) such that \(\sum _{\omega \in \mathcal {A}} x_{\omega } y_{\omega , p, f}= C_{f}\). We resolve such conflicts by creating up and down branches based on the charger allocation \(y_{\omega , p, f}\). For this purpose, we identify the vehicle \(k\) which relies most on charger \(f\) in period \(p\), formally, \(k= \underset{k' \in \mathcal {K}}{\arg \max } \sum _{\omega \in \mathcal {A}_{k'}} x_{\omega } \cdot y_{\omega , p, f}\), and create up and down-branches that cut off all solutions where vehicle \(k\) uses/does not use charger \(f\) in period \(p\), respectively.

3.3 Primal Heuristic

We propose a primal heuristic based on Sub-MIPing that works exclusively with the variables of the master problem. Its fundamental idea is to remove a subset of columns present in the current node’s (N) reduced column pool \(\tilde{\mathcal {A}}^N\) and resolve the resulting problem using IP. We select schedules to remove from \(\tilde{\mathcal {A}}^N\) based on quality (i.e., cost) and diversity. Here, diversity is measured through the number of shared charger allocations. We execute this procedure before branching on non-integral nodes unless an upper bound has already been found.

Table 1. Results of our experiments on small instances.
Full size table
Fig. 1.
figure 1

Runtimes on large instances

Full size image

4 Numerical Experiments

We benchmark the performance of our B &P algorithm on two sets of randomly generated instances. The first set comprises small instances (2 vehicles, 1 charger, 1 day) with varying numbers of tours (1, 2) and departure time window lengths (0%, 25%, 50%, given as a percentage of tour duration). Other parameters, such as tour timing, duration, and charging speed are drawn randomly. We use these to benchmark our algorithm against an equivalent IP. The second set contains instances of varying sizes to demonstrate the scalability of our algorithm. The reference setting spans a planning horizon of 3 days and comprises a fleet of 6 vehicles, each operating 2 tours per day with 30% flexibility. The depot is equipped with \(\max (1, \lfloor \frac{|\mathcal {K}|}{2} \rfloor )\) fast and \(|\mathcal {K}|\) slow chargers. We generate instances with varying fleet sizes and planning horizon lengths based on this setting. We used CPLEX 20.1 limited to a single thread and 3600 s of runtime on a Intel(R) i9-9900, 3.1 GHz CPU with 16 GB of RAM for our computational study. Table 1 shows the results of our benchmark on the small instances. As can be seen, our algorithm outperforms the mixed integer program (MIP) formulation on all instance types, solving each generated instance in less than 500 s. Figures 1a and 1b show the scalability of our algorithm w.r.t. fleet size and planning horizon length. Each dot corresponds to an individual instance. The blue lines give the average runtime over all instances. As is illustrated, our algorithm scales to a fleet size of 20 vehicles and manages to solve instances spanning up to 5 days.

5 Conclusion

We presented a novel charge- and service operation scheduling problem where a fleet of electric vehicles fulfills a set of service operations under the assumption of limited charging station capacity, variable energy prices, battery degradation, and non-linear charging behavior. We developed an exact algorithm based on B &P to solve the proposed problem. A novel labeling algorithm, a state-of-the-art primal heuristic, and problem-specific branching rules establish the efficiency of our algorithm, which is demonstrated in an accompanying numerical study. This study asserts the competitiveness of our algorithm through a benchmark against an equivalent mixed-integer formulation, showing that our algorithm significantly outperforms commercial solvers and scales to instances of larger size, optimally solving instances with planning horizons of up to 5 days or 20 vehicles within one hour, allowing an application in practice.