动力能源差异下混合公交车队调度方案生成方法

摘要

为了实现电动公交与燃油公交混合车队运营调度优化，提出了一种平衡电动公交与燃油公交环境成本和经济成本的混合公交车队调度方法。首先结合不同动力能源公交车辆的运行特性给定约束条件，将碳排放和分时电价融入电动公交和燃油公交运营能耗及成本分析中；然后考虑混合公交运营系统的经济成本与环境成本，建立综合运营成本最小化模型；最后提出基于嵌套禁忌搜索的改进遗传算法对所建模型进行求解，该算法不仅弥补了传统遗传算法收敛过早、易陷入局部最优解的缺陷，而且提高了模型求解的质量与精度。以云南省文山州1路公交运营数据为例对本研究所提出的模型和算法进行验证。结果表明，基于嵌套禁忌搜索的改进遗传算法相较于传统遗传算法求解精度提高了12%左右，并且生成的调度方案能够在减少碳排放和提高车辆利用率中取得最佳平衡，有效降低了综合运营成本，实现了电动公交与电价错峰执行任务的效果，为平稳实现公交车队“电动化”提供了绿色高效可靠的调度方法。

关键词

交通规划; 混合公交车队; 智能公交调度; 碳排放; 禁忌搜索遗传算法

新能源汽车在公交领域得到了逐步推广，但是在短时间内很难迅速实现公交系统的全面“电气化”，燃油公交与电动公交的混合运行仍将普遍存在。不同类型的公交车辆动力特性、能源类别和消耗特征存在巨大差异。当前，大多数燃油公交的续驶里程能够满足一天的运营要求，但以燃油为动力能源的公交车辆，在运行过程会产生大量的碳排放，环境污染严重；而电动公交车辆虽然使用清洁能源，但由于电池容量限制，车辆需在运营期间多次充电，空驶里程增多，需配置更多的车辆来满足服务需求，致使运营经济成本提高。因此在混合车队运营环境下，如何平衡燃油公交的碳排放成本与电动公交的经济成本成为公交行业管理者亟需解决的问题。

本研究的重心在于混合公交车队组成和车辆调度问题。当前，对于混合公交车队车辆配置问题研究较多，Santos等^［1］和Li等^［2］以电动车辆购置成本和运营收入盈亏平衡为基础，提出了混合公交车队配置优化方法。Grijalva等^［3］从二氧化碳排放的角度分析了电动公交取代传统燃油公交后对环境的改善作用。Teng等^［4］在管理公交车队时，通过寻求最佳替代车辆数取代传统燃油公交车，实现碳排放的降低。以上对混合公交车队调度的研究止步于车队组成管理，事实上车队组成管理是混合公交调度方案生成的前提，因此对于车辆配置的研究不仅要考虑路线运行参数的约束，还要在后续调度方案研究中综合考虑经济成本和环境成本对车辆配置优化的影响。而与混合公交车队调度方案生成相关的研究具有以下顺承关系：基于传统公交车队调度方法对给定车队进行调度优化是混合公交车队调度研究的基础，大多以车队规模最小或运营成本最小为优化目标，并未将燃油公交产生的碳排放纳入到运营成本中^［5-7］。随后，相关研究者将车辆配置纳入考虑，Paul等^［8］将电动公交总运营里程最大作为电动公交和柴油公交运行计划生成目标，但忽略了电动公交电池容量限制所带来的空驶里程增加等方面的问题。之后在纯电动公交车队的调度研究引入充电因素，Wang等^［9］和Hall等^［10］研究不同充电技术对纯电动公交运行计划的影响，建立以充电成本最小为目标的优化模型，将其作为线性规划问题求解生成调度方案。孟越^［11］和高佳宁^［12］在调度模型中重点考虑电动公交的续航里程和充电时间约束，基于遗传算法得到运营成本最小的行车计划。Dreier等^［13］构造了特定线路和特定时间的驾驶情景，设计降低能耗的插电式混合动力双铰接公交车队的充电调度优化策略。随着充电因素的引入，部分学者在进行混合公交车队调度时进一步考虑车队配置与充电方式之间的关系，Li等^［14］和Rinaldi等^［15］在电动公交日间充电约束下，应用整数线性规划方法生成运营经济成本最小的混合公交车队调度方案。根据已有公交车队调度方面的研究可知，混合公交车队由于车辆类型配置差异，致使不同类型公交车辆在运行过程中表现出不同的经济成本和环境成本倾向性，但混合公交车队调度研究在建立优化模型时，更侧重电动公交的经济效益，对环境成本未给予重视。针对当前混合公交车队调度研究中未同时考虑经济成本和环境成本对系统运营所造成的影响等问题，在此将环境成本和经济成本同时考虑在内作为混合公交车队调度方案的目标函数，以期实现混合公交车队调度方案在提高车辆利用率的同时，降低运营成本和碳排放，从而解决混合车队调度过程中因单纯追求经济优势导致碳排放增加与单纯追求环保优势而降低经济效益之间的矛盾。

