考虑多路径选择的定制电动公交线路优化

郭戎格，关伟，张文义，段梦媛

(北京交通大学，综合交通运输大数据应用技术交通运输行业重点实验室，北京100044)

0 引言

定制公交凭借其灵活、直达和响应快速的优势，成为提高公共交通准时性和舒适性的解决方案。定制公交作为一种需求响应型服务，如何优化运营线路来满足出行需求是亟待研究的问题。Guo 等[1]考虑乘客出行时间窗，实现线路与时刻表的共同决策。Huang 等[2]采用两阶段优化方法，以运营收益最大为目标，求解针对动态出行需求的线路方案。陈汐等[3]同时考虑乘客出行成本和运营成本，构建多区域运营模式的定制公交线路规划模型。然而，当前研究主要针对传统车辆，未考虑纯电动车辆在定制服务中的应用。杨扬等[4]表明纯电动公交在环境保护和节约能源方面有较大优势，可替代传统公交车，但其运营特性(续航里程短、充电时间长)会为线路规划带来挑战。Hiermann 等[5]通过确定车辆的充电地点和充电时间，实现不同类型电动车辆的线路决策。Montoya等[6]则采用分段线性函数近似捕捉车辆充电过程的非线性行为。

实际路网中，地理上分隔的两点间通常存在多条可选子路径，且每条路径包含多个属性，为线路进一步优化提供可能性。Baldacci 等[7]引入多路径路网的概念，用以研究生活垃圾转运车辆路径优化问题。Lai等[8]基于行驶时间、距离等属性获取两点之间的多路径，设计了求解异构车辆路径问题的禁忌搜索算法。Garaix等[9]在多路径的按需运输问题中，提出一种动态规划算法求解固定序列弧段选择问题。尽管学界对路径选择问题进行了广泛而深入的研究，但较少考虑多路径选择对定制公交线路的影响。

综上，本文提出一个混合整数规划模型，实现定制电动公交线路与路径的共同决策，目标函数考虑乘客出行费用、车辆运营费用和充电费用。算法求解方面，基于自适应大邻域搜索算法框架，设计可优化线路的destroy和repair规则。最后，通过实例数值分析，验证多路径选择可有效提高定制公交运营效率。

1 问题描述与模型

1.1 问题描述

本文须解决的问题可描述为，场站拥有相同容量的满电车辆，服务已知的乘客出行时空需求，通过优化站点访问顺序和路径选择创建线路，使得：①车辆服务所有出行需求，且满足乘客和场站服务时间窗，②每辆车载客人数不少于车辆最低载客量，③车辆在充电站达到满电状态后离开。图1为本文多子路径路网示意图，每条路径广义费用考虑距离和时间两种属性。

图1 路网示意图Fig.1 Schematic drawing of road network

本文使用G=(V,A)表示路网，其中，V为节点集，它由站点集S、场站集O及充电站集F共同组成，即V=S∪O∪F，A表示弧集。集合S中的节点i(i∈S)对应非负权值属性：服务时间si和服务时间窗[TiArr,TiDep]，其中，TiArr为车辆最早到达时间，TiDep为车辆最迟离开时间。集合S中任意两节点r(r∈S)与s(s∈S)对应乘客出行需求qr,s和乘客出行费用fr,s。集合O中的节点j对应场站服务时间窗[uj,lj]，uj和lj分别表示场站开始和结束服务时间，即车辆须在[uj,lj]内出发并返回场站。集合F中的节点对应充电速率g，充电基本费用c4和单位时间充电成本c5。集合A中的每条弧(i,j)对应一组可选路径Pi,j，每条路径φi,j,p(p∈Pi,j)与距离di,j,p和旅行时间ti,j,p相关联。K表示车辆集合，每辆车k对应非负权值属性：满电电量E，能耗速率h，最大车容量M，抵达点i时的在车乘客数Qi,k，最低载客量λ，最大访问站点数R，单位车辆发车成本c1，单位时间运营成本c2和单位距离运营成本c3。决策变量定义如表1所示。

表1 决策变量含义Table 1 Decision variables

1.2 模型建立

定制电动公交线路优化问题是一个NP-hard问题，可构造成一个混合整数规划模型。模型目标函数考虑乘客出行费用、运营费用(CBus)和充电费用(CElectric)，以收益最大为目标，构建数学模型为

式中：B为一个较大常数。

