随着近年来我国城市轨道交通体系成网度越来越高，地铁出行已成为城市通勤过程中的重要组成。然而，作为“门到门”运输服务的关键环节，以连接地铁站点为目的的短途接驳服务目前还未能发挥出其应有的作用。特别是在雨雪等恶劣天气条件下，现有短途接驳方式面临多种困境：常规公交车内拥挤程度增加，舒适性一落千丈; 共享单车环境暴露度高，安全性难以保障; 由于行驶距离相对较短，且恶劣天气限制了部分接单意愿，可供短途接驳的出租车、网约车等小汽车数量变少，无法满足激增的需求，这也使乘客转而使用小汽车完成长距离通勤，加剧了城市交通拥堵。常规公交、共享单车、短途接驳车辆的不舒适、不方便、不准时等问题，往往成为乘客放弃公共交通出行的主要原因。

近年来，基于深度学习的自动驾驶技术日益成熟^[1]，电动汽车在公共交通中也得到普及应用^[2]，无人驾驶电动公交以其低能耗、低运行成本的优势，可支撑多种条件下的集约化灵活调度，具有良好的发展趋势，将在未来建立绿色、安全、智能的公共交通系统中发挥其重要的作用。无人驾驶电动公交作为短途接驳公交使用时，不再受到人员排班约束，多轮次使用大大提高了接驳效率，能够实现精准路径规划和车辆智能调度，并且具有无污染低能耗的特点，可成为增强城市大运量交通工具吸引力的重要手段。针对无人驾驶电动公交这类新型交通形式，如何制定和优化车辆接驳路径成为有待研究的关键问题。

车辆路径问题(vehicle routing problem，VRP)一直是运筹学和组合优化研究中一个前沿热点问题。该问题由Dantzig等^[3]提出，并在后续进一步发展出带多个软时间窗约束的问题(vehicle routing problem with multiple soft time windows，VRPMSTW)。国外在此领域起步较早，Savelsbergh^[4]证明了VRPTW是一个NP-hard问题; Gendreaun等^[5]将禁忌搜索方法应用于VRP; 此后Crainic等^[6]使用模拟退火结合禁忌搜索对子问题进行求解; Taillard等^[7]重点研究了将禁忌搜索算法和遗传算法混合的启发式算法。潘帅等^[8]提出了带软时间窗的需求车辆调度问题及其禁忌搜索算法; 胡钟骏等^[9]提出了改进遗传算法以研究可拆分车辆路径; 此外，许多学者还将更多现代启发式算法方法陆续引入VRPMSTW的求解中。针对国内具体情况，我国学者还对该类问题做出了很多有益的改进：张烜荧等^[10]以最小化车辆行驶总里程和最大化服务准时率为优化目标，研究了同时取送货车辆路径问题; 张书玮等^[11]考虑了电动车辆出行过程中存在的多种优化因素与约束限制，结合动态交通环境制定了基于多目标优化的出行策略; 李楠等^[12]则在多时间窗车辆路径问题的基础上考虑了客户需求的模糊性，设计了两阶段混合优化求解算法; 刘虹等^[13]针对多行程配送过程建立多目标优化模型，同时满足客户对配送时间和服务次数的要求; 王正武等^[14]以系统总运行成本最小为目标，提出了动态需求与行程时间下响应型接驳公交路径优化模型，能够改善发车频次、总运行时间以及座位利用率; 范文豪^[15]系统分析了需求响应式接驳公交的特点，并以企业运营成本和乘客时间惩罚成本之和最小为目标函数，建立了接驳公交路径优化模型。

尽管现有研究能够一定程度上为无人驾驶接驳公交路径问题提供解决方案，但目前一般基于均质化假设，即人群对服务质量的要求相同，而对于异质化需求的车辆调度与路径优化研究不多，未能充分考虑乘客在准时性、快捷性、舒适性等方面的需求差异。为此，本文提出面向异质化需求的无人驾驶电动公交接驳路径优化模型，为将来我国城市短途接驳服务提供可靠的解决方案。

1 异质化需求分析 1.1 异质化需求问卷

为解异质化需求特点，本研究通过调查问卷，针对北京市在职人员的出行需求进行调研。回收有效问卷251份，其中男性127份，女性124份，平均年龄32.6岁(STD=7.33)，平均通勤时间56.5 min(STD=23.8 min)。