以碳排放权交易管理办法的实施为契机，本研究针对混合公交车队的运营调度，量化电动公交的减排效益，考虑燃油公交的碳排放成本和电动公交的空载成本，建立综合运营成本最小化模型，并设计嵌套禁忌搜索的改进遗传算法进行求解，以确定混合公交车队的最优车队组成和生成相应的调度方案，在减少碳排放的同时最大限度地保持经济优势。

1 模型建立

1.1　问题描述

公交车辆调度中关键问题之一是合理编排车辆执行公交时刻表的车次任务顺序。本研究的主要研究对象为固定线路下的混合公交车队，其调度问题可表述为：针对固定公交线路下的混合车队运行，根据场站和线路信息来编制公交车次表。电动公交车辆集合$E=\left\{k\left|k=\mathrm{1,2},\cdots ,K\right.\right\}$和燃油公交车辆集合$O=\left\{h\left|h=\mathrm{1,2},\cdots ,H\right.\right\}$共同构成场站储备公交车辆，如图1所示，其中$k$为电动公交车辆编号，$K$为公交车队中电动公交车辆的总数；$h$为燃油公交车辆编号，$H$为公交车队中燃油公交车辆的总数。根据给定的公交时刻表，从电动公交车辆集合$E$和燃油公交车辆集合$O$中选择车辆执行时刻表中的车次$i$，$N$为一天内公交行车计划的总车次数。

图1 混合公交车队配车模式

Fig.1 Allocation model of mixed bus fleet

虽然电动公交运行过程中不产生尾气污染，随着更多的燃油公交被电动公交所取代，电动公交的购买投资及燃油公交旧车处理致使财政投入明显增加，并且电动公交往返场站充电将带来车队总空驶里程的增加。在此需对公交场站储备集合中的车辆类型和数量配置进行讨论，从而为运营车队是否需要进一步增加电动公交代替燃油公交提供决策参考，这也是生成公交行车计划的重要前提。一味增加电动公交车辆的数量极有可能导致运营成本的大幅增加，因此通过管理方式合理安排混合车队不同时段的运营方案，使现有车队取得更大运营效益是非常必要的。混合公交车队调度需要解决以下两个问题：①在车队组成方面，每种类型的车辆占比，即确定K和H的值；②在车队运行方面，各车辆类型应执行的车次，即确定执行车次i的车辆类型。

本研究的混合公交车队调度问题将基于以下假设展开：

（1）公交场站配备足够数量的慢充充电桩，各公交站台未配备充电设施，电动公交在储能量低于设定值时需返回场站进行充电，充满后重新投入运营。

（2）为保证电动公交的正常运营，电动公交在执行车次作业期间不返回场站充电。

（3）公交线路运营速度稳定。

本研究混合公交车队调度模型的相关符号如表1所示。

表1 模型参数定义

Tab.1 Definition of model parameter

描述对象	符号	解释
公交线路	$T$	线路运营时段，为车次的执行时间序列
	$N$	一天线路车次总数，由线路运营时段和线路发车间隔决定
	$t_{\mathrm{i}\mathrm{n}\mathrm{t}}$	线路发车间隔，min
	$K$	电动公交车辆总数，辆
	$H$	燃油公交车辆总数，辆
	$k$	电动公交车辆编号，$k\in \left\{\mathrm{1,2},\cdots ,H\right\}$
	$h$	燃油公交车辆编号，$h\in \left\{\mathrm{1,2},\cdots ,H\right\}$
	$K_{\mathrm{m}\mathrm{a}\mathrm{x}}$	公交车队车辆全为电动公交时，线路运营最少需要的电动公交数量，辆
	$H_{\mathrm{m}\mathrm{a}\mathrm{x}}$	公交车队车辆全为燃油公交时，线路运营最少需要的电动公交数量，辆
	$J$	公交车辆总数，$J=K+H$，辆
	$l_{\mathrm{L}}$	线路长度，km
	$l_{\mathrm{S}}$	场站与始发站的距离，又称空驶距离，km
	$v$	线路平均运营速度，km·h-1
