一种基于多时间窗口需求响应接驳服务优化

朱晓锋

（广州松田职业学院 信息工程学院，广东 广州 511370）

固定路线公交网络和居民区连接的最后一公里接驳是公共交通面临的主要挑战之一。解决该问题的可行方法是规划﹑设计和实施高效的支线运输服务［1］。传统上，运输服务分为两大类：固定路线（FRT）和需求响应（DRT），FRT 不符合个人旅行的需求（接送地点或者下车地点的位置）和预定的时间表，而DRT 则提供门到门式的服务［2］。因此，与FRT 相比，DRT 能提供更高的便利性以及更低的运营成本和更高的服务水平，尤其在低密度住宅区内。

DRT 是带时间窗的车辆路径选择问题（VRP）和提货运输问题（PDP）的扩展［3］。类似于具有多个时间窗口的VRP［4］，具有多个时间窗口的DRT 可以比单个时间窗口问题节省更多的里程。为了满足乘客个性化的出行需求，设定乘客的最大和最小预期乘车时间，在不增加其他乘客在途时间的情况下追求最短的路线距离。

本文研究的另一个主要动机是要解决DRT 的乘客满意度问题，其中涉及许多因素，例如公交车票价，交通拥堵和环境等。一些文献研究了考虑顾客满意度的VRP，但涉及DRT 的较少［5］。在不失一般性的前提下，它仅与支线运输操作中的预期乘车时间有关，即当乘车时间在最小和最大期望值之间时，满意度范围为0 到1。显然，更大的乘客满意度和更多的车辆提供直接服务，这将增加总里程和运营支出。因此，有必要研究乘客满意度和总里程之间的最佳关系，以权衡服务质量和运营成本。

本文研究的主要目的是开发一种基于乘客多个时间窗口与满意度的DRT 优化模型，以提高服务质量和降低运营成本。重点研究以下两个关键问题：1）协调乘客上车时间窗引导和支线运输路线选择过程，以权衡总里程数和乘客满意度；2）开发一种启发式求解算法，以有效地产生所提出模式的可接受解。最后，通过实例仿真证明所提出的方法，并将该模型应用于实际的DRT 优化设计过程中。

1 问题描述

DRT 是一种门到门的运输服务，可为需求响应型乘车人员的接驳问题提供解决方法［6］。人们通常将其描述为基本车辆路径和调度问题的扩展［7］，其中：车辆路径问题（VRP）分配了一些车辆访问一组地理位置分散的位置，接送问题（PDP）将货物数量从某些取货地点移动到某些交货地点。但是，到目前为止讨论的VRP 和PDP 与DRT 之间也存在明显差异。VRP 和PDP 专注于货物运输，而DRT 则关注人员运输。因此，与VRP 和PDP 相比，DRT 解决了更多其他问题，并且更加复杂。对于DRT 的回顾，它们大多数与服务和乘客便利性有关。由于FRT 人口密度低而效率不高，因此在这些调度区域，尤其是交通基础设施薄弱的地区，DRT 表现更好［8］。

一般情况下，乘客是在特定的时间窗口中乘车的，从而导致具有时间窗口的VRP（VRPTW）和具有时间窗口的PDP（PDPTW）［9］。对于VRPTW 和PDPTW 的最新回顾，当车辆返回停车场后可以立即采取另一条路线时，会出现另一种变化形式，称为多次使用车辆的路线问题［10］。DRT 都是通过各种目标解决的，包括最小化车队以降低运营成本，路线的最短长度或行程时间［11］，所需的最小车队规模班车服务［1］，乘车时间和乘客等待时间。巧合的是，目标通常不会影响DRT 的属性，可以采用类似的模型和算法来解决具有不同目标的问题。

DRT 问题属于NP 难题，启发式方法是最常用于DRT 以处理大量的车辆路线和调度方式。一些学者试图通过先生成一组可行的路径，然后搜索微调初始解来发展路径构建启发式方法［3-4］。除了已开发的基于路径构建的启发式算法外，还经常采用三种广泛使用的元启发式方法来应对VRPTW，例如进化算法［3］，禁忌搜索［7］和遗传算法［10］。

本文提出一种DRT，其提供的服务可以方便地将需求点的乘客运送到火车站［1］。利用手机APP 和开放的GIS 工具，我们可以获取研究区域内部分乘客的出行信息、交通网络。每位乘客都有一个或几个可选的上车时间窗口，以及一个最小和最大的预期乘车时间。在设计路线的过程中，每辆车都从停车场开始，到火车站结束，在指定的时间段内访问需求点接驳乘客，以满足诸如时间窗和预期乘车时间等现实约束条件。揭示接驳巴士路线设计效率与乘客满意度和总里程之间的最佳关系，建立混合整数规划模型以设计从选定的需求点到火车站的路线，并从多个优选的时间窗口引导需求点的乘客在指定的时间段内出行［12］。

我们的目标是找到同时将旅客满意度降低的损失和设计的支线路线的总里程成本降至最低的模型。为了确保提出的DRT 模型与实际情况完全吻合，本研究做以下假设：

