11affiliationtext: Department of Civil Engineering, Indian Institute of
Science (IISc), Bengaluru, India22affiliationtext: Center for infrastructure,
Sustainable Transportation and Urban Planning (CiSTUP), Indian Institute of
Science (IISc), Bengaluru, India33affiliationtext: School of Management &
Munich Data Science Institute, Technical University of Munich (TUM), Munich,
Germany

# On the Impact of Co-Optimizing Station Locations, Trip Assignment, and
Charging Schedules for Electric Buses

Rito Brata Nath  Tarun Rambha  Maximilian Schiffer

###### Abstract

As many public transportation systems around the world transition to electric
buses, the planning and operation of fleets can be improved via tailored
decision-support tools. In this work, we study the impact of jointly locating
charging facilities, assigning electric buses to trips, and determining when
and where to charge the buses. We propose a mixed integer linear program that
co-optimizes planning and operational decisions jointly and an iterated local
search heuristic to solve large-scale instances. Herein, we use a concurrent
scheduler algorithm to generate an initial feasible solution, which serves as
a starting point for our iterated local search algorithm. In the sequential
case, we first optimize trip assignments and charging locations. Charging
schedules are then determined after fixing the optimal decisions from the
first level. The joint model, on the other hand, integrates charge scheduling
within the local search procedure. The solution quality of the joint and
sequential iterated local search models are compared for multiple real-world
bus transit networks. Our results demonstrate that joint models can help
further improve operating costs by 14.1% and lower total costs by about 4.1%
on average compared with sequential models. In addition, energy consumption
costs and contracted power capacity costs have been reduced significantly due
to our integrated planning approach.

Keywords: electric vehicle scheduling problem, location planning, charge
scheduling, mixed integer programming, iterated local search.

††footnotetext: * These authors contributed equally to this manuscript.

##  1 Introduction

Electric Vehicles (EVs) have the potential to significantly reduce the
environmental impacts of tail-pipe emissions. While several government
subsidies promote electric mobility (Sierzchula et al., 2014), most are
personal-vehicle centric and hence do not address congestion issues (Wan et
al., 2015). For cities to grow sustainably, it is necessary to electrify
public transportation systems (Pelletier et al., 2019) that offer eco-friendly
travel alternatives and at the same time limit the use of personal travel
modes. However, large-scale deployment of electric buses requires proper
charging infrastructure and strategies for day-to-day operations. To this end,
one must factor in the buses’ state of charge (SoC) at different time points
and the energy needs of transit trips to optimize operational and planning
decisions.

In this context, the range of EV buses can vary widely depending on the
battery capacity. For example, the BYD’s K7M buses have an advertised range of
258 km, and their K8M models have a higher range of 315 km (BYD, 2023). The
true range is usually lower and depends on several other factors, such as
driving styles, passenger loads, and weather conditions. Unlike
diesel/gasoline buses, electric buses may require charging between operations
to replenish their battery levels due to limited range. Furthermore, it is
recommended not to discharge the battery below a certain threshold for
handling unforeseen events and improving the battery life cycle (Ellingsen et
al., 2022).

If the layover times between trips are short, buses may not have sufficient
time to recharge their batteries. This issue can be addressed by understanding
where to locate charging stations – the Charging Location Problem (CLP), how
to assign buses to trips – the Vehicle Scheduling Problem (VSP), and when and
how much to charge buses at a charging station – the Charge Scheduling Problem
(CSP). Figure 1 illustrates these problem components. While the decisions to
these problems can be made sequentially, strategic choices can have a
significant role on the operational ones (Dirks et al., 2022). For instance,
the bus-to-trip assignment is more constrained if the charging locations are
pre-determined. Likewise, the bus-to-trip assignment determines the charging
demand and the time slots for recharging. Consequently, a holistic framework
that co-optimizes these planning tasks in an integrated fashion promises cost
savings over their sequential counterparts. However, finding high-quality
solutions for joint models presents significant challenges due to increased
search space, raising the question: Can we design algorithms that co-optimize
the aforementioned planning tasks and are computationally tractable? If so,
what is the added benefit of such an integrated approach? This paper explores
solution techniques for such integrated frameworks and demonstrates their
potential to achieve significant cost savings while remaining tractable.

Figure 1: Different tasks involved in strategic and operational planning of
electric bus fleets

Specifically, our paper addresses the Charging Location and Electric Vehicle
Scheduling Problem (CLP-EVSP) and the Charging Location, Electric Vehicle
Scheduling Problem, and Charge Scheduling Problem (CLP-EVSP-CSP) jointly.
Numerous research studies have focused on these planning tasks in isolation,
but there has been very limited effort in developing a holistic framework, due
to the aforementioned challenges. We seek solutions that minimize the fixed
costs – total investment cost of electric buses and charging facilities – and
operational costs due to deadheading and recharging. In the charge scheduling
problem, we permit recharging multiple buses simultaneously.

A list of features modeled in this research and comparisons with relevant
papers are shown in Table 1. Our research makes multiple contributions to the
literature on the planning and operations of electric bus fleets, as
summarized below:

  * •

We propose a Mixed Integer Linear Programming (MILP) formulation for the CLP-
EVSP-CSP for a multiple depot setting. Our formulation captures several other
practical characteristics of electric transit systems, such as grid capacity,
time-of-day pricing, and split charging.

  * •

We design an iterated local search (ILS) procedure for the CLP-EVSP to
optimize locations and bus rotations. We also propose a novel MILP and two
surrogate Linear Programming (LP) formulations to solve the charge scheduling
problem. These LPs allow us to extend the ILS framework to the joint CLP-EVSP-
CSP while maintaining tractability.

  * •

We demonstrate the practical value of our integrated planning approach using
multiple real-world GTFS datasets. With reasonable assumptions about input
parameters, our joint CLP-EVSP-CSP model exhibited average savings of 41.4% in
scheduling costs, 39.6% in operational costs, and 14.4% in total costs over
all the test networks compared to the concurrent scheduler. The corresponding
average savings compared to the sequential CLP-EVSP model were 17.5%, 14.1%,
and 4.1%, respectively.

The rest of the paper is structured as follows: Section 2 explores relevant
literature on the CLP, EVSP, and CSP, including a few studies on joint
modeling. Section 3 formally defines the CLP-EVSP-CSP problem. In Section 4,
we present CSP models and a joint formulation for the CLP-EVSP-CSP. Section 5
introduces algorithms for the CLP-EVSP and CLP-EVSP-CSP ILS heuristics. We
study the benefits from applying these heuristics to different networks in
Section 6. Finally, Section 7 summarizes the paper’s findings and discusses
future research directions.

Table 1: Modeling features of relevant works ($\bullet$ Fully modeled, $\circ$ Partially modeled). In ambiguous situations where it was not clear how a certain feature was represented, we considered it to be fully modeled. References |  Bus acquisition |  Charging station costs |  Vehicle scheduling |  Dynamic pricing |  Multiple depots |  Power load costs |  Partial charging |  Split charging
---|---|---|---|---|---|---|---|---
Rogge et al. (2018) |  $\bullet$ |  $\circ$ |  $\bullet$ |  |  |  $\bullet$ |  |
Janovec and Koháni (2019) |  $\bullet$ |  |  $\bullet$ |  |  |  |  $\bullet$ |
Li et al. (2019) |  $\bullet$ |  $\bullet$ |  $\bullet$ |  |  $\bullet$ |  |  |
Liu et al. (2019) |  $\bullet$ |  $\bullet$ |  $\bullet$ |  |  $\bullet$ |  |  $\bullet$ |
Abdelwahed et al. (2020) |  |  |  |  $\bullet$ |  |  |  $\bullet$ |  $\bullet$
Li et al. (2020) |  $\bullet$ |  $\circ$ |  $\bullet$ |  $\bullet$ |  $\bullet$ |  |  $\bullet$ |
Liu and Ceder (2020) |  |  $\circ$ |  $\bullet$ |  |  $\bullet$ |  |  $\bullet$ |
Olsen and Kliewer (2020) |  $\bullet$ |  |  $\bullet$ |  |  |  |  $\bullet$ |
Teng et al. (2020) |  $\bullet$ |  |  $\bullet$ |  $\bullet$ |  |  |  |
Yao et al. (2020) |  $\bullet$ |  |  $\bullet$ |  |  $\bullet$ |  |  |
Zhou et al. (2020) |  |  |  $\bullet$ |  $\bullet$ |  |  |  $\bullet$ |
Alvo et al. (2021) |  $\circ$ |  |  $\bullet$ |  |  |  $\bullet$ |  $\bullet$ |
Alwesabi et al. (2021) |  $\bullet$ |  $\bullet$ |  |  |  |  $\circ$ |  $\bullet$ |
Jiang et al. (2021) |  $\bullet$ |  |  $\bullet$ |  $\bullet$ |  $\bullet$ |  |  $\bullet$ |
Lee et al. (2021) |  $\bullet$ |  $\bullet$ |  $\bullet$ |  |  |  $\bullet$ |  $\bullet$ |
Stumpe et al. (2021) |  $\bullet$ |  $\bullet$ |  $\bullet$ |  |  |  |  $\bullet$ |
Olsen and Kliewer (2022) |  $\bullet$ |  $\bullet$ |  $\bullet$ |  |  |  |  $\bullet$ |
Zhang et al. (2022) |  $\bullet$ |  $\bullet$ |  $\bullet$ |  |  |  |  $\bullet$ |
Gairola and Nezamuddin (2023) |  $\bullet$ |  $\bullet$ |  $\circ$ |  $\bullet$ |  $\circ$ |  $\circ$ |  $\bullet$ |
Our work |  $\bullet$ |  $\bullet$ |  $\bullet$ |  $\bullet$ |  $\bullet$ |  $\bullet$ |  $\bullet$ |  $\bullet$

##  2 Literature Review

Strategic and operational problems in managing electric buses and charging
stations have been widely researched in recent years. Strategic problems
include locating charging and battery swapping stations and fleet transition
decisions. On the other hand, operational problems deal with electric bus
scheduling, charging schedule optimization, and battery swapping. A detailed
survey on these problems can be found in Perumal et al. (2022). This section
discusses the state-of-the-art models for CLP, EVSP, and CSP of the joint
framework proposed in this paper.

###  2.1 Optimizing Charging Locations

Locating EV charging stations resembles the classic facility location problem
(Schettini et al., 2023). The objective of the CLP is to establish charging
sites from a set of candidate locations to fulfill the demand of electric
vehicles. For transit networks, charging stations are typically located at the
start and end of bus routes, areas where buses tend to have extended parking
times. Station capacities are also usually optimized along with location
decisions. E.g., a new charging facility is redundant if a nearby station can
serve the peak demand (Metais et al., 2022). Capacities, often determined by
the number of chargers, are constrained by available parking spaces. Some
studies ignore this effect and assume infinite capacities (Wang and Wang,
2010; He et al., 2015), while others associate station capacities to power
grid limits (Zhang et al., 2016). CLP formulations can optimize objectives
such as distance traveled by EVs (Shahraki et al., 2015), number of EVs
charged (Cavadas et al., 2015), and deadheading distances (Xu et al., 2013).
For electric buses, specific objectives include energy consumption of the
system (Xylia et al., 2017), number and locations of chargers (Kunith et al.,
2017), and infrastructure cost (He et al., 2019). Most of these problems are
solved using MILP models (Alwesabi et al., 2020) and meta-heuristics
(Iliopoulou and Kepaptsoglou, 2019).

###  2.2 Electric Vehicle Scheduling Problem

The VSP assigns a set of timetabled trips to vehicles originating from one or
more depots based on time compatibility (Bunte and Kliewer, 2009). The multi-
depot VSP (MDVSP) can be formulated either as a multi-commodity flow model
(Forbes et al., 1994; Kliewer et al., 2006) or as a set partitioning model
(Ribeiro and Soumis, 1994) and is known to be an NP-hard problem (Bertossi et
al., 1987). The EVSP is an extension of the VSP with additional range
constraints (Reuer et al., 2015; Liu and Ceder, 2020; Olsen and Kliewer,
2020). EVSP objectives are similar to those of VSP, but they can also include
transit-specific aims, such as minimizing the total cost of ownership (Rogge
et al., 2018). Most studies in the literature differ in solution techniques
and problem scales. Exact methods using MILP models are common (Li, 2014;
Janovec and Koháni, 2019; Li et al., 2019). The Column Generation (CG) method
can also be applied to the EVSP for improving tractability (Adler and
Mirchandani, 2017; Tang et al., 2019). However, large problem instances
require heuristics or meta-heuristics such as GAs (Rogge et al., 2018; Liu et
al., 2019; Li et al., 2020; Yao et al., 2020), particle swarm optimization
(Teng et al., 2020), simulated annealing (Zhou et al., 2020), and ant colony
optimization (Wang and Shen, 2007). Heuristics based on constraint generation
(Haghani and Banihashemi, 2002), concurrent scheduling (Adler and Mirchandani,
2017), adaptive large neighborhood search (Wen et al., 2016; Perumal et al.,
2021), and iterative neighborhood search (Zhou et al., 2020) have also proven
to scale successfully to larger instances.

###  2.3 Charge Scheduling Problem

The stand-alone version of the CSP assumes that the allocation of buses to
their respective trips and the charging stations’ locations are predetermined.
The goal of the CSP is usually to minimize charging costs under time-varying
electricity prices. While charging schedules are typically designed not to
exceed grid capacity (Zhang et al., 2016), some studies allow grid
reinforcement and exclude such constraints (Sadeghi-Barzani et al., 2014).
Among literature that considered dynamic electricity pricing, Leou and Hung
(2017) presented two MILP models for a single charging station to minimize
capacity and energy charges. Abdelwahed et al. (2020) proposed discrete time-
and discrete event-based MILP models to minimize charging costs. Although they
considered split charging events, they did not extend their model to multiple
charging locations. A similar approach to minimize total charging costs was
adopted by He et al. (2020) using a linearized model that could be solved
using commercial solvers. Ke et al. (2020) employed a GA to minimize
electricity costs. They also considered selling electricity back to the power
company.

Several other studies have focused on power load management at charging
stations. Jahic et al. (2019) proposed a greedy algorithm and a heuristic to
minimize the peak load at a central depot. Houbbadi et al. (2019) analyzed
overnight depot charging, considering battery aging, using nonlinear
programming. The operational cost of power distribution systems was minimized
by Bagherinezhad et al. (2020) using a relaxed cone programming model. Lastly,
Yang et al. (2017) focused on minimizing electricity consumption costs in a
wireless charging system.

###  2.4 Joint Models

The decision variables in the problems discussed above are interconnected.
Several papers have jointly studied CLP-EVSP and EVSP-CSP to optimize electric
bus operations fully. These studies vary in their objective functions,
methodologies, assumptions about charging profiles, and the sizes of test
networks. This section offers a discussion on the joint modeling of CLP-EVSP
and EVSP-CSP. Since the solution to the CSP inherently includes the solution
for the CLP, we do not discuss integrated CLP-CSP models separately. Table 2
provides an overview of the papers addressing the CLP-EVSP.

Table 2: Overview of different networks and methods used to solve the CLP-EVSP. (Data on the largest instance used is shown in the table. Missing information has been marked as ‘-’) Reference |  Trips |  Routes |  Stops |  Candidate Locations |  Solution Techniques
---|---|---|---|---|---
Rogge et al. (2018) |  200 |  3 |  - |  - |  Grouping GA
Li et al. (2019) |  288 |  6 |  - |  2 |  MILP model
Liu et al. (2019) |  544 |  4 |  - |  2 |  Bin-packing and GA
Li et al. (2020) |  867 |  8 |  164 |  5 |  Adaptive GA
Yao et al. (2020) |  931 |  4 |  - |  2 |  GA with a fitness computation algorithm
Alwesabi et al. (2021) |  102 |  6 |  - |  57 |  MILP model
Lee et al. (2021) |  74 |  1 |  38 |  38 |  A two-stage nonlinear integer model
Stumpe et al. (2021) |  1296 |  - |  - |  88 |  MILP and VNS
Hu et al. (2022) |  213 |  3 |  111 |  111 |  MILP model
Olsen and Kliewer (2022) |  3067 |  - |  209 |  209 |  VNS algorithm
Zhang et al. (2022) |  - |  16 |  238 |  7 |  MILP model

Stumpe et al. (2021) and Olsen and Kliewer (2022) introduced MILP models for
the CLP-EVSP. For larger instances, they used a variable neighborhood search
(VNS) algorithm, originally proposed by Mladenović and Hansen (1997) and
Hansen et al. (2010). Alwesabi et al. (2021) integrated vehicle scheduling
with charging planning using dynamic wireless charging. Li et al. (2020) used
a GA variant for the Stationary Charger Deployment and MDVSP, with partial
charging and time-of-day electricity pricing.