车队车辆	$w$	电动公交的政策偏向系数，一般令$w\le 0.5$
	$l_j$	第$j$辆公交的行驶里程，km
	$R_0$	公交车辆的预计净残值率，用于计算公交的使用成本
	$\begin{array}{ccc}{M}_{\mathrm{o}}& ,& M_{\mathrm{e}}\end{array}$	分别为燃油公交和电动公交的总成本，元
	$\begin{array}{ccc}{M}_{\mathrm{o},1}& ,& M_{\mathrm{e},1}\end{array}$	分别为燃油公交和电动公交的使用成本，元
	$\begin{array}{ccc}{M}_{\mathrm{o},2}& ,& M_{\mathrm{e},2}\end{array}$	分别为燃油公交和电动公交的能耗成本，元
	$\begin{array}{ccc}{M}_{\mathrm{o},3}& ,& M_{\mathrm{e},3}\end{array}$	分别为燃油公交的碳排放成本和电动公交的碳排放成本，元；$M_{\mathrm{e},3}$<0，$\left|M_{\mathrm{e},3}\right|$表示电动公交的减排效益
	$\begin{array}{ccc}{m}_{\mathrm{o}}& ,& m_{\mathrm{e}}\end{array}$	分别为燃油公交和电动公交的车辆购买成本，元
	$\begin{array}{ccc}{d}_{\mathrm{o}}& ,& d_{\mathrm{e}}\end{array}$	分别为燃油公交和电动公交的预计行驶里程总数，km
	$\begin{array}{ccc}{E}_{\mathrm{o}}& ,& E_{\mathrm{e}}\end{array}$	$E_{\mathrm{o}}$为燃油公交燃油消耗量，L；$E_{\mathrm{e}}$为电动公交电能消耗量，kWh
	$\begin{array}{ccc}{q}_{\mathrm{o}}& ,& q_{\mathrm{e}}\end{array}$	$q_{\mathrm{o}}$为燃油公交单位里程的耗油量，L·（veh·km）-1；$q_{\mathrm{e}}$为电动公交单位里程的耗电量，kWh·（veh·km）-1
	$\begin{array}{ccc}{P}_{\mathrm{o}}& ,& P_{\mathrm{e}}\end{array}$	$P_{\mathrm{o}}$为燃油单位成本，元·L-1；$P_{\mathrm{e}}$为电能单位成本，元·kWh-1
	$F_{\mathrm{o}}$	燃油公交消耗单位燃油产生的碳排放，kg·L-1
	$\gamma$	碳排放成本转化系数，由碳交易的成交额确定，元·kg-1
	$U_{\mathrm{e}}$	电动公交最大储能量，kWh
	$U_{\mathrm{r}}$	电动公交运营期间的实际储能量，kWh
	$\theta$	电动公交电池电量约束，0‒1变量，0表示不需要充电，1表示需要充电
	$\epsilon$	电动公交单位时间充电量，kWh·min-1
	$t_{\mathrm{c}\mathrm{h}}$	电动公交的充电时间，min
调度方案	$i$	运行车次编号，$i\in \left\{\mathrm{1,2},\cdots ,N\right\}$
	$j$	公交车队中车辆编号，$j\in \left\{\mathrm{1,2},\cdots ,J\right\}$
	$x_j$	第$j$辆公交的车辆类型，0‒1变量，0表示燃油公交，1表示电动车辆
	$x_{j,i}$	第$i$个车次第$j$辆公交的执行状态，0‒1变量，0表示该车辆不执行该运行车次，1表示该车辆执行该运行车次
	$X_i$	第$i$个车次所有车辆执行状态，$X_i=\left(x_{1,i},x_{2,i},\cdots ,x_{j,i},\cdots ,x_{J,i}\right)$
	$X$	公交调度方案，$X=\left[X_1,X_2,\cdots \cdots ,X_{N-1},X_N\right]$

1.2　问题模型化

本研究将混合公交车队的车辆集合表示为$V=\left\{x_{\mathrm{1}},x_{\mathrm{2}},\cdots ,x_j,\cdots ,x_J\right\}$，$J$为公交车队的车辆总数，则有$J=K+H$。为了保证公交运行的可靠性，每个车次必须由指定车辆执行，考虑线路发车间隔、线路长度、线路运营速度以及电动公交的充电时间等约束对线路运行中混合公交车队的最小规模进行确定。线路混合车队最小规模上界的确定将按照车辆类型进行分别讨论。

（1）确定燃油公交上界。在一天的运营过程中燃油公交不需要返回场站，所以当公交车队全部为燃油公交时，只要保证车辆数量满足发车间隔和线路运营时间要求即可

$$H_{\mathrm{m}\mathrm{a}\mathrm{x}}=\left[\frac{\mathrm{2}{l}_{\mathrm{L}}/v}{t_{\mathrm{i}\mathrm{n}\mathrm{t}}}\right]+\mathrm{1}$$

（1）

（2）确定电动公交上界。在一天的运营过程中当电动公交剩余能量不满足执行完整车次时，电动公交需提前返回场站进行能量补给，此时需调动其他车辆维持该车次链的正常运营。假设公交车队全部为电动公交时，车辆数在满足发车间隔和线路运营时间约束的同时，还需考虑充电时间的限制，即

$$K_{\mathrm{m}\mathrm{a}\mathrm{x}}=\left[\frac{t_{\mathrm{c}\mathrm{h}}+\mathrm{2}\left(l_{\mathrm{L}}+l_{\mathrm{S}}\right)/v}{t_{\mathrm{i}\mathrm{n}\mathrm{t}}}\right]+\mathrm{1}$$