目标函数：式(1)定义了运营收益最大化，由乘客出行费用，运营费用和充电费用组成；式(2)表示运营费用，包含发车费用，运行时间费用和运行距离费用；式(3)表示充电费用，包括充电基本费用和充电时间费用。约束条件：式(4)表示可多次访问站点和充电站；式(5)表示车辆从场站出发并返回；式(6)为流量平衡约束；式(7)规定，车辆在服务某需求时，须访问该需求的起讫点；式(8)表示当车辆访问充电站时，即发生充电行为；式(9)表示当车辆行驶某一路段时，只选择其中一条路径；式(10)规定每辆车的最低载客量；式(11)为乘客分配约束；式(12)～式(14)为车容量约束；式(15)和式(16)表示车辆能耗与距离相关，保证每辆车的电量不低于0；式(17)和式(18)分别保证车辆在离开场站、站点及充电站后的时间可行；式(19)～式(21)为时间窗约束；式(22)表示车辆离开站点时间为车辆到达站点时间与服务时间之和；式(23)规定了每条线路访问站点的数量。

2 优化模型求解算法

定制电动公交线路优化问题属于NP-hard 问题，且规模较大。因此，本文基于自适应大邻域搜索 算 法(Adaptive Large Neighborhood Search，ALNS)，设计求解方法[10]。本文在ALSN框架下，基于贪心算法制定初始解产生规则，设计多个destroy和repair算子进行邻域搜索，优化站点访问顺序，并采用轮盘赌选择机制选择算子。由于在邻域搜索中，并未指定车辆进行运送时两站点间的具体子路径，故本文采用Garaix等[9]提出的动态规划算法，以广义费用(行驶距离成本和行驶时间成本)最小，求解两点间的最优路径。

2.1 初始解求解

采用贪心算法寻找初始可行解，其核心思想为：在不破坏模型约束的前提下寻找距离当前节点最近的OD 加入线路，如果违反任意约束，则基于同样规则搜索新线路。同时，还要考虑最优路径选择情况。算法步骤如下：

Step 1 选择场站i规划新路线l，i为当前节点a。

Step 2 搜索距离a最近未被服务的OD(r,s)，计算发车时间，选择最优路径，判断加入该OD(r,s)是否满足时间窗和车容量约束。如果是，继续；否则，返回Step 1。

Step 3 判断电池容量是否满足服务OD(r,s)。如果是，将OD 加入线路l，将s设置为当前节点a，转至Step 5；否则，继续。

Step 4 判断a附近是否存在充电站F，使车辆由最佳路径前往F充电，并服务OD(r,s)。如果是，依次将F、OD(r,s)插入线路，将s作为当前节点a，继续；否则，返回Step 1。

Step 5 判断站点数是否达到R。如果否，转至Step 2；否则，搜索距离当前a最近场站j，选择最优路径，判断加入j是否满足时间窗约束，若满足，继续，否则，返回Step 1。

Step 6 判断电池容量是否满足到达j。如果满足，将j加入线路l，结束；否则，继续。

Step 7 判断j附近是否存在充电站F，使得车辆由最佳路径前往F充电，返回j。如果存在，依次将F、j插入线路，结束；否则，返回Step 1。

2.2 Destroy规则

在ALNS中，destroy算子可随机破坏当前解的一部分[10]。本文从随机性与节省运营费用的角度提出与站点相关的两个算子。考虑到电动车在服务过程中的充电行为是线路规划的关键，去除不必要的充电站可有效提高运营效率，故提出针对充电站的destroy算子。具体如下：

(1)Random destroy，随机选取n组OD，移除对应的站点。

(2)Worst cost destroy，依据节约广义出行费用移除站点，通过计算每个站点造成所在线路的广义运营费用增量，选择增量最多的n个站点进行移除，如图2所示，其中站点上方的数字表示乘客上下车人数，例如+10表示上车10人，-10表示下车10人。费用增量为

图2 Worst cost destroy算子Fig.2 Worst cost destroy operator

(3)Low charge destroy，考虑到车辆在到达充电站时仍保有较多电量，充电效率低，可移除充电量低于Emin的充电站。如图3所示，百分比为车辆剩余电量SOC，当充电量低于30%的满额电量，则移除充电站。

图3 Low charge destroy算子Fig.3 Low charge destroy operator

2.3 Repair规则

在ALNS 中，repair 算子针对被destroy 算子破坏的部分进行重建，实现邻域搜索，从而得到一系列解的集合[10]，同时，需要判断重建线路是否满足模型约束。Repair算子介绍如下：

(1)Random repair，依次随机选择被破坏线路中的任意位置插入被移除OD，直到所有出行需求都被服务。

(2)Greedy repair，选择被移除站点的现有线路l，采用式(24)计算使广义运营费用增量最小的位置j，插入站点。