Both in-depot and en-route charging can replenish electric buses’ battery
levels (Zhou et al., 2020). A few studies optimize charge schedules and bus-
to-trip assignments for a given set of charging stations. Jiang et al. (2021)
optimized the MDVSP along with charging events while allowing partial
charging. A linearized version of a non-convex programming model was used by
Zhou et al. (2022) to address the bus and charge scheduling for a single
route. Lee et al. (2021) studied joint bus and charge scheduling for small
networks using a two-stage exact approach that considered electricity
consumption costs. Similar problems were investigated with fixed electricity
pricing (Janovec and Koháni, 2019; Olsen and Kliewer, 2020; Gkiotsalitis et
al., 2023) and time-varying costs (Teng et al., 2020; Zhou et al., 2020; Jiang
et al., 2021; Klein and Schiffer, 2023). Integrated approaches that jointly
optimize charger configurations and vehicle routing decisions have also shown
significant benefits in logistics (Schiffer et al., 2019, 2021). Yet, the
application of such integrated strategies in electrification of bus networks
remains less explored.

In conclusion, many CLP-EVSP models overlook charge scheduling, which can
yield additional cost savings. EVSP-CSP, on the other hand, assumes known
charging stations whose locations could have been sub-optimal. The problem of
integrating CLP-EVSP with CSP has not been widely researched, primarily
because of its computational challenges. Our joint CLP-EVSP-CSP addresses this
gap and is designed for tractability for network sizes commonly found in the
literature. We also improve upon simplifying assumptions frequently found in
CSP literature by considering multiple charging locations and power load
capacities.

##  3 Problem Description

EV bus fleet operations vary across transit agencies. Buses typically start
their journey from a depot and return to the same or a different depot at the
end of the day. Two types of charging models are common: overnight-slow and
opportunity-fast charging. Overnight charging is usually done at depots, and
buses start with a fully charged battery the next day. Opportunity charging
can be performed at any charging location during the day when the battery
levels are low or in response to dynamic prices and availability of charging
opportunities. Our model focuses on opportunity charging and, in this context,
makes the following assumptions.

  * •

The candidate charging stations are chosen from terminal bus stops of routes
where most buses stay for a significant duration. We make this assumption
because charging buses at intermediate bus stops adds to passenger delays
(Iliopoulou and Kepaptsoglou, 2021).

  * •

All buses are electric and homogeneous with the same range and can perform any
scheduled trip. Buses can charge multiple times during their layovers with
linear charging rates. We disallow deadheading to a charging station not in a
bus itinerary, but allow partial charging.

  * •

Due to the challenge of obtaining accurate information on the locations and
capacities of depots, we assume a predetermined set of depots. We chose these
depots strategically based on the major terminal stops, which serve as
starting or ending points for multiple routes.

  * •

Interlining is permitted, i.e., a bus can serve trips along multiple routes. A
bus does not need to return to its starting depot at the end of the day.
However, since schedules are periodic over different days, we require the
initial and final distribution of buses to be the same across depots.

  * •

Charging costs vary by the time of the day. Hence, it may benefit to fully
charge a bus during an off-peak period or wait when the electricity prices are
high. We assume all stations are equipped with smart charging technology that
dynamically regulates the amount of energy transferred to the buses (Sadeghian
et al., 2022).

  * •

Overnight charging costs at the depots are ignored since they do not vary
across bus-to-trip assignments; this is due to deadheading being already
accounted for and prices typically remaining constant during this period.

  * •

Transit schedules are deterministic. While it is also possible to re-design
trip schedules (Tang et al., 2023), we only optimize supply components and
assume that the timetabled trips (that are typically developed using transit
demand estimates) are not altered. Effects of congestion and delays due to
traffic or vehicle breakdowns are out of scope of the current work. Still,
they can be integrated into our methodology to some degree by adding
appropriate slacks.

The transit data includes a set of stops $S$, daily trips $I$, and bus routes
$R$. We assume that the candidate charging locations
$S^{cand}=\\{s_{1},s_{2},\ldots,s_{p}\\}$ are the start and end locations of
all routes. Figure 2(a) shows an example network. Stops in $S$ are indicated
in blue, and those in $S^{cand}$ are shown as larger green nodes. The bus
stops along a sample route are shown in Figure 2(b).

(a) Bus stops and candidate charging locations

(b) Washtenaw bus route

Figure 2: Bus stops and candidate charging locations in the Ann Arbor Area
Transportation Authority network, US.

A pair of trips $i$ and $j$ are compatible if trip $j$ can be carried out
after trip $i$ by the same bus, i.e.,
$\beta_{i}+\gamma_{i,j}+\theta_{i,j}\leq\alpha_{j}$, where $\beta_{i}$ is the
end time of $i$, $\gamma_{i,j}$ is the deadhead trip duration from the end
stop of $i$ to the start stop of $j$, $\theta_{i,j}$ is the idle time before
or after the deadhead trip (layover time $-$ deadhead time) in minutes and
rounded down to the nearest integer, and $\alpha_{j}$ is the start time of
$j$. The idle time is set to zero if one of the trip ends is a depot.

Figure 3: Network diagram for the EVSP

Trip compatibility can be visualized using a graph $G=(N,A)$, where $N$ and
$A$ are the set of nodes and arcs as shown in Figure 3. We define $N=I\cup D$,
where $I=\\{1,2,\ldots,n\\}$ is the set of $n$ trips and
$D=\\{n+1,n+2,\ldots,n+m\\}$ is the set of $m$ depots. The set of compatible
trip pairs, $A^{comp}$, are denoted using solid blue arcs, and the connections
between the depots and the trip nodes are shown using dashed green arcs. We do
not require additional nodes for candidate charging locations since the trip
itineraries capture the sequence of visits to charging station locations.

The set of all arcs $A$ can be written as $A=A^{comp}\cup_{i\in
I}\\{(n+1,i),(n+2,i),\ldots,(n+m,i)\\}\cup_{i\in
I}\\{(i,n+1),(i,n+2),\ldots,(i,n+m)\\}$. Bus charging levels are tracked only
at trip terminals. We denote $O_{s}$ and $E_{s}$ as the set of trips with $s$
as their start/origin and end/destination stops, respectively. Mathematically,
they can be written as: $O_{s}=\\{i\in I:i^{start}=s\\}$ and $E_{s}=\\{i\in
I:i^{end}=s\\}$, where $i^{start}$ and $i^{end}$ are the starting and ending
stops of trip $i$, respectively. We assume an initial set of buses
$B=\\{b_{1},b_{2},\ldots,b_{n}\\}$ (not all of which may be used in the
optimal solution). The maximum number of buses available can be set to the
number of trips $n$ as each bus can be assigned to exactly a single trip, but
tighter bounds or existing fleet data can also be used if available.

The joint CLP-EVSP-CSP model is formulated as a MILP in Section 4.2. The
objective is to minimize the fixed cost of buses and charging stations, along
with operational costs encompassing deadheading, electricity consumption, and
grid power capacity costs. Specifically, through bus scheduling, we aim to
ensure that all the trip nodes depicted in Figure 3 are served exactly once.
Charging stations are opened based on the charge feasibility of buses, and
charge schedules are devised considering charging station availability, bus
idle time, and time-of-day electricity prices. Constraints include trip
compatibility, charging level feasibility, and battery level thresholds. The
decision variables in the model capture the arc flows in $G$, the candidate
bus stops that are converted into charging stations, and the energy
transferred to buses every minute while charging. We present a formal
exposition of the CSP and the joint model in Section 4.

##  4 Charge Scheduling and Joint Models

The CLP-EVSP model commonly found in the literature (Li et al., 2019; Stumpe
et al., 2021) does not consider electricity costs and grid capacity in
deciding when and where buses should charge. This could increase the need for
simultaneous charging and lead to higher operating costs. To tackle this
issue, we first formulate a general CSP that minimizes both electricity
consumption and contracted power capacity costs in Section 4.1. In this CSP,
buses have the flexibility to charge between trips, either at the last stop of
a trip, the starting stop of its next trip, or at both ends if charging
stations are available. This approach necessitates a MILP framework, which is
subsequently integrated into a CLP-EVSP formulation, resulting in our joint
optimization model, CLP-EVSP-CSP, in Section 4.2. However, the MILP version of
the CSP is not computationally tractable for realistic instance sizes.
Therefore, we introduce surrogate CSP models in Section 4.3. These models
prioritize where to charge between trip ends, enabling us to solve the CSP
using linear programs.

###  4.1 CSP Model

Considering time-of-day electricity prices and the contracted capacity of
charging locations, a bus may choose to charge at the end stop of a trip, then
deadhead to the starting stop of the next trip and charge again if a charging
opportunity exists. We address this aspect through a MILP model, where the
time-step at which a bus begins deadheading if charging opportunities are
available at both ends is also a decision variable. We refer to this model as
the Charge at Either End (CEE) version of the CSP. We split time into one-
minute intervals and consider the energy provided to buses at charging
stations every minute as a decision variable. Figure 4 illustrates the CEE
charging. Trip ends where charging stations are located are shown using an
icon, and the nodes are shaded when charging is permitted. In cases where the
bus can charge at both the ending stop of a trip and the starting stop of the
next trip (e.g., trips 1 and 4), the idle time $\theta_{1,4}$ is divided into
two charging sessions, and the model determines the optimal time to begin
deadheading. The solid red lines on the plots between trips indicate the start
and end times of deadheading. We denote the deadheading duration for bus $b$
during its $k^{\text{th}}$ charging opportunity by $\tau_{b,k}$. The dotted
green lines represent the maximum energy transferable ($\psi_{b}$) in a single
time period. Note that not charging in a particular time-step may be optimal,
depending on the energy needs of other buses at the charging station. For the
charging opportunities between trips (4,7) and (7,6), the process is
straightforward as the charging station is only at one end of the trips.
Therefore, the bus will either charge and deadhead to the next trip or
deadhead first and charge before starting the next trip.

Figure 4: An illustration of the CEE charging strategy (The green dashed
arrows indicate depot trips, black dotted arrows indicate service trips, and
blue solid arrows indicate deadhead trips. Charging is allowed at the gray
terminals.)

Table 3 summarizes the notation used in the MILP formulation of CSP. Charging
opportunities are indexed consecutively for each bus in a set $K_{b}$, and
subsets $K_{b}^{1}$ and $K_{b}^{2}$ are created depending on the type of
charging opportunity. For instance, in Figure 4, $K_{b}=\\{0,1,2,3\\}$,
$K_{b}^{1}=\\{2,3\\}$, and $K_{b}^{2}=\\{1\\}$. Opportunities in $K_{b}^{1}$
allow charging at only one trip end, whereas ones in $K_{b}^{2}$ allow
charging at both ends. For opportunities in $K_{b}^{2}$ such as $k=1$, we
refer to 1 as the current trip and 4 as the next trip.

Table 3: Notation used in the CSP formulation Notation Description |
---|---
Decision variables: |
$w_{b,s,t}$ |  Energy (kWh) provided to bus $b$ at charging location $s$ and time-step $t$
$r_{b,t}^{end}$ |  Binary variable which is $1$ if bus $b$ can charge at time-step $t$ at the end stop location of a trip, when charging is allowed at both the end points
$r_{b,t}^{start}$ |  Binary variable which is $1$ if bus $b$ can charge at time-step $t$ at the start stop location of a trip, when charging is allowed at both the end points
$q_{s}$ |  Contracted power capacity (kW) at charging location $s$
Auxiliary variables: |
$l_{b,k}$ |  Charging level (kWh) of bus $b$ at the end of its $k^{\text{th}}$ charging opportunity
Sets: |
$B$ |  Set of electric buses
$Z$ |  Set of charging locations
$K_{b}$ |  Set of sequentially enumerated charging opportunities, i.e., trip changes/layovers by $b$, each with at least a charging station at trip ends. We include 0 to keep track of the charge levels from the depot.
$K_{b}^{1}$ |  Indices of charging opportunities that have a charging station at only one of the trip ends
$K_{b}^{2}$ |  Indices of charging opportunities that have charging stations at both trip ends
$T_{b,k}$ |  Set of time-steps of bus $b$ at charging opportunity $k\in K_{b}^{1}$
$T^{end}_{b,k}$ |  Set of time-steps when bus $b$ can charge at the ending stop of a trip at charging opportunity $k\in K_{b}^{2}$
$T^{start}_{b,k}$ |  Set of time-steps of bus $b$ at the starting stop of a trip at charging opportunity $k\in K_{b}^{2}$
$P$ |  Set of time periods with different energy prices. Each period is a collection of successive time-steps
$T_{p}$ |  Set of time-steps in time period $p\in P$
$T$ |  Set of all time-steps that cover the period of operations
Data/Parameters: |
$e_{b,k,k+1}$ |  Energy consumed (kWh) by bus $b$ to cover the distance from the end of charging opportunity $k\in K_{b}$ to the start of its $(k+1)^{\text{th}}$ charging opportunity
$e_{b,k}$ |  Energy consumed (kWh) by bus $b$ for deadheading during charging opportunity $k\in K_{b}^{2}$
$s_{b,k}$ |  Charging location of bus $b$ at charging opportunity $k\in K_{b}^{1}$
$s^{end}_{b,k}$ |  End stop of the current trip on bus $b$ at charging opportunity $k\in K_{b}^{2}$
$s^{start}_{b,k}$ |  Start stop of next trip on bus $b$ at charging opportunity $k\in K_{b}^{2}$
$\tau_{b,k}$ |  Deadheading time for bus $b$ during charging opportunity $k\in K_{b}$
$\psi_{b}$ |  Maximum amount of charge that can be provided to a bus $b$ in a single time-step (kWh/min)
$c^{elec}_{p}$ |  Electricity price ($/kWh) at time period $p$
$c^{cap}$ |  Unit price of contracted capacities ($/kW) of charging locations
$l_{max}$ |  Battery capacity (kWh) of an electric bus
$l_{min}$ |  Lower limit of energy level (kWh) of buses
Figure 5: Decision variables at charging opportunities with stations at both
trip ends

We divide the time horizon of operations into one-minute steps and label time
intervals where energy prices vary (e.g., 0900–1400, 1400–1600, etc.) as
periods. We denote the sets of time steps where a bus can potentially charge
at a station as $T_{b,k}$, $T^{end}_{b,k}$, and $T^{start}_{b,k}$. We populate
these time steps by excluding the deadheading time associated with a charging
opportunity, $\tau_{b,k}$, from the layover time. Figure 5 shows an example of
such sets for a charging opportunity in $K_{b}^{2}$.

The objective (1) of the CSP consists of four terms. The first term considers
the electricity consumption costs for charging at opportunities in
$K_{b}^{1}$. The second and third terms represent the electricity costs for
charging at the ending stop of the current trip and the starting stop of the
next trip, respectively, for charging opportunities in $K_{b}^{2}$. The final
term of the objective function accounts for the contracted power capacity
costs. This represents the fixed cost associated with establishing charging
infrastructure at different stations. The $q_{s}$ variable represents the
maximum power required to meet the charging needs of buses recharging at
station $s$.