（2）

车队调度方案采用矩阵形式定义$\mathit{X}=\left[X_{\mathrm{1}},X_{\mathrm{2}},\cdots ,X_{N-\mathrm{1}},X_N\right]$，X为公交车队调度方案，包含公交线路运营一天内N个车次的车辆调度情况。对于生成混合公交车队行车计划的数学模型设计主要包含两步，其中Step1为基于电动公交和燃油公交运行能耗模型分别建立公交运营成本模型，具体见1.2.1；Step2为联立Step1建立的电动公交和燃油公交运营成本模型，以公交车队综合运营成本最小为目标建立求解函数，具体见1.2.2。

1.2.1　成本分析

在构建不同类型公交成本模型中需首先建立能耗模型，为了降低模型的复杂程度在此选用平均能耗进行计算，公交车辆的平均能耗可以参考车辆制造商公布的数据^［16］。由此建立行驶里程与单位行驶里程能耗的线性模型^［17-18］：电动公交能耗模型为$E_{\mathrm{e}}=l_i{q}_{\mathrm{e}}$；燃油公交能耗模型为$E_{\mathrm{o}}=l_i{q}_{\mathrm{o}}$。

（1）基于碳排放建立燃油公交成本模型。燃油公交成本$M_{\mathrm{o}}$包括燃油公交车辆使用成本$M_{\mathrm{o},\mathrm{1}}$和能源消耗成本$M_{\mathrm{o},\mathrm{2}}$，以及在行驶过程中产生的碳排放成本$M_{\mathrm{o},\mathrm{3}}$。按照工作量法计算公交车辆的使用成本，$M_{\mathrm{o},\mathrm{1}}=\frac{m_{\mathrm{o}}\left(\mathrm{1}-R_{\mathrm{0}}\right)}{d_{\mathrm{o}}}{l}_j$；燃油公交的燃油成本主要产生于执行车次的过程，与燃油公交的燃油消耗量及燃油单价有关，$M_{\mathrm{o},\mathrm{2}}=E_{\mathrm{o}}{P}_{\mathrm{o}}$；燃油公交碳排放成本的测算通过碳排放因子来计算燃油碳含量，然后结合碳成本转化系数确定：$M_{\mathrm{o},\mathrm{3}}=E_{\mathrm{o}}{F}_{\mathrm{o}}\gamma$。

由此构建燃油公交成本模型如下：

$$M_{\mathrm{o}}=M_{\mathrm{o},\mathrm{1}}+M_{\mathrm{o},\mathrm{2}}+M_{\mathrm{o},\mathrm{3}}=\frac{m_{\mathrm{o}}\left(\mathrm{1}-R_{\mathrm{0}}\right)}{d_{\mathrm{o}}}{l}_j+$$

$$E_{\mathrm{o}}{P}_{\mathrm{o}}+E_{\mathrm{o}}{F}_{\mathrm{o}}\gamma$$

（3）

（2）基于减排效益建立电动公交成本模型。电动公交由于采用清洁能源，在运营过程中不产生碳排放成本，因此可将其作为减排效益纳入电动公交成本模型中。相较于燃油公交的续航能力及能源补给效率，电动公交因受电池容量的限制，使其在返回场站进行能量补给的过程中产生了更多的空载成本。

电动公交的成本$M_{\mathrm{e}}$包含电动公交车辆使用成本$M_{\mathrm{e},\mathrm{1}}$和能源消耗成本$M_{\mathrm{e},\mathrm{2}}$，以及考虑电动公交替代燃油公交运营减少的碳排放作为电动公交的减排效益$\left|M_{\mathrm{e},\mathrm{3}}\right|$。按照工作量法计算电动公交的使用成本：$M_{\mathrm{e},\mathrm{1}}=\frac{m_{\mathrm{e}}\left(\mathrm{1}-R_{\mathrm{0}}\right)}{d_{\mathrm{e}}}l{}_j{}^{}$；在测算电动公交的能耗成本时引入分时电价$P_{\mathrm{e}}\left(t\right)$，引导电动公交错峰充电，$M_{\mathrm{e},\mathrm{2}}=E_{\mathrm{e}}{P}_{\mathrm{e}}\left(t\right)$；将电动公交取代燃油公交运营减少的碳排放$M_{\mathrm{o},\mathrm{3}}$部分作为电动公交的减排效益$\left|M_{\mathrm{e},\mathrm{3}}\right|$，并且在计算电动公交替代燃油公交运营实现的减排效益时扣除电动公交运营过程中产生的额外空载碳排放，即$M_{\mathrm{e},\mathrm{3}}=-\left(l_i-\mathrm{2}\theta l_{\mathrm{S}}\right)q_{\mathrm{o}}{F}_{\mathrm{o}}\gamma$，其中$\theta \in \left\{\mathrm{0,1}\right\}$，$\theta$为电动公交电池剩余容量的约束，每个变量值可以是0或1，分别代表该电动车辆需不需要返回场站进行能量补给，0代表不需要，1代表需要。$\theta$值取决于电动公交的电池剩余量$U_{\mathrm{r}}$，$U_{\mathrm{r}}$具体表达方式为：电动公交行驶$n$个往返车次后返回至场站充电，$U_{\mathrm{r}}=U_{\mathrm{e}}-\mathrm{2}\left(n{l}_{\mathrm{L}}+l_{\mathrm{S}}\right)q_{\mathrm{e}}$，当$U_{\mathrm{r}}>\left(\mathrm{2}{l}_{\mathrm{L}}+l_{\mathrm{S}}\right)q_{\mathrm{e}}$时，$\theta =\mathrm{0}$；$U_{\mathrm{r}}\le \left(\mathrm{2}{l}_{\mathrm{L}}+l_{\mathrm{S}}\right)q_{\mathrm{e}}$时，$\theta =\mathrm{1}$。