(3)High charge repair，计算当前线路车辆在电池容量满额情况下可访问的最远站点i，在i附近寻找导致广义运营费用增量最小的充电站，插入到线路中，重复上述步骤，直到所有线路满足乘客需求，如图4所示，该算子可造成新的充电站替换被移除充电站。

图4 High charge repair算子Fig.4 High charge repair operator

为证明ALNS 的有效性，分别运用CPLEX 和ALNS对算例进行求解[3]。如表2所示，发现ALNS所得最大目标函数值与精确解相差较小，且在计算效率上存在较大优势，故认为ALNS可应用于大规模实例求解。

表2 算法对比结果Table 2 Comparison results of algorithms

3 实例研究

3.1 实例设计

本文以北京市区路网及乘客出行时空需求为基础，设计3种类似于Solomon标准算例R、C和RC的实例[3]，R、C 和RC 分别对应随机乘客分布、聚集乘客分布和混合乘客分布。每个实例包含工作日早高峰7:00-8:00 的20 组出行需求(227 名乘客)和11 个场站，每一组出行需求包含出行起讫点，服务时间窗和出行人数信息，其中，两站点间存在3 条可选子路径。如图5所示，R实例通过随机选择20组出行需求获得，C实例基于密度的空间聚类方法获得，RC实例由随机选取的10组需求和聚类产生的10组需求组成。

图5 R，C和RC案例的乘客位置Fig.5 Passenger locations of R,C and RC instances

实例采用40 座的电动公交车，满电电量为80 kWh，能耗速率为2 kWh·km-1，每辆车的最小负载为20 人，服务6 个站点，须在场站服务时间窗[7:00, 8:30]内完成任务。案例中，场站即为充电站，充电速率为4 kWh·min-1。其余参数如下：c1=80元，c2=60元·h-1，c3=1.8元·km-1，c4=50元，c5=10 元·min-1，si=1 min。自适应大邻域搜索算法迭代150次。

3.2 结果分析

采用上述求解算法分析充电方式、乘客分布及多路径选择对收益的影响，为降低启发式算法随机性对结果的影响，重复计算每个算例10次，基于此结果进行分析。

(1)充电方式及乘客分布对收益的影响

考虑到不同充电方式会极大影响公交运营成本，针对快充模式(R1，C1，RC1)和换电模式(R2，C2，RC2)进行收益分析，计算3 种乘客分布情况下的总收益(z)，运行时间(T)，运行距离(D)，充电费用(CElectric)和车辆数(N)。其中，换电模式的充电时间为0，换电基本费用c4=300元。

如表3所示，针对每种乘客分布情况，采用快充模式可获得更多运营收益，尽管整车快充会增加充电时间，但相较于换电模式，快充模式的基本充电费用较低，降低了车辆的充电成本。分析3种乘客分布对应的数值结果可以发现：聚类乘客分布及混合乘客分布的收益优势逐渐体现出来，C 与RC实例对应的总收益较高；与R相比，C与RC采用较多运营车辆，有效减少充电次数与充电时间；车辆服务分布较为集中的乘客时，运行距离和运行时间相应减少。因此，在设计定制服务时，寻求乘客分布和运输成本之间的平衡是极其重要的。

表3 快充模式与换电模式算例结果Table 3 Results of fast charging and battery swapping

(2)多路径选择效果分析

为研究路径灵活性的影响，分析比较两站点间单一子路径和多子路径情况下的结果。其中，单一子路径在实例基础上保留两站点间距离最短路径。

由表4可知，考虑路径选择的运营方案比单一子路径情况更优。R实例，主要通过减少充电次数和充电时间提高收益；C与RC实例，主要通过减少车辆运行时间和距离达到减少运营费用的目的。这是由于单一子路径为距离最短子路径，而非时间最短子路径，车辆为了满足乘客出行时空约束，往往会改变节点访问次序，在运送途中进行充电以满足出行需求。相比之下，多子路径的情况可通过选择时间-距离加权最短子路径到达下一个站点，从而减少电量消耗，降低运营成本，为运营商提供更多运行方案来实现运营效率的提升。结果表明，多路径选择在提高定制电动公交系统充电效率和降低运营成本方面潜力巨大。

表4 单一子路径与多子路径算例对比结果Table 4 Comparison results between single path and multiple paths

4 结论

本文提出一种带多路径选择的定制电动公交线路优化方法，构建了混合整数规划模型。基于自适应大邻域搜索算法框架，设计针对站点和充电站的destroy和repair规则求解模型。在实例分析中，通过比较不同充电模式发现，整车充电模式可有效减少充电成本，增加总收益，而乘客聚类分布和混合聚类分布情况的收益优势较大；同时，实例验证了多路径选择的加入可有效节省充电和运营费用，提高服务运营效率。