$\min\sum\limits_{p\in P}c^{elec}_{p}\sum\limits_{b\in
B}\Biggl{(}\sum\limits_{\begin{subarray}{c}s\in Z,t\in T_{p}\cap T_{b,k}:\\\
k\in
K_{b}^{1},s_{b,k}=s\end{subarray}}w_{b,s,t}+\sum\limits_{\begin{subarray}{c}s\in
Z,t\in T_{p}\cap T^{end}_{b,k}:\\\ k\in
K_{b}^{2},s^{end}_{b,k}=s\end{subarray}}w_{b,s,t}+\sum\limits_{\begin{subarray}{c}s\in
Z,t\in T_{p}\cap T^{start}_{b,k}:\\\ k\in
K_{b}^{2},s^{start}_{b,k}=s\end{subarray}}w_{b,s,t}\Biggl{)}+c^{cap}\sum\limits_{s\in
Z}q_{s}$ (1) s.t. $\displaystyle
l_{b,k+1}=l_{b,k}-e_{b,k,k+1}+\sum\limits_{t\in T_{b,k+1}}w_{b,s,t}$
$\displaystyle\forall\,b\in B,\,(k+1)\in K_{b}^{1},\,s=s_{b,k+1}$ (2)
$\displaystyle l_{b,k+1}=l_{b,k}-e_{b,k,k+1}+\sum\limits_{t\in
T^{end}_{b,k+1}}w_{b,s,t}-e_{b,k+1}+\sum\limits_{t\in
T^{start}_{b,k+1}}w_{b,s^{\prime},t}$ $\displaystyle{\forall\,b\in
B,\,(k+1)\in K_{b}^{2},\,s=s^{end}_{b,k+1},\,s^{\prime}=s^{start}_{b,k+1}}$
(3) $\displaystyle{l_{b,k}-e_{b,k,k+1}\geq l_{min}}$
$\displaystyle{\forall\,b\in B,\,k\in K_{b}}$ (4)
$\displaystyle{l_{b,k}-e_{b,k,k+1}+\sum\limits_{t\in
T^{end}_{b,k+1}}w_{b,s,t}-e_{b,k+1}\geq l_{min}}$ $\displaystyle{\forall\,b\in
B,\,(k+1)\in K_{b}^{2},s=s^{end}_{b,k+1}}$ (5) $\displaystyle{l_{b,k}\leq
l_{max}}$ $\displaystyle{\forall\,b\in B,\,k\in K_{b}}$ (6)
$\displaystyle{l_{b,k}-e_{b,k,k+1}+\sum\limits_{t\in
T^{end}_{b,k+1}}w_{b,s,t}\leq l_{max}}$ $\displaystyle{\forall\,b\in
B,\,(k+1)\in K_{b}^{2},s=s^{end}_{b,k+1}}$ (7) $\displaystyle l_{b,0}=l_{max}$
$\displaystyle\forall\,b\in B$ (8) $\displaystyle 0\leq w_{b,s,t}\leq\psi_{b}$
$\displaystyle\forall\,b\in B,\,k\in K_{b}^{1},\,s=s_{b,k},\,t\in T_{b,k}$ (9)
$\displaystyle 0\leq w_{b,s,t}\leq\psi_{b}\,r_{b,t}^{end}$
$\displaystyle{\forall\,b\in B,\,k\in K_{b}^{2},\,s=s^{end}_{b,k},\,t\in
T^{end}_{b,k}}$ (10) $\displaystyle 0\leq
w_{b,s,t}\leq\psi_{b}\,r_{b,t}^{start}$ $\displaystyle{\forall\,b\in B,\,k\in
K_{b}^{2},\,s=s^{start}_{b,k}},\,t\in T^{start}_{b,k}$ (11) $\displaystyle
r_{b,t+1}^{end}\leq r_{b,t}^{end}$ $\displaystyle{\forall\,b\in B,\,k\in
K_{b}^{2},\,t,\,(t+1)\in T^{end}_{b,k}}$ (12) $\displaystyle
r_{b,t+1}^{start}\geq r_{b,t}^{start}$ $\displaystyle{\forall\,b\in B,\,k\in
K_{b}^{2}},\,t,\,(t+1)\in T^{start}_{b,k}$ (13) $\displaystyle
r_{b,t+\tau_{b,k}}^{start}\leq 1-r_{b,t}^{end}$ $\displaystyle\forall\,b\in
B,\,k\in K_{b}^{2},\,t\in T^{end}_{b,k}$ (14)
$\displaystyle\sum\limits_{\begin{subarray}{c}b\in B,k\in K_{b}^{1}:\\\
s_{b,k}=s,t\in
T_{b,k}\end{subarray}}w_{b,s,t}+\sum\limits_{\begin{subarray}{c}b\in B,k\in
K_{b}^{2}:\\\ s^{end}_{b,k}=s,t\in
T^{end}_{b,k}\end{subarray}}w_{b,s,t}+\sum\limits_{\begin{subarray}{c}b\in
B,k\in K_{b}^{2}:\\\ s^{start}_{b,k}=s,t\in
T^{start}_{b,k}\end{subarray}}w_{b,s,t}\leq q_{s}/60$
$\displaystyle\forall\,s\in Z,\,t\in T$ (15) $\displaystyle
r_{b,t}^{end}\in\\{0,1\\},\,r_{b,t^{\prime}}^{start}\in\\{0,1\\}$
$\displaystyle{\forall\,b\in B,\,k\in K_{b}^{2},\,t\in
T^{end}_{b,k}},t^{\prime}\in T^{start}_{b,k}$ (16)

Constraints (2) and (3) update the charging levels between two consecutive
charging opportunities for each bus. Specifically, (2) applies when charging
at the ($k+1)^{\text{th}}$ opportunity is permitted only at one of the end
stops, while (3) applies when charging is allowed at both end stops.
Constraints (4) and (5) ensure that the buses’ charging levels do not drop
below a minimum threshold at any time. Constraints (6) and (7) prevent buses
from charging beyond their battery capacity. Buses start their daily
operations with a fully charged battery due to (8). The maximum energy
transferred to a bus within a single time-step is governed by the availability
of the bus at charging locations, which is captured in constraints (9)–(11).
When a charging opportunity $k$ is in $K_{b}^{1}$, we simply set the upper
bound based on the maximum rate $\psi_{b}$ at which the batteries on the bus
can be charged. For a charging opportunity $k\in K_{b}^{2}$, we use binary
variables $r_{b,t}^{end}$ and $r_{b,t}^{start}$ to decide on the time-steps
where charging is permitted at the trip ends (see Figure 5). Constraint (12)
ensures that the $r_{b,t}^{end}$ variables exhibit a sequence of consecutive
ones followed by zeros. Similarly, (13) forces $r_{b,t}^{start}$ variables to
assume a series of zeros followed by ones. Furthermore, charging at the start
stop of the next trip can begin only after finishing charging at the current
trip’s end stop and the deadheading operation. Hence, the $r_{b,t}^{start}$
variables in $T^{start}_{b,k}$ can be active after considering the deadheading
time from the last time-step where $r_{b,t}^{end}$ is one, as specified in
(14). Finally, (15) and the minimization objective help set $q_{s}$ to the
maximum amount of energy used by the charging station at $s$ in a single time
step. Binary restrictions on the deadheading decision variables are imposed
using (16).

###  4.2 CLP-EVSP-CSP Model

We enhance CLP-EVSP formulations found in the literature by incorporating CSP-
specific variables. Instead of charging opportunities, we utilize trip indices
since the locations are not predetermined and are determined jointly by the
model. Table 4 introduces additional notation to describe the MILP. The
notation from the CSP formulation remains applicable.

Table 4: Additional notation used in the joint optimization formulation of CLP-EVSP-CSP Notation Description |
---|---
Decision variables: |
$x_{i,j,b}$ |  Binary variable which is $1$ if node $j$ is visited after node $i$ by bus $b$, and $0$ otherwise
$z_{s}$ |  Binary variable which is $1$ if a charging facility is set up at stop $s$, and $0$ otherwise
$w^{start}_{b,i,t}$ |  Energy (kWh) provided to bus $b$ at the starting stop of trip $i$ at time-step $t$
$w^{end}_{b,i,t}$ |  Energy (kWh) provided to bus $b$ at the ending stop of trip $i$ at time-step $t$
Auxiliary variables: |
$y^{start}_{i,t}$ |  Binary variable which is $1$ if charging can be done at the starting stop of trip $i$ at time-step $t$, and $0$ otherwise
$y^{end}_{i,t}$ |  Binary variable which is $1$ if charging can be done at the ending stop of trip $i$ at time-step $t$, and $0$ otherwise
$l_{i,b}^{start}$ |  Energy level (kWh) of bus $b$ at the starting stop of trip $i$ or at the end of depot $i$
$l_{i,b}^{end}$ |  Energy level (kWh) of bus $b$ at the ending stop of trip $i$ or at the start of depot $i$
Sets: |
$I$ |  Set of trips
$D$ |  Set of depots
$N$ |  Set of nodes for the EVSP
$A$ |  Set of arcs for the EVSP
$A^{comp}$ |  Set of compatible trip pairs
$S^{cand}$ |  Set of candidate charging locations
$O_{s}$ |  Set of trips with stop $s$ as starting/origin stop
$E_{s}$ |  Set of trips with stop $s$ as ending/destination stop
$T^{start}_{i,j}$ |  Set of time-steps during which a bus can charge at the starting stop of node $j$ if the preceding node was $i$
$T^{end}_{i,j}$ |  Set of time-steps during which a bus can charge at the ending stop of node $i$ before moving to node $j$
$T^{prev}_{i}$ |  Set of time-steps that precedes the starting time of trip $i$
$T^{next}_{i}$ |  Set of time-steps that succeeds the ending time of trip $i$
Data/Parameters: |
$d_{i}$ |  Energy consumed (kWh) to travel the distance of trip $i$
$d_{i,j}$ |  Energy consumed (kWh) in deadheading from the end of node $i$ to the start of node $j$
$M$ |  A large positive number
$i^{start}$ |  Starting stop of trip $i$
$i^{end}$ |  Ending stop of trip $i$
$\gamma_{i,j}$ |  Deadhead trip duration from the end stop of $i$ to the start stop of $j$
$c^{bus}$ |  Acquisition cost ($) of an electric bus
$c^{loc}$ |  Fixed investment cost ($) per charging location
$c_{i,j}^{km}$ |  Total energy consumption costs ($) from the end location of node $i$ to the start location of node $j$ (which equals the per km cost multiplied by the corresponding deadhead distance traveled)

The objective (17) comprises five terms: the acquisition cost of electric
buses required to serve all the trips, the fixed cost of a charging station,
the deadheading costs, the total electricity consumption cost, and the total
cost for installing sufficient power capacity at all charging stations. The
deadheading and electricity consumption costs are scaled appropriately to
account for the life cycle of electric buses.

$\min\sum\limits_{b\in B}\sum_{\begin{subarray}{c}(i,j)\in A:\\\ i\in
D\end{subarray}}c^{bus}\,x_{i,j,b}+\sum\limits_{s\in
S^{cand}}c^{loc}z_{s}+\sum\limits_{b\in B}\sum\limits_{(i,j)\in
A}c_{i,j}^{km}x_{i,j,b}+\sum\limits_{p\in P}\sum\limits_{t\in
T_{p}}\sum\limits_{i\in I}\sum\limits_{b\in
B}c^{elec}_{p}(w^{start}_{b,i,t}+w^{end}_{b,i,t})+c^{cap}\sum\limits_{s\in
S^{cand}}q_{s}$ (17) s.t. $\displaystyle\sum\limits_{j:(i,j)\in
A}x_{i,j,b}-\sum\limits_{k:(k,i)\in A}x_{k,i,b}=0$
$\displaystyle\,\forall\,i\in I,\,b\in B$ (18) $\displaystyle\sum\limits_{b\in
B}\sum\limits_{j:(i,j)\in A}x_{i,j,b}-\sum\limits_{b\in
B}\sum\limits_{k:(k,i)\in A}x_{k,i,b}=0$ $\displaystyle\,\forall\,i\in D$ (19)
$\displaystyle\sum\limits_{b\in B}\sum\limits_{j:(i,j)\in A}x_{i,j,b}=1$
$\displaystyle\,\forall\,i\in I$ (20) $\displaystyle\sum\limits_{i\in
D}\sum\limits_{j:(i,j)\in A}x_{i,j,b}\leq 1$ $\displaystyle\,\forall\,b\in B$
(21) $\displaystyle l_{i,b}^{start}\leq l_{max}\sum\limits_{k:(k,i)\in
A}x_{k,i,b}$ $\displaystyle\,\forall\,i\in I,\,b\in B$ (22) $\displaystyle
l_{i,b}^{end}\leq l_{max}\sum\limits_{j:(i,j)\in A}x_{i,j,b}$
$\displaystyle\,\forall\,i\in I,\,b\in B$ (23) $\displaystyle
l_{i,b}^{end}=l_{max}\sum\limits_{j:(i,j)\in A}x_{i,j,b}$
$\displaystyle\,\forall\,b\in B,\,i\in D$ (24) $\displaystyle
l_{i,b}^{start}-\sum\limits_{k:(k,i)\in A}d_{i}\,x_{k,i,b}\geq
l_{min}\sum\limits_{k:(k,i)\in A}x_{k,i,b}$ $\displaystyle\,\forall\,i\in
I,\,b\in B$ (25) $\displaystyle l_{i,b}^{end}-\sum\limits_{j:(i,j)\in
A}d_{i,j}\,x_{i,j,b}\geq l_{min}\sum\limits_{j:(i,j)\in A}x_{i,j,b}$
$\displaystyle\,\forall\,i\in I,\,b\in B$ (26) $\displaystyle
l_{j,b}^{start}\geq l_{min}\,\sum\limits_{i\in I}x_{i,j,b}$
$\displaystyle\,\forall\,j\in D,\,b\in B$ (27) $\displaystyle
l_{i,b}^{end}\leq l_{i,b}^{start}-d_{i}+\sum\limits_{t\in
T^{end}_{i,j}}w^{end}_{b,i,t}+M(1-x_{i,j,b})$ $\displaystyle\,\forall\,b\in
B,\,\,i\in I,\,(i,j)\in A$ (28) $\displaystyle l_{i,b}^{end}\geq
l_{i,b}^{start}-d_{i}+\sum\limits_{t\in
T^{end}_{i,j}}w^{end}_{b,i,t}-M(1-x_{i,j,b})$ $\displaystyle\,\forall\,b\in
B,i\in I,\,(i,j)\in A$ (29) $\displaystyle l_{j,b}^{start}\geq
l_{i,b}^{end}-d_{i,j}\,x_{i,j,b}+\sum\limits_{t\in
T^{start}_{i,j}}w^{start}_{b,j,t}-M(1-x_{i,j,b})$
$\displaystyle\,\forall\,b\in B,\,(i,j)\in A$ (30) $\displaystyle
l_{j,b}^{start}\leq l_{i,b}^{end}-d_{i,j}\,x_{i,j,b}+\sum\limits_{t\in
T^{start}_{i,j}}w^{start}_{b,j,t}+M(1-x_{i,j,b})$
$\displaystyle\,\forall\,b\in B,\,(i,j)\in A$ (31) $\displaystyle
w^{start}_{b,i,t}\leq\psi_{b}\,y^{start}_{i,t}$ $\displaystyle\,\forall\,b\in
B,\,i\in I,\,t\in T^{prev}_{i}$ (32) $\displaystyle
w^{end}_{b,i,t}\leq\psi_{b}\,y^{end}_{i,t}$ $\displaystyle\,\forall\,b\in
B,\,i\in I,\,t\in T^{next}_{i}$ (33) $\displaystyle y^{start}_{i,t+1}\geq
y^{start}_{i,t}$ $\displaystyle\,\forall\,i\in I,\,t,\,(t+1)\in T^{prev}_{i}$
(34) $\displaystyle y^{end}_{i,t+1}\leq y^{end}_{i,t}$
$\displaystyle\,\forall\,i\in I,\,t,\,(t+1)\in T^{next}_{i}$ (35)
$\displaystyle y^{start}_{j,t+\gamma_{i,j}}\leq
1-y^{end}_{i,t}+M(1-x_{i,j,b})$ $\displaystyle\,\forall\,b\in B,\,(i,j)\in
A^{comp},t\in T^{end}_{i,j}$ (36) $\displaystyle\sum\limits_{i\in
O_{s}}\sum\limits_{t\in T^{prev}_{i}}y^{start}_{i,t}+\sum\limits_{i\in
E_{s}}\sum\limits_{t\in T^{next}_{i}}y^{end}_{i,t}\leq Mz_{s}$
$\displaystyle\,\forall\,s\in S^{cand}$ (37) $\displaystyle\sum\limits_{b\in
B}\sum\limits_{\begin{subarray}{c}i\in I:\\\
i^{end}=s\end{subarray}}w^{end}_{b,i,t}+\sum\limits_{b\in
B}\sum\limits_{\begin{subarray}{c}i\in I:\\\
i^{start}=s\end{subarray}}w^{start}_{b,i,t}\leq q_{s}/60$
$\displaystyle\forall\,t\in T,\,s\in S^{cand}$ (38) $\displaystyle q_{s}\leq
Mz_{s}$ $\displaystyle\,\forall\,s\in S^{cand}$ (39) $\displaystyle
x_{i,j,b},\,z_{s},\,y^{start}_{i,t},y^{end}_{i,t^{\prime}}\in\\{0,1\\}$
$\displaystyle\,\forall\,i,j\in N,b\in B,t\in T^{prev}_{i},t^{\prime}\in
T^{next}_{i},s\in S^{cand}$ (40) $\displaystyle
w^{start}_{b,i,t},w^{end}_{b,i,t^{\prime}},q_{s},l_{i,b}^{start},l_{i,b}^{end}\in\mathbb{R^{+}}$
$\displaystyle\,\forall\,i\in N,b\in B,t\in T^{prev}_{i},t^{\prime}\in
T^{next}_{i},s\in S^{cand}$ (41)