受访者针对准时性、快捷性、舒适性进行了打分，打分方式参考NASA-TLX量表设计可移动滑动条，使打分结果保留一定的模糊性的同时，通过连续值刻画其大小。打分范围为(0, 1]，最高分为1分别表示“必须绝对准时来接我，不要让我等，1分钟都不行”“必须最快速度把我送到公交/地铁站，晚一点都不行”“车内空间足够大，最好就我一个人在车上”3类极端需求。异质化需求统计结果如表 1所示，可见人群中需求偏好的异质性，为后续优化模型的建立提供了背景与必要性支撑。

考虑到乘客在对3项异质化指标打分相同的情况下指标本身可能存在的权重差异，针对不同需求指标进行两两对比，分别有55.5%、36.8%、7.7%的受访者对准时性、快捷性、舒适性有更高的要求，可用于计算指标的相对重要程度。通过进一步分析不同偏好人群特点，可以发现对准时性、快捷性、舒适性要求更高的人群在出行方式、收入水平以及放弃公交地铁出行的主因等方面的结构差异，如图 1所示。对准时性、快捷性要求更高的人群更愿意使用地面公交或地铁出行，而舒适性要求较高的人群更青睐网约车或私家车出行，且月收入水平8 000~20 000元居多。对准时性要求更高的人群更可能因为距离站点较远而放弃公交地铁出行，对快捷性要求更高的人群更可能因为行程时间较长而放弃公交地铁出行，而对舒适性要求更高的人群更可能因为特殊天气难以换乘而放弃公交地铁出行。通过对不同需求属性的打分情况，可拟合获得用户异质化需求偏好分布，如图 2所示，图中概率密度大于1表示在该打分系数附近的概率陡峭程度较大，在该系数附近邻域内积分后所得概率也偏大。该分布可用于后续优化案例中模拟生成更为真实的用户需求。

1.2 异质化需求惩罚费用

根据接驳车辆到达乘客上车点的准时程度、到达终到站点的快捷程度以及车内的空间占用程度，本文通过式(1)-(3)刻画对准时性、快捷性、舒适性3类异质化需求的惩罚费用。

车辆的准时性需求惩罚费用表示如下：

$ C_{\mathrm{ou}}= \begin{cases}0, & a_{u} \leqslant t_{u} \leqslant b_{u} ;\\ \gamma_{1} p_{1} O_{u} q_{u}\left(t_{u}-b_{u}\right), & t_{u}>b_{u}.\end{cases} $

(1)

其中：u={1, 2，…, n}为订单节点编号，a_u为订单u的最早期望服务时刻，假设乘客自a_u开始等待; b_u为订单u的最晚期望服务时刻; t_u为车辆到达订单u相对应物理点的时刻; γ₁为准时性系数相对于快捷性、舒适性两两比较得到的相对重要性比例系数，根据问卷所得权重该系数取值为0.555; p₁为车辆准时性超出乘客期望服务的单位时间惩罚费用; O_u为订单u对于准时性的打分系数，可由用户对准时性指标打分情况等比放大获得或由准时性需求偏好分布模拟生成，取值范围为(0, 100]; q_u为订单u相对应物理点的乘客数。

车辆的快捷性需求惩罚费用表示如下：

$ C_{\mathrm{du}}= \begin{cases}0, & T_{n+1}^{k r} \leqslant \mathrm{DT}_{u} ;\\ \gamma_{2} p_{2} D_{u} q_{u}\left(T_{n+1}^{k r}-\mathrm{DT}_{u}\right), & T_{n+1}^{k r}>\mathrm{DT}_{u}.\end{cases} $

(2)

其中：u=0为车辆出发站点，u=n+1为接到n个订单乘客后的车辆终到站点; T_n+1^kr为第k辆车第r轮次到达终到站点的时刻; DT_u为订单u期望车辆到达终到站点的时刻; γ₂为快捷性系数相对于准时性、舒适性两两比较得到的相对重要性比例系数，根据问卷所得权重该系数取值为0.368; p₂为车辆快捷性超出乘客期望服务的单位时间惩罚费用; D_u为订单u对于快捷性的打分系数，可由用户对快捷性指标打分情况等比放大获得或由快捷性需求偏好分布模拟生成，取值范围为(0, 100]。

车辆的舒适性需求惩罚费用表示如下：

$ C_{\mathrm{su}}= \begin{cases}0, & Q_{n+1}^{k r} \leqslant \mathrm{EQ}_{u}; \\ \gamma_{3} p_{3} S_{u} q_{u}\left(Q_{n+1}^{k r}-\mathrm{EQ}_{u}\right), & Q \geqslant Q_{n+1}^{k r}>\mathrm{EQ}_{u}.\end{cases} $

