The vehicle scheduling problem under consideration is a multi-depot VSP. However, given the problem setup (see Sec. II-A), where each trip originates and terminates at the same depot, and each e-bus exclusively serves a single depot, the only coupling factor between depots is the total number of e-buses, |B||\mathcal{B}|. Consequently, once the set of buses associated with each depot, B_(d)\mathcal{B}_{d}, is determined, the problem can be decoupled into several single-depot VSPs. These single-depot problems can then be solved independently for each depot, resulting in a more computationally efficient approach. 所考虑的车辆调度问题是一个多仓库车辆调度问题(VSP)。然而,鉴于问题设置(见第 II-A 节),每次行程均从同一仓库出发并在同一仓库结束,并且每辆电动公交车仅服务于一个仓库,因此仓库之间的唯一耦合因素是电动公交车的总数 |B||\mathcal{B}| 。因此,一旦确定与每个仓库相关的公交车集合 B_(d)\mathcal{B}_{d} ,该问题就可以解耦为几个单仓库的 VSP。这些单仓库问题可以独立地为每个仓库解决,从而实现更高的计算效率。
In light of this, we propose a three-stage VSP. Firstly, we formulate and solve the VSP-I, which determines the optimal number of e-buses allocated to each depot, considering the average daily energy requirements among depots. This decouples the depots and enables us to address the remaining problems as single-depot VSPs for each depot dd. In the second stage, we introduce the VSP-II_(d)\mathrm{VSP}-\mathrm{II}_{d}, which minimizes the maximum daily energy requirement for the buses within the depot dd. The optimal objective value of VSP-II_(d)\mathrm{VSP}-I I_{d} is then integrated to VSP-III _(d){ }_{d} as a constraint, which optimally determines schedules and the chargeable time-slots for each e-bus in depot dd and facilitates reduction of battery degradation. 鉴于此,我们提出了一个三阶段的电动公交车调度问题(VSP)。首先,我们制定并解决了 VSP-I,该问题确定分配给每个车库的电动公交车的最优数量,考虑到各车库之间的平均每日能量需求。这使得车库之间相互解耦,使我们能够将剩余问题作为每个车库的单车库 VSP 来处理 dd 。在第二阶段,我们引入 VSP-II_(d)\mathrm{VSP}-\mathrm{II}_{d} ,该问题最小化车库内公交车的最大每日能量需求 dd 。然后,将 VSP-II_(d)\mathrm{VSP}-I I_{d} 的最优目标值作为约束整合到 VSP-III _(d){ }_{d} 中,最优地确定车库 dd 中每辆电动公交车的调度和可充电时间段,并促进电池退化的减少。
A. Allocation of e-Buses to Depots A. 电动公交车分配到车库
The objective of the first stage VSP, VSP-I, is to determine the number of e-buses assigned to each depot such that the average daily energy requirement for each e-bus is evenly distributed between depots [34]. This objective provides the foundation for the VSP in the next stage, VSP-II _(d){ }_{d}, wherein the daily energy requirement for each e-bus is evenly distributed within depots. It is crucial to ensure a balanced distribution of energy requirements among e-buses, as this leads to uniform processed energy per e-bus and consequently contributes to consistent aging of e-bus batteries within the fleet. This promotes uniform battery performance and longevity. 第一阶段电动公交车调度问题(VSP-I)的目标是确定分配给每个车库的电动公交车数量,以便每辆电动公交车的平均每日能量需求在各个车库之间均匀分配[34]。这一目标为下一阶段的电动公交车调度问题(VSP-II)奠定了基础,在这一阶段,每辆电动公交车的每日能量需求在车库内均匀分配。确保电动公交车之间能量需求的平衡分配至关重要,因为这会导致每辆电动公交车的处理能量均匀,从而有助于车队内电动公交车电池的一致老化。这促进了电池性能和使用寿命的均匀性。
The following mixed-integer program defines the VSP-I: 以下混合整数规划定义了 VSP-I:
{:[" VSP-I : min "psi],[" s.t. "b_(d) >= B_(d)^(min)","AA d inD","],[sum_(d inD)b_(d)=|B|","],[(1)/(b_(d))sum_(r inR_(d))e_(r) <= psi","quad AA d inD.]:}\begin{aligned}
& \text { VSP-I : min } \boldsymbol{\psi} \\
& \text { s.t. } \boldsymbol{b}_{d} \geq B_{d}^{\min }, \forall d \in \mathcal{D}, \\
& \sum_{d \in \mathcal{D}} \boldsymbol{b}_{d}=|\mathcal{B}|, \\
& \frac{1}{b_{d}} \sum_{r \in \mathcal{R}_{d}} e_{r} \leq \boldsymbol{\psi}, \quad \forall d \in \mathcal{D} .
\end{aligned}
In this formulation, the objective function defined in (1a) aims to minimize the maximum daily expected energy consumption per e-bus across depots, thereby ensuring an equitable distribution of this quantity among depots. (1b) sets the lower bound on b_(d)\boldsymbol{b}_{d}, ensuring that each depot is assigned a sufficient number of e-buses to serve their associated trips. The lower bound B_(d)^(min)B_{d}^{\min } is simply the maximum number of trips served simultaneously for depot dd, which can be calculated from the trip timetables as B_(d)^(min)=max{sum_(r inR_(b))m_(r,t)^(d)}_(t inT)B_{d}^{\min }=\max \left\{\sum_{r \in \mathcal{R}_{b}} m_{r, t}^{d}\right\}_{t \in \mathcal{T}}. (1c) ensures that each e-bus in the fleet is allocated to a depot. The term on the left-hand side of (1d) represents the daily expected energy consumption per e-bus for depot dd. The objective function utilizes the variable psi\psi to minimize the highest value of this term across all depots. 在这个公式中,(1a)中定义的目标函数旨在最小化各个车库之间每辆电动公交车的最大每日预期能耗,从而确保这一数量在车库之间的公平分配。(1b)设定了 b_(d)\boldsymbol{b}_{d} 的下限,确保每个车库分配足够数量的电动公交车以服务其相关的行程。下限 B_(d)^(min)B_{d}^{\min } 仅仅是车库 dd 同时服务的最大行程数量,可以从行程时间表中计算得出为 B_(d)^(min)=max{sum_(r inR_(b))m_(r,t)^(d)}_(t inT)B_{d}^{\min }=\max \left\{\sum_{r \in \mathcal{R}_{b}} m_{r, t}^{d}\right\}_{t \in \mathcal{T}} 。(1c)确保车队中的每辆电动公交车都分配给一个车库。(1d)左侧的项表示车库 dd 每辆电动公交车的每日预期能耗。目标函数利用变量 psi\psi 来最小化所有车库中该项的最高值。
The solution of VSP-I reveals the optimal number of e-buses assigned to each depot, i.e., {b_(d)}^(***VSP-I)\left\{\boldsymbol{b}_{\boldsymbol{d}}\right\}^{\star \mathrm{VSP}-\mathrm{I}} for all d inDd \in \mathcal{D}, which is used to construct the e-bus fleet sets for each depot dd as B_(d)\mathcal{B}_{d} to be used in the subsequent formulations. VSP-I 的解揭示了分配给每个车库的电动公交车的最优数量,即 {b_(d)}^(***VSP-I)\left\{\boldsymbol{b}_{\boldsymbol{d}}\right\}^{\star \mathrm{VSP}-\mathrm{I}} 对于所有 d inDd \in \mathcal{D} ,这用于构建每个车库的电动公交车车队集合 dd ,作为 B_(d)\mathcal{B}_{d} 以便在后续的公式中使用。
B. Determining the Maximum Daily Energy Consumption of Depots B. 确定仓库的最大日能耗
Once the fleets of each depot dd are distinguished by the sets B_(d)\mathcal{B}_{d} using VSP -I , the vehicle scheduling problem of each depot is decoupled and the vehicle scheduling of each depot can be done independently. The objective of VSP-III_(d)\mathrm{VSP}-\mathrm{II} I_{d} is to equalize the daily energy consumption of each e-bus within a depot dd while ensuring that each trip in R_(d)\mathcal{R}_{d} can be feasibly served. Using the trip timetable data m_(r,t)^(d)m_{r, t}^{d}, we formulate the VSP-II_(d)\mathrm{VSP}-I \mathrm{I}_{d} as a MILP as follows: 一旦通过 VSP -I 区分了每个仓库 dd 的车队与集合 B_(d)\mathcal{B}_{d} ,每个仓库的车辆调度问题就被解耦,且每个仓库的车辆调度可以独立进行。 VSP-III_(d)\mathrm{VSP}-\mathrm{II} I_{d} 的目标是在确保 R_(d)\mathcal{R}_{d} 中的每个行程都能可行服务的同时,使每个仓库 dd 内的每辆电动公交车的每日能耗保持平衡。利用行程时间表数据 m_(r,t)^(d)m_{r, t}^{d} ,我们将 VSP-II_(d)\mathrm{VSP}-I \mathrm{I}_{d} 公式化为如下的混合整数线性规划 (MILP):
{:[VSP-II_(d):mingamma_(d)],[qquad{:[" s.t. "sum_(r inR_(d))h_(b,r)^(d) >= 1","quad AA b inB_(d)],[sum_(b inB_(d))h_(b,r)^(d)=1","quad AA r inR_(d)],[sum_(r inR_(d))h_(b,r)^(d)m_(r,t)^(d) <= 1","AA b inB_(d)","AA t inT],[sum_(r inR_(d))h_(b,r)^(d)e_(r) <= gamma_(d)","quad AA b inB_(d)]:}]:}\begin{aligned}
& \mathrm{VSP}-\mathrm{II}_{d}: \min \boldsymbol{\gamma}_{d} \\
& \qquad \begin{aligned}
\text { s.t. } & \sum_{r \in \mathcal{R}_{d}} \boldsymbol{h}_{b, r}^{d} \geq 1, \quad \forall b \in \mathcal{B}_{d} \\
& \sum_{b \in \mathcal{B}_{d}} \boldsymbol{h}_{b, r}^{d}=1, \quad \forall r \in \mathcal{R}_{d} \\
& \sum_{r \in \mathcal{R}_{d}} \boldsymbol{h}_{b, r}^{d} m_{r, t}^{d} \leq 1, \forall b \in \mathcal{B}_{d}, \forall t \in \mathcal{T} \\
& \sum_{r \in \mathcal{R}_{d}} \boldsymbol{h}_{b, r}^{d} e_{r} \leq \boldsymbol{\gamma}_{d}, \quad \forall b \in \mathcal{B}_{d}
\end{aligned}
\end{aligned}
Here, the objective function in (2a) targets minimizing the maximum daily expected energy consumption within depot dd to ensure uniform energy consumption among e-buses. h_(b,r)^(d)\boldsymbol{h}_{b, r}^{d} is the binary trip assignment variable, which takes the value 1 if the e-bus b inB_(d)b \in \mathcal{B}_{d} is assigned to serve the trip r inR_(d)r \in \mathcal{R}_{d}, and zero otherwise. Constraints (2b)-(2d) are the standard constraints for a VSP. In particular, (2b) ensures that every e-bus is assigned to serve at least one trip, while (2c) guarantees that each trip is served by only one e-bus. (2d) prevents the allocation of two trips with overlapping schedules to the same e-bus. The left-hand side of (2e) is the daily energy consumption of a single e-bus, and the maximum energy consumption among all e-buses is represented by the variable gamma_(d)\boldsymbol{\gamma}_{d}, which is minimized by (2a) to equalize the daily energy consumption of each e-bus in B_(d)\mathcal{B}_{d}. 在这里,目标函数(2a)旨在最小化仓库 dd 内的最大每日预期能耗,以确保电动公交车之间的能耗均匀。 h_(b,r)^(d)\boldsymbol{h}_{b, r}^{d} 是二进制行程分配变量,当电动公交车 b inB_(d)b \in \mathcal{B}_{d} 被分配服务行程 r inR_(d)r \in \mathcal{R}_{d} 时取值为 1,否则为 0。约束条件(2b)-(2d)是车辆调度问题的标准约束。特别地,(2b)确保每辆电动公交车至少被分配服务一个行程,而(2c)保证每个行程仅由一辆电动公交车服务。(2d)防止将两个时间表重叠的行程分配给同一辆电动公交车。(2e)左侧是单辆电动公交车的每日能耗,所有电动公交车中的最大能耗由变量 gamma_(d)\boldsymbol{\gamma}_{d} 表示,该变量通过(2a)被最小化,以使 B_(d)\mathcal{B}_{d} 中每辆电动公交车的每日能耗相等。
It is noted that we only recover gamma_(d):={gamma_(d)}^(**VSP-II)_(d)\gamma_{d}:=\left\{\boldsymbol{\gamma}_{d}\right\}^{* \mathrm{VSP}-\mathrm{II}}{ }_{d} from VSP-II_(d)\mathrm{VSP}-\mathrm{I} I_{d}, and the final trip assignments are determined by the solution of VSP-III_(d)\mathrm{VSP}-\mathrm{II} I_{d}, which is defined next. 注意到我们仅从 VSP-II_(d)\mathrm{VSP}-\mathrm{I} I_{d} 中恢复 gamma_(d):={gamma_(d)}^(**VSP-II)_(d)\gamma_{d}:=\left\{\boldsymbol{\gamma}_{d}\right\}^{* \mathrm{VSP}-\mathrm{II}}{ }_{d} ,最终的行程分配由 VSP-III_(d)\mathrm{VSP}-\mathrm{II} I_{d} 的解确定,接下来将定义该解。
C. Determining Trip Assignments, e-Bus Timetables and Chargeable Time-Slots C. 确定行程分配、电子公交时刻表和可收费时间段
The third stage VSP involves determining the trip assignments for each depot while ensuring that the maximum daily energy consumption within depot dd, denoted as gamma_(d)\gamma_{d} and obtained through the solution of VSP-III_(d)\mathrm{VSP}-\mathrm{II} I_{d}, is not exceeded. In order to facilitate interaction between the VSP and reduction of battery degradation, the concepts of chargeable dwell period and chargeable time-slot are introduced, and the problem VSP-\mathrm{VSP}- II _(d)_{d} is defined. To elaborate on this, we first introduce the binary variable k_(b,t)\boldsymbol{k}_{b, t}, referred to as the e-bus timetable, defined as follows: 第三阶段的 VSP 涉及为每个车库确定行程分配,同时确保车库 dd 内的最大日能耗 gamma_(d)\gamma_{d} ,通过解决 VSP-III_(d)\mathrm{VSP}-\mathrm{II} I_{d} 获得,不被超过。为了促进 VSP 与电池衰减的减少之间的互动,引入了可充电停留时间和可充电时间段的概念,并定义了问题 VSP-\mathrm{VSP}- II _(d)_{d} 。为此,我们首先引入二元变量 k_(b,t)\boldsymbol{k}_{b, t} ,称为电动公交时刻表,定义如下:
k_(b,t)=sum_(r inR_(d))h_(b,r)^(d)m_(r,t)^(d),quad AA b inB_(d),AA t inT\boldsymbol{k}_{b, t}=\sum_{r \in \mathcal{R}_{d}} \boldsymbol{h}_{b, r}^{d} m_{r, t}^{d}, \quad \forall b \in \mathcal{B}_{d}, \forall t \in \mathcal{T}
where the variable k_(b,t)\boldsymbol{k}_{b, t} takes the value 1 if an e-bus bb is serving a trip during time-slot tt, and zero otherwise. Consequently, k_(b,t)\boldsymbol{k}_{b, t} comprises of consecutive ones and zeros, representing the trip periods on the road and dwell periods at the depot, respectively. During the dwell periods, the e-bus may be available for charging. However, as per the practical considerations delineated in Sec. II-B, not every dwell period is considered as chargeable. In particular, based on PC1-PC3, a dwell period is considered chargeable if and only if its duration is greater than or equal to T_(LB):=T_(pre)+T_(post)+T_(min)T_{L B}:=T_{p r e}+T_{p o s t}+T_{m i n}. 变量 k_(b,t)\boldsymbol{k}_{b, t} 的值为 1,当电动公交车 bb 在时间段 tt 内执行一次行程时,其他情况下为零。因此, k_(b,t)\boldsymbol{k}_{b, t} 由连续的 1 和 0 组成,分别表示在路上的行程时间和在车库的停留时间。在停留期间,电动公交车可能可用于充电。然而,根据第 II-B 节中列出的实际考虑,并非每个停留时间都被视为可充电的。特别是,根据 PC1-PC3,只有当停留时间的持续时间大于或等于 T_(LB):=T_(pre)+T_(post)+T_(min)T_{L B}:=T_{p r e}+T_{p o s t}+T_{m i n} 时,才被视为可充电的停留时间。
The aim of VSP-III _(d){ }_{d} is to maximize the number of chargeable dwell periods within the day for each e-bus while maintaining the minimized maximum daily energy consumption gamma_(d)\gamma_{d} obtained by VSP-II_(d)\mathrm{VSP}-I I_{d} and ensuring feasible trip assignments based on constraints (2c) - (2e). The rationale for this objective is to increase the charging opportunities of e-buses within the day, thereby keeping the depth-of-discharge low and reducing battery degradation. VSP-III 的目标是最大化每辆电动公交车在一天内可充电的停留时间,同时保持通过 VSP-II_(d)\mathrm{VSP}-I I_{d} 获得的最小化最大日能耗 gamma_(d)\gamma_{d} ,并确保基于约束条件(2c) - (2e)的可行行程分配。这个目标的理由是增加电动公交车在一天内的充电机会,从而保持放电深度较低,减少电池退化。
To mathematically represent the number of chargeable dwell periods, we introduce the binary variables k_(b,t)^("st "),k_(b,t)^("end "),l_(b,t)\boldsymbol{k}_{b, t}^{\text {st }}, \boldsymbol{k}_{b, t}^{\text {end }}, \boldsymbol{l}_{b, t}, and write the following constraints: 为了数学上表示可收费的停留时间数量,我们引入二元变量 k_(b,t)^("st "),k_(b,t)^("end "),l_(b,t)\boldsymbol{k}_{b, t}^{\text {st }}, \boldsymbol{k}_{b, t}^{\text {end }}, \boldsymbol{l}_{b, t} ,并写出以下约束:
{:[k_(b,t)-k_(b,t-1)=k_(b,t)^(st)-k_(b,t)^(end)","AA t inT","AA b inB_(d)],[k_(b,0)=0","AA b inB_(d)],[k_(b,t)^(st)+k_(b,t)^("end ") <= 1","AA t inT","AA b inB_(d)],[(T_(LB)+1)l_(b,t) <= k_(b,t)^(st)+T_(LB)-sum_(t^(')=t+1)^(t+T_(LB))k_(b,t^(')) <= (T_(LB)+1)],[quad-(1-l_(b,t))","AA t in{1,dots,|T|-T_(LB)}","quad AA b inB_(d)]:}\begin{aligned}
& \boldsymbol{k}_{b, t}-\boldsymbol{k}_{b, t-1}=\boldsymbol{k}_{b, t}^{s t}-\boldsymbol{k}_{b, t}^{e n d}, \forall t \in \mathcal{T}, \forall b \in \mathcal{B}_{d} \\
& \boldsymbol{k}_{b, 0}=0, \forall b \in \mathcal{B}_{d} \\
& \boldsymbol{k}_{b, t}^{s t}+\boldsymbol{k}_{b, t}^{\text {end }} \leq 1, \forall t \in \mathcal{T}, \forall b \in \mathcal{B}_{d} \\
& \left(T_{L B}+1\right) \boldsymbol{l}_{b, t} \leq \boldsymbol{k}_{b, t}^{s t}+T_{L B}-\sum_{t^{\prime}=t+1}^{t+T_{L B}} \boldsymbol{k}_{b, t^{\prime}} \leq\left(T_{L B}+1\right) \\
& \quad-\left(1-\boldsymbol{l}_{b, t}\right), \forall t \in\left\{1, \ldots,|\mathcal{T}|-T_{L B}\right\}, \quad \forall b \in \mathcal{B}_{d}
\end{aligned}