We ensure flow conservation at every trip node and depot node using (18) and
(19), respectively. Constraint (20) indicates that each trip is served by
exactly one bus. Constraint (21) models the scenario where a bus may remain
unused and determines the buses starting at different depots. Inequalities
(22) and (23) ensure that the battery can be charged up to the maximum
capacity, avoiding overcharging. Used buses leave the depot fully charged
according to (24). Constraints (25), (26), and (27) set minimum charge-level
requirements so that buses have sufficient energy to complete their assigned
trips. Specifically, (25) handles service trips, (26) is applied to deadhead
trips, and (27) deals with depot trips. Constraints (28) and (29) track the
energy levels of each bus throughout its assigned trips, using the appropriate
energy consumption and battery replenishment variables. Similar inequalities
are defined for the deadhead trips (including the pull-in and pull-out depot
trips and the compatible service trips) using (30) and (31). Constraints (32)
and (33) restrict the amount of energy that can be transferred to a bus at
every time-step. Constraints (34)–(36) model the split charging of buses at
both ends of a layover in a manner similar to (12)–(14). Constraint (37)
allows charging activities to occur if a charging facility is located at a
terminal stop. Constraint (38) sets $q_{s}$ to the maximum power supply needed
for buses charging at $s$. It is permitted to be non-negative only if a
charging station is opened at $s$, as stipulated by (39). Finally, binary
restrictions and limits on the decision variables are imposed by (40) and
(41).

###  4.3 Surrogate CSPs

The CEE MILP presented in Section 4.1 can be simplified using surrogate LP
models. More importantly, these LPs enable the development of efficient local
search heuristics, which will be discussed in Section 5. In these variants, we
restrict buses to charge at only one of the end stops during a layover when
charging stations are available at both ends. This approach eliminates the
need for integer variables that determine the timing of deadheading. Two types
of priority rules can be applied at such layovers: a charge-and-go (CAG)
strategy, which involves charging at the end stop of the current trip before
deadheading, and a go-and-charge (GAC) strategy, where deadheading is
performed first, followed by charging at the starting stop of the next trip.
Both models can be further simplified by assuming that the energy supplied to
the buses either changes dynamically over time (split charging) or remains
constant (uniform charging) during each charging opportunity. Our experiments
demonstrate that these LPs are highly tractable, and there is an improvement
in the overall objective and the CSP costs when they are integrated with other
location and scheduling problems.

####  4.3.1 Split Charging with Priority

Figure 6 depicts an example of the split charging strategy. For the layover
between trips 1 and 4, which has charging stations at both ends, the CAG
strategy prioritizes charging at the ending stop of trip 1 (indicated by the
gray node) as shown in Figure 6(a). Similarly, Figure 6(b) demonstrates the
GAC strategy, where charging at the starting stop of trip 4 is given priority.
The formulations for the CAG and GAC models are similar, differing only in the
input data.

$\displaystyle\min$ $\displaystyle\sum\limits_{p\in P}\sum\limits_{b\in
B}\,\sum\limits_{\begin{subarray}{c}s\in Z,t\in T_{p}\cap T_{b,k}:\\\ k\in
K_{b}^{1},s_{b,k}=s\end{subarray}}\,c^{elec}_{p}\,w_{b,s,t}+c^{cap}\sum\limits_{s\in
Z}\,\,q_{s}$ (42) s.t.
$\displaystyle\eqref{eqn:cons_split_milp_1},\eqref{eqn:cons_split_milp_3a},\eqref{eqn:cons_split_milp_4},\eqref{eqn:cons_split_milp_6},\eqref{eqn:cons_split_milp_7}\,\text{with}\,K_{b}^{2}=\emptyset$
$\displaystyle\sum\limits_{\begin{subarray}{c}b\in B,k\in K_{b}^{1}:\\\
s_{b,k}=s,t\in T_{b,k}\end{subarray}}w_{b,s,t}\leq q_{s}/60$
$\displaystyle\forall\,s\in Z,\,t\in T$ (43)

The objective (42) consists of two terms: the electricity consumption costs in
different periods and the contracted capacity costs across all charging
locations. Constraint (43) models the contracted power capacity requirements
of charging stations and is a simplified version of (15). We experimented with
these strategies using a specific set of location and bus rotations and found
that the objective of the CAG strategy is closer to that of the optimal CEE
solution for most networks. Therefore, for the remainder of this paper, we
will assume that the CSP is solved using the CAG strategy unless stated
otherwise.

(a) Charge-and-Go (CAG) strategy

(b) Go-and-Charge (GAC) strategy

Figure 6: Illustration of split charging strategies

####  4.3.2 Uniform Charging with Priority

To further reduce the number of variables and the runtime of the local search
operators, one could consider implementing a uniform charging strategy. In
this formulation, we assume that buses are charged throughout their entire
idle period at a charging station, thereby eliminating the need for time
indices as shown in the example in Figure 7. We determine the charging levels
based on the energy requirements of the buses and their idle duration at the
charging locations. Let $w_{b,k}$ represent the energy provided and
$\delta_{b,k}$ denote the idle time for bus $b$ at its $k^{\text{th}}$
charging opportunity. The uniform charging formulation can be written as
follows.

$\displaystyle\min$ $\displaystyle\sum\limits_{p\in P}\sum\limits_{b\in
B}\sum\limits_{\begin{subarray}{c}k\in K_{b}^{1}:\\\ t\in T_{p}\cap
T_{b,k}\end{subarray}}c^{elec}_{p}\,\frac{w_{b,k}}{\delta_{b,k}}+c^{cap}\sum\limits_{s\in
Z}\,\,q_{s}$ (44) s.t. $\displaystyle l_{b,k+1}=l_{b,k}-e_{b,k,k+1}+w_{b,k+1}$
$\displaystyle\forall\,b\in B,\,(k+1)\in K_{b}^{1}$ (45)
$\displaystyle{l_{b,k}\leq l_{max}}$ $\displaystyle{\forall\,b\in B,\,k\in
K_{b}^{1}}$ (46) $\displaystyle{l_{b,k}-e_{b,k,k+1}\geq l_{min}}$
$\displaystyle{\forall\,b\in B,\,k\in K_{b}^{1}}$ (47) $\displaystyle
l_{b,0}=l_{max}$ $\displaystyle\forall\,b\in B$ (48) $\displaystyle 0\leq
w_{b,k}\leq\psi_{b}\,\delta_{b,k}$ $\displaystyle\forall\,b\in B,\,k\in
K_{b}^{1}$ (49) $\displaystyle\sum\limits_{\begin{subarray}{c}b\in B,k\in
K_{b}^{1}:\\\ s_{b,k}=s,t\in
T_{b,k}\end{subarray}}\frac{w_{b,k}}{\delta_{b,k}}\leq\,q_{s}/60$
$\displaystyle\forall\,s\in Z,\,t\in T$ (50)

The objective (44) again consists of two terms: the electricity costs for
charging and the contracted power capacity costs across all charging
locations. Constraint (45) maintains consistency in the charging levels
between two consecutive charging opportunities for each bus. Constraint (46)
prohibits buses from charging in excess of their battery limits. Constraint
(47) guarantees that the energy levels in buses are always maintained above a
specified minimum threshold. Furthermore, due to (48), buses begin their daily
activities with a battery that is fully charged. The maximum energy
transferred to a bus within a single charging opportunity is captured in
constraint (49). Finally, equation (50) defines the station-level maximum
contracted capacity, based on the energy supply rate during various charging
opportunities, for buses charging simultaneously at the station.

Figure 7: Illustration of the uniform CAG charging strategy

From an implementation perspective, constraint (50) need not be added for
every time step. Alternatively, for each station, we could identify
overlapping charging opportunities for different buses. This allows us to
calculate the total rate at which multiple buses are charged simultaneously.
To this end, we construct an undirected graph for each charging station $s$
with pairs of $(b,k)$ as vertices, where $b\in B,\,k\in K_{b}^{1},s_{b,k}=s$.
We add an edge between two vertices if the charging opportunity time windows
overlap. Once this graph is constructed, (50) can be populated by enumerating
all maximal cliques using the Bron-Kerbosch algorithm (Bron and Kerbosch,
1973). This method of finding cliques is time-efficient since it avoids
duplicating constraints for different time-steps. Figure 8 presents an example
of three buses, $b_{1},b_{2},$ and $b_{3}$, at a station, where the charging
opportunity time windows are indicated by green bars. The time windows for the
pairs $(b_{1},k_{1})$, $(b_{2},k_{3})$, and $(b_{3},k_{5})$ overlap, as do the
time windows for the pairs $(b_{1},k_{2})$ and $(b_{2},k_{4})$. These overlaps
are illustrated in the right panel of the figure. Based on this graph, only
two equations are required to represent (50) at this station.

Figure 8: Clique enumeration for populating CSP constraints

The MDVSP is known to be NP-Hard (Bertossi et al., 1987). Unsurprisingly, the
CLP-EVSP-CSP, even with surrogate models, scales poorly for real-world
instances. To tackle this challenge, we propose two ILS heuristic procedures:
one for the CLP-EVSP, which is sequentially followed by a CSP, and another for
the joint CLP-EVSP-CSP, which integrates the aforementioned LPs into the
search operators. Additionally, we occasionally use the solution to a CLP-CSP
where the EVSP decisions are pre-determined, and each charging station’s usage
is optional. This scenario is modeled by introducing additional binary
variables $z_{s}$ in the CAG CSP formulations, along with a constraint of the
form (39).

##  5 Iterated Local Search

We use an ILS framework to overcome the computational challenges of the MILP
model and solve CLP-EVSP and CLP-EVSP-CSP efficiently. The procedure’s initial
solution is generated through the concurrent scheduler algorithm (Bodin et
al., 1978). This algorithm organizes trips in ascending order of departure
times and assigns them to available buses in a greedy manner. Additionally, it
activates charging stations at terminal stops when the buses’ charge levels
fall below certain thresholds. Details on generating initial solutions and
charge-level feasibility checks are discussed in Sections 5.1 and 5.2,
respectively.

In the sequential model, we first solve the CLP-EVSP using the ILS procedure.
At a high level, the ILS for the CLP-EVSP involves two sets of operators:
location operators and scheduling operators. The location operators (refer
Section 5.4), which can be viewed as the ones making the first-stage
decisions, optimize the CLP by evaluating the impact of opening and closing
charging stations. While opening charging stations does not compromise the
feasibility of existing vehicle rotations, closing them can render rotations
charge-infeasible. In such cases, a rotation may have to be split,
necessitating the creation of additional rotations. These rotations are
subsequently passed to the scheduling operators (see Section 5.3), which
optimize the EVSP through trip/depot exchanges and shifts. Operating costs are
thus reduced either due to minimized deadheading or through the removal of
rotations when trips are shifted. The resulting rotations are then used to
calculate utilization metrics, which track the time spent by buses at
different terminal stops, helping the location operators prioritize decisions
on opening and closing charging stations. Subsequently, assuming that the
charging station locations and vehicle rotations are fixed, we optimize the
CSP by solving the CEE CSP formulation. Figure 9(a) summarizes the steps
involved in the ILS process of the sequential model, and Table 5 describes the
additional notation used for the local search methods. Unless stated
otherwise, notations used in this section have the same meaning as those
defined in the previous sections.

(a) ILS procedure for the CLP-EVSP

(b) ILS procedure for the CLP-EVSP-CSP

Figure 9: Iterated Local Search procedures

Integrating the MILP model for charge scheduling with the local search for the
CLP-CSP, while not inconceivable, is impractical, as the MILP model need to be
solved numerous times within the scheduling operators. Hence, we use our novel
surrogate CSP formulations, which help find effective upper bounds to the
optimal charging-related costs and assist in distinguishing the good exchanges
and shifts from the bad ones. Inarguably, employing these surrogate models
introduces an optimality gap when compared to the generic CEE version.
However, more important than the magnitude is the consistency in the ordering
of the CSP costs between the CEE MILP and the surrogate models across
different rotations. Since these surrogate models are LPs, they exhibit
shorter runtimes, making a strong case for their use within the ILS framework.

Table 5: Notation used in ILS methods Notation |  Description
---|---
Sets/Lists: |
$V$ |  List of rotations of all the electric buses
$V_{b}$ |  Rotation of $b^{\text{th}}$ electric bus present in a list of bus rotations
Data/Variables: |
$n_{b}$ |  Number of trips performed by bus $b$
$i_{b}^{j}$ |  $j^{\text{th}}$ trip performed by bus $b$
$i_{b}^{0}$ |  Starting depot of bus $b$
$i_{b}^{n_{b}+1}$ |  Ending depot of bus $b$
$\Delta_{i}$ |  Nearest depot location from the starting bus stop location of trip $i\in I$
$\kappa_{s}$ |  Current utilization of terminal $s$
$\pi_{s}$ |  Potential utilization of terminal $s$
$q^{*}_{s}$ |  Optimal power capacity of terminal $s$ from the CLP-CSP split charging formulation
$f(V,Z)$ |  Objective function with or without the CSP cost

The overarching idea guiding our decisions for integration is straightforward.
Operators that frequently invoke the CSP (such as exchanges and shifts) employ
the uniform CAG model due to its speed. In contrast, operators that call the
CSP model sparingly, such as the objective function evaluations, utilize the
split CAG version. In addition, we treat the charging locations suggested by
the location operators merely as candidate locations, allowing a CLP-CSP split
CAG model to optimize the actual locations within this set. This CLP-CSP
solution takes into account the fixed costs of establishing charge scheduling
infrastructure and the power capacity costs, and can potentially reduce the
number of charging stations.

A summary of the enhancements to the ILS procedure is shown in Figure 9(b).
The green boxes indicate the CSP-related sub-routines. The candidate locations
are set as before, using the first-stage location operators. The EVSP-CSP is
then addressed using the rotation scheduling operators with the CSP surrogate
models. Finally, utilization metrics, which tracked the time spent by buses at
different terminal stops, are now augmented with power capacity variables that
guide the search for opening and closing charging stations. In the following
subsections, we delve into the details of the individual components of the
ILS. We summarize the overall procedure in Section 5.5.

###  5.1 Initial Solutions

The Concurrent Scheduler (CS) algorithm generates an initial feasible
solution, see Algorithm 1. The solutions to the CLP-EVSP can be represented
using a list of bus rotations, $V$, and a set of charging locations
$Z\subseteq S^{cand}$. We denote $V$ as
$[V_{1},V_{2},\ldots,V_{b},\ldots,V_{|B|}]$, where $V_{b}$ is the rotation of
the $b^{\text{th}}$ bus, containing information on the sequence of service
trips, along with its initial and final depot locations. We use the indices
$b$, $u$, and $v$ to refer to buses. Assume that the number of trips performed
by the $b^{\text{th}}$ bus is $n_{b}$. The list $V_{b}$ can then be
mathematically written as
$V_{b}=[i_{b}^{0},i_{b}^{1},i_{b}^{2},\ldots,i_{b}^{n_{b}},i_{b}^{n_{b}+1}]$,
where $i_{b}^{k}$ denotes the $k^{\text{th}}$ trip performed by bus $b$. The
starting and ending depots for bus $b$ are represented as dummy trips
$i_{b}^{0}$ and $i_{b}^{n_{b}+1}$, respectively. Note that the starting and
ending depots can be different. For these rotations, the corresponding
decision variables in the MILP models are
$x_{i_{b}^{0},i_{b}^{1},b}=1,x_{i_{b}^{1},i_{b}^{2},b}=1,\ldots,x_{i_{b}^{n_{b}},i_{b}^{n_{b}+1},b}=1$,
and for the charging station locations, $z_{s}=1$ for all $s\in Z$.

Input: $I$

Output: $V,Z$

1

2$V,Z\leftarrow\phi,\phi$

3 Rearrange $I$ in the ascending order of the trip start times

4 Pick the first trip $i$ from the sorted list of $I$

5 $V_{1}\leftarrow[\Delta_{i},i,\Delta_{i}]$ and add $V_{1}$ to $V$

6

// Insert trips to existing rotations

7 for  _$j=2$ to $n$_ do

8 $i_{j}\leftarrow$ The $j^{\text{th}}$ element from the sorted list of $I$

9

10 for  _$b=1$ to $|V|:$ $(i_{b}^{n_{b}},i_{j})\in A^{comp}$_ do

11 $V^{temp}_{b}\leftarrow V_{b}$ and insert $i_{j}$ to the list of service
trips in $V^{temp}_{b}$

12
$\textsf{insertTrip},Z^{temp}\leftarrow\textsc{IsRotationChargeFeasible}(V^{temp}_{b},Z)$

13 if  _$\mathsf{insertTrip}$_ then

14 $V_{b}\leftarrow V^{temp}_{b}$ and $Z\leftarrow Z^{temp}$

15 break

16

// Create new rotations

17 if  _$i_{j}$ is not assigned to any of the buses used so far_ then

18 Use a new bus $|V|+1$, update its rotation to
$[\Delta_{i_{j}},i_{j},\Delta_{i_{j}}]$, and add it to $V$

19

20

Algorithm 1 ConcurrentScheduler (CS)