(3)

其中：Q_n+1^kr为第k辆车第r轮次到达终到站点时的载客量; EQ_u为订单u期望车辆内乘客数量; Q为车辆最大容量; γ₃为舒适性系数相对于快捷性、准时性两两比较得到的相对重要性比例系数，根据问卷所得权重该系数取值为0.077; p₃为车辆舒适性超出乘客期望服务的单位人惩罚费用; S_u为订单u对于舒适性的打分系数，可由用户对舒适性指标打分情况等比放大获得或由舒适性需求偏好分布模拟生成，取值范围为(0, 100]。

2 接驳路径优化 2.1 模型构建

面向异质化需求的无人驾驶电动公交接驳路径优化问题可描述为：无人驾驶电动公交在一定的服务区域内为周边有出行需求的居民提供接驳服务，接驳车辆以地铁站为场站出发根据提交的订单对乘客依次提供自动化接驳服务，并在最大程度上满足乘客的异质化需求，最终接驳乘客至地铁站形成闭环，尝试解决乘客出行过程中连接公交地铁等公共交通方式站点与起讫点的接驳问题。

模型假设：1) 服务区域内有多个订单和1个地铁站点，每个订单对应1个实际的物理点，每个订单可以有一名或多名乘客，订单异质化需求已知，地铁站点位置确定; 2) 同一订单的每个乘客对车辆准时性、快捷性和舒适性的要求一致; 3) 接驳车辆在各物理网点间行驶过程中，保持一定的速度匀速行驶，不考虑交通拥堵、交通事故以及车辆抛锚等特殊交通状况对接驳车辆车速的影响; 4) 换乘车站和各物理网点互相通达，每2个物理网点之间的距离和最短行驶时间固定且已知; 5) 乘客在整个途中只上不下，在地铁车站统一下车; 6) 服务区域内所有订单均被服务，不存在被拒绝的情况; 7) 每一辆接驳车辆都从地铁站点出发，依次服务物理网点，最后返回原地铁站点。

本研究建立的接驳路径优化模型如式(4)-(20)所示，式中符号说明见表 2。其中，z₁为无人驾驶电动公交的走行费用，z₂、z₃、z₄分别为准时性、快捷性和舒适性的惩罚总费用。对于本文的研究重点，即各项用户异质化指标的惩罚费用，本文采用一定的换算系数，即前文中式(1)-(3)，将公交运营企业没有满足旅客异质化需求部分的超额情况换算为公交企业的成本，与车辆运营成本线性加和作为目标函数。由于接驳车辆采用无人驾驶电动公交，因此可忽略有人驾驶问题中连续工作时间、司乘排班计划、人工成本等相关约束及计算，最大程度上降低模型运算复杂度和求解难度。

$ \min z=z_{1}+z_{2}+z_{3}+z_{4}, $

(4)

$ z_{1}=\sum\limits_{u \in N} \sum\limits_{w \in N} \sum\limits_{k \in K} \sum\limits_{r \in R} C_{1} X_{u w}^{k r} d_{u w}, $

(5)

$ z_{2}=\sum\limits_{u \in N} \sum\limits_{w \in N} \sum\limits_{k \in K} \sum\limits_{r \in R} C_{\mathrm{ou}} X_{u w}^{k r}, $

(6)

$ z_{3}=\sum\limits_{u \in N} \sum\limits_{w \in N} \sum\limits_{k \in K} \sum\limits_{r \in R} C_{\mathrm{du}} X_{u w}^{k r}, $

(7)

$ z_{4}=\sum\limits_{u \in N} \sum\limits_{w \in N} \sum\limits_{k \in K} \sum\limits_{r \in R} C_{\mathrm{su}} X_{u w}^{k r} $

(8)

$ {\rm{s}}{\rm{. t}}\\ \sum\limits_{w \in N} \sum\limits_{k \in K} \sum\limits_{r \in R} X_{u w}^{k r}=1 ; $

(9)

$ \sum\limits_{w \in N} X_{u w}^{k r}-\sum\limits_{w \in N} X_{u u}^{k r}=0, \quad \forall k \in K, \quad \forall r \in R ; $

(10)

$\sum\limits_{w \in P} X_{0 w}^{k r}=1, \quad \forall k \in K, \quad \forall r \in R ; $

(11)

