目前,国内大多数城市公交系统仍普遍采用调度规则简单、便于管理的单线路调度模式,即每条线路独立编制时刻表和调度计划,车辆在固定的线路上循环运行。然而,随着城市公交系统的不断发展,车线绑定的运营方式逐渐暴露出运营效率较低、服务灵活性不足等问题。相比传统的单线路调度模式,跨线调度允许车辆服务多条公交线路,实现车辆资源在不同线路之间的共享;联运调度通过车辆在换乘需求较高的联运线路上连续运营,能够为乘客提供更高效的出行服务。因此,通过跨线、联运等调度策略,实现对区域多线公交的整合调度优化,能够有效地提高公交系统的整体运营效率,改善服务水平。目前,对于公交乘客的换乘优化问题已有大量学者进行研究,旨在改进时刻表与行车计划,解决多模式交通接驳以及公交换乘衔接问题。周广汇等
[1 ] 针对城轨接运公交问题,构建了考虑客流流失与运能匹配的多目标模型,采用非支配排序遗传算法求解不均匀发车间隔方案,该方法相较于传统均匀发车模式,能有效地减少换乘等待时间并提升车辆满载率。蔡晶等
[2 ] 考虑共享电单车普及导致轨道交通接驳公交客流流失,构建了多视角的公交服务质量评价体系,并基于乘客满意度调查,结合随机森林、层次分析法及竞争性对比分析获取服务指标的重要度,通过逼近理想解排序法识别影响接驳公交吸引力的关键因素,旨在为公交运营提供精准的优化方向。梁晓辉等
[3 ] 研究相交公交线路在换乘站点出现乘客滞站问题,构建了以候车总时间、换乘等待时间及非换乘乘客候车时间最小化为目标的时刻表优化模型,该研究能显著提高相交线路的运营效率,减少换乘等待时间。对于采用公交联运解决乘客换乘问题的研究较为有限,仅有吕林剑等
[4 ] 构建了一个用于联运站点选取的数学模型,研究联运线路中联运站点的选取问题。相比之下,对于跨线调度的相关研究较为广泛,根据研究场景可分为两类,一类是单场站跨线调度问题,即对同一场站内车辆合理的调配,使车辆能够服务多条公交线路,另一类是多场站跨线调度问题,通过在场站之间插入空驶行程,实现车辆在不同线路之间的跨线运营,以满足车辆在多个场站、线路之间的调度需求。
在城市公交系统中,多条线路共用同一公交场站的场景较为常见。针对这一场景,单场站公交跨线调度问题也引起了一些学者的关注和研究。Zhao等
[5 ] 提出基于同场站多线路的区域协同调度模式,通过调整同场站内的多条公交线路的运力配置,实现时刻表、车辆、驾驶员等资源的共享,构建以最小化车辆与驾驶员成本为目标的调度优化模型,并设计了一种结合动态规划算法和禁忌搜索算法的混合算法,可以有效地解决单线调度中低峰车辆闲置与高峰运力不足的矛盾。Zahedi等
[6 ] 针对在同一枢纽站开始运营的多条公交线路,允许部分车辆在枢纽站内的多条线路之间进行共享,动态调配车队资源以缓解延误并提高服务可靠性。Bie等
[7 ] 基于存在共用公交场站以及充电设施的多线运营场景下,提出了一种多线路协调调度方法,车辆根据实际需求灵活调配至不同的线路运行,旨在最小化电动公交充电的平均排队时间、运营强度的差异以及充电成本。Teng等
[8 ] 提出了一种多线路公交调度模型,适用于共用同一首末站并共享车辆资源的多条公交线路,在多线路间集中分配公交车辆运行任务,尽量减少无效运行时间,能够有效地缩减公交车队规模。Delgado
[9 ] 研究多条公交线路在同一场站开始运营的场景下,车辆可以在不同线路之间调换运营,并为即将到达共同场站的车辆分配其服务线路及具体发车时刻,采用滚动时域策略来应对公交系统中的动态性和不确定性,以最小化实际发车间隔与计划发车间隔之间的偏差。
多场站跨线调度能够整合不同线路和场站的车辆资源,实现车辆灵活调配和高效利用。随着城市公交系统的复杂化,该调度问题也成为优化城市公共运营效率和提升服务质量的重要研究方向。翁剑成等
[10 ] 提出了基于客流特征的跨线调度线路组的识别规则和跨线车辆数的确定方法,能够整合优化现有公交资源配置,提高公交线路运力供需匹配程度和公交运营效率。Wang等
[11 ] 提出在城市范围内系统地利用跨线调度策略,构建了一个新颖且可推广的城市电动公交系统图论模型,并提出一种多项式时间算法,寻找以最少的电动公交车数量满足公共交通需求。姚恩建等
[12 ] 研究在多场站区域调度模式的场景下,考虑充电任务的发生和执行,以公交车辆成本和充电设施成本在内的总固定成本和总运营成本之和为优化目标,建立公交区域行车计划编制模型。Zhang等
[13 ] 研究多场站多车型电动公交调度问题,引入了部分混合线路策略和部分充电策略,并提出一种融合问题特异性机制的自适应大邻域搜索算法以实现对模型的高效求解,能够使多条公交线路以更具成本效益的方式运营。李欣等
[14 ] 针对行程时间波动环境下的公交车辆跨线调度问题,提出了公交多线协同跨线调度两阶段鲁棒优化模型,并构建了基于场景融合的分支定价算法进行求解,能够实现最终行车计划跨线班次多、车辆利用率高、用车成本低和准点率高的效果。Liu等
[15 ] 研究多场站公交调度问题,通过调整部分车次行程和允许车辆跨线运营,提出了一种基于行程调整策略的遗传算法,设计了一种包含3种交叉算子和7种变异算子的遗传算法,并引入行程调整策略,能够优化车辆数量和均衡车辆行程任务数。Wen等
[16 ] 针对多场站公交车辆调度问题,允许车辆在充电站进行部分充电或完全充电,以公交车队规模和总空驶里程最小化为优化目标,构建混合整数规划模型,并设计了一种具有多种破坏和修复算子的大邻域搜索算法,能够高效地求解该优化模型。Keshavarzian等
[17 ] 针对电动公交网络的车队规模优化问题,提出了一种基于图论的跨线调度模型,协同解决了车辆跨线与充电设施布局问题,并通过纽约、墨尔本等城市的公交网络数据验证了该方法在降低车队规模和优化充电计划方面的有效性。
综上所述,国内外学者针对公交跨线调度问题已开展了广泛且深入的研究,在模型构建与求解算法方面积累了丰富的经验。大量文献重点探讨了如何通过车辆跨线运营,实现车辆在不同线路之间的灵活调配,旨在提高公交系统的整体运营效率,降低运营成本。然而,很少有学者在跨线运营模式下,关注乘客在线路间的换乘优化问题,导致未能充分响应乘客的出行需求,影响公交系统的服务满意度。因此,现从跨线调度和联运调度相结合的角度出发,综合考虑公交公司运营成本和乘客的出行需求,对电动公交区域调度优化问题开展研究,以制定更加高效合理的公交运营方案。
1 问题描述
传统车线绑定的单线路运营方式易出现低峰运力闲置、高峰运力紧张的供需不匹配以及服务灵活性不足等问题,影响系统的整体运营效率以及服务质量。针对具有客流时空差异和换乘关系的多条线路(如进出城换乘衔接线路),提出跨线与联运的组合优化调度策略,从系统角度解决区域多线组合调度和换乘优化问题。跨线调度和联运调度策略分别如
图1(a) 和如
图1(b) 所示。
电动公交区域调度优化问题,是指在已知多条公交线路运营时刻表的基础之上,对各个公交场站的公交车辆进行合理的车次任务安排,确保车辆调度计划能够覆盖时刻表中的所有车次任务。公交车辆由发车场站经过中间一系列公交站点到达终点场站视为一个车次。每个车次包含4个要素:发车场站、发车时间、到达场站、到达时间。车辆每天由公交场站出发完成一系列车次任务,构成公交车辆一天的车次链。基于跨线与联运组合调度优化方法,在考虑时刻表、车次链等相关约束条件下,以公交运营成本最小化和发车间隔平滑性最大化为优化目标,建立双目标混合整数规划模型,并设计结合遗传算法与多目标粒子群算法的混合算法对优化模型进行求解。
2 模型构建
2.1 模型假设与符号定义
针对所建立的电动公交区域调度优化模型,做出以下基本假设:①以日为单位对车辆调度计划进行研究;②所有行程车次严格按照时刻表执行;③车辆首次执行任务处于满电状态;④不考虑公交车辆运行受天气、道路运行状况的影响。
模型涉及的相关集合、参数及变量的具体含义定义如下。
(1)集合定义。L 为公交线路集合,$\mathit{L}=\{\mathrm{1,2},\dots,\mathit{a},\mathit{b},\mathit{L}\}$ AB 为线路a 和线路b 联运构建的联运线路集合,$\mathit{a}\mathit{b}\in \mathit{A}\mathit{B},\mathit{a},\mathit{b}\in \mathit{L}$ K 为场站集合$\mathit{K}=\mathit{K}\mathit{\text{'}}\bigcup \mathit{K}″$ K' 为起点场站集合,K ″为终点场站集合,$\mathit{k}\in \mathit{K}$ V 为公交车辆合集,$\mathit{v}\in \mathit{V}$ I a a 在规划时间段的发出车次集合,$\mathit{i}\in {\mathit{I}}_{\mathit{a}}$ N a a 在规划时间段内的发车次数,$\{\mathit{i}=\mathrm{1,2},\dots,{\mathit{N}}_{\mathit{a}}\}$ D 为将运营时段以小时划分出的时段集合,$\mathit{d}\in \mathit{D}$ T 为运营时段内以最小时间间隔t 划分出的时段集合,$\mathit{t}\in \mathit{T}$
(2)参数定义。B 0 为电池额定容量,kW·h;c e t )为在时段t 的电价,元/kW·h;P 为充电桩充电功率,kW;C 1 为公交车辆单位空驶距离的成本,元/km;C t C r N y ${\mathit{t}}_{\mathit{v}}^{\mathit{c}}$ ${\mathit{t}}_{\mathit{i}}^{\mathit{a}}$ a 车次i 的行程时间,min;t ic i 结束场站到充电站的行驶时间,min;t cj j 开始场站的行驶时间,min;t vicj v 在车次i ,j 之间进行充电的充电时间;B ij i 结束场站到车次j 开始场站的电量消耗百分比;B ic i 结束场站到充电站电量消耗百分比;B cj j 车次开始场站的电量消耗百分比;D ij i 结束场站到车次j 开始场站之间的空驶距离,km;D ic i 结束场站到充电站的空驶距离,km;D cj j 开始场站的空驶距离,km;${\mathit{D}}_{\mathit{j}\mathit{k}}^{\mathit{v}}$ v 执行最后一个车次j 的结束场站到开始执行首个车次场站k 的空驶距离;t ij i 结束场站与车次j 开始场站之间的空驶时间,min;B i i 消耗的电量百分比;${\mathit{N}}_{\mathit{d}}^{\mathit{a}\mathit{b}}$ d 时段内联运线路ab 的联运车次数;N ab ab 的联运车次总数;k s i 、k e i i 的开始、结束场站;P b P t ${\mathit{T}}_{\mathit{d}}^{\mathit{a}}$ d 内线路a 的公交换乘系数;${\mathit{R}}_{\mathit{a}}^{\mathit{d}}$ d 内在线路a 上的出行乘客总数;${\mathit{N}}_{\mathit{d}}^{\mathit{a}}$ d 内线路a 的发车次数;${\mathit{R}}_{\mathit{d}}^{\mathit{a}\mathit{b}}$ d 内线路a 换乘到线路b 的乘客人数;${\mathit{R}}_{\mathit{d}}^{\mathit{a}\mathit{b}}/{\mathit{N}}_{\mathit{d}}^{\mathit{a}}$ d 内每车次由线路a 换乘到b 线路的平均换乘人数;${\mathit{N}}_{\mathit{d}}^{\mathit{a}\mathit{b}}$ d 内在a 线路和b 线路之间开通的最小联运车次数;T a a 预设的换乘系数阈值;[T s T f t 1 ,t 2 ]为构建联运车次连接的时间窗口;[T s d T e d d 的开始时间和结束时间;[B min B max $[{\mathit{H}}_{\mathit{m}\mathit{i}\mathit{n}}^{\mathit{a}},{\mathit{H}}_{\mathit{m}\mathit{a}\mathit{x}}^{\mathit{a}}]$ a 发车间隔范围约束。
(3)变量定义。${\mathit{x}}_{\mathit{i}}^{\mathit{a}}$ a 车次i 的发车时间,$\mathit{i}\in {\mathit{I}}_{\mathit{a}}$ B e i i 结束时的电量百分比;t vicj v 在车次i ,j 之间的充电时间,min;${\mathit{B}}_{\mathit{i}\mathit{j}}^{\mathit{c}\mathit{v}}$ v 在车次i ,j 之间进行充电的充电量;${\mathit{E}}_{\mathit{i}\mathit{j}}^{\mathit{c}\mathit{v}}$ v 在连续执行的车次i ,j 之间进行充电时等于1,否则等于0;${\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{1}$ a 车次i ,线路b 车次j 由车辆v 连续执行时等于1,否则等于0;${\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{2}$ i ,j )由公交车辆v 执行时等于1,否则等于0;q vit v 执行完车次i 后在充电事件的时段t 正在充电等于1,否则等于0;X vki v 从场站k 开始执行首个车次i 等于1,否则等于0;X vjk v 执行最后一个车次j 结束场站为k 时等于1,否则等于0;Z vjk v 执行的最后一个车次j 的结束场站与车辆v 执行首个车次i 开始场站k 不同,通过空驶返回场站k 时等于1,否则等于0;${\mathit{Z}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{\mathit{d}}$ d 内,线路b 车次j 的开始时间与线路a 车次i 的结束时间加上车次i 结束场站${{\mathit{k}}^{\mathit{e}}}_{\mathit{i}}({{\mathit{k}}^{\mathit{e}}}_{\mathit{i}}\in \mathit{K}\mathit{\text{'}})$ j 开始场站${{\mathit{k}}^{\mathit{s}}}_{\mathit{j}}({{\mathit{k}}^{\mathit{s}}}_{\mathit{j}}\in \mathit{K}\mathit{\text{'}})$
2.2 目标函数
从区域多线公交组合调度优化的角度出发,兼顾公交公司与乘客双方利益,以运营成本最小化与发车间隔平滑性最大化作为优化目标。
2.2.1 目标函数I:公交运营成本最小化
公交运营成本具体包括车辆使用成本Z 1 ,充电成本Z 2 ,空驶成本Z 3 ,具体公式可表示为
(1) $\mathit{m}\mathit{i}\mathit{n}\mathit{Z}={\mathit{Z}}_{1}+{\mathit{Z}}_{2}+{\mathit{Z}}_{3}$
(1)车辆使用成本。以时刻表中车次的发车时刻作为决策变量,构建二元辅助变量${\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{1}$ ${\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{2}$ i ,j 能否连接,即车次i ,j 能否由同一公交车辆完成。通过式(2)计算最大化车次链连接数。
(2) $\mathit{m}\mathit{a}\mathit{x}{\mathit{X}}_{\mathit{i}\mathit{j}}={\sum }_{\mathit{v}\in \mathit{V}}^{}{\sum }_{\mathit{a}\in \mathit{L}}^{}{\sum }_{\mathit{b}\in \mathit{L}}^{}{\sum }_{\mathit{i}\in {\mathit{I}}_{\mathit{a}}}^{}{\sum }_{\mathit{j}\in {\mathit{I}}_{\mathit{b}}}^{}({\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{1}+{\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{2})$
公交车辆数可由文献[
18 ]中的车队规模计算公式得到,即为了执行时刻表中所有车次行程,所需要的最小车辆数
N ,可以通过式(3)计算得到。
(3) $\begin{array}{c}\mathit{m}\mathit{i}\mathit{n}\mathit{N}={\sum }_{\mathit{a}\in \mathit{L}}^{}{\mathit{N}}_{\mathit{a}}-\mathit{m}\mathit{a}\mathit{x}{\mathit{X}}_{\mathit{i}\mathit{j}}\end{array}$
因此,车辆的使用成本可由式(4)表示为
(4) $\begin{array}{c}{\mathit{Z}}_{1}={\mathit{C}}_{\mathit{v}}\mathit{N}\end{array}$
式(4)中:C v
(5) $\begin{array}{c}{\mathit{C}}_{\mathit{v}}\end{array}=\frac{{\mathit{C}}_{\mathit{t}}-{\mathit{C}}_{\mathit{r}}}{365{\mathit{N}}_{\mathit{y}}}$
(2)车辆充电成本。
(6) $\begin{array}{c}{\mathit{Z}}_{2}={\sum }_{\mathit{v}\in \mathit{V}}^{}{\sum }_{\mathit{t}\in \mathit{T}}^{}{\sum }_{\mathit{a}\in \mathit{L}}^{}{\sum }_{\mathit{i}\in {\mathit{I}}_{\mathit{a}}}^{}{\mathit{c}}_{\mathit{e}}\left(\mathit{t}\right){\mathit{q}}_{\mathit{v}\mathit{i}\mathit{t}}\mathit{P}/60\end{array}$
(3)车辆空驶成本。
(7) $\begin{array}{l}{\mathit{Z}}_{3}={\mathit{C}}_{1}{\sum }_{\mathit{v}\in \mathit{V}}^{}{\sum }_{\mathit{a}\in \mathit{L}}^{}{\sum }_{\mathit{b}\in \mathit{L}}^{}{\sum }_{\mathit{i}\in {\mathit{I}}_{\mathit{a}}}^{}{\sum }_{\mathit{j}\in {\mathit{I}}_{\mathit{b}}}^{}{\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{1}\\ \left[\right(1-{\mathit{E}}_{\mathit{i}\mathit{j}}^{\mathit{c}\mathit{v}}){\mathit{D}}_{\mathit{i}\mathit{j}}+{\mathit{E}}_{\mathit{i}\mathit{j}}^{\mathit{c}\mathit{v}}({\mathit{D}}_{\mathit{i}\mathit{c}}+{\mathit{D}}_{\mathit{c}\mathit{j}}\left)\right]+\\ {\mathit{C}}_{1}{\sum }_{\mathit{k}\in \mathit{K}}^{}{\sum }_{\mathit{v}\in \mathit{V}}^{}{\sum }_{\mathit{b}\in \mathit{L}}^{}{\sum }_{\mathit{j}\in {\mathit{I}}_{\mathit{b}}}^{}{\mathit{Z}}_{\mathit{v}\mathit{j}\mathit{k}}{\mathit{D}}_{\mathit{j}\mathit{k}}^{\mathit{v}}\end{array}$
2.2.2 目标函数Ⅱ:发车间隔平滑性最大化
为了防止对发车时刻进行微调过程中,引发连续车次间的发车间隔出现较大扰动,导致发车间隔平滑性下降,以及联运车次的不均匀分布影响乘客的出行体验;以原线路和联运线路的发车间隔标准差之和来表示发车间隔平滑性,在保持原定发车频率的基础上,进一步优化发车间隔平滑性,使发车间隔变化保持相对平稳,并尽可能实现联运车次的均匀分布,具体计算公式可表示为
(8) $\begin{array}{c}\mathit{m}\mathit{i}\mathit{n}\mathit{T}={\mathit{T}}_{1}+{\mathit{T}}_{2}\end{array}$
(1)线路a 发车间隔标准差。
(9) $\begin{array}{c}{\mathit{T}}_{1}={\sum }_{\mathit{a}\in \mathit{L}}^{}\sqrt{\frac{1}{{\mathit{N}}_{\mathit{a}}-1}\sum _{\mathit{i}=1}^{{\mathit{N}}_{\mathit{a}}-1}({\mathit{d}}_{\mathit{a}}^{\mathit{i}}-{\overline{\mathit{d}}}_{\mathit{a}}{)}^{2}}\end{array}$
(10) $\begin{array}{c}{\mathit{d}}_{\mathit{a}}^{\mathit{i}}=({\mathit{x}}_{\mathit{i}+1}^{\mathit{a}}-{\mathit{x}}_{\mathit{i}}^{\mathit{a}}),\mathit{i}=\mathrm{1,2},\dots,{\mathit{N}}_{\mathit{a}}-1,\mathit{a}\in \mathit{L}\end{array}$
(11) $\begin{array}{c}{\overline{\mathit{d}}}_{\mathit{a}}=\sum _{\mathit{i}=1}^{{\mathit{N}}_{\mathit{a}}-1}\frac{1}{{\mathit{N}}_{\mathit{a}}-1}({\mathit{x}}_{\mathit{i}+1}^{\mathit{a}}-{\mathit{x}}_{\mathit{i}}^{\mathit{a}}),\mathit{a}\in \mathit{L}\end{array}$
式(9)表示线路a 连续车次之间的发车间隔标准差。式(10)表示线路a 连续车次之间的发车间隔计算。式(11)表示线路a 车次的平均发车间隔计算。
(2)联运线路ab 发车间隔标准差。
(12) ${\mathit{T}}_{2}={\sum }_{\mathit{a}\mathit{b}\in \mathit{A}\mathit{B}}^{}\sqrt{\frac{1}{{\mathit{N}}^{\mathit{a}\mathit{b}}-1}\sum _{\mathit{n}=1}^{{\mathit{N}}^{\mathit{a}\mathit{b}}-1}({\mathit{d}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{\mathit{n}}-{\overline{\mathit{d}}}_{\mathit{a}\mathit{b}}{)}^{2}}$
(13) $\begin{array}{l}{\mathit{d}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{\mathit{n}}={\mathit{X}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{\mathit{n}+1}-{\mathit{X}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{\mathit{n}},\mathit{ }\mathit{n}=\mathrm{1,2},\dots,{\mathit{N}}^{\mathit{a}\mathit{b}}-1,\\ \mathit{a}\mathit{b}\in \mathit{A}\mathit{B}\end{array}$
(14) $\begin{array}{l}{\overline{\mathit{d}}}_{\mathit{a}\mathit{b}}=\sum _{\mathit{n}=1}^{{\mathit{N}}^{\mathit{a}\mathit{b}}-1}\frac{1}{{\mathit{N}}^{\mathit{a}\mathit{b}}-1}({\mathit{X}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{\mathit{n}+1}-{\mathit{X}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{\mathit{n}}),\\ \mathit{a}\mathit{b}\in \mathit{A}\mathit{B}\end{array}$
式(12)表示联运线路ab 连续车次之间的发车间隔标准差。式(13)表示联运线路ab 相邻联运车次的发车间隔计算。式(14)表示联运线路ab 联运车次的平均发车间隔计算。
2.3 约束条件
模型构建需考虑时刻表、时间窗、车次链、车次连接、车辆充电等约束条件,具体公式表示如下。
2.3.1 时刻表约束
(15) $\begin{array}{c}{\mathit{T}}_{\mathit{s}}\le {\mathit{x}}_{\mathit{i}}^{\mathit{a}}\le {\mathit{T}}_{\mathit{f}},\forall \mathit{i}\in {\mathit{I}}_{\mathit{a}},\mathit{a}\in \mathit{L}\end{array}$
(16) $\begin{array}{c}{\mathit{T}}_{\mathit{s}}\le {\mathit{x}}_{\mathit{i}}^{\mathit{a}}+{\mathit{t}}_{\mathit{i}}^{\mathit{a}}\le {\mathit{T}}_{\mathit{f}},\forall \mathit{i}\in {\mathit{I}}_{\mathit{a}},\mathit{a}\in \mathit{L}\end{array}$
(17) $\begin{array}{c}\begin{array}{l}{\mathit{H}}_{\mathit{m}\mathit{i}\mathit{n}}^{\mathit{a}}\le {\mathit{x}}_{(\mathit{i}+1)}^{\mathit{a}}-{\mathit{x}}_{\mathit{i}}^{\mathit{a}}\le {\mathit{H}}_{\mathit{m}\mathit{a}\mathit{x}}^{\mathit{a}}\\ \mathit{i}=\mathrm{1,2},\dots,{\mathit{N}}_{\mathit{a}}-1,\mathit{a}\in \mathit{L}\end{array}\end{array}$
式(15)和式(16)保证所有线路车次的开始时间和结束时间都在规划时间段范围之内。式(17)保证每条公交线路连续车次的发车间隔在最小发车间隔和最大发车间隔约束范围之内。
2.3.2 时间窗约束
(18) $\begin{array}{l}{\mathit{Z}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{\mathit{d}}=\left\{\begin{array}{ll}1,& \mathit{ }{\mathit{t}}_{1}\le {\mathit{x}}_{\mathit{j}}^{\mathit{b}}-({\mathit{x}}_{\mathit{i}}^{\mathit{a}}+{\mathit{t}}_{\mathit{i}}^{\mathit{a}}+{\mathit{t}}_{\mathit{i}\mathit{j}})\le {\mathit{t}}_{2}\\ 0,& \mathrm{其}\mathrm{他}\end{array}\right.\\ \forall \mathit{a},\mathit{b}\in \mathit{L},\mathit{a}\ne \mathit{b},\mathit{i}\in {\mathit{I}}_{\mathit{a}},\mathit{j}\in {\mathit{I}}_{\mathit{b}},\mathit{d}\in \mathit{D}\end{array}$
(19) $\begin{array}{l}{\mathit{k}}_{\mathit{i}}^{\mathit{e}}\ne {\mathit{k}}_{\mathit{j}}^{\mathit{s}},{\mathit{Z}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{\mathit{d}}=1\mathit{ }\forall \mathit{a},\mathit{b}\in \mathit{L},\mathit{a}\ne \mathit{b},\mathit{i}\in {\mathit{I}}_{\mathit{a}},\\ \mathit{ }\mathit{ }\mathit{j}\in {\mathit{I}}_{\mathit{b}},{{\mathit{k}}^{\mathit{e}}}_{\mathit{i}},{{\mathit{k}}^{\mathit{s}}}_{\mathit{j}}\in \mathit{K}\mathit{\text{'}},\mathit{d}\in \mathit{D}\end{array}$
(20) $\begin{array}{l}{{\mathit{T}}^{\mathit{s}}}_{\mathit{d}}\le {\mathit{x}}_{\mathit{i}}^{\mathit{a}}\le {{\mathit{T}}^{\mathit{e}}}_{\mathit{d}},{\mathit{Z}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{\mathit{d}}=1\\ \mathit{ }\mathit{ }\forall \mathit{a},\mathit{b}\in \mathit{L},\mathit{a}\ne \mathit{b},\mathit{i}\in {\mathit{I}}_{\mathit{a}},\mathit{j}\in {\mathit{I}}_{\mathit{b}},\mathit{d}\in \mathit{D}\end{array}$
(21) ${\sum }_{\mathit{a}\in \mathit{L}}^{}{\sum }_{\mathit{i}\in {\mathit{I}}_{\mathit{a}}}^{}{\mathit{Z}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{\mathit{d}}\le 1,\forall \mathit{b}\in \mathit{L},\mathit{j}\in {\mathit{I}}_{\mathit{b}}$
(22) ${\sum }_{\mathit{b}\in \mathit{L}}^{}{\sum }_{\mathit{j}\in {\mathit{I}}_{\mathit{b}}}^{}{\mathit{Z}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{\mathit{d}}\le 1,\forall \mathit{a}\in \mathit{L},\mathit{i}\in {\mathit{I}}_{\mathit{a}}$
(23) $\begin{array}{l}{\sum }_{\mathit{a}\in \mathit{L}}^{}{\sum }_{\mathit{b}\in \mathit{L}}^{}{\sum }_{\mathit{i}\in {\mathit{I}}_{\mathit{a}}}^{}{\sum }_{\mathit{j}\in {\mathit{I}}_{\mathit{b}}}^{}{\mathit{Z}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{\mathit{d}}={\mathit{N}}_{\mathit{d}}^{\mathit{a}\mathit{b}}\\ \mathit{ }\mathit{ }\forall \mathit{a},\mathit{b}\in \mathit{L},\mathit{a}\ne \mathit{b},\mathit{a}\mathit{b}\in \mathit{A}\mathit{B},\mathit{d}\in \mathit{D}\end{array}$
(24) $\begin{array}{l}{\mathit{X}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{\mathit{n}}={\mathit{x}}_{\mathit{i}}^{\mathit{a}}{\mathit{Z}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{\mathit{d}}\mathit{ }\forall \mathit{a},\mathit{b}\in \mathit{L},\mathit{a}\ne \mathit{b},\mathit{i}\in {\mathit{I}}_{\mathit{a}},\\ \mathit{ }\mathit{ }\mathit{j}\in {\mathit{I}}_{\mathit{b}},\mathit{d}\in \mathit{D},\mathit{n}\in {\mathit{N}}^{\mathit{a}\mathit{b}}\end{array}$
式(18)和式(19)表示在时段d 内,车次j 的开始时间与车次i 的结束时间加上车次i 结束场站${{\mathit{k}}^{\mathit{e}}}_{\mathit{i}}({{\mathit{k}}^{\mathit{e}}}_{\mathit{i}}\in \mathit{K}\mathit{\text{'}})$ j 开始场站${{\mathit{k}}^{\mathit{s}}}_{\mathit{j}}({{\mathit{k}}^{\mathit{s}}}_{\mathit{j}}\in \mathit{K}\mathit{\text{'}})$ ${\mathit{Z}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{\mathit{d}}$ d 构建联运车次的发车时间,在各自时段d 的时间约束范围之内。式(21)和式(22)保证车次i 最多只能与一个车次j 构建联运车次。式(23)表示各个时段构建的联运车次数等于该时段规定的联运车次数。式(24)表示联运车次的发车时间,以构建联运车次的第一个车次i 作为该联运车次的发车时间。
2.3.3 联运车次数计算
(25) ${\mathit{T}}_{0}=\frac{{\mathit{P}}_{\mathit{b}}+{\mathit{P}}_{\mathit{t}}}{{\mathit{P}}_{\mathit{b}}}$
(26) $\begin{array}{l}{\mathit{T}}_{\mathit{d}}^{\mathit{a}}=\frac{{\mathit{R}}_{\mathit{a}}^{\mathit{d}}+{\mathit{R}}_{\mathit{d}}^{\mathit{a}\mathit{b}}-{\mathit{N}}_{\mathit{d}}^{\mathit{a}\mathit{b}}\frac{{\mathit{R}}_{\mathit{d}}^{\mathit{a}\mathit{b}}}{{\mathit{N}}_{\mathit{d}}^{\mathit{a}}}}{{\mathit{R}}_{\mathit{a}}^{\mathit{d}}}\le {\mathit{T}}_{\mathit{a}}\\ \mathit{ }\mathit{ }\mathit{a},\mathit{b}\in \mathit{L},\mathit{a}\ne \mathit{b},\mathit{a}\mathit{b}\in \mathit{A}\mathit{B},\mathit{d}\in \mathit{D}\end{array}$
式(25)表示公交换乘系数的计算公式,用来衡量公交乘客的直达出行效率。式(26)表示通过开通联运车次的方式增加该系统的直达出行乘客数量,使各个时段的公交换乘系数${\mathit{T}}_{\mathit{d}}^{\mathit{a}}\le {\mathit{T}}_{\mathit{a}}$ d 在联运线路a 和b 之间开通的最小联运车次数目${\mathit{N}}_{\mathit{d}}^{\mathit{a}\mathit{b}}$
2.3.4 车次链约束
(27) $\begin{array}{l}{\sum }_{\mathit{v}\in \mathit{V}}^{}{\sum }_{\mathit{a}\in \mathit{L}}^{}{\sum }_{\mathit{i}\in {\mathit{I}}_{\mathit{a}}}^{}({\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{1}+{\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{2})+{\sum }_{\mathit{v}\in \mathit{V}}^{}{\sum }_{\mathit{k}\in \mathit{K}}^{}{\mathit{X}}_{\mathit{v}\mathit{k}\mathit{j}}=1\\ \mathit{ }\mathit{ }\forall \mathit{b}\in \mathit{L},\mathit{j}\in {\mathit{I}}_{\mathit{b}}\end{array}$
(28) $\begin{array}{l}{\sum }_{\mathit{v}\in \mathit{V}}^{}{\sum }_{\mathit{b}\in \mathit{L}}^{}{\sum }_{\mathit{j}\in {\mathit{I}}_{\mathit{b}}}^{}({\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{1}+{\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{2})+{\sum }_{\mathit{v}\in \mathit{V}}^{}{\sum }_{\mathit{k}\in \mathit{K}}^{}({\mathit{X}}_{\mathit{v}\mathit{i}\mathit{k}}+{\mathit{Z}}_{\mathit{v}\mathit{i}\mathit{k}})=1\\ \mathit{ }\mathit{ }\forall \mathit{a}\in \mathit{L},\mathit{i}\in {\mathit{I}}_{\mathit{a}}\end{array}$
(29) $\begin{array}{l}{\sum }_{\mathit{a}\in \mathit{L}}^{}{\sum }_{\mathit{i}\in {\mathit{I}}_{\mathit{a}}}^{}({\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{1}+{\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{2})+{\sum }_{\mathit{k}\in \mathit{K}}^{}{\mathit{X}}_{\mathit{v}\mathit{k}\mathit{j}}=\\ \mathit{ }\mathit{ }{\sum }_{\mathit{a}\in \mathit{L}}^{}{\sum }_{\mathit{i}\in {\mathit{I}}_{\mathit{a}}}^{}({\mathit{Y}}_{\mathit{v}\mathit{b}\mathit{j}\mathit{a}\mathit{i}}^{1}+{\mathit{Y}}_{\mathit{v}\mathit{b}\mathit{j}\mathit{a}\mathit{i}}^{2})+{\sum }_{\mathit{k}\in \mathit{K}}^{}({\mathit{X}}_{\mathit{v}\mathit{j}\mathit{k}}+{\mathit{Z}}_{\mathit{v}\mathit{j}\mathit{k}})\\ \mathit{ }\mathit{ }\forall \mathit{b}\in \mathit{L},\mathit{j}\in {\mathit{I}}_{\mathit{b}},\mathit{v}\in \mathit{V}\end{array}$
(30) ${\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{1}+{\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{2}\le 1,\forall \mathit{a},\mathit{b}\in \mathit{L},\mathit{i}\in {\mathit{I}}_{\mathit{a}},\mathit{j}\in {\mathit{I}}_{\mathit{b}},\mathit{v}\in \mathit{V}$
(31) ${\sum }_{\mathit{a}\in \mathit{L}}^{}{\sum }_{\mathit{i}\in {\mathit{I}}_{\mathit{a}}}^{}{\mathit{X}}_{\mathit{v}\mathit{k}\mathit{i}}={\sum }_{\mathit{a}\in \mathit{L}}^{}{\sum }_{\mathit{j}\in {\mathit{I}}_{\mathit{a}}}^{}({\mathit{X}}_{\mathit{v}\mathit{j}\mathit{k}}+{\mathit{Z}}_{\mathit{v}\mathit{j}\mathit{k}}),\forall \mathit{v}\in \mathit{V},\mathit{k}\in \mathit{K}$
式(27)和式(28)保证所有线路的每个车次都被车辆执行一次。式(29)保证每个车次连接的节点流量守恒。式(30)保证车次之间只能建立一次车次连接。式(31)保证车辆执行完一系列行程后返回原场站。
2.3.5 车次连接约束
(32) $\begin{array}{l}{\mathit{T}}_{\mathit{i}\mathit{j}}=(1-{\mathit{E}}_{\mathit{i}\mathit{j}}^{\mathit{c}\mathit{v}})({\mathit{t}}_{\mathit{v}}^{\mathit{c}}+{\mathit{t}}_{\mathit{i}\mathit{j}})+{\mathit{E}}_{\mathit{i}\mathit{j}}^{\mathit{c}\mathit{v}}({\mathit{t}}_{\mathit{i}\mathit{c}}+{\mathit{t}}_{\mathit{v}\mathit{i}\mathit{c}\mathit{j}}+{\mathit{t}}_{\mathit{c}\mathit{j}})\\ \mathit{ }\mathit{ }\forall \mathit{a},\mathit{b}\in \mathit{L},\mathit{i}\in {\mathit{I}}_{\mathit{a}},\mathit{j}\in {\mathit{I}}_{\mathit{b}},\mathit{v}\in \mathit{V}\end{array}$
(33) $\begin{array}{l}{\mathit{x}}_{\mathit{j}}^{\mathit{b}}\ge {\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{1}({\mathit{x}}_{\mathit{i}}^{\mathit{a}}+{\mathit{t}}_{\mathit{i}}^{\mathit{a}}+{\mathit{T}}_{\mathit{i}\mathit{j}})\\ \mathit{ }\mathit{ }\forall \mathit{a},\mathit{b}\in \mathit{L},\mathit{i}\in {\mathit{I}}_{\mathit{a}},\mathit{j}\in {\mathit{I}}_{\mathit{b}},\mathit{v}\in \mathit{V}\end{array}$
(34) $\begin{array}{l}{\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{2}\ge {{\mathit{Z}}^{\mathit{d}}}_{\mathit{a}\mathit{i}\mathit{b}\mathit{j}}\\ \mathit{ }\mathit{ }\forall \mathit{a},\mathit{b}\in \mathit{L},\mathit{a}\ne \mathit{b},\mathit{i}\in {\mathit{I}}_{\mathit{a}},\mathit{j}\in {\mathit{I}}_{\mathit{b}},\mathit{v}\in \mathit{V},\mathit{d}\in \mathit{D}\end{array}$
(35) $\begin{array}{l}{\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{1}({\mathit{B}}_{\mathit{j}}+{\mathit{B}}_{\mathit{m}\mathit{i}\mathit{n}}+{\mathit{B}}_{\mathit{j}\mathit{c}})\le (1-{\mathit{E}}_{\mathit{i}\mathit{j}}^{\mathit{c}\mathit{v}})({{\mathit{B}}^{\mathit{e}}}_{\mathit{i}}-{\mathit{B}}_{\mathit{i}\mathit{j}})+\\ \mathit{ }\mathit{ }{\mathit{E}}_{\mathit{i}\mathit{j}}^{\mathit{c}\mathit{v}}({{\mathit{B}}^{\mathit{e}}}_{\mathit{i}}-{\mathit{B}}_{\mathit{i}\mathit{c}}+{\mathit{B}}_{\mathit{i}\mathit{j}}^{\mathit{c}\mathit{v}}-{\mathit{B}}_{\mathit{c}\mathit{j}})\\ \mathit{ }\mathit{ }\forall \mathit{a},\mathit{b}\in \mathit{L},\mathit{i}\in {\mathit{I}}_{\mathit{a}},\mathit{j}\in {\mathit{I}}_{\mathit{b}},\mathit{v}\in \mathit{V}\end{array}$
(36) $\begin{array}{l}{\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{2}({\mathit{B}}_{\mathit{j}}+{\mathit{B}}_{\mathit{m}\mathit{i}\mathit{n}}+{\mathit{B}}_{\mathit{j}\mathit{c}})\le {{\mathit{B}}^{\mathit{e}}}_{\mathit{i}}-{\mathit{B}}_{\mathit{i}\mathit{j}}\\ \mathit{ }\mathit{ }\forall \mathit{a},\mathit{b}\in \mathit{L},\mathit{i}\in {\mathit{I}}_{\mathit{a}},\mathit{j}\in {\mathit{I}}_{\mathit{b}},\mathit{v}\in \mathit{V}\end{array}$
(37) $\begin{array}{l}{\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{2},{\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{1}\in \left\{\mathrm{0,1}\right\}\\ \mathit{ }\mathit{ }\forall \mathit{a},\mathit{b}\in \mathit{L},\mathit{i}\in {\mathit{I}}_{\mathit{a}},\mathit{j}\in {\mathit{I}}_{\mathit{b}},\mathit{v}\in \mathit{V}\end{array}$
(38) ${\mathit{E}}_{\mathit{i}\mathit{j}}^{\mathit{c}\mathit{v}}\in \left\{\mathrm{0,1}\right\},\forall \mathit{a},\mathit{b}\in \mathit{L},\mathit{i}\in {\mathit{I}}_{\mathit{a}},\mathit{j}\in {\mathit{I}}_{\mathit{b}},\mathit{v}\in \mathit{V}$
式(32)表示车次连接之间的时间计算。式(33)保证车次连接的时间能够满足约束。式(34)保证满足时间窗的联运车次都能够被车辆执行。式(35)保证车辆执行车次连接时满足电量要求。式(36)保证车辆执行联运车次时,车辆的电量能够满足运营要求。式(37)规定了二元变量${\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{1}$ ${\mathit{Y}}_{\mathit{v}\mathit{a}\mathit{i}\mathit{b}\mathit{j}}^{2}$ i ,j 由公交车辆v 连续执行时等于1,否则等于0。式(38)规定了二元变量${\mathit{E}}_{\mathit{i}\mathit{j}}^{\mathit{c}\mathit{v}}$ v 在执行的车次i ,j 之间充电等于1,否则等于0。
2.3.6 车辆充电约束
(39) $\begin{array}{l}{\mathit{t}}_{\mathit{v}\mathit{i}\mathit{c}\mathit{j}}\ge {\mathit{t}}_{\mathit{m}\mathit{i}\mathit{n}}^{\mathit{c}}{\mathit{E}}_{\mathit{i}\mathit{j}}^{\mathit{c}\mathit{v}}\\ \mathit{ }\mathit{ }\forall \mathit{a},\mathit{b}\in \mathit{L},\mathit{a}\ne \mathit{b},\mathit{i}\in {\mathit{I}}_{\mathit{a}},\mathit{j}\in {\mathit{I}}_{\mathit{b}},\mathit{v}\in \mathit{V}\end{array}$
(40) $\begin{array}{l}{\mathit{E}}_{\mathit{i}\mathit{j}}^{\mathit{c}\mathit{v}}{\mathit{t}}_{\mathit{v}\mathit{i}\mathit{c}\mathit{j}}\le \frac{{\mathit{B}}_{0}[{\mathit{B}}_{\mathit{m}\mathit{a}\mathit{x}}-({\mathit{B}}_{\mathit{i}}^{\mathit{e}}-{\mathit{B}}_{\mathit{i}\mathit{c}}\left)\right]}{\mathit{P}}\times 60\\ \mathit{ }\mathit{ }\forall \mathit{a},\mathit{b}\in \mathit{L},\mathit{a}\ne \mathit{b},\mathit{i}\in {\mathit{I}}_{\mathit{a}},\mathit{j}\in {\mathit{I}}_{\mathit{b}},\mathit{v}\in \mathit{V}\end{array}$
(41) ${\mathit{B}}_{\mathit{i}\mathit{j}}^{\mathit{c}\mathit{v}}={\mathit{E}}_{\mathit{i}\mathit{j}}^{\mathit{c}\mathit{v}}\frac{{\mathit{t}}_{\mathit{v}\mathit{i}\mathit{c}\mathit{j}}\mathit{P}}{60{\mathit{B}}_{0}},\forall \mathit{a},\mathit{b}\in \mathit{L},\mathit{i}\in {\mathit{I}}_{\mathit{a}},\mathit{j}\in {\mathit{I}}_{\mathit{b}},\mathit{v}\in \mathit{V}$
式(39)和式(40)保证公交车辆的充电时间在最小充电时长和最大充电时长约束范围之内。式(41)表示车辆v 在车次(i ,j )之间进行充电的充电量百分比计算。
3 求解算法
区域公交调度问题属于NP-hard问题,适合采用启发式算法进行求解。结合遗传算法(GA)的交叉、变异机制与多目标粒子群算法(MOPSO)构建混合算法(MOPSO-GA)建立模型进行求解。该算法的主要步骤及流程如下。
3.1 粒子编码方式
构建初始解时,首先对粒子进行编码,由于线路车次的发车时刻调整量为整数,因此对粒子采用整数编码的方式。对规划时段内的所有线路车次行程的发车时刻根据式(15)~式(26)的相关约束条件生成一组时刻表粒子,生成的时刻表粒子作为初始解生成的输入。具体编码方式如
图2 所示。
3.2 初始解生成
采用启发式算法求解公交车辆调度模型首先生成初始解,基于贪婪算法中的贪婪策略生成初始解,具体流程如下。
步骤1 数据输入与参数设置。输入基础数据、相关参数,根据初始发车时刻表确定决策变量个数,并根据式(15)~式(26)生成时刻表粒子编码,初始化车次任务集合。
步骤2 初始化发车时刻,更新车次任务集合。根据步骤1生成的时刻表粒子编码,合并构建联运车次的车次对,将构建的联运车次加入车次集合中,删除构建联运车次的原始车次编号,并计算发车时刻调整后的发车时刻表,更新车次任务集合。如果该解没有构建满足每个时段规定数量的联运车次数,则对该解记录惩罚。
步骤3 车次链生成。
步骤3.1 从更新后的车次任务集合中,选择最早可出发的车次任务作为当前车辆(编号n )的起始任务,同时记录该车辆的车型信息和初始电池状态。
步骤3.2 当车辆完成当前车次任务后,更新车辆的位置、到达时间和剩余电量,根据当前任务结束后车辆的位置和时间,寻找满足下一车次连接时间要求的候选任务,检查候选任务对应的衔接行程是否在车辆剩余电量的允许范围内,确定出满足连接约束的可选任务集合。
步骤3.3 从可连接任务集合中,选择发车时间最早的车次任务作为当前车辆的下一任务,更新车辆的状态(位置、到达时间、电池电量),返回步骤3.2继续衔接后续任务。
步骤3.4 如果当前车辆的电池状态不足以支持直接执行下一任务,则安排车辆前往最近的充电站进行充电,并更新车辆位置、充电结束时间和充电后的剩余电量,返回步骤3.2继续寻找后续可连接任务。
步骤3.5 当检查后发现不存在既满足连接时间要求又满足电量约束的后续任务时,结束当前车辆的调度,并记录该车辆完成的车次任务链。
步骤3.6 检查所有的车次任务是否都被执行,如果没有,则继续安排车辆(n +1)返回步骤3.1,如果所有车次任务已全部分配,则初始解构造完成。
步骤4 输出初始解。
3.3 MOPSO-GA算法
在MOPSO算法负责全局搜索的基础之上,结合GA算法的交叉、变异操作以提高解集多样性,设计了MOPSO-GA混合算法,该混合算法(MOPSO-GA)的具体流程如
图3 所示。
4 案例分析
4.1 案例介绍
选取北京市57路、322路、455路3条公交线路为实例分析对象,3条公交线路存在一个共用的公交场站,公交线路位置分布如
图4 所示。
采用北京市2021年12月20日客流数据。公交运营数据、分时电价等数据从百度地图以及多个网站获取。3条公交线路中322、455与57线路之间存在客流换乘需求,并且线路运营高峰时间具有一定的差异。所有线路一天总计580个运营车次,其中57路运营车次244个,322路运营车次186个,455路运营车次150个。3条公交线路分别使用不同型号的电动公交车辆,其中57路使用车型为纯电动公交车广通GTQ6131BEVST3,电池额定容量为138.5 kW·h;322路使用车型为纯电动公交车广通GTQ6121BEVBT3,电池额定容量为104.4 kW·h;455路使用车型为纯电动公交车广通GTQ6121BEVBT21,电池额定容量为116.0 kW·h。各时段电价如
表1 所示,3条公交线路运营基本信息如
表2 所示,联运信息如
表3 所示,参照文献[
19 ]和相关官网数据设定相关参数如
表4 所示。
4.2 结果分析
设计实验在Intel Core i5-10200H CPU @2.40GHz处理器、RAM 16GB内存的计算机上运行,基于MATLAB语言在MATLABR2022a上编译运行。设置算法的初始种群数量为50,最大迭代次数为400,惯性权重为(0.8,0.2),交叉概率为0.8,变异概率为0.1,各线路独立运营方案和帕累托解优化方案结果对比如
表5 所示。
如
表5 所示,方案E
0 为各线路独立运营下的车辆调度方案,方案E
1 ~E
5 为优化运营方案,5个方案在公交运营成本和发车间隔平滑性上均有不同程度的优化效果,表明所提出的跨线与联运的组合调度方法能够有效提高公交系统的运营效率以及服务质量。其中方案E
1 对公交运营成本
Z 的优化程度最大,降低了12.43%,在发车间隔平滑性上提高了7.95%,方案E
5 对线路发车间隔平滑性的优化效果最大,提高了11.27%,在公交运营成本上降低了9.31%。
以方案E3 为例,对各个优化目标进行分析,其中3条公交线路的总公交运营成本Z 降低了11.18%,车辆使用成本降低了17.86%,充电成本降低了2.98%,空驶成本提高了28.78%,发车间隔平滑性T 提高了10.07%,原线路发车间隔平滑性T 1 提高了12.33%,车队规模N 减少10辆。表明,在跨线与联运的组合调度方法下,对总公交运营成本的优化中,主要能够优化公交系统的车队规模,降低车辆使用成本,对于充电成本的优化效果较为有限,随着公交车辆的跨线运营造成空驶成本出现了一定的上升。同时,对线路发车间隔平滑性也有一定的优化效果,对原线路的发车间隔平滑性有着明显的提升,进一步改善了乘客的出行体验。联运线路的发车间隔平滑性为0.47,表明联运线路构建的联运车次在时间上的分布较为均匀,能够为乘客提供更高质量的出行服务。
方案E
3 的跨线联运调度甘特图如
图5 所示,使用车辆数为46辆,所有车辆产生的跨线次数为206次,每辆车平均跨线运营4.48次,联运车次数为7次,每个车辆平均执行12.61个车次任务。方案E
3 与各线独立运营调度计划的相关数据对比如
表6 所示,公交车辆执行车次任务的平均运营时间增加了1.84 h,车辆在车次间的平均空闲时间减少了0.67 h,车辆执行的车次任务的最短时间和最长时间都有一定的提高,充电时间和空驶时间由于车辆数量的减少和车辆跨线运营有所增加。表明方案E
3 的车辆调度计划,能够减少车辆的空闲时间,提高公交车辆的运营效率,以减少满足运营所需的车辆数。
4.3 算法参数分析
设计的混合算法(MOPSO-GA)涉及多个参数,设置合适的参数能够有效提高算法的求解效率和质量,因此对算法中涉及的种群数量、迭代次数、粒子惯性权重、粒子加速系数以及变异概率和交叉概率等6个参数进行分析,其中粒子个体加速系数和全局最优加速系数设为定值1.5,4个方案参数设置如
表7 所示。
本文算法参数共设置4组参数进行算法分析,测试结果如
图6 所示。
由
图6 测试4个参数方案得到的帕累托解集可知。通过对比方案1和方案2,在同样增加种群规模和迭代次数的情况下,方案2的求解效果更优,进而确定算法的种群数量和迭代次数,由于设计的混合算法(MOPSO-GA)结合遗传算法作为子算法,能够进一步增加种群的多样性,故后续方案不再进一步增加种群数量进行分析。方案2和方案3测试不同惯性权重下求得的帕累托最优解对比,结果显示方案3的求解效果更好,能够确定多目标粒子群算法惯性权重的设置参数。最后对遗传算法的交叉概率和变异概率参数进行分析,通过方案3和方案4运行得到的帕累托最优解对比,可得方案4在两个目标的求解质量上均优于方案3,故最终本文选择方案4设定的参数对建立的模型进行求解。
4.4 算法求解效率与效果对比
针对传统多目标粒子群算法(MOPSO)易陷入局部最优的局限,构建了融合遗传算子的混合算法(MOPSO-GA),旨在利用交叉与变异机制降低早熟收敛风险。为验证改进效果,设置相同的算法参数,对两种算法分别进行了10次独立重复试验以消除随机性影响,算法性能比对如
表8 所示。
由
表8 可知,传统MOPSO算法的平均运行时间为401 s,而MOPSO-GA算法的平均运行时间为441 s,这主要由于算法中嵌入的遗传算子,增加了单次迭代的计算复杂度。虽然,改进的算法运行时间增加了约9.97%,但441 s的求解时间仍在可接受范围内。在求解质量方面,MOPSO-GA算法的平均超体积值相较于传统的MOPSO算法提升13.69%。表明,MOPSO-GA算法得到的帕累托解集在收敛性和多样性上均优于MOPSO算法。这意味着改进的算法能够有效避免陷入局部最优,探索到更广阔的解空间,提供更高质量的求解方案。改进前后算法的帕累托解详细对比如
表9 所示。
由
表9 可知,所设计的混合算法相比于传统的多目标粒子群算法的求解效果更优,在公交运营成本和发车间隔平滑性两个目标的求解效果上,均有不同程度的优化提升。以方案E
3 为例,混合算法求解模型得到的公交运营成本
Z 降低了11.18%,发车间隔平滑性提高了10.07%,多目标粒子群算法求解得到的公交运营成本
Z 降低了9.51%,发车间隔平滑性提高了7.22%。混合算法(MOPSO-GA)相比于多目标粒子群算法(MOPSO),在公交运营成本上的优化效果提升了1.67%,在发车间隔平滑的优化效果上提高了2.85%,表明所设计的混合算法能够提供更高质量的解,为公交公司提供更高效的车辆调度方案。
4.5 灵敏度分析
4.5.1 电量安全范围参数分析
电池电量安全范围是影响公交运营效率与电池寿命的关键参数,其上下限阈值的设定影响公交车辆的有效续航以及充电计划,进而影响调度系统的整体表现。因此,对电池电量安全范围进行灵敏度分析,以探究不同阈值设置对运营系统的具体影响。
电量安全范围共设置4组参数如
图7 所示。由不同电量安全范围参数运行得到的帕累托解集可知,相比方案3设置的电池电量安全范围,方案4的公交运营成本出现明显的上升,而方案2的公交运营成本出现了一定的下降。进一步降低下限阈值时,设置方案1的参数为(10%,90%),运营成本出现小幅度下降。故随着电量安全范围阈值下限的提高和上限的降低,公交运营成本有着不同程度的增加。因此,降低电池电量安全范围下限以及提高上限阈值,能够在一定程度上提高公交车辆的利用率,进而降低公交运营成本。但同时应考虑到电池电量安全范围对电池退化程度和使用寿命的影响,公交公司应结合实际的运营条件,在方案1和方案3的参数之间设置电量安全范围参数阈值。
4.5.2 联运车次数输入分析
设置一定的联运车次数在一定程度上能够增加公交系统中的直达乘客,提高乘客的出行效率。考虑到乘客的出行需求不断提高,以及进一步提高公交系统的服务水平,对联运线路每个时段设置的联运车次数进行灵敏度分析。共设置3组联运车次数,输入方案如
表10 所示。
由
表11 中输入不同联运车次数的3个方案所得到的帕累托解集可知,随着联运车次数的增加,公交运营成本出现了一定的上升。而联运线路的发车间隔平滑性受到较大的影响,出现明显的下降。由于联运车次分别由联运线路中的两个车次构成,随着联运车次数的增加,联运车次分布的均匀性受到较大的影响。因此,公交公司在实际运营中,应在提高服务质量与控制运营成本之间进行权衡,既要考虑联运线路高峰时间段乘客的换乘需求,也要考虑到联运车次的均匀分布性下降以及公交运营成本的小幅度增加。
4.5.3 车次连接准备时间参数分析
本文研究的跨线调度问题,涉及公交车辆在不同公交线路之间的跨线运营,需要考虑到公交车辆在连续执行不同线路之间的车次任务时,车辆更改电显、报站信息等操作。因此进一步对车次连接准备时间进行灵敏度分析,设置8、12和15 min共3个方案进行对比求解,得到的帕累托解集如
图8 所示。公交运营成本随着车次连接准备时间的增加而不断上升,当设置为15 min时,车队规模和运营成本出现较为明显的上升。在公交运营过程中,准备时间过长会导致车辆利用率下降,造成公交系统运营成本的上升,而过短的准备时间则可能无法保障必要的运营准备工作,影响运行效率与服务质量。因此,在实际运营过程中,应根据实际的调度状况和运营条件,将车次连接准备时间设置在12 min之内,在保障公交服务质量的同时,避免设定较长的车次连接准备时间参数,影响系统整体的运营效率。
5 结论
(1)针对具有客流时空差异和换乘关系的区域多条公交线路,提出跨线与联运组合调度优化方法,研究电动公交区域调度优化问题,建立混合整数规划模型,并设计混合算法(MOPSO-GA)对模型进行求解,最后以北京市的3条公交线路为实例分析对象,验证本文模型以及算法的可行性。优化结果表明,在组合调度优化方法下,得到的区域公交调度计划,相比于车线绑定的单线路调度方式,在公交运营成本上降低了11.18%,线路发车间隔平滑性提高了10.07%,原线路发车间隔平滑性提高了12.33%,公交车队规模减少了17.85%。表明,所提供的区域公交调度计划能够整合现有公交资源并提高车辆的利用率,优化系统的整体运营效率,同时能够提高公交系统的服务灵活性以及服务质量,为乘客提供更高效的出行服务。
(2)设计的混合算法(MOPSO-GA)在保留多目标粒子群算法全局搜索优势的基础上,引入了遗传算法的交叉和变异操作,增加局部搜索的随机性和种群的多样性,以提高算法的求解质量。通过对比混合算法(MOPSO-GA)与单一的多目标粒子群算法(MOPSO)的求解效果,结果表明,相比传统的多目标粒子群算法,该混合算法能够进一步提高求解的质量,提供更高效的公交车辆调度计划。
PDF
(7288KB)