1）允许需求点的乘客在一个或几个首选时间窗口内上车。调查火车站周围每个需求点的乘客数量，不考虑他们之间的乘客流量。

2）需求点﹑停车场和铁路站点之间的距离和行驶时间是使用百度GIS 获取的。

3）每个需求点只能被一辆车辆覆盖一次。

4）乘客的满意度与乘车时间无关，乘客满意度下降的损失可以估计。

2 模型建立

为了便于模型表示，表1 中汇总了下文中使用的所有定义和符号。

表1 数学模型中的参数和变量

将所提出的问题表示为以下混合整数规划（MIP）：

在该公式中，目标函数由式（1）表示，以使乘客满意度降低的损失和设计支线的总里程成本最小化。约束（2）表示每辆车至少访问一个需求点。约束（3）保证每个需求点仅由一辆车辆覆盖。约束（4a）和（4b）保证每辆车最终都在停车场候选点启动。约束（5a）和（5b）确保每辆车最终都在火车站结束。约束（6）将车辆服务的每个需求点（火车站和停车场除外）设置为具有完全相同的进出弧。约束（7）用于车辆路径中的子行程消除。约束（8a）和（8b）用于计算车辆k覆盖的相邻需求点i和j的到达时间。约束（9）保证了车辆k到达需求点i的时间满足其多个行驶时间窗口的一个；约束（10a）和（10b）用于计算车辆k覆盖的相邻需求点i和j的负载能力。约束（11）保证每条路线上的乘客人数必须小于车辆的载客量。约束（12）和（13）确保每条路线的行驶距离和时间必须满足其上限和下限。

3 用于解决DRT 改进的Bat 算法

所提出的模型是VRP 的扩展，其精确算法无法在可接受的时间内解决大规模实例。蝙蝠算法（BA）是一种群体智能算法，用于模拟蝙蝠在猎物中的回声定位行为［13］。为了避免BA 的不成熟收敛，将BA 与其他智能算法相结合是解决该问题的有效方法。群组搜索优化器（GSO）是一种群体智能算法，可以模拟自然界中动物的行为以寻找生存资源。BA和GSO 之间的同源性决定了它们具有自然的融合特性［14］，目前很少见到混合算法。

在本文中，设计了一个混合BA 来解决DRT 问题，根据问题的特点重新定义了编码方案、生成初始种群的启发式算法、更新的位置和速度公式。

3.1 编码方案

每只蝙蝠具有位置和速度两个特征，在解搜索空间中抽象为一个潜在解。速度矢量是蝙蝠的运动方向。根据问题的特点，构造了DRT 的位置向量X=（x1，x2，…xI+K），包括两部分：元素xi（1≤i≤│I│）为需求点编号，元素xi（│I│+1≤i≤│I│+│K│）为车辆编号。它们都是实数。根据该值xi，确定车辆和需求点在向量中的位置，从而得到任意车辆访问需求点的顺序。基于贪心原理，我们也知道车辆从哪个停车场出发。例如2 辆车4 个需求点的可行解决方案为（0.1 1.3 0.4 0.7 0.2 0.5），两条车辆路线为4-2-1 和3。

3.2 适应性评估

根据解决方案的编码规则，每个候选解决方案必须满足约束（3）～（7），并且可能违反约束（10），（12）～（14）。为了解决这个问题，我们将那些约束作为惩罚项纳入适应性评估功能中。因此，在本文的研究中，修正的目标函数如下：

本文的目标函数直接用于评估个人的满意度。

3.3 生成初始种群的启发式算法

影响DRT 模型的许多复杂因素导致难以随机生成对此问题的一种可行的解决方案。因此，设计了一种启发式算法来生成初始种群，具体步骤如下：

步骤1：读取DRT 模型的输入数据，包括：I、M、Q、Dmax、Tmin.

步骤2：随意选择停车场m，然后让i=m和N'=I。对于位于停车场的每辆车km，转到第3 步以构建路线。

步骤4：N'=N'-{j}。如果N'=Ø，输出结果；否则，请转到步骤3。

3.4 蝙蝠速度和位置的更新规则

在混合BA 中，每个蝙蝠i当时会自我更新t如果所有蝙蝠都聚集在同一位置，则通过跟踪全局最优值，导致拒绝搜索其余解空间。从GSO 的想法中汲取了教训，即“少数群外流浪随机行走”，一些蝙蝠随机产生头角和距离，并交换部分矢量位置以遍历解空间以保持群的多样性。在t时间对每个蝙蝠i的位置和速度进行更新的公式如下：

其中，fi=fmin+（fmax-fmin）β（β∈［0，1］）是每个蝙蝠的回声频率i；X*表示当前的全局最优解；li是介于0 和最大搜索距离之间的随机距离lmax；φt+1是介于0 和最大搜索角度之间的随机头角θmax；表示对应于该角度的向量；ε，β和rand是间隔［0，1］中的均匀分布的随机数。

3.5 蝙蝠的本地搜索规则