$ \sum\limits_{w \in P} X_{w, n+1}^{k r}=1, \quad \forall k \in K, \quad \forall r \in R ; $

(12)

$ \sum\limits_{u=0}^{n} \sum\limits_{w=1}^{n+1} d_{u w} X_{u w}^{k r} \leqslant D, \quad \forall k \in K, \quad \forall r \in R ; $

(13)

$ \sum\limits_{k \in K} \sum\limits_{w \in N} X_{0 w}^{k r} \leqslant K, \quad \forall r \in R ; $

(14)

$ Q_{u}^{k r}+q_{u}=Q_{w}^{k r}, \\ \forall k \in K, \forall r \in R, \forall u \in P, \forall w \in P, u \neq w; $

(15)

$T_{u}= \begin{cases}a_{u}, & t_{u} \leqslant a_{u} ;\\ b_{u}, & t_{u}>a_{u};\end{cases} $

(16)

$ Q_{u}^{k r} \leqslant Q, \quad \forall k \in K, \quad \forall r \in R, \quad \forall u \in N ; $

(17)

$ T_{0}^{k, r+1} \geqslant T_{n+1}^{k, r}+Q_{n+1}^{k, r} t_{m}, \quad \forall k \in K, \quad \forall r \in R ; $

(18)

$ T_{0}^{k r}+t_{0 u}=T_{u}, \quad \forall k \in K, \quad \forall r \in R ; $

(19)

$ \begin{gathered} T_{u}+q_{u} t_{m}+t_{u w}=T_{w}, \\ \forall k \in K, \forall r \in R, \forall u \in P, \forall w \in P, u \neq w . \end{gathered} $

(20)

考虑主要约束条件包括：1) 容量限制，在进行服务过程中，所接受的乘车需求不能超出车辆的容量限制，式(17)，即接驳过程中车上乘客数量始终不超过车辆的承载能力; 第k辆车第r轮到达u节点时载客数与u节点乘客数之和等于到达w节点时载客数，式(15); 2) 时间窗限制，同一时刻同一辆车不可出现在不同地点; 第k辆车第r轮到达w节点时刻等于到达u节点与u节点到w节点间服务时间之和，式(20); 接驳车辆下一次出发时刻在上一轮服务结束后，式(18); 3) 里程数限制，里程数不能超过最大里程数的限制，式(13); 4) 最大车辆数限制，每轮运行车辆均不超过车辆总数，式(14); 5) 其他基本限制，每个订单都能得到服务且只服务1次，式(9); 接驳车辆到达每个需求点进入数和从需求点出发数相等，式(10); 起始站与终点站的流平衡约束，式(11)、(12); 车辆在车站开始服务时间约束，式(16); 到达与离开站点时间间隔约束，式(19)。

2.2 禁忌搜索算法求解

本文所研究的VRPMSTW问题是VRP的一个变种，属于典型的NP难问题，精确算法尚无法有效求解实际规模级的该问题。现有研究在求解实际规模的VRP问题多采用禁忌搜索、邻域搜索、遗传算法等更具搜索广度的元启发式算法，而其中尤以禁忌搜索方法的应用最广^[16]。禁忌搜索算法通过系统地引入和运用禁忌表、禁忌长度和藐视规则，可有效避免不合理的重复搜索，进而提升解的质量。鉴于求解算法并非本文创新点，本文采用元启发式随机搜索算法--禁忌搜索算法对模型进行求解。在禁忌搜索算法中，局部搜索是算法框架中的核心部分，在很大程度上决定最优解的质量。在选择局部搜索算子时，经过组合实验，并对结果和运行时间进行分析之后，针对性地设计了2-opt、2-exchange、GES算子作为本文算法中的局部搜索算子，实现功能如下：

1) 2-opt算子：随机选择访问的订单序列中除出发和到达点外任意两节点i和j，保持i之前的序列和j之后的序列不变，将i到j之间的序列翻转，得到新序列集。

2) 2-exchange算子：随机选择序列集中除出发和到达点外任意两节点i和j，将节点i和j互换位置，得到新序列集。

3) GES算子：在降低使用的车辆数目方面具有十分明显的效果。通过不断尝试删减一个序列，并将此序列上的订单插入其他序列，并进行时间、车辆载重约束的检查，从而降低车辆的使用数目。

3 案例分析与方案评价 3.1 案例分析