Initially, we assume no open charging locations. The algorithm starts by
sorting the service trips in the ascending order of their start times (line
2). It creates a new rotation by assigning the first trip $i$ to a bus by
starting a bus from the depot nearest to trip $i$, $\Delta_{i}$ (lines 3–4).
The algorithm then checks if the next trip $i_{j}$ from the sorted list can be
assigned to a used bus (lines 5–12). When multiple rotations can accommodate
the trip, priority is given to the bus rotation, which was created first. The
time compatibility for inserting the trip is checked in line 7, and a copy of
the updated bus rotation is created in line 8. Additionally, the energy level
feasibility of the bus rotation is checked in line 9 using the
IsRotationChargeFeasible function. This function returns a Boolean value and
an updated list of charging stations, which can be opened at any terminal
stop. It is similar to Algorithm 2, described in Section 5.2. The charging
locations are modified using the CAG strategy, where opening a charging
facility is prioritized at the end stops of trips. If the trip insertion is
feasible, the bus rotation and charging locations are updated in line 11, and
the algorithm proceeds to insert the next trip. If not, the algorithm creates
a new bus rotation and assigns the trip to it (lines 13–14).

###  5.2 Charge Feasibility Check

Checking the charge feasibility of a bus for a given set of charging stations
is central to the local search procedure and is performed by Algorithm 2.
Several sub-routines use variants of this algorithm, which are briefly
described in their respective sections. The charge level at terminals is
monitored using the $l$ variable. Since buses depart the depot fully charged,
they are not permitted to be charged at the start location of the first trip.
Lines 2–3 ensure that the bus can deadhead to the start terminal of the first
trip and successfully complete it. In cases where a rotation is infeasible, it
is sometimes necessary to identify the last trip in its sequence that can be
completed without running out of charge. This information is tracked using the
feasibleTillTrip variable. This variable is updated in line 5, which checks if
the rotation can be terminated early and the end depot can be reached without
letting the charge levels fall below the minimum threshold.

Checking whether the charge level $l$ falls below $l_{min}$ must be carefully
carried out after every trip, especially considering the availability of
charging opportunities. We declare the bus rotation as infeasible if charging
at the maximum possible rate cannot meet the energy requirements of its trips.
This leads to three scenarios under the CAG strategy. In the first scenario
(lines 6–8), the end terminal is a charging station, allowing the bus to
either charge to the maximum possible level, i.e., recharge at the maximum
rate possible during the idle time between trips, denoted as
$\lambda\delta_{i_{b}^{j},i_{b}^{j+1}}$. Subsequently, the bus may need to
deadhead to the start location of the next trip, after which the charge level
is compared with $l_{min}$.

In the second scenario (lines 9–12), the bus can only charge after
deadheading. Therefore, the charge levels are first checked for infeasibility
and then updated with the maximum possible energy that can be provided within
its available idle time. In the third scenario (lines 13–15), where there is
no charging opportunity, the charge levels are updated following the
deadheading trip. Line 16 accounts for the energy required for the next trip,
and line 20 addresses the scenario of deadheading to the end depot after the
last trip.

Input: $V_{b},Z$

Output: True/False

1

2feasibleTillTrip $\leftarrow-1$

3 $l\leftarrow l_{max}-(d_{i_{b}^{0},i_{b}^{1}}-d_{i_{b}^{1}})$

4 if  _$l <l_{min}$_ then return false

5 for  _$j=1$ to $(n_{b}-1)$_ do

6 if  _$l-d_{i_{b}^{j},i_{b}^{n_{b}+1}}\geq l_{min}$_ then
$\textsf{feasibleTillTrip}\leftarrow j$

// Current trip end is a charging station

7 if  _$i_{b}^{j,end}\in Z$_ then

8
$l\leftarrow\min\\{l_{max},l+\lambda\delta_{i_{b}^{j},i_{b}^{j+1}}\\}-d_{i_{b}^{j},i_{b}^{j+1}}$

9 if  _$l <l_{min}$_ then $\textsf{isNextTripFeasible}\leftarrow$ false

10

// Only next trip start is a charging station

11 if  _$i_{b}^{j,end}\notin Z$ , $i_{b}^{j+1,start}\in Z$_ then

12 $l\leftarrow l-d_{i_{b}^{j},i_{b}^{j+1}}$

13 if  _$l <l_{min}$_ then $\textsf{isNextTripFeasible}\leftarrow$ false

14 $l\leftarrow\min\\{l_{max},l+\lambda\delta_{i_{b}^{j},i_{b}^{j+1}}\\}$

15

// Current trip end and next trip start are not charging stations

16 if  _$i_{b}^{j,end}\notin Z,i_{b}^{j+1,start}\notin Z$_ then

17 $l\leftarrow l-d_{i_{b}^{j},i_{b}^{j+1}}$

18 if  _$l <l_{min}$_ then $\textsf{isNextTripFeasible}\leftarrow$ false

19

20

21 $l\leftarrow l-d_{i_{b}^{j+1}}$

22

23 if  _$l\geq l_{min}$_ then $\textsf{isNextTripFeasible}\leftarrow$ true

24

25 if  _$\mathbf{not}~{}\mathsf{isNextTripFeasible}$_ then

26

27 return false

28

29

30$l\leftarrow l-d_{i_{b}^{n_{b}},i_{b}^{n_{b}+1}}$

31

32if  _$l <l_{min}$_ then

33 return false

34$\textsf{feasibleTillTrip}\leftarrow n_{b}$

35 return true

Algorithm 2 IsRotationChargeFeasible

Figure 10 illustrates the charge level updates between two consecutive trips
($4$ and $7$) of a bus rotation. The numbers on the arcs indicate the energy
required for each trip or for deadheading. The values displayed in the colored
boxes represent the charge levels under different scenarios. Assuming that
charging occurs throughout the entire idle time at a maximum rate of 2.5
kWh/min, the charge levels increase by 50 kWh at each charging opportunity. In
the following sections, we use variants of this function, such as the
AreRotationChargeFeasible, in which this function is applied in a loop across
different rotations. The notations for these functions are slightly abused to
spare the reader from a description of overloaded versions of the function.

(a) Charging station is at the end terminal of the current trip

(b) Charging station is at the start terminal of the next trip

(c) There are no charging stations at the end terminal of the current trip and
the start terminal of the next trip

Figure 10: Scenarios for charging between trips with a maximum charging rate
$\lambda=2.5$ kWh/min

###  5.3 Optimizing Rotations

We optimize rotations through simple local search moves that involve
exchanging and shifting service trips or exchanging depots. Each iteration of
this procedure (see Algorithm 3) alters the rotations in a greedy way by
selecting a move that yields the maximum objective function improvement. This
iterative process yields solutions that we call exchange optimal and shift
optimal, i.e., solutions that cannot be improved through exchanging two trips
or shifting a trip. One can view this as being similar to 2-opt moves in the
traveling salesman problem. Exchanging and shifting multiple trips can also be
performed, but this comes at a higher computational cost as the number of
possibilities explodes. In this context, methods such as improvement graphs
(Ahuja et al., 2002) are not directly applicable since the savings are not
additive. Instead, we use an OptimizeMultipleShifts subroutine on a limited
set of rotations involving few trips (based on a user-defined threshold) to
determine if multiple trips can be shifted elsewhere.

1

Input: $V,Z$

Output: $V$

2

3$\textsf{improvement}\leftarrow\infty$

4 $V^{best}\leftarrow V$

5 while  _$\mathsf{improvement} >0$_ do

6 $V\leftarrow V^{best}$

7 $V^{best}\leftarrow\textsc{ApplyBestImprovement}(V,Z)$

8 $\textsf{improvement}\leftarrow f(V,Z)-f(V^{best},Z)$

9

10$V\leftarrow\textsc{OptimizeMultipleShifts}(V,Z)$

Algorithm 3 OptimizeRotations

Rotations are updated within each iteration using the ApplyBestImprovement
sub-routine (Algorithm 4). The best exchange and shift across all service
trips are first evaluated (lines 1–2), and the better of the two is chosen
(lines 8–11). The subroutines Exst and Sst are described in Appendix A. When
service trip exchanges and shifts do not yield any benefit, we try exchanging
depots (lines 3–7). Note that buses do not need to return to the same depot at
the end of the day as long as the distribution of buses across depots remains
the same at the start and end of operations. This allows the service provider
to repeat schedules without needing to re-balance the buses. Trip exchanges
and shifts are the most time-consuming parts of the local search process,
particularly when the CSP is integrated. Hence, when dealing with networks
with a large number of trips, we use a hybrid version of this algorithm to
keep the computation tractable. In this hybrid method, a candidate pool of
exchanges and shifts is shortlisted based on the savings in deadheading, and
the CSP is jointly solved only for new rotations derived from this pool.

Input: $V,Z$

Output: $V$

1

2$V^{exst},\textsf{exchangeSavings}\leftarrow\textsc{Exst}(V,Z)$

3 $V^{sst},\textsf{shiftSavings}\leftarrow\textsc{Sst}(V,Z)$

4

// Exchange depots

5 if  _$\mathsf{exchangeSavings}\leq
0\mathbf{~{}and~{}}\mathsf{shiftSavings}\leq 0$_ then

6 $V^{exd},\textsf{depotExchangeSavings}\leftarrow\textsc{Exd}(V,Z)$

7 if  _$\mathsf{depotExchangeSavings} >0$_ then

8 $V\leftarrow V^{exd}$

9

10 return

11

// Exchange or shift service trips

12 if  _$\mathsf{exchangeSavings} >\mathsf{shiftSavings}$_ then

13 $V\leftarrow V^{exst}$

14

15else

16 $V\leftarrow V^{sst}$

17

Algorithm 4 ApplyBestImprovement

###  5.4 Optimizing Stations

####  5.4.1 Utilization Metrics

To prioritize the opening and closing of charging stations, we track the time
spent by buses at different charging stations. If several buses are idle at
stops that currently are not charging stations, opening a station at that
location can potentially reduce charging costs. Likewise, if buses do not
spend much time at locations where charging stations are currently open,
closing them would help recover the fixed costs associated with charging
infrastructure.

1

Input: $V,Z$

Output: $Z$

// Initialize current and potential utilizations

2 $\kappa_{s},\pi_{s}\leftarrow 0,0\,\forall\,s\in Z$

3

4for  _$\\{b\in V:b\text{ requires charging}\\}$_ do

5 for  _$j=1$ to $n_{b}-1$_ do

// The current trip’s end terminal is a charging station

6 if  _$i_{b}^{j,end}\in Z$_ then

7
$\kappa_{i_{b}^{j,end}}\leftarrow\kappa_{i_{b}^{j,end}}+\theta_{i_{b}^{j},i_{b}^{j+1}}$

// Only the next trip’s start terminal is a charging station

8 if  _$i_{b}^{j,end}\notin Z$ , $i_{b}^{j+1,start}\in Z$_ then

9
$\kappa_{i_{b}^{j+1,start}}\leftarrow\kappa_{i_{b}^{j+1,start}}+\theta_{i_{b}^{j},i_{b}^{j+1}}$

10
$\pi_{i_{b}^{j,end}}\leftarrow\pi_{i_{b}^{j,end}}+\theta_{i_{b}^{j},i_{b}^{j+1}}$

// The current trip’s end and next trip’s start terminals are not charging
stations

11 if  _$i_{b}^{j,end}\notin Z,i_{b}^{j+1,start}\notin Z$_ then

12
$\pi_{i_{b}^{j+1,start}}\leftarrow\pi_{i_{b}^{j+1,start}}+\theta_{i_{b}^{j},i_{b}^{j+1}}$

13
$\pi_{i_{b}^{j,end}}\leftarrow\pi_{i_{b}^{j,end}}+\theta_{i_{b}^{j},i_{b}^{j+1}}$

14

15

16

17

// Close charging terminals with zero utilization

18 for  _$s\in Z:\kappa_{s}=0$_ do

19 $Z\leftarrow Z\setminus\\{s\\}$

Algorithm 5 UpdateUtilization

Algorithm 5 is designed to update the utilization of various locations. We
keep track of two types of utilization metrics at each terminal $s$: current
utilization $\kappa_{s}$ and potential utilization $\pi_{s}$. The current
utilization simply stores the cumulative time spent by all buses at a charging
station. Potential utilization, on the other hand, captures the total idle
time spent by all the buses should a charging station be opened at $s$.
Finally, the algorithm also removes any charging stations from the set of
locations that have zero current utilization in lines 12–13.

Initially, the algorithm sets both the current and potential utilizations of
each location to zero. For each trip made by a bus, it checks if the ends of a
layover have a charging station and works in three scenarios just like
Algorithm 2. In case 1, if the end terminal of the current trip is a charging
station, the algorithm increments the current utilization of that station by
the idle time between the current and the next trip. Note that the utilization
stats are dependent on the current charging station configuration since we
assume that operations are carried out under the CAG policy. Hence, an open
charging station at the start of a trip will not be utilized if there is
already a charging station at the end terminal of its previous trip. In
scenario 2, if the end terminal is not a charging station but the start
terminal of the next trip is, it increments the current utilization of the
next trip’s start terminal and the potential utilization of the current trip’s
end terminal by the idle time. Finally, in scenario 3, if neither end of a
layover is a charging station, only the potential utilization for both
terminals is incremented by the idle time.

####  5.4.2 Opening Charging Stations

Algorithm 6 evaluates the impact of adding new charging stations on the
overall cost. It takes as input a list of charging stations to open $Z^{open}$
and checks for improvement in the rotations (and charge scheduling in the case
of the joint model). That is, the fixed costs of opening the station must be
offset by a reduction in the vehicle and charge scheduling costs. Charging
stations that are not needed are then removed using the UpdateUtilization
function (in the case of the sequential model) and the CLP-CSP model (in the
joint model case). If the new objective value is not better, no changes are
made to the set of charging stations and bus rotations (lines 7–9).

1

Input: $V,Z,Z^{open}$

Output: $V,Z$

2 $Z^{temp}\leftarrow Z\cup\\{Z^{open}\\}$

3 $V^{temp}\leftarrow\textsc{OptimizeRotations}(V,Z^{temp})$

4 if  _the sequential model is solved_ then

5 $Z^{temp}\leftarrow\textsc{UpdateUtilization}(V,Z^{temp})$

6

7if  _if the joint model is solved_ then

8 Solve CLP-CSP model (Section 4.3), remove unused stations from $Z^{temp}$

9if  _$f(V^{temp},Z^{temp}) <f(V,Z)$_ then

10 $V\leftarrow V^{temp}$

11 $Z\leftarrow Z^{temp}$

Algorithm 6 OpenChargingStation

####  5.4.3 Closing Charging Stations and Splitting Trips

We also test the effect of closing charging stations in a similar way, except
that closing charging stations affects charge feasibility, and hence, we allow
rotations to be split. Algorithm 7 takes as input the specific charging
station that is considered for closure and identifies a subset of buses that
are affected by the closure of the specified charging station under the CAG
strategy (lines 2–6). The algorithm then temporarily removes the specified
charging station from the location set and checks if the bus rotations are
still feasible. If the rotations are not feasible, the algorithm splits trips
at locations from where the bus can return to the depot without falling below
the lower threshold of charge using the AreRotationsChargeFeasible function.
This function, a variant of Algorithm 2, returns a Boolean value and a set of
potentially modified rotations. It yields ‘true’ if closing the station does
not result in a bus being stranded due to inadequate charge. This is
determined after recursively splitting rotations and checking their charge
feasibility. Splitting trips will require new buses and can increase the fixed
costs of buses. However, this can be compensated by better bus-to-trip
assignments. Hence, the bus rotations are optimized using the
OptimizeRotations sub-routine in line 11. If there is an improvement, the
station is kept closed, and the algorithm terminates.

1

Input: $V,Z,s^{close}$

Output: $V,Z$

2

// Identify the rotations affected by the terminal closure

3 $\textsf{affectedRotations}\leftarrow\emptyset$

4 for  _$\\{b\in V:b\text{ requires charging}\\}$_ do

5 for  _$j=1$ to $n_{b}-1$_ do

6 if
_$(i_{b}^{j,end}=s^{close})\mathbf{~{}or~{}}(i_{b}^{j+1,start}=s^{close}\mathbf{~{}and~{}}i_{b}^{j,end}\notin
Z)$_ then

7 $\textsf{affectedRotations}\leftarrow\textsf{affectedRotations}\cup\\{b\\}$

8 break

9

10

11

12

13$Z^{temp}\leftarrow Z\setminus\\{s^{close}\\}$

14

// Check for charge feasibility after terminal closure and split trips if
necessary

15
$\textsf{closureFeasible},V^{temp}\leftarrow\textsc{AreRotationsChargeFeasible}(V,Z^{temp},\textsf{affectedRotations})$

16 if  _$\mathbf{not~{}}\mathsf{closureFeasible}$_ then

17 return

18

19

// Optimize rotations after terminal closure

20 $V^{temp}\leftarrow\textsc{OptimizeRotations}(V^{temp},Z^{temp})$