当所有蝙蝠逐渐收敛到同一位置时，当前最优蝙蝠以一定的概率σ随机行走产生一个新的位置，其中At代表所有蝙蝠的平均响度；ε∈［0，1］是一个随机数。

3.6 混合蝙蝠算法的特定步骤

步骤1：初始化参数，包括m和Iter_max 等等。

步骤4：计算总体多样性以获得一定的随机干扰操作概率，并干扰当前对新位置的最优解X*=X*+εAt。重新排列所有现有的蝙蝠以更新当前的最佳解决方案。

步骤6：让t=t+1。如果t＜Iter_max，转到步骤3；否则，输出结果。

4 实例仿真

为了证明所提出的模型在设计支线公交网络到城市轨道交通中的适用性，本研究选择了一个火车站（M），六个停车场（D1-D6）和总共十五个需求点（C1-C15））在中国南昌市进行案例研究。图1为这些车辆访问点的分布图（百度），其中黄色圆圈代表停车场，红色小气球代表客户点，白色正方形代表火车站。表2 中显示了乘客数量及其在租车点中的首选时间窗口和预期乘车时间。案例研究中使用的关键参数如下：

图1 车辆需求点的空间分布

表2 需求点的基本信息

接驳公交线路最大载客量：Q=12；

车辆路线最大长度：Dmax+9 公里；

车辆路线的最短行驶时间：Tmin=3 分钟；

运营成本：c1=6.5 元/公里；

旅客满意度降低的损失：c2=1 元/人；

混合算法的参数：N=100，MaxIter=200，α=0.9，γ=0.9，lmax=5、θmax=45 °。

如前所述，该模型可以解决两个维度，即车辆接驳的乘客数量的分配以及车辆路线。表3 总结了分配结果，包括每个需求点的上车时间、乘车时间和满意度。以到达需求点C5 的车辆为例，车辆在8:15 离开停车场D1，8:27 到达火车站M，在需求点C5 的乘客8:17 上车，乘坐时间约为10.2 分钟。由于他们的预期乘坐时间为5 分钟到10 分钟，满意度的计算公式为（20-10.2）/（20-5）=0.65。表3 还指导乘客从几个首选时间窗口在指定时间段内出行。

表3 车辆接驳乘客的分配结果

表4 列出了每辆车的路线计划，其中为这三辆车选择了两个停车场D1 和D4。它们的总行驶里程分别为3.1 km，3.1 km 和3.0 km，它们的总行驶时间分别为12.2 分钟，12.5 分钟和12.1 分钟。从表2，3和4 中可以看出，路线的总里程和时间分别为9.2 公里和36.8 分钟，其总乘客满意度为96.4。也可以获取每个点的车辆载重量的变化。以路线1 为例，车辆将离开停车场D1，分别到达需求点C5，C6，C7，C8和C1，并在火车站M 处终止。一辆空车从D1 出发，该车辆首先在C5 停下来接驳两名乘客，因此C5 和C6 之间载有2 名乘客；然后，这辆车前往C6，载有三名乘客，因此C6 和C7 之间载有5 名乘客；然后这辆车前往C7，C8 和C15 接驳四名乘客，一名乘客和两名乘客，因此C7 和C8 之间分别为9，C8 和C15 之间分别为10，C15 和M 之间分别为12 和12。最后，这辆车拜访了M，以运送12 名乘客。在这种情况下，路线1 每个点的车辆装载量可描述为：{D1（0），C5（2），C6（5），C7（9），C8（10），C15（13），M（0）}，对于路线2 和3，类似地为：{D4（0），C14（1），C11（5），C12（6），C10（8），M（0）} 和{D4（0），C13（3），C2（4），C4（6），C3（7），C1（10），C9（12），M（0）}。

表4 每辆车的路线和调度计划

此外，与传统的DRT 相比，我们的研究具有其独特的功能。图2 揭示了所提出的模型与具有单一时间窗口的DRT（DRTSTW）之间的差异。与配备DRTSTW 的DRT 相比，提出模型的行驶里程和满意度损失将分别降低1.4 公里和7.1%。原因是车辆在多个时间窗口之一内的任何时间到达需求点将减少无效的行驶里程和时间。因此，在实际应用中允许乘客选择多个旅行时间窗口非常重要。如上所示，通过实例证明所提出的模型是有效的。

图2 提出模型与传统DRT 的结果比较

5 结论

本文提出了一种具有多个时间窗口的DRT 优化方法，以揭示总里程数与乘客满意度之间的关系。与现有研究不同，提出的方法具有以下特点：1）提供一个交互过程，设计支线运输路线并指导乘客选择最佳上车时间窗口；2）开发结合BA 和GSO 的混合算法，以有效地为所提出的模型提供可接受的解决方案。所提出模型的可行性和适用性以解决最优性的实例进行了说明。结果表明，与传统的DRT 模型相比，该模型的总行驶里程减少了15.2%，总满意度提高了7.1%。随着车辆数量的增加，总满意度和里程数都略有增加。