本研究选取北京市丰台区丰台科技园地铁站及周边地区为案例，得出面向异质化出行需求的短途接驳共享出行路径规划结果，并与传统方案进行对比。根据区域特点，选择19个需求生成点，区域路网需求点分布如图 3a所示。使用Floyd最短路算法得出2点间最短距离和行驶时间，生成路网距离矩阵及时间矩阵，由此搭建路网拓扑结构如图 3b所示，各路网节点间标注数字表示最短距离。

本研究使用调查问卷对北京市在职人员的出行需求进行调研，根据用户异质化需求指标的偏好分布，生成1 h内100个模拟订单需求。使用Python语言，在CoreTMi7双核处理器(2.40 GHz)，内存16 GB的微机上实现模型求解。候选集合长度设置为50，禁忌表长度设置为20，迭代次数设置为200。根据算法求解结果，可得出接驳车辆调度方案，绘制订单访问顺序图。如图 4为一次求解第一轮线路的优化结果线路图。

为测试算法稳定性，本文生成了20组样例数据，每组包含100个模拟用户订单，每组数据均使用该算法测试了10次，每次迭代至第100代(即共运行200次算法程序)。经过计算，求解时间介于67.998~120.999 s，在可接受范围内。在200次运算中，最优目标函数值为167.71，较均值低37.51，占平均值的81.72%，算法较为稳定。

3.2 方案评价

传统的接驳公交规划不考虑异质化需求，认为所有旅客的需求趋于同质化，其派车方案可通过改写本模型中的3项异质化需求打分系数为相同平均值进行求解获得。相比于传统的接驳公交规划方案，本研究优化方案充分融合了不同出行者的个性化偏好，即考虑旅客的异质化出行需求。旅客的准时性、快捷性与舒适性需求满意度指标分别由等待时间、行程时间、车上人数决定。如图 5所示给出了传统方案与考虑异质化需求方案在出行者不同指标的满意度与其对该指标的偏好程度间的关系。以准时性为例，如图 5a，可见本文提出的模型能够更好地满足旅客对准时性的要求，即准时性系数越高，所需等待时间相对越少，而传统方案并未呈现这一效果。类似地，针对快捷性与舒适性，本文的优化方案也更能适应旅客需求，如图 5b-5d所示。对应不同舒适性系数区间的指标分级如表 3所示。

研究结果还发现，考虑异质化出行需求前后不同订单不同指标的满意度变化情况不一，这是由于这些出行者对不同指标的侧重程度不同。为综合考虑不同异质化需求的满足度，提出异质化需求满足度综合指标计算方法，如式(21)所示，其中，分子项为计算结果对用户3项异质化需求的实际满足度指标(w_ou，w_cu，w_su)，包括实际等待时间、行驶时间以及车上人数情况; 分母项为用户对3项异质化需求提出的指标要求(w_ou^*，w_cu^*，w_su^*)，包括期望等待时间、期望行驶时间、期望车上人数。针对异质化需求指标情况设置满足度计算方式，如取w_ou^*为期望等待时间的倒数，当实际等待时间比期望等待时间更长时，等待时间这一指标满足度将小于1，而该值越小则表明对该指标满足度越低。根据本文优化模型求解获得派车方案，将考虑异质化出行需求前后结果对需求的满足度综合指标值对比，结果如图 6所示。本文提出的方法在给定案例中平均需求满足度达到84%，满足订单比例相较于传统方法提高40%。

$ W=\frac{1}{3}\left(\frac{w_{\mathrm{ou}}}{w_{\mathrm{ou}}^{*}}+\frac{w_{\mathrm{cu}}}{w_{\mathrm{cu}}^{*}}+\frac{w_{\mathrm{su}}}{w_{\mathrm{su}}^{*}}\right) . $

(21)

4 结论

本文研究了面向异质化需求的接驳路径优化问题，得到主要结论如下：

1) 人群中需求偏好存在异质性，根据问卷调查结果，分别有55.5%、36.8%、7.7%的受访者对准时性、快捷性、舒适性有更高的要求，对准时性、快捷性、舒适性要求更高的人群在出行方式、收入水平以及放弃公交地铁出行的主因等方面存在结构差异。

2) 通过模型构建和求解，本文提出的无人驾驶电动公交接驳路径优化方法求解时间介于67.998~120.999 s，在可接受范围内，在200次运算中最优目标函数值为167.71，较均值低37.51，占平均值的81.72%，算法能够快速稳定求解。

3) 充分考虑乘客对准时性、快捷性、舒适性的异质化需求，本文提出的方法在给定案例中平均需求满足度达到84%，满足订单比例相较于传统方法提高40%。