21

22if  _$f(V^{temp},Z^{temp}) <f(V,Z)$_ then

23 $V\leftarrow V^{temp}$

24 $Z\leftarrow Z^{temp}$

Algorithm 7 CloseChargingStation

###  5.5 Summary

The overall ILS procedure is summarized in Algorithm 8. The CS algorithm
initalizes bus rotations (line 1). The OptimizeMultipleShifts operator (line
2) then optimizes these rotations by efficiently reallocate trips, focusing
particularly on rotations with fewer trips. We present the pseudocode for this
operator in Appendix B.

1

Input: $I$

Output: $V,Z$

2

// Initialize rotations and locations

3 $V,Z\leftarrow\textsc{ConcurrentScheduler}(I)$

4

// Optimize rotations that serve few trips

5 $V\leftarrow\textsc{OptimizeMultipleShifts}(V,Z)$

// Open charging stations and optimize rotations

6 $Z\leftarrow\textsc{UpdateUtilization}(V,Z)$

7 $Z^{open}\leftarrow$ Sort terminals not in $Z$ for which $\pi_{s}>0$ in
ascending order

8 $V,Z\leftarrow\textsc{OpenChargingStations}(V,Z,Z^{open})$

// Close charging stations and optimize rotations

9

10$Z^{close}\leftarrow$ Select all terminals in $Z$

11

12 do

13

14 if  _the sequential model is solved_ then

15 $Z\leftarrow\textsc{UpdateUtilization}(V,Z)$

16

17 if  _if the joint model is solved_ then

18 Solve CLP-CSP model (Section 4.3), remove unused stations from $Z$, and
update the optimal power capacities $q^{*}_{s}$

19

20 Remove terminal $s$ from $Z^{close}$ for which $\kappa_{s}=0$ (sequential
model) or $q^{*}_{s}=0$ (joint model)

21 Find terminal $s^{close}$ with minimum $\kappa_{s}$ (sequential model) or
$q^{*}_{s}$ (joint model) and remove it from $Z^{close}$

22

23 $V,Z\leftarrow\textsc{CloseChargingStation}(V,Z,s^{close})$

24

25while  _$Z^{close}\neq\emptyset$_

Find the optimal charge schedule using the CSP MILP (Section 4.1)

Algorithm 8 OptimizeEBusFleet

Subsequently, the algorithm calculates utilization metrics and opens charging
stations at locations that exhibit positive potential utilization (see
Algorithm 6). This process can also be executed sequentially for each station,
selecting a station with the highest potential utilization $\pi_{s}$. These
utilization metrics can then be updated after each iteration after further
optimizing the rotations.

From lines 7 to 15, the algorithm evaluates the impact of sequentially closing
charging stations, optimizing rotations during this process, and addressing
any charge infeasibilities by splitting rotations. The stations currently in
operation are tracked in $Z^{close}$. In the sequential model, the algorithm
updates utilizations and identifies the least utilized station for closure.
For joint models, the CLP-CSP split formulation is solved, and station power
capacities are utilized to prioritize closures. Stations exhibiting zero
utilization or power capacity are also removed from the potential closure
list.

Ultimately, after determining the optimal configuration of charging stations
and rotations, the algorithm solves the MILP CSP formulation described in
Section 4.1 to optimize charge scheduling costs. Although we explored the
possibility of swapping an open charging station with a closed one, the
benefits were negligible in our tested datasets and did not justify the
additional computational time.

##  6 Experiments and Results

We demonstrate the benefits of our framework on 14 real-world bus transit
networks by solving both the joint CLP-EVSP-CSP and the sequential CLP-EVSP
with a subsequent CSP model. The MILP model, outlined in Section 4.2, could
only be solved for small toy networks using CPLEX. The local search
subroutines were implemented in C++ using the GCC compiler version 11.4.0. LPs
were solved using CPLEX, and the Boost library was utilized for the Bron-
Kerbosch algorithm within the uniform charging LPs as CSP surrogates. All
experiments were conducted on a Dell Inc. Precision 7875 Tower equipped with
an AMD Ryzen Threadripper Pro 7975wx CPU @ 4.0 GHz and 128 GB of RAM. OpenMP
was employed with $32$ cores to run the exchange and shift operators in
parallel. The source codes are available at github.com/transetlab/clp-evsp-
csp.

###  6.1 Performance Evaluation of ILS

Datasets and Parameters: The GTFS data for all networks were collected from
transitfeeds.com. For deadheading trips, the shortest path distances between
stops are calculated using Open Street Maps (OSM) and converted into time,
assuming a constant bus speed of 30 km/h. This speed is consistent with the
bus speeds implied by the trip schedules for various networks. Table 6
provides a summary of the network data. The origins and destinations of
different routes determine candidate charging locations. Considering the
number of trips originating or terminating at each location, a maximum of five
depots are chosen from this subset. The initial CS solution determines the
column ‘Depots used’ based on the number of depots assigned to rotations.

To establish a lower limit on the required number of buses, we track the
number of simultaneous trips across time for all the networks. For example,
see Figure 11, where the SCMTD network requires a minimum of 134 buses to
accommodate simultaneous afternoon trips. Table 6 also presents the lower
limit on the number of buses for all networks.

Figure 11: Distribution of simultaneous trips over time for sample networks Table 6: Summary of transit network characteristics Network name |  Trips |  Routes |  Stops |  $|S^{cand}|$ |  Depots used |  Min buses required
---|---|---|---|---|---|---
Cornwall, Canada |  432 |  13 |  308 |  23 |  4 |  18
Milton, Canada |  501 |  9 |  312 |  5 |  3 |  22
Mountain Line, US |  716 |  9 |  181 |  11 |  5 |  42
Ann Arbor, US |  858 |  22 |  966 |  29 |  3 |  40
LA Go, US |  928 |  20 |  909 |  28 |  3 |  57
Cascades East, US |  1093 |  20 |  310 |  27 |  3 |  42
Denton County,US |  1148 |  32 |  560 |  25 |  5 |  32
Gold Coast, US |  1292 |  23 |  651 |  35 |  4 |  78
CityLink, US |  1364 |  20 |  1026 |  30 |  5 |  69
Intercity, US |  1591 |  22 |  954 |  22 |  4 |  85
SCMTD, US |  1830 |  24 |  786 |  26 |  4 |  134
Strathcona, Canada |  2355 |  28 |  373 |  30 |  3 |  117
Embark, US |  2830 |  34 |  1508 |  58 |  3 |  125
Arlington, US |  3337 |  19 |  635 |  32 |  5 |  123

Table 7 presents the parameter values used in this study. We apply an exchange
rate factor of 1.09 to convert cost parameters from euros (€) to dollars ($)
based on some of the original sources mentioned in Table 7. We assume dynamic
electricity pricing with the following schedule: 444 $/kWh from 9 AM to 2 PM,
555 $/kWh from 2 PM to 4 PM and 9 PM to 9 AM, with a peak rate of 1355 $/kWh
from 4 PM to 9 PM (PGEC, 2023). The table includes costs (in $) and energy-
related parameters sourced from existing literature. Some components of the
objective are strategic, while other costs are from tactical and operational
decisions. Therefore, these values are adjusted to account for a 12-year life
cycle operational period for buses and charging infrastructure. We do not
consider discounting and projected future energy prices, but these
modifications can be easily incorporated with good-quality estimates. In the
following sections, we detail the results of various heuristics for one
network, Ann Arbor, US. Similar trends were observed in other cases.

Table 7: Parameter values (operating costs are multiplied by $12\times 365$ to account for a 12-year operational period) Parameters | Values | References
---|---|---
$c^{bus}$ | $381,500 | Dirks et al. (2022)
$c^{loc}$ | $218,000 | Olsen and Kliewer (2022)
per km travel cost | $2,100 | Dirks et al. (2022)
$c^{cap}$ | 654 ($/kW) | Dirks et al. (2022)
$\lambda$ | 2.505 (kWh/min) | Jahic et al. (2019)
$l_{max}$ | 300 (kWh) | Stumpe et al. (2021)
$l_{min}$ | 45 (kWh) | Sadati et al. (2019)
$\psi_{b}$ | 2.505 (kWh/min) | Jahic et al. (2019)

Initial Solution Generation: We generate an initial feasible solution for both
the sequential and joint models using the CS algorithm. The initial solution
often recommends opening a large number of charging locations. However, only a
subset of these locations might be used when we solve the CSP using the MILP
model. The fixed charging location cost is calculated based on the stations
utilized by the post-CSP solution. Table 6.1 displays the initial solutions
for all networks, revealing that bus acquisition costs are a significant share
of the total cost. The % share of charge scheduling costs typically surpasses
facility opening and deadheading costs. In Figure 12(a), the Gantt chart
illustrates the bus schedules, featuring trips (indicated by blue bars) and
charging events. Charging gaps result from split charging, while gaps in bus
schedules include deadheading trips. The schedules are densely packed,
aligning with the CS algorithm’s logic. Colored backgrounds and borders help
distinguish the energy price periods. The Ann Arbor network’s initial solution
employs 10 charging locations, with many charging activities scheduled during
peak periods. Subsequent refinements of bus and charging schedules are made
through ILS and CSP models.

ILS – Sequential Model Results: The ILS for the sequential model addresses the
CLP-EVSP by refining the CS algorithm solution. Subsequently, the CEE model is
employed to solve the CSP. Table 6.1 presents outcomes for various networks,
revealing substantial cost savings over the CS solution. The reduction is
primarily due to fewer charging locations compared to the CS solution,
accompanied by notable deadheading cost reductions via exchange and shift
operators. Charge scheduling costs are also consistently lower across transit
networks. Figure 12(b) depicts the resulting Gantt chart of bus schedules,
featuring structural changes due to trip exchanges and shifts.

Table 8: Concurrent Scheduler results

Network
Name |  Buses Used |  Charging
Locations
Opened |  Total Cost
(Million
$) | % Share
---|---|---|---|---
Bus acquisition |  Facility Opening |  Deadhead |  CSP
Cornwall |  20 |  1 |  10.20 |  74.81 |  2.14 |  2.36 |  20.69
Milton |  25 |  4 |  14.31 |  66.64 |  6.09 |  2.39 |  24.88
Mountain Line |  45 |  1 |  22.36 |  76.76 |  0.97 |  1.99 |  20.28
Ann Arbor |  57 |  10 |  31.93 |  68.11 |  6.83 |  7.30 |  17.76
LA Go |  87 |  13 |  57.67 |  57.55 |  4.91 |  25.69 |  11.85
Cascades East |  71 |  11 |  41.67 |  65.00 |  5.75 |  17.13 |  12.12
Denton County |  46 |  13 |  32.23 |  54.46 |  8.79 |  14.96 |  21.79
Gold Coast |  97 |  12 |  57.52 |  64.33 |  4.55 |  14.34 |  16.78
CityLink |  87 |  13 |  56.69 |  58.55 |  5.00 |  15.16 |  21.29
Intercity |  195 |  11 |  95.70 |  77.73 |  2.51 |  6.99 |  12.77
SCMTD |  187 |  11 |  134.62 |  52.99 |  1.78 |  19.60 |  25.63
Strathcona |  146 |  4 |  82.98 |  67.13 |  1.05 |  7.86 |  23.96
Embark |  183 |  31 |  116.84 |  59.75 |  5.78 |  15.07 |  19.40
Arlington |  145 |  20 |  84.43 |  65.52 |  5.16 |  11.22 |  18.10

Figure 12: Cost components of the objective for the Ann Arbor network

ILS – Joint Model Results: We then applied the ILS technique to the joint CLP-
EVSP-CSP model, using the CS algorithm solution as a starting point. This
approach yields noticeable savings in charging costs, even though deadheading
costs increase compared to the sequential model for most networks. The joint
model’s results, summarized in Table 6.1, show overall cost savings across all
networks. The values in the table indicate savings relative to the solutions
of the sequential model.

Figure 12 breaks down the costs associated with using the CS, sequential, and
joint models for the Ann Arbor network. The joint model utilizes fewer
charging locations than the sequential model. Despite the increased
deadheading costs in the joint model, they remain lower than those incurred
using the CS algorithm. Figure 12(c) displays schedules from the joint model,
where one can prominently notice significant cost savings in electricity
consumption during peak periods, as only a few buses are charged. Similar
trends were observed in other networks.

A majority of the cost is incurred in bus acquisition. For agencies where bus
procurement happens through subsidies or when gasoline/diesel buses are
exchanged/replaced, these savings estimates are conservative and can actually
be closer to the CSP savings.

(a) Concurrent Scheduler model

(b) Sequential model

(c) Joint model

Figure 13: Bus schedules for the Ann Arbor network

Table 9: ILS model results (Instances marked with a ‘*’ were solved using a
hybrid method where the top $400$ shifts/exchanges were considered based on
savings in deadheading costs.) (a) Sequential model

Network
Name |  Buses Used |  Charging
Locations
Opened | % Savings w.r.t. CS Model |
---|---|---|---|---
Overall |  Bus acquisition |  Facility Opening |  Deadhead |  CSP |  Runtime (s)
Cornwall |  20 |  1 |  $0.51$ |  $0.00$ |  $0.00$ |  $15.93$ |  $0.67$ |  $0.08$
Milton |  25 |  2 |  $7.48$ |  $0.00$ |  $50.00$ |  $67.26$ |  $11.38$ |  $0.10$
Mountain Line |  45 |  1 |  $1.76$ |  $0.00$ |  $0.00$ |  $48.89$ |  $3.90$ |  $0.14$
Ann Arbor |  57 |  3 |  $14.84$ |  $0.00$ |  $70.00$ |  $70.49$ |  $27.69$ |  $0.28$
LA Go |  87 |  11 |  $8.13$ |  $0.00$ |  $15.38$ |  $20.42$ |  $18.00$ |  $0.45$
Cascades East |  71 |  8 |  $11.24$ |  $0.00$ |  $27.27$ |  $46.23$ |  $14.46$ |  $0.46$
Denton County |  46 |  7 |  $17.60$ |  $0.00$ |  $46.15$ |  $60.26$ |  $20.78$ |  $0.54$
Gold Coast |  97 |  7 |  $13.35$ |  $0.00$ |  $41.67$ |  $45.16$ |  $29.67$ |  $0.73$
CityLink |  87 |  6 |  $17.05$ |  $0.00$ |  $53.85$ |  $67.85$ |  $19.11$ |  $0.82$
Intercity |  195 |  7 |  $9.99$ |  $0.00$ |  $36.36$ |  $66.98$ |  $34.47$ |  $1.28$
SCMTD |  187 |  9 |  $14.77$ |  $0.00$ |  $18.18$ |  $45.66$ |  $21.44$ |  $1.76$
Strathcona |  146 |  3 |  $6.28$ |  $0.00$ |  $25.00$ |  $52.96$ |  $7.73$ |  $1.79$
Embark |  183 |  28 |  $15.16$ |  $0.00$ |  $9.68$ |  $57.39$ |  $30.69$ |  $4.07$
Arlington |  145 |  12 |  $11.49$ |  $0.00$ |  $40.00$ |  $52.19$ |  $19.73$ |  $6.25$

(b) Joint model

Network
Name |  Buses Used |  Charging
Locations
Opened | % Savings w.r.t. Sequential Model |
---|---|---|---|---
Overall |  Bus acquisition |  Facility Opening |  Deadhead |  CSP |  Runtime (s)
Cornwall |  20 |  1 |  $7.69$ |  $0.00$ |  $0.00$ |  $-3.88$ |  $37.58$ |  $41.58$
Milton |  25 |  2 |  $6.52$ |  $0.00$ |  $0.00$ |  $-46.93$ |  $29.01$ |  $59.17$
Mountain Line |  45 |  1 |  $5.11$ |  $0.00$ |  $0.00$ |  $10.03$ |  $25.25$ |  $90.65$
Ann Arbor |  57 |  2 |  $4.04$ |  $0.00$ |  $33.33$ |  $-47.11$ |  $29.34$ |  $102.70$
LA Go |  89 |  8 |  $0.99$ |  $-2.30$ |  $27.27$ |  $-4.09$ |  $19.90$ |  $865.11$
Cascades East |  71 |  5 |  $5.17$ |  $0.00$ |  $37.50$ |  $-7.47$ |  $35.74$ |  $702.00$
Denton County |  46 |  4 |  $4.84$ |  $0.00$ |  $42.86$ |  $-9.71$ |  $14.67$ |  $509.89$
Gold Coast |  98 |  6 |  $0.94$ |  $-1.03$ |  $14.29$ |  $-10.68$ |  $16.45$ |  $1420.18$
CityLink |  88 |  2 |  $6.66$ |  $-1.15$ |  $66.67$ |  $-5.43$ |  $28.57$ |  $4631.02$
Intercity |  195 |  2 |  $7.70$ |  $0.00$ |  $71.43$ |  $-16.36$ |  $73.65$ |  $11897.79$
SCMTD* |  193 |  7 |  $0.13$ |  $-3.21$ |  $22.22$ |  $-11.66$ |  $13.54$ |  $7024.60$
Strathcona* |  147 |  1 |  $3.70$ |  $-0.68$ |  $66.67$ |  $-27.41$ |  $19.97$ |  $1265.62$
Embark* |  188 |  19 |  $2.95$ |  $-2.73$ |  $32.14$ |  $-13.54$ |  $24.74$ |  $3135.22$
Arlington* |  146 |  7 |  $1.55$ |  $-0.69$ |  $41.67$ |  $-29.47$ |  $14.56$ |  $142177.98$