由此构建电动公交的成本模型为

$$M_{\mathrm{e}}=M_{\mathrm{e},\mathrm{1}}+M_{\mathrm{e},\mathrm{2}}+M_{\mathrm{e},\mathrm{3}}=\frac{m_{\mathrm{e}}\left(\mathrm{1}-R_{\mathrm{0}}\right)}{d_{\mathrm{e}}}{l}_i+E_{\mathrm{e}}{P}_{\mathrm{e}}\left(t\right)-\left(l_i-\mathrm{2}\theta l_{\mathrm{S}}\right)q_{\mathrm{o}}{F}_{\mathrm{o}}\gamma$$

（4）

1.2.2　目标函数

在Step2中，根据Step1所建立的电动公交和燃油公交运行能耗与成本模型，以公交车队综合运营成本最小为目标，目标函数如式（5）所示。

$$\mathrm{M}\mathrm{i}\mathrm{n}Z=w\sum _i\sum _j(x_j{x}_{j,i})M_{\mathrm{e}}+\left(\mathrm{1}-w\right)\sum _i\sum _j\left(\mathrm{1}-x_j\right)\left(\mathrm{1}-x_{j,i}\right)M_{\mathrm{o}}$$

（5）

式中：$Z$为混合公交车队全天运营成本。电动公交政策倾向系数$w$表示受当地相关政策影响，公交企业运营使用电动公交执行车次的倾向。引入电动公交政策偏向系数作为调度方案中电动公交运营成本权重，通过调整$w$值，使生成的混合公交车队调度方案实现不同优化效果。并给定如下约束条件式 （6）~（13）。