###  6.2 Extended Analysis

Power Requirements: The predominant objective component in the CSP is
electricity consumption costs. Table 10 summarizes the maximum and average
power requirements for charging locations opened using sequential and joint
models. In most instances, the maximum power required by the joint model is
lower than that of the sequential model. In cases where the sequential model
exhibits lower average power requirements, the difference is relatively
modest. Given that we model these decisions as continuous variables, the
overall power requirement can also be translated into the equivalent number of
chargers to be stationed at a charging facility. For example, a power
requirement of 300 kW will warrant installing two 150 kW chargers at the
charging location.

Table 10: Power requirements of charging stations in kW (The lower value of the two models are shown in bold) Network Name | Maximum Power Required | Average Power Required
---|---|---
|  Sequential |  Joint |  Sequential |  Joint
Cornwall |  811.22 |  262.29 |  811.22 |  262.29
Milton |  543.13 |  300.60 |  421.86 |  250.31
Mountain Line |  1032.66 |  681.01 |  1032.66 |  681.01
Ann Arbor |  694.65 |  601.65 |  450.49 |  601.43
LA Go |  377.14 |  300.60 |  148.56 |  152.02
Cascades East |  314.09 |  219.98 |  179.34 |  144.06
Denton County |  302.00 |  315.03 |  198.84 |  274.50
Gold Coast |  536.57 |  549.97 |  246.42 |  241.56
CityLink |  2004.53 |  1106.46 |  549.82 |  778.68
Intercity |  1503.00 |  498.72 |  318.35 |  278.07
SCMTD |  1653.30 |  1675.09 |  600.01 |  730.78
Strathcona |  4401.20 |  3007.14 |  2068.27 |  3007.14
Embark |  450.90 |  450.90 |  183.29 |  191.17
Arlington |  300.60 |  332.96 |  237.97 |  298.11

Activity-Based Time Allocation: Figure 14 illustrates the time allocated to
various activities, as determined by the joint model for the Ann Arbor
network. Buses engage in service trips, deadhead trips, recharging activities,
idling during recharging due to split charging, and true idling when not
plugged into the grid. On average, buses spend approximately 8 hours on trips
and charging activities. Some buses covering short distances may not require
opportunity charging but require overnight charging. Periodic bus swapping
between different rotations/itineraries might be necessary to balance overall
usage and mitigate potential long-term maintenance issues.

Figure 14: Activity-based duration for buses in the Ann Arbor network using
the joint model

Station-level Analysis: Figure 15 displays station-level metrics for a sample
charging station situated at the Blake Transit Center (bus stop 54), Ann
Arbor. The metrics plotted include the number of buses present at the station,
the number of buses charging simultaneously, and the power demand at the
charging station over time. Under sequential and joint models, a maximum of 23
and 22 buses are observed to be simultaneously present at the charging
location, respectively. There are slight variations in the number of vehicles
present (see Figures 14(a) & 14(d)) between the sequential and joint models
due to variations in vehicle scheduling. Both sequential (Figure 14(b)) and
joint models (Figure 14(e)) accommodate a maximum of six simultaneously
charging buses. However, the overall power demand at the charging station
remains lower for the joint model than that observed in the sequential model
(see Figures 14(c) & 14(f)) at any given point in time. We notice this pattern
despite a nearly equal number of buses being present at the station over time
in both the sequential and joint models. Furthermore, very few charging events
take place during the peak periods in the joint case.

(a) Buses present (Sequential)

(b) Concurrent charging (Sequential)

(c) Power requirement (Sequential)

(d) Buses present (Joint)

(e) Concurrent charging (Joint)

(f) Power requirement (Joint)

Figure 15: Station-level comparison between the sequential and joint models
for the charging location at the Blake Transit Center of the Ann Arbor network

Bus-level Analysis: We can also monitor the energy levels of each bus during
operational hours using the results obtained from the ILS methods. Figure 16
traces the energy levels of buses 1 and 26 using the joint model solution.
Buses commence daily operations with a fully charged battery capacity of 300
kWh. Buses that require charging during the day finish daily operations with
an energy level of 45 kWh, indicating no overcharging. The red lines denote
energy dissipation during service or deadheading trips. Green lines represent
charging activities, while blue lines indicate bus idling. Varying slopes of
the red lines result from different speeds during service and deadheading
trips. Bus speeds fluctuate based on the schedule and the assumed deadheading
speed. On the other hand, varying slopes of the green lines result from
different charging rates and the split charging assumption. Bus $1$ exhibits
no split charging, whereas bus $26$ engages in split charging activities from
16:45 to 16:48, shown in Figure 15(c).

(a) Bus 1

(b) Bus 26

(c) Bus 26 (16:00 – 18:00)

Figure 16: Bus energy levels in the Ann Arbor network using the joint model

Convergence Analysis – ILS Models: We examine the convergence patterns of ILS
models using a normalized cost metric. The total cost of the CS model is
normalized to $1$, and the normalized total cost of the sequential/joint model
at termination is assumed to be $0$. In this analysis, CSP costs are excluded
when studying the convergence of the sequential model, as the focus is
exclusively on the CLP-EVSP. Convergence plots, as shown in Figure 17 for both
sequential and joint models across all networks, reveal that smaller networks
tend to converge faster than larger ones. Notably, most networks exhibit a
sharp decline in normalized costs after a few iterations, primarily due to the
closing of unused charging stations. The iteration count on the x-axis is
assumed to increment each time a cost improvement occurs during calls to the
OptimizeRotations function within Algorithm 8.

(a) Sequential model

(b) Joint model

Figure 17: Convergence of ILS models

##  7 Conclusions and Future Work

This study focused on a comprehensive approach to address the joint
optimization of charging locations, bus-to-trip assignments, and charge
scheduling. We first presented a sequential problem, which solves the CLP-
EVSP, followed by charge schedule optimization using a new CSP MILP model.
Additionally, we explored a fully integrated joint CLP-EVSP-CSP framework to
better capture the interdependence between decision variables. Although MILP
models can be formulated for both problems, they fall short of solving real-
world instances. To overcome this, we employ a novel ILS framework for both
models, with initial solutions generated using a concurrent scheduler
algorithm. The joint model solves the CLP-EVSP-CSP, integrating the CSP during
trip exchanges and shifts using innovative surrogate linear programming
formulations. We applied the sequential and joint models to various real-world
bus transit networks, with the joint model consistently outperforming the
sequential model, achieving an average of 17.5% and 14.1% savings in
scheduling and operational costs, respectively over all networks and maximum
total cost savings of up to 7.7%.

This research sets the stage for combining learning-based approaches to
identify parts of the state space worth exploring, thereby enabling the
application of these techniques to larger transit networks. Potential areas
for investigation could also include modifications to objectives and
constraints based on battery life cycles, incorporation of realistic battery
charging and discharging curves, addressing uncertainty in energy usage and
travel time due to congestion, and enabling buses to take charging detours.
Transit networks and schedules evolve over time; in this context, exploring
multi-stage deterministic and stochastic models would be interesting. These
models could account for changes in land use and travel patterns in urban
settings, assessing their impact on long-term decisions regarding bus
acquisition and charging infrastructure. Overall, our study makes a compelling
case for joint modeling, suggesting that introducing additional features is
worthwhile, provided that the trade-offs between solution quality and
computation time are carefully managed.

## Acknowledgments

The authors thank the Indo-German Science and Technology Centre (IGSTC) for
awarding the Paired Early Career Research Fellowship in Applied Research
(PECFAR) which allowed us to undertake this collaborative work.

## Author Contributions

Rito Brata Nath: Methodology, Software, Writing – Original Draft, Data
Curation, Investigation, Visualization; Tarun Rambha: Conceptualization,
Methodology, Software, Writing – Original Draft, Investigation, Supervision,
Funding acquisition; Maximilian Schiffer: Conceptualization, Methodology,
Writing – Review & Editing, Supervision, Funding acquisition.

##  Appendix Appendix A Optimize Rotations

In this appendix, we detail the exchange and shift operators for service trips
Exst and Sst, respectively. The sub-routine for exchanging depot trips, Exd,
is similar to Exst and is hence not presented in detail.

###  Appendix A.1 Exchanging Service Trips

Algorithm 9 exchanges service trips between a pair of buses to reduce
operational costs, primarily from deadheading. The algorithm computes cost
savings for all feasible pairs based on trip compatibility (line 4) and
charging levels (line 7). We finally perform the exchange yielding the highest
cost saving (lines 10–12).

Figure 18: Example of exchanging service trips

For the joint CLP-EVSP-CSP model, this exchange sub-routine additionally
calculates savings in electricity and power capacity costs using the charge
scheduling LP (line 9). Figure 18 illustrates a trip exchange step, where
trips $7$ and $9$ are exchanged between two buses. Note that trip pairs
($4,9$), ($9,3$), ($5,7$), and ($7,2$) must be compatible, and the exchange
should not make the rotations charge infeasible.

1

Input: $V,Z$

Output: $V^{exst},\textsf{exchangeSavings}$

2

3$V^{exst}\leftarrow V$

4 $\textsf{exchangeSavings}\leftarrow-\infty$

// Iterate across all possible trip exchanges

5 for  _$\left\\{\\{V_{u},V_{v}\\}:V_{u},V_{v}\in V,V_{u}\neq V_{v}\right\\}$_
do

6 for
_$j\in\\{1,2,\ldots,n_{u}\\},k\in\\{1,2,\ldots,n_{v}\\}:(i_{u}^{j-1},i_{v}^{k}),(i_{v}^{k},i_{u}^{j+1}),(i_{v}^{k-1},i_{u}^{j}),(i_{u}^{j},i_{v}^{k+1})\in
A$_ do

7 $V^{temp}\leftarrow V$

8 Update $V^{temp}$ by exchanging the $j^{\text{th}}$ trip of bus $u$ with
$k^{\text{th}}$ trip of bus $v$

9 if  _$\textsc{AreRotationsChargeFeasible}(V^{temp},Z$)_ then

10 if  _the joint model is solved_ then

11 Solve the CSP LP (Section 4.3) and add the charging costs to the $f$ values

12

// Select the exchange that yields maximum savings

13 if  _$f(V^{temp},Z)-f(V,Z) >\mathsf{exchangeSavings}$_ then

14 $\textsf{exchangeSavings}\leftarrow f(V^{temp},Z)-f(V,Z)$

15 $V^{exst}\leftarrow V^{temp}$

16

17

18

19

Algorithm 9 ExchangeServiceTrips (Exst)

###  Appendix A.2 Shifting Service Trips

Algorithm 10 performs an exhaustive search by shifting a service trip from one
bus to another. We verify the possibility of trip insertion based on trip
compatibility (line 4) and charge feasibility of the updated configuration
(line 7). The cost savings are similarly to those for the exchange operator
(lines 10–12), with the exception that if a bus performs no service trips, it
is omitted, and the vehicle’s fixed cost is recovered. As before, we solve the
charge scheduling LP only for the joint CLP-EVSP-CSP model (line 9).

Figure 19: Example of shifting service trips

Figure 19 illustrates an example of shifting of service trips. Suppose $(7,5)$
and $(5,3)$ are compatible trip pairs. Trip $5$, originally performed by bus
$v$, is shifted after trip $7$ of bus $u$ after ensuring that the resulting
rotation is charge feasible.

1

Input: $V,Z$

Output: $V^{sst},\textsf{shiftSavings}$

2

3$V^{sst}\leftarrow V$

4 $\textsf{shiftSavings}\leftarrow-\infty$

// Iterate across all possible shifts

5 for  _$V_{u},V_{v}\in V:V_{u}\neq V_{v}$_ do

6 for
_$j\in\\{1,2,\ldots,n_{u}\\},k\in\\{1,2,\ldots,n_{v}\\}:(i_{u}^{j},i_{v}^{k}),(i_{v}^{k},i_{u}^{j+1})\in
A$_ do

7 $V^{temp}\leftarrow V$

8 Update $V^{temp}$ by shifting the $k^{\text{th}}$ trip of bus $v$ after
$j^{\text{th}}$ trip of bus $u$

9 if  _$\textsc{AreRotationsChargeFeasible}(V^{temp},Z)$_ then

10 if  _the joint model is solved_ then

11 Solve the CSP LP (Section 4.3) and add the charging costs to the $f$ values

12

// Select the shift that yields maximum savings

13 if  _$f(V^{temp},Z)-f(V,Z) >\mathsf{shiftSavings}$_ then

14 $\textsf{shiftSavings}\leftarrow f(V^{temp},Z)-f(V,Z)$

15 $V^{sst}\leftarrow V^{temp}$

16

17

18

19

20

Algorithm 10 ShiftServiceTrips (Sst)

##  Appendix Appendix B ILS Routines for Shifting Multiple Trips

Although we found that the rotations from the concurrent scheduler are usually
tight, the closure of charging stations can lead to the splitting of rotations
and the creation of rotations with fewer trips. In such cases, shifting one
trip at a time in the Sst subroutine may not help release these newly created
rotations since it may be optimal to exchange and shift other trips in
subsequent iterations. Since bus acquisition costs are one of the largest
components of the overall objective, we use an operator that attempts to shift
multiple trips in rotations that have fewer trips than a user-defined
threshold. The locations at which these trips are to be inserted are chosen
greedily. Even when they do not reduce the number of rotations, these
operators offer some benefits to the deadheading costs while remaining
computationally inexpensive.

1

Input: $V,Z$

Output: $V$

2

3$\textsf{improvement}\leftarrow\infty$

4 $V^{best}\leftarrow V$

5

// Apply shifts repeatedly until the benefits are exhausted

6 while  _$\mathsf{improvement} >0$_ do

7 $V\leftarrow V^{best}$

8

9 $V^{few}\leftarrow$ Rotations in $V$ with fewer than $\zeta$ service trips

10

11 $\textsf{maxSavings}\leftarrow-\infty$

12

// Find the rotation that gives the maximum savings from shifting multiple
trips

13 for  _$V_{b}\in V^{few}$_ do

14
$V^{msst},\textsf{multiShiftSavings}\leftarrow\textsc{ShiftMultipleTrips}(V,Z,V_{b})$

15 if  _$\mathsf{multiShiftSavings} >\mathsf{maxSavings}$_ then

16 $\textsf{maxSavings}\leftarrow\textsf{multiShiftSavings}$

17 $V^{best}\leftarrow V^{msst}$

18

19

20

21 $\textsf{improvement}\leftarrow f(V,Z)-f(V^{best},Z)$

22

Algorithm 11 OptimizeMultipleShifts

Algorithm 11 describes a sub-routine that iteratively checks if there is a
rotation that improves the objective when multiple trips are shifted to other
rotations. To keep these calculations tractable, we consider only those
rotations with $\zeta=5$ or fewer service trips (see line 5). Each rotation in
$V^{few}$ is examined in the ShiftMultipleTrips sub-routine (lines 7–8) for
savings from shifting multiple trips, and the resulting rotations are saved in
$V^{msst}$. The most promising of these bus-to-trip assignments are saved in
$V^{best}$ in lines 9–11. We then calculate the change in the objective in
line 12, and the process is repeated until such shifts are no longer
advantageous.

The ShiftMultipleTrips sub-routine (see Algorithm 12) is similar to the Sst
algorithm, except that it tries to shift multiple trips assigned to a bus to
other rotations. The output includes an adjusted list of bus rotations
($V^{msst}$) and the maximum savings possible from such greedy insertions
(multiShiftSavings). The algorithm begins by creating a copy of the original
bus rotations that is returned if no trip can be shifted (line 1). It then
iterates over each trip in $V_{b}$ and initializes variables to track the
feasibility of a single shift and determines where to insert the displaced
trip for maximum savings in the objective. Trip compatibility and charge
feasibility are necessary during these calculations, and we embed the CSP
linear program when the problem is jointly solved. Lines 4–13 carry out these
steps and are similar to the Sst algorithm. If the shifted trip can be
inserted elsewhere, the algorithm updates the rotation list, and proceeds to
shift the next trip in $V_{b}$. Note that some of the shifts can lead to
negative savings. The overall objective of this procedure, however, can only
improve as it is taken care of in line 3 of Algorithm 11.

1

Input: $V,Z,V_{b}$

Output: $V^{msst},\textsf{multiShiftSavings}$

2

3$V^{org}\leftarrow V$

// Shift multiple trips in the rotation

4 for  _$k=1$ to $n_{b}$_ do

5 multiShiftSavings $\leftarrow-\infty$

// Iterate across all possible locations to insert the trip

6 for  _$V_{u}\in V:V_{u}\neq V_{b}$_ do

7 for
_$j\in\\{1,2,\ldots,n_{u}\\}:(i_{u}^{j},i_{b}^{k}),(i_{b}^{k},i_{u}^{j+1})\in
A$_ do

8 $V^{temp}\leftarrow V$

9 Update $V^{temp}$ by shifting the $k^{\text{th}}$ trip of bus $b$ after
$j^{\text{th}}$ trip of bus $u$

10 if  _$\textsc{AreRotationsChargeFeasible}(V^{temp},Z)$_ then

11 if  _the joint model is solved_ then

12 Solve the CSP LP (Section 4.3) and add the charging costs to the $f$ values

13

// Select the shift that gives the maximum savings

14 if  _$f(V^{temp},Z)-f(V,Z) >\mathsf{multiShiftSavings}$_ then

15 $\textsf{multiShiftSavings}\leftarrow f(V^{temp},Z)-f(V,Z)$

16 $V^{msst}\leftarrow V^{temp}$

17

18

19

20

21

// Update the rotations if shifting the trip is feasible

22 if  _$\mathsf{multiShiftSavings=-\infty}$_ then

23 return $V^{org}$

24 $V\leftarrow V^{msst}$

25

Algorithm 12 ShiftMultipleTrips

## References

  * Abdelwahed et al. (2020) Abdelwahed, A., P. L. van den Berg, T. Brandt, J. Collins, and W. Ketter (2020).  Evaluating and optimizing opportunity fast-charging schedules in transit battery electric bus networks.  Transportation Science 54(6), 1601–1615.
  * Adler and Mirchandani (2017) Adler, J. D. and P. B. Mirchandani (2017).  The vehicle scheduling problem for fleets with alternative-fuel vehicles.  Transportation Science 51(2), 441–456.
  * Ahuja et al. (2002) Ahuja, R. K., Ö. Ergun, J. B. Orlin, and A. P. Punnen (2002).  A survey of very large-scale neighborhood search techniques.  Discrete Applied Mathematics 123(1-3), 75–102.
  * Alvo et al. (2021) Alvo, M., G. Angulo, and M. A. Klapp (2021).  An exact solution approach for an electric bus dispatch problem.  Transportation Research Part E: Logistics and Transportation Review 156, 102528.
  * Alwesabi et al. (2021) Alwesabi, Y., Z. Liu, S. Kwon, and Y. Wang (2021).  A novel integration of scheduling and dynamic wireless charging planning models of battery electric buses.  Energy 230, 120806.
  * Alwesabi et al. (2020) Alwesabi, Y., Y. Wang, R. Avalos, and Z. Liu (2020).  Electric bus scheduling under single depot dynamic wireless charging infrastructure planning.  Energy 213, 118855.
  * Bagherinezhad et al. (2020) Bagherinezhad, A., A. D. Palomino, B. Li, and M. Parvania (2020).  Spatio-temporal electric bus charging optimization with transit network constraints.  IEEE Transactions on Industry Applications 56(5), 5741–5749.
  * Bertossi et al. (1987) Bertossi, A. A., P. Carraresi, and G. Gallo (1987).  On some matching problems arising in vehicle scheduling models.  Networks 17(3), 271–281.
  * Bodin et al. (1978) Bodin, L., D. Rosenfield, and A. Kydes (1978).  UCOST: A micro approach to a transportation planning problem.  Journal of Urban Analysis 5(1).
  * Bron and Kerbosch (1973) Bron, C. and J. Kerbosch (1973).  Algorithm 457: Finding all cliques of an undirected graph.  Communications of the ACM 16(9), 575–577.
  * Bunte and Kliewer (2009) Bunte, S. and N. Kliewer (2009).  An overview on vehicle scheduling models.  Public Transport 1(4), 299–317.
  * BYD (2023) BYD (2023).  BYD electric bus specifications.  https://en.byd.com/bus/.  Accessed: 2023-07-26.
  * Cavadas et al. (2015) Cavadas, J., G. H. de Almeida Correia, and J. Gouveia (2015).  A MIP model for locating slow-charging stations for electric vehicles in urban areas accounting for driver tours.  Transportation Research Part E: Logistics and Transportation Review 75, 188–201.
  * Dirks et al. (2022) Dirks, N., M. Schiffer, and G. Walther (2022).  On the integration of battery electric buses into urban bus networks.  Transportation Research Part C: Emerging Technologies 139, 103628.
  * Ellingsen et al. (2022) Ellingsen, L. A.-W., R. J. Thorne, J. Wind, E. Figenbaum, M. Romare, and A. Nordelöf (2022).  Life cycle assessment of battery electric buses.  Transportation Research Part D: Transport and Environment 112, 103498.
  * Forbes et al. (1994) Forbes, M., J. Holt, and A. Watts (1994).  An exact algorithm for multiple depot bus scheduling.  European Journal of Operational Research 72(1), 115–124.
  * Gairola and Nezamuddin (2023) Gairola, P. and N. Nezamuddin (2023).  Optimization framework for integrated battery electric bus planning and charging scheduling.  Transportation Research Part D: Transport and Environment 118, 103697.
  * Gkiotsalitis et al. (2023) Gkiotsalitis, K., C. Iliopoulou, and K. Kepaptsoglou (2023).  An exact approach for the multi-depot electric bus scheduling problem with time windows.  European Journal of Operational Research 306(1), 189–206.
  * Haghani and Banihashemi (2002) Haghani, A. and M. Banihashemi (2002).  Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints.  Transportation Research Part A: Policy and Practice 36(4), 309–333.
  * Hansen et al. (2010) Hansen, P., N. Mladenović, and J. A. Moreno Perez (2010).  Variable neighbourhood search: methods and applications.  Annals of Operations Research 175, 367–407.
  * He et al. (2015) He, F., Y. Yin, and J. Zhou (2015).  Deploying public charging stations for electric vehicles on urban road networks.  Transportation Research Part C: Emerging Technologies 60, 227–240.
  * He et al. (2020) He, Y., Z. Liu, and Z. Song (2020).  Optimal charging scheduling and management for a fast-charging battery electric bus system.  Transportation Research Part E: Logistics and Transportation Review 142, 102056.
  * He et al. (2019) He, Y., Z. Song, and Z. Liu (2019).  Fast-charging station deployment for battery electric bus systems considering electricity demand charges.  Sustainable Cities and Society 48, 101530.
  * Houbbadi et al. (2019) Houbbadi, A., R. Trigui, S. Pelissier, E. Redondo-Iglesias, and T. Bouton (2019).  Optimal scheduling to manage an electric bus fleet overnight charging.  Energies 12(14), 2727.
  * Hu et al. (2022) Hu, H., B. Du, W. Liu, and P. Perez (2022).  A joint optimisation model for charger locating and electric bus charging scheduling considering opportunity fast charging and uncertainties.  Transportation Research Part C: Emerging Technologies 141, 103732.
  * Iliopoulou and Kepaptsoglou (2019) Iliopoulou, C. and K. Kepaptsoglou (2019).  Integrated transit route network design and infrastructure planning for on-line electric vehicles.  Transportation Research Part D: Transport and Environment 77, 178–197.
  * Iliopoulou and Kepaptsoglou (2021) Iliopoulou, C. and K. Kepaptsoglou (2021).  Robust electric transit route network design problem (RE-TRNDP) with delay considerations: model and application.  Transportation Research Part C: Emerging Technologies 129, 103255.
  * Jahic et al. (2019) Jahic, A., M. Eskander, and D. Schulz (2019).  Charging schedule for load peak minimization on large-scale electric bus depots.  Applied Sciences 9(9), 1748.
  * Janovec and Koháni (2019) Janovec, M. and M. Koháni (2019).  Exact approach to the electric bus fleet scheduling.  Transportation Research Procedia 40, 1380–1387.
  * Jiang et al. (2021) Jiang, M., Y. Zhang, and Y. Zhang (2021).  Multi-depot electric bus scheduling considering operational constraint and partial charging: A case study in Shenzhen, China.  Sustainability 14(1), 255.
  * Ke et al. (2020) Ke, B.-R., Y.-H. Lin, H.-Z. Chen, and S.-C. Fang (2020).  Battery charging and discharging scheduling with demand response for an electric bus public transportation system.  Sustainable Energy Technologies and Assessments 40, 100741\.
  * Klein and Schiffer (2023) Klein, P. S. and M. Schiffer (2023).  Electric vehicle charge scheduling with flexible service operations.  Transportation Science 57(6), 1605–1626.
  * Kliewer et al. (2006) Kliewer, N., T. Mellouli, and L. Suhl (2006).  A time–space network based exact optimization model for multi-depot bus scheduling.  European Journal of Operational Research 175(3), 1616–1627.
  * Kunith et al. (2017) Kunith, A., R. Mendelevitch, and D. Goehlich (2017).  Electrification of a city bus network—An optimization model for cost-effective placing of charging infrastructure and battery sizing of fast-charging electric bus systems.  International Journal of Sustainable Transportation 11(10), 707–720.
  * Lee et al. (2021) Lee, J., H. Shon, I. Papakonstantinou, and S. Son (2021).  Optimal fleet, battery, and charging infrastructure planning for reliable electric bus operations.  Transportation Research Part D: Transport and Environment 100, 103066.
  * Leou and Hung (2017) Leou, R.-C. and J.-J. Hung (2017).  Optimal charging schedule planning and economic analysis for electric bus charging stations.  Energies 10(4), 483.
  * Li (2014) Li, J.-Q. (2014).  Transit bus scheduling with limited energy.  Transportation Science 48(4), 521–539.
  * Li et al. (2019) Li, L., H. K. Lo, and F. Xiao (2019).  Mixed bus fleet scheduling under range and refueling constraints.  Transportation Research Part C: Emerging Technologies 104, 443–462.
  * Li et al. (2020) Li, X., T. Wang, L. Li, F. Feng, W. Wang, and C. Cheng (2020).  Joint optimization of regular charging electric bus transit network schedule and stationary charger deployment considering partial charging policy and time-of-use electricity prices.  Journal of Advanced Transportation 2020.
  * Liu and Ceder (2020) Liu, T. and A. A. Ceder (2020).  Battery-electric transit vehicle scheduling with optimal number of stationary chargers.  Transportation Research Part C: Emerging Technologies 114, 118–139.
  * Liu et al. (2019) Liu, Y., E. Yao, M. Lu, and L. Yuan (2019).  Regional electric bus driving plan optimization algorithm considering charging time window.  Mathematical Problems in Engineering 2019, 1–9.
  * Metais et al. (2022) Metais, M.-O., O. Jouini, Y. Perez, J. Berrada, and E. Suomalainen (2022).  Too much or not enough? planning electric vehicle charging infrastructure: A review of modeling options.  Renewable and Sustainable Energy Reviews 153, 111719.
  * Mladenović and Hansen (1997) Mladenović, N. and P. Hansen (1997).  Variable neighborhood search.  Computers & Operations Research 24(11), 1097–1100.
  * Olsen and Kliewer (2020) Olsen, N. and N. Kliewer (2020).  Scheduling electric buses in public transport: modeling of the charging process and analysis of assumptions.  Logistics Research 13(1), 4.
  * Olsen and Kliewer (2022) Olsen, N. and N. Kliewer (2022).  Location planning of charging stations for electric buses in public transport considering vehicle scheduling: A variable neighborhood search based approach.  Applied Sciences 12(8), 3855.
  * Pelletier et al. (2019) Pelletier, S., O. Jabali, J. E. Mendoza, and G. Laporte (2019).  The electric bus fleet transition problem.  Transportation Research Part C: Emerging Technologies 109, 174–193.
  * Perumal et al. (2021) Perumal, S. S., T. Dollevoet, D. Huisman, R. M. Lusby, J. Larsen, and M. Riis (2021).  Solution approaches for integrated vehicle and crew scheduling with electric buses.  Computers & Operations Research 132, 105268.
  * Perumal et al. (2022) Perumal, S. S., R. M. Lusby, and J. Larsen (2022).  Electric bus planning & scheduling: A review of related problems and methodologies.  European Journal of Operational Research 301(2), 395–413.
  * PGEC (2023) PGEC (2023).  Pacific Gas and Electric Company: Electric schedule BEV.  https://www.pge.com/tariffs/assets/pdf/tariffbook/ELEC_SCHEDS_BEV.pdf.  Accessed: 2024-01-10.
  * Reuer et al. (2015) Reuer, J., N. Kliewer, and L. Wolbeck (2015).  The electric vehicle scheduling problem: A study on time-space network based and heuristic solution.  In Proceedings of the Conference on Advanced Systems in Public Transport (CASPT).
  * Ribeiro and Soumis (1994) Ribeiro, C. C. and F. Soumis (1994).  A column generation approach to the multiple-depot vehicle scheduling problem.  Operations Research 42(1), 41–52.
  * Rogge et al. (2018) Rogge, M., E. Van der Hurk, A. Larsen, and D. U. Sauer (2018).  Electric bus fleet size and mix problem with optimization of charging infrastructure.  Applied Energy 211, 282–295.
  * Sadati et al. (2019) Sadati, S. M. B., J. Moshtagh, M. Shafie-khah, A. Rastgou, and J. P. Catalão (2019).  Operational scheduling of a smart distribution system considering electric vehicles parking lot: A bi-level approach.  International Journal of Electrical Power & Energy Systems 105, 159–178.
  * Sadeghi-Barzani et al. (2014) Sadeghi-Barzani, P., A. Rajabi-Ghahnavieh, and H. Kazemi-Karegar (2014).  Optimal fast charging station placing and sizing.  Applied Energy 125, 289–299.
  * Sadeghian et al. (2022) Sadeghian, O., A. Oshnoei, B. Mohammadi-Ivatloo, V. Vahidinasab, and A. Anvari-Moghaddam (2022).  A comprehensive review on electric vehicles smart charging: solutions, strategies, technologies, and challenges.  Journal of Energy Storage 54, 105241.
  * Schettini et al. (2023) Schettini, T., M. Dell’Amico, F. Fumero, O. Jabali, and F. Malucelli (2023).  Locating and sizing electric vehicle chargers considering multiple technologies.  Energies 16(10), 4186.
  * Schiffer et al. (2021) Schiffer, M., P. S. Klein, G. Laporte, and G. Walther (2021).  Integrated planning for electric commercial vehicle fleets: A case study for retail mid-haul logistics networks.  European Journal of Operational Research 291(3), 944–960.
  * Schiffer et al. (2019) Schiffer, M., M. Schneider, G. Walther, and G. Laporte (2019).  Vehicle routing and location routing with intermediate stops: A review.  Transportation Science 53(2), 319–343.
  * Shahraki et al. (2015) Shahraki, N., H. Cai, M. Turkay, and M. Xu (2015).  Optimal locations of electric public charging stations using real world vehicle travel patterns.  Transportation Research Part D: Transport and Environment 41, 165–176.
  * Sierzchula et al. (2014) Sierzchula, W., S. Bakker, K. Maat, and B. Van Wee (2014).  The influence of financial incentives and other socio-economic factors on electric vehicle adoption.  Energy Policy 68, 183–194.
  * Stumpe et al. (2021) Stumpe, M., D. Rößler, G. Schryen, and N. Kliewer (2021).  Study on sensitivity of electric bus systems under simultaneous optimization of charging infrastructure and vehicle schedules.  EURO Journal on Transportation and Logistics 10, 100049\.
  * Tang et al. (2023) Tang, C., H. Shi, and T. Liu (2023).  Optimization of single-line electric bus scheduling with skip-stop operation.  Transportation Research Part D: Transport and Environment 117, 103652.
  * Tang et al. (2019) Tang, X., X. Lin, and F. He (2019).  Robust scheduling strategies of electric buses under stochastic traffic conditions.  Transportation Research Part C: Emerging Technologies 105, 163–182.
  * Teng et al. (2020) Teng, J., T. Chen, and W. Fan (2020).  Integrated approach to vehicle scheduling and bus timetabling for an electric bus line.  Journal of Transportation Engineering, Part A: Systems 146(2), 04019073.
  * Wan et al. (2015) Wan, Z., D. Sperling, and Y. Wang (2015).  China’s electric car frustrations.  Transportation Research Part D: Transport and Environment 34, 116–121.
  * Wang and Shen (2007) Wang, H. and J. Shen (2007).  Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints.  Applied Mathematics and Computation 190(2), 1237–1249.