$$x_j=\left\{\begin{array}{l}\mathrm{0},\mathrm{车}\mathrm{辆}\mathrm{j}\mathrm{为}\mathrm{燃}\mathrm{油}\mathrm{公}\mathrm{交}\\ \mathrm{1},\mathrm{车}\mathrm{辆}\mathrm{j}\mathrm{为}\mathrm{电}\mathrm{动}\mathrm{公}\mathrm{交}\end{array}\right.$$

（6）

$$x_{j,i}=\left\{\begin{array}{l}\mathrm{0},\mathrm{车}\mathrm{辆}\mathrm{j}\mathrm{不}\mathrm{执}\mathrm{行}\mathrm{车}\mathrm{次}\mathrm{i}\\ \mathrm{1},\mathrm{车}\mathrm{辆}\mathrm{j}\mathrm{执}\mathrm{行}\mathrm{车}\mathrm{次}\mathrm{i}\end{array}\right.$$

（7）

$${\displaystyle \sum _{j=\mathrm{1}}^J}{x}_{j,i}=\mathrm{1},\forall i\in \left\{\mathrm{1,2},\cdots ,N\right\}$$

（8）

$$\left|T\left(i\right)-T\left(i^{\text{'}}\right)\right|>\left(\mathrm{2}{l}_{\mathrm{L}}/v\right),\left\{i\left|x_j=\mathrm{0},x_{j,i}=\mathrm{1}\right.\right\},i\ne i^{\text{'}}$$

（9）

$$U_{\mathrm{r}}>\left(\mathrm{2}{l}_{\mathrm{L}}+l_{\mathrm{S}}\right)q_{\mathrm{e}}$$

（10）

$$\left|T\left(i\right)-T\left(i^{\text{'}}\right)\right|>\left(\frac{U_{\mathrm{e}}-U_{\mathrm{r}}}{\epsilon }+\mathrm{2}\frac{l_{\mathrm{S}}+l_{\mathrm{L}}}{v}\right),\left\{i\left|x_j=\mathrm{1},x_{j,i}=\mathrm{1}\right.\right\},i\ne i^{\text{'}}$$

（11）

$$\mathrm{0}\le K\le K_{\mathrm{m}\mathrm{a}\mathrm{x}}$$

（12）

$$\mathrm{0}\le H\le H_{\mathrm{m}\mathrm{a}\mathrm{x}}$$

（13）

约束（6）为车辆类型判断；约束（7）为车辆执行状态判断；约束（8）保证每个车次必须有车辆运行，且只有一辆车运行；约束（9）表示车辆类型为燃油公交（$x_j=\mathrm{0}$）时，比较第$j$辆燃油公交所执行的车次$i$和车次$i\mathrm{\text{'}}$（$x_{j,i}=\mathrm{1},x_{j,i^{\text{'}}}=\mathrm{1}$）对应的时间之差（$\left|T\left(i\right)-T\left(i{}^{\text{'}}\right)\right|$）与燃油公交完整执行一个车次所需时间二者的大小，保证第$j$辆燃油公交所执行的车次时间间隔大于线路运营时间；约束（10）为电动公交电量约束，剩余电量至少保证公交车辆能够返回场站和一个完整车次的运行；约束（11）为电动公交充电时间约束，式中$\left|T\left(i\right)-T\left(i{}^{\text{'}}\right)\right|$为该辆电动公交相邻运行车次的时间间隔；约束（12）为混合公交车队中电动公交车辆数量规模约束；约束（13）为混合公交车队中燃油公交车辆数的规模约束。

显然，所构建的模型为NP（nondeterministic polynomial，非确定性多项式）问题，由于电动公交与燃油公交的能源供应、用车成本差异导致公交调度问题解的规模扩大以及计算复杂化，传统的优化求解方法遇到了很大困难，启发式算法是目前求解NP问题较为有效的方法，相关研究学者成功利用遗传算法^［19］和自适应大邻域搜索算法^［20-21］求解电动汽车车队的旅行商问题，这为混合公交车队调度问题的求解提供了有力的参考。

2 算法

针对NP问题的求解，由美国Holland教授提出的遗传算法作为一种全局优化搜索算法在公交车队的优化调度问题中可以在相对较短的时间内找到最优解，其中包括电动公交车队的车辆调度和电动公交车队的充电调度^［22-23］。由于遗传算法采用适应度值的大小来决定个体是否被复制的选择机制，容易形成近亲繁殖，造成算法的局部搜索和过早收敛，从而导致全局寻优失败。而由美国Glover提出的禁忌搜索是一种用来跳脱局部最优解的搜索方法，扩展了局部邻域搜索。禁忌搜索通过记忆功能，在搜索过程中每当最优解被作为搜索方向后，允许将未搜索过的次优解作为新的搜索方向，使得搜索跳脱局部最优。禁忌搜索为许多组合优化问题提供了近似最优解，在公交乘务人员排班^［24］和路径规划^［25］中被证明了它的可行性和有效性。但禁忌搜索对初始解具有较强的依赖性，当初始解较差时，收敛速度将会降低。因此在遗传算法中嵌入禁忌搜索，允许求解过程选择非最优解能够在很大程度上帮助遗传算法避免“早熟收敛”问题的出现，同时保证了算法收敛速度，提高了遗传算法的全局寻优能力。

2.1　算法框架

求解优化模型采用的算法，整体框架设计如图2所示。

图2 遗传禁忌搜索算法流程

Fig.2 Flow of genetic tabu searching algorithm

2.2　算法设计

2.2.1　初始解产生

利用遗传算法从初始种群$C\left(X\right)$中产生一个较好的初始解$X$，使禁忌搜索能够从一个较好的起点开始，既能避免遗传算法陷入局部最优，又能提高禁忌搜索的收敛速度。首先对公交调度方案进行染色体编码，需要包含混合公交车队运营的两部分信息：①执行哪些车次；②执行车次对应的公交车辆。按照一天公交运营车次的时间顺序进行染色体编码，仅需构造1条染色体，即可包含①、②的信息，如图3所示。

图 3 染色体编码示例

Fig.3 Examples of chromosome coding

采用随机方法产生初始个体，然后进行选择、交叉以及变异等遗传操作，产生新种群作为禁忌搜索的初始种群，如图4所示。

图4 种群初始化流程

Fig.4 Process of individualized initialization

适应度的大小决定着进化方向，由于本文的优化问题属于求目标函数最小的优化问题，适应度值越小，其保留下来的概率越大。如式（14）所示，定义式（5）为染色体适应度函数。

$$F\left(x\right)=w\sum _i\sum _j(x_j{x}_{j,i})M_{\mathrm{e}}+\left(\mathrm{1}-w\right)\sum _i\sum _j\left(\mathrm{1}-x_j\right)\left(\mathrm{1}-x_{j,i}\right)M_{\mathrm{o}}$$

（14）

2.2.2　禁忌表建立与突破

禁忌表$T$是禁忌搜索实现跳脱局部最优解的核心要素，它包含禁忌表长度$T_{\mathrm{L}}$的确定和禁忌对象的选择。$T_{\mathrm{L}}$过长导致收敛速度减慢，计算复杂程度增加；$T_{\mathrm{L}}$过短容易陷入局部最优^［26］。所以为了降低取值对收敛迭代的次数和方案与最优解接近程度的影响，在后续仿真中将会对比$T_{\mathrm{L}}$不同取值下的收敛效果从而确定禁忌长度。如图2所示，每次回选搜索域中的最优解作为禁忌对象，禁忌对象将不作为寻优搜索的新方向，当禁忌对象的适应度小于历史记录最低适应度时，即满足藐视准则时，可以突破禁忌将其作为寻优搜索的下一步方向。

2.2.3　搜索邻域构造

采用转移法和交换法构建搜索邻域，转移法为在同一车次把车次任务转移到相邻的车辆，如图5所示；交换法为不同车次任务交换执行车辆，如图6所示。两种邻域结构互为补充，尽可能拓宽算法搜索的解空间从而避免陷入局部最优。

图5 转移构造邻域

Fig.5 Transfer method of constructing neighborhood

图6 交换构造邻域

Fig.6 Change method of constructing neighborhood

2.2.4　停止准则判断

给定最大迭代数$\mathrm{m}\mathrm{a}\mathrm{x}g$，当迭代次数达到$\mathrm{m}\mathrm{a}\mathrm{x}g$或者搜索域的解全部被列为禁忌对象时，结束搜索。

3 结果和讨论

3.1　案例数据

选取云南省文山州1路作为本节的实例研究。公交线路运营情况如表2所示，配备的公交车辆技术参数如表3所示^［27］。为了引导电动公交错峰充电，参考城市分时电价模式进行公交充电需求管理。在分时电价机制的基础上，基于不同时段电价确定不同充电成本，根据公交运行时刻表和公交动力能源差异，合理配置车辆规模和排班计划。实例选取线路所在城市的分时电价如式（15）所示

$$P_{\mathrm{e}}\left(t\right)=\left\{\begin{array}{l}\mathrm{1.100}\mathrm{2}\mathrm{元}\cdot \mathrm{k}\mathrm{W}{\mathrm{h}}^{-\mathrm{1}},t\in \left\{\left(\mathrm{8}:\mathrm{00}-\mathrm{12}:\mathrm{00}\right)\bigcup \left(\mathrm{17}:\mathrm{00}-\mathrm{21}:\mathrm{00}\right)\right\},\mathrm{峰}\mathrm{时}\\ \mathrm{0.660}\mathrm{1}\mathrm{元}\cdot \mathrm{k}\mathrm{W}{\mathrm{h}}^{-\mathrm{1}},t\in \left\{\left(\mathrm{12}:\mathrm{00}-\mathrm{17}:\mathrm{00}\right)\bigcup \left(\mathrm{21}:\mathrm{00}-\mathrm{24}:\mathrm{00}\right)\right\},\mathrm{平}\mathrm{时}\\ \mathrm{0.322}\mathrm{0}\mathrm{元}\cdot \mathrm{k}\mathrm{W}{\mathrm{h}}^{-\mathrm{1}},t\in \left\{\left(\mathrm{0}:\mathrm{00}-\mathrm{8}:\mathrm{00}\right)\right\},\mathrm{谷}\mathrm{时}\end{array}\right.$$

（15）

表2 线路运营相关参数

Tab.2 Related parameters of bus line operation

线路运营时段	发车间隔/min	线路长度/km	场站距始发站距离/km	线路运营速度/（km·h-1）
6：30-21：30	15	15.6	2	15

表3 公交车辆技术参数

Tab.3 Technical parameters of bus

车辆型号	宇通ZK6821DG2	宇通ZK6815BEVG3
购买成本/万元	72	104
使用年限/年	10	10
使用年限预计行程里程总数/万km	70	70
单位能耗	柴油0.35 L·（veh·km）-1	电能0.84 kWh·（veh·km）-1
电池容量/kWh		142

测算燃油公交碳排放成本时，主要参考中国能源统计年鉴以及碳交易的成交额确定相关参数^［28］，如表4所示。

表4 碳排放相关参数

Tab.4 Parameters related to carbon emissions

参数	取值
$F_{\mathrm{o}}$/（kg·L-1）	3
$\gamma$/（元·kg-1）	0.05

3.2　调度方案分析

为了验证本研究所提出的调度方案优化方法的有效性和优越性，使用Matlab 2016进行仿真。设置相同的参数对比传统遗传算法和本研究所提出的基于嵌套禁忌搜索的改进遗传算法，图7为两种算法的目标函数值收敛曲线。由图7可知，当禁忌表长度设置为6时，基于嵌套禁忌搜索的改进遗传算法相比于传统遗传算法求解精度提高了12%左右；此外，虽然基于嵌套禁忌搜索的改进遗传算法收敛速度较慢，但该算法跳脱了局部最优，全局寻优能力更强，更适合最优解的搜索。

图7 算法收敛过程对比

Fig.7 Comparison of convergence processes between algorithms

电动公交政策倾向系数$w$的取值大小反映了公交车队调度决策倾向，在不同$w$取值下生成的最优调度方案空驶里程和碳排放量如图8所示。从空驶里程变化曲线可以看出，$w$取值越靠近0.5，总空驶里程数越小，此时生成的方案车辆利用率越高；从碳排放量变化曲线可以看出，随着$w$取值增大，碳排放量也随之增大，对应方案减排效益越低。故当调度决策倾向于提高公交车队车辆利用率减少空驶里程时，应该设置较大的$w$；当调度决策倾向于提高公交车队减排效益时，应该设置较小的$w$。考虑到本次研究的目标是实现综合运营成本最小，进一步讨论不同$w$取值下生成的最优调度方案综合运营成本变化，如图9所示。由图9可以看出，当$w=\mathrm{0.15}$时，调度方案的综合运营成本最低，故本次研究将对基于$w=\mathrm{0.15}$生成的调度方案进行分析。

图8 不同w取值下方案车队总空驶里程和总碳排放量的变化曲线

Fig.8 Curves of empty driving distance and carbon emission of schemes at different values of w

图9 不同w取值下方案综合运营成本变化曲线

Fig.9 Curves of comprehensive operation cost of schemes at different values of w

生成初始解部分算法参数设置如下：种群规模为30；交叉概率为0.8；变异概率为0.2，禁忌搜索算法部分参数选取如下：$T_{\mathrm{L}}=\mathrm{6},\mathrm{m}\mathrm{a}\mathrm{x}g=\mathrm{2}\mathrm{000},w=\mathrm{0.15}$，求解优化目标函数得到的调度方案如图10所示，其中黑色矩形表示电动公交的车次行程，灰色矩形表示燃油公交的车次行程。按图10所示的调度方案排班，此时混合公交车队综合运营成本最小，为每天1549.7元。显然，如图11所示的优化调度方案中，电动公交执行车次任务分配数量远高于燃油公交，提高了新能源公交的利用，减少车队中现有燃油公交使用，尽可能实现混合公交车队减排效益最大化。同时，在优化模型中引入分时电价机制，通过调节电动公交执行车次任务的时段，引导电动公交错峰充电，节约充电成本。图12为调度方案中分时电

图10 混合公交车队调度方案

Fig.10 Scheduling plan for mixed bus fleet

图11 不同类型公交车辆分配任务数量

Fig.11 Number of tasks assigned to different types of buses

图12 分时电价与电动公交执行车次任务时段的关系

Fig.12 Relationship between the time-of-use electricity price and the task period of electric buses

价与电动公交执行车次任务的时段关系。图12实线为研究线路所在城市的分时电价机制，虚线为在不同电价时段电动公交执行的车次任务数量占该时段总车次任务数量的比例，对比发现谷时段的车次任务全由电动公交执行；上午峰时，电动公交执行的车次任务数量占该时段总车次任务数量的比例大幅下降，为一天运营中最低的时段；中午平时阶段，电动公交执行的车次任务数量占该时段总车次任务数量的比例回升；下午峰时，电动公交执行的车次任务数量占该时段总车次任务数量的比例再次下降。调度方案整体与分时电价机制相对应，呈现与电价错峰执行任务的效果。

4 结论

本研究针对燃油公交与电动公交共存系统中的能源消耗与调度优化问题，根据公交路线运行参数配置混合公交车队的车辆类型和数量，综合考虑电动公交空载成本和燃油公交碳排放成本，并将分时电价机制引入电动公交充电调度中，构建公交车队调度运营成本优化模型，生成最优车次链，主要成果如下：

（1）联立不同类型公交成本建立混合公交车队综合运营成本，以综合运营成本最小为优化目标，由此生成的调度方案能有效降低车队中燃油公交车任务分配比例，提高了车队运营减排效益，同时分时电价机制的引入实现了电动公交与用电高峰时段错峰充电，节约了电动公交的充电成本。

（2）本文所提出的基于嵌套禁忌搜索的改进遗传算法有效克服了传统遗传算法易陷入局部最优的缺陷，提高了算法的求解精度。

（3）公交运营企业可以根据自身情况和城市交通现状，通过采用不同的电动公交政策倾向系数值，使生成的调度方案满足不同的决策目标，实现电动公交减排效益与车辆利用率之间的平衡。

本文在进行混合公交车队调度、分析车队运营成本时主要从车辆技术特征（如能源补给方式差异）展开，后续可以进一步考虑人员（如司机）成本，使生成的调度方案更全面地服务公交运营系统。

作者贡献声明

杨 敏：研究概念生成，研究目标制定，实验方式设计。

黎 彧：初稿撰写，计算机程序设计，实验结果分析。

王 建：论文审阅与修订。

王立超：研究数据整理。