自动驾驶车辆公共交通系统：调度与准入控制

摘要

自动驾驶车辆（AV）技术正变得日益成熟，许多自动驾驶车辆将在不久的将来出现在道路上。在多种车载通信技术的支持下，自动驾驶车辆实现了联网，并具备高度可控性，能够以高效率和灵活性协同应对瞬时状况。本文提出一种基于自动驾驶车辆的新型公共交通系统。该系统管理一个自动驾驶车辆车队，以满足运输请求，并提供支持共享出行的点对点服务。我们重点关 注该系统的两个核心问题：调度与准入控制。前者旨在为自动驾驶车辆配置最经济高效的行程计划和路线，以满足可接受的请求；后者则是在所有请求中确定一组可接受的请求，以实现利润最大化。调度问题被建模为一个混合整数线性规划问题，而准入控制问题则被构建为一个双层优化问题，其中将调度问题作为主要约束嵌入其中。通过利用该问题的解析特性，我们开发了一种有效的基于遗传算法的方法来解决准入控制问题。我们使用真实世界交通服务数据对算法性能进行了验证。

关键词 —自动驾驶车辆（AV），准入控制，双层优化，汽车共享，智慧城市。

一、引言

HUMAN mobility在很大程度上依赖于公共交通。当出行目的地超出步行距离时，许多人依靠公共交通从一个地方前往另一个地方。为了将基础设施空间有限的城市转变为智慧城市，其公共交通系统可能需要主要基于现有的道路网络进行进一步升级。基于道路的公共交通代表是公交车和出租车，每种类型都有其优缺点。一般来说，公交车遵循固定路线，提供合乘服务，从而在每次行程中可以服务更多乘客。另一方面，出租车提供私人服务，并运行基于乘客请求的灵活专用路线。然而，单一类型的公共交通无法同时支持高吞吐量和高灵活性。如果存在一种新型公共交通，能够在短时间内容纳大量乘客并满足高流动性需求，则整个公共交通系统的效率和容量可能会得到提升。这种公共交通可通过提供点对点服务来保持灵活性，同时通过支持合乘服务来提高效率。此类公共交通需要具备一些典型公共交通所不具备的特性。为了开发这样的公共交通，车辆需要协同合作以响应客户请求，而不是在城市中巡航寻找随机订单。为了提高效率和协同性，可采用一个控制中心来协调所有车辆、管理所有服务请求，并分配车辆执行请求任务。此外，车辆应遵循指定路线并执行规划的行程，以实现系统整体目标。近年来，自动驾驶车辆（AV）正经历积极的研究，预计在不久的将来将有大量自动驾驶车辆上路运行。自动驾驶车辆是具备上述多数要求的理想候选者。因此，可采用自动驾驶车辆构建一种高效且灵活的新型智能公共交通系统。

在本文中，我们提出了一种基于智能自动驾驶车辆的公共交通系统。该系统管理一个自动驾驶车辆车队，以满足运输请求，并提供支持共享出行的点对点服务。我们重点关注该系统中的两个重要问题：调度和准入控制。前者涉及如何将指定车辆分配给可接受的运输请求，以及车辆应在何时何地到达以提供服务并实现最低成本；后者则是从所有请求中确定一组可接受的请求，以实现最大收益。

总体而言，本文的贡献包括：
- 提出自动驾驶公共交通系统；
- 改进了[1],中提出的调度模型，使得本文建立的建模现在能够同时支持有向图和无向图；
- 开发分布式调度；
- 制定准入控制问题；
- 引入可接受性的概念及相关分析结果；
- 设计一种有效的方法来解决准入控制问题；以及
- 使用真实世界交通服务数据验证求解方法的性能。

本文其余部分组织如下。第二节介绍相关工作，第三节介绍各种系统组件及其操作。第四节讨论调度问题。第五节中，我们对准入控制问题进行建模，并提供相关的分析结果。第六节提出一种基于遗传算法的准入控制求解方法，并开发分布式调度。第七节利用真实世界交通服务数据评估系统性能。最后在第八节总结全文。

II. 相关工作

自动驾驶车辆的概念在1920年代被提出，相关研究已开展三十多年。自动驾驶车辆配备了多种传感器，使其具备全面的感知能力，能够适应邻近环境并实现完全自动化控制。2007年，DARPA城市挑战赛提升了人们对能够在交通环境中行驶并执行复杂操作的自动驾驶车辆的认知[2]。2010年，VisLab开展了实验，几辆无人驾驶车辆成功从意大利行驶13,000公里到达中国[3]。谷歌在2011[4]展示了自动驾驶车辆原型。截至2013年底，美国包括内华达州、佛罗里达州、加利福尼亚州和密歇根州在内的多个州已通过法律，允许自动驾驶车辆在公共道路上行驶[5]。首款上市销售的自动驾驶接驳车来自NAVIA[6]。其他汽车制造商，如梅赛德斯‐奔驰[7],宝马和奥迪[8],，也已投资自动驾驶技术，并将自动驾驶车辆纳入生产计划。

关于自动驾驶车辆的研究工作主要集中在控制和通信方面。Mladenovic和Abbas[9]提出了一种用于分布式车辆智能的自组织与协同控制框架。Hu et al.[10]研究了联网自动驾驶车辆的车道分配策略，并提出了一种变道操作，以平衡效率与安全之间的权衡。Petrov和Nashashibi[11]开发了一种无需依赖道路标线和车辆间通信的自动驾驶超车反馈控制器。Li et al.[12]提出了一种基于多层级融合的道路检测系统，用于无人驾驶车辆导航，以确保在各种道路条件下的安全性。这些研究均表明，在政府、高科技公司和汽车制造商的支持下，自动驾驶车辆是一项前景广阔的技术。

车辆可以通过各种车载无线通信技术与彼此及固定基础设施进行通信[13]。如今，车载通信主要通过卫星、蜂窝网络和车载自组织网络（VANETs）部署[13]。VANET是一种移动自组织网络，其中车辆作为移动节点[14]，能够提升构成智能交通系统的自动驾驶车辆的通信容量和组织能力。Furda et al.[15]提出了一种面向无人驾驶车辆的无线通信框架，该框架促进了车对车和车对基础设施的通信，提高了车辆的安全性和效率。Alsabaan et al.[16]利用交通信号灯和车对车（V2V）通信帮助车辆调整速度，避免不必要的加速度和超速。Gomes et al.[17]设计了一种驾驶辅助系统，使车辆能够通过车联网通信从邻近区域的其他车辆收集实时摄像头图像。通过这种方式，自动驾驶车辆实现了联网，并能与控制中心通信。

最近对出租车服务的可共享性进行了研究。Santi et al.[18]研究了乘客不便与共享的集体效益之间的权衡，得出结论：乘客不适感的小幅增加可以带来显著的好处，包括更少拥堵、更低运营成本、更少分摊费用以及更少污染和更清洁的环境。Ma et al.提出了一种名为T‐Share的出租车拼车系统，在[19],中研究了动态出租车拼车问题。针对北京出租车服务的数据集显示，通过节省总行驶距离的13%，可额外服务25%的出租车用户。这些研究证实了拼车服务的益处，但主要集中在传统出租车服务上。本文则聚焦于自动驾驶车辆，其具备传统出租车难以实现的一个关键内在特性：车辆的直接控制不涉及任何人为因素。换句话说，自动驾驶车辆能够完全遵循控制中心的指令，既不会承接未分配的请求，也不会拒绝已分配的请求。可以看出，自动驾驶车辆能够充分协作以实现系统目标，而人工驾驶出租车则可能无法做到这一点。

自动驾驶公共交通系统经过独特设计，有助于提高未来交通系统的容量和灵活性。该系统已在[20],中扩展为多租户系统，其中引入了新的服务类型并解决了定价问题。为了进一步证明其可行性，我们在表I中展示了上述现有研究如何为系统做出贡献。

调度问题已在[1]中提出，可被视为预约出行问题（DARP）的一种变体[21]。然而，在我们的自动驾驶车辆调度问题中，允许在合适的时间修改先前已分配但尚未服务的请求，以实现全局性能目标。随着系统的发展，自动驾驶车辆在不同的时间点出现在不同的位置。在不同时 间，特定的请求可能由不同的自动驾驶车辆更好地提供服务。考虑一个包含两辆自动驾驶车辆（AV‐I和AV‐II）的例子：在某一时刻，AV‐I位于某地点的邻近区域，而AV‐II不在该区域，因此来自该地点的请求由AV‐I服务可能更为合适；一段时间后，AV‐I可能已离开，而AV‐II可能已进入该邻近区域，此时该请求由AV‐II服务可能更优。由于自动驾驶车辆通过适当的车载通信技术实现联网，自动驾驶车辆的调度计划可以不时进行调整。我们在建模中考虑了这一点，从而使我们的调度问题不同于传统的DARP。由于系统涉及多辆自动驾驶车辆，以分布式方式确定其行程计划无疑能够加快处理速度。分布式调度已在许多工程学科中得到发展，例如通信网络[22],[23]。作为一种新型系统，我们将专门设计一种用于该系统调度的分布式方法。

准入控制通常指通信系统中用于服务质量保证的验证过程。确定哪些新的连接或服务请求可以在后续操作中获得资源支持。例如，[24]为4G无线网络设计了一种准入控制机制，用于添加或丢弃会话请求，而[25]讨论了多业务IP网络中的各种准入控制算法。我们将这一思想应用于交通系统，并设计一种准入控制机制，以区分交通服务请求，从而最大化总利润。有许多方法可以实现准入控制，遗传算法（GA）是其中之一，已成功用于设计准入控制机制，例如[26]和[27]。基于准入控制问题的特殊建模（将在第五节中讨论），我们也将采用GA来解决该问题。

三、系统模型

在本节中，我们设计了能够管理自动驾驶车辆车队以为客户提供交通服务的系统架构。接下来，我们首先介绍系统组件，然后描述表征这些组件交互的操作。

A. 系统组件

1) 网络结构 ：采用图来建模系统服务的区域。它描述了位置和道路连接，以必要地表示移动情况。自动驾驶车辆的服务请求的出发地和目的地，以及其他必要设施。它是一个有向图，表示为G(V, E)，其中V是一组位置，E指连接这些位置的道路路段，从而可以使用G完整描述自动驾驶车辆的路线。对于i, j ∈ V，每条边(i, j) ∈ E都关联一个运营成本cij和行驶时间tij，后者是基于历史数据对自动驾驶车辆从i行驶到j所需时间的估计。根据系统目标，cij通常表示道路路段(i, j)的距离，因为自动驾驶车辆的运营成本通常以燃油消耗来衡量，而燃油消耗又由行驶距离决定。如果系统旨在优化总服务时长，则可将所有(i, j)的cij= tij设置为此值。我们允许cij ≠ cji和tij ≠ tji反映道路路段的不对称性。此外，加油站在某些指定位置˜设置于V ⊂ V中，每辆自动驾驶车辆可在其中任意一个加油站结束行程（原因见第三节-B1）。根据自动驾驶车辆的特性，若自动驾驶车辆为电动车（传统车辆），则V ⊂ V对应充电（加油）站的位置。对于电动车的情况，V ⊂ V可根据充电需求以及充电站网络的连通性按照[28]确定。

2) 运输请求 ：客户以运输请求的形式请求服务，这些请求collectively记为R。每个r ∈ R由五元组〈sr, dr, Tr,[er, lr], qr〉表示。sr ∈ V和dr ∈ V分别表示客户的上车和下车地点。Tr是最长乘车时间，超过该时间将导致客户不满。[er, lr]指服务开始时间窗口，其中er和lr分别是最早和服务最晚开始时间。qr表示请求r中所需的座位数。

3) 车辆 ：系统协调一个由K表示的自动驾驶车辆车队。每个k ∈ K由五元组〈ak, t0k , T˜k, Qk, Rk〉表示。ak ∈ V是k将从k的当前位置出发访问的第一个位置，而t0k是从其当前位置到达ak所需的时间。在调度时，自动驾驶车辆可能正位于前往ak的道路段中间。通过向系统提交˜其当前位置，可以轻松估算ak和t0k。Tk表示k在无需加油的情况下可继续提供服务的最大剩余运行时间。Qk是k可同时容纳的乘客容量。Rk= Rk ∪ Rk ∈ R是先前分配给k的请求集合。Rk可进一步˜分为两种类型；Rk包含当前正在由k提供服务的请求，而Rk是在先前的调度中已分配给k但服务尚未实施的请求。对于前者，˜部分座位已被来自Rk的乘客占用。相反，座位仅被预留，但尚未实际˜占用Rk的座位。我们将在第四节的调度过程中对Rk和Rk进行不同处理。

不失一般性，我们假设任何请求中所需的座位数不超过任何车辆的容量，即
$$ qr ≤ Qk , ∀ r ∈ R, k ∈ K. (1) $$
k的最大剩余运行时间可以从其相应的燃油量转换得到。我们总可以将违反条件(1)的请求拆分为多个请求，以确保该条件始终成立。

B. 操作

该系统由一个控制中心管理和运行，其主要职责是收集所有所需信息，并将自动驾驶车辆分配用于满足运输请求。系统以固定的时间间隔运行，每个时间间隔被划分为数据收集和任务分配子区间（见图1）。在每个间隔内，控制中心首先在数据收集子区间内收集运输请求和车辆状态。然后在任务分配子区间内将自动驾驶车辆分配以服务运输请求。一方面，每个间隔的持续时间应足够长，以确保通信延迟不会导致客户和车辆在调度过程中的任何数据丢失；另一方面，该持续时间又应足够短，以确保所收集的数据能够反映该间隔内的当前情况。实际上，数据收集子区间比任务分配子区间更长，前者可能持续几分钟，而后者可能仅需几秒钟。

图2展示了系统在运行区间内的操作流程。通过多种无线车载通信技术的支持，所有自动驾驶车辆均处于联网状态，并能与控制中心即时通信。这样，控制中心可以在数据收集子间隔内收集必要的车辆状态信息，例如自动驾驶车辆的当前位置、请求服务确认情况、交通拥堵信息等。客户也可以通过适当的途径（如电话、移动应用等）向控制中心提交他们的请求。在数据收集子间隔结束后，控制中心已准备好执行任务分配所需的所有数据。

在任务分配子区间内，控制中心处理收集到的数据并计算任务分配。由于之前系统条件下不适合，可能存在一些来自先前区间的未处理请求。这些请求将与新提交的请求合并，并被统一考虑en masse。任务分配进一步包含两个过程：准入控制和调度。准入控制检查所有待处理的请求，并确定哪些请求将在当前区间被接纳。未通过请求将保留至下一区间再次考虑。任何无效或不合适 的请求也将在准入控制过程中被永久排除。在调度过程中，我们计算自动驾驶车辆的行驶计划，以服务已接纳的请求。如果一辆车辆被分配了请求，则其由控制中心确定的行程计划需要满足以下要求：

1) 完整路线规划 ：由于车辆是无人驾驶的，我们需要指定精确的路线，以便车辆能够按照该路线行驶，接载已分配的请求中的乘客，并将其送至所需的目的地。此外，路线应足够短，以确保车辆有足够的燃料完成整个行程。车辆最终应抵达一个加油站，以避免在道路路段中途抛锚。这可以保证车辆在完成所有已分配的服务后能够及时加油。

2) 时间约束 ：车辆必须能够在请求中指定的服务开始时间窗口内的某个时间接载乘客。此外，实际乘车时间不应超过请求中规定的时间最大值。

3) 容量约束 ：当车辆到达上车地点时，必须始终有足够的空余座位来容纳该请求中的所有乘客。

准入控制和调度相互关联，我们将在后续章节中详细讨论它们。确定结果后，控制中心会将任务分配给相应的自动驾驶车辆，由这些车辆为客户服务。

IV. 调度

调度涉及确定以下内容：
- 自动驾驶车辆与请求的匹配；
- 自动驾驶车辆完成已分配请求的路线；以及
- 自动驾驶车辆应到达特定位置的时间。

这里我们假设所有正在调度的请求都是可接受的，其中请求的可接受性由准入控制处理。因此，所有请求在调度后都将由适当的车辆提供服务。在第五节讨论准入控制时，我们将解释准入控制与调度之间的关系。

为了便于调度，我们假设所有车辆均已联网，并能以较短的延迟与控制中心通信。这确保了没有明显的改变在图1给出的每个时间间隔内，自动驾驶车辆的位置会发生变化。在现代先进通信技术的支持下，这一假设是可行的。在我们的模型中，要求调度计算能够在较短的时间内完成，以确保车辆沿指定路线行驶时交通数据的有效性。交通数据基本分为两类：道路路段的距离和行驶时间。前者是时不变的，而后者通常会逐渐变化。换句话说，行驶时间的显著变化只会在远长于时间间隔的时间跨度内发生。

A. 预处理

我们对自动驾驶车辆进行调度，以完成运输请求，实现最低的总运营成本，该成本以燃料成本衡量，而燃料成本又通过总行驶距离来计算。任意两个位置之间的距离是不变的，我们将G(V, E)转换为G′(V′, E′)，使用任意最短路径算法（例如Dijkstra算法）[29],，其中V′ ⊂ V是我们需要确定已分配自动驾驶车辆到达时间的位置集合，以便配置其行驶计划。V′包括所有车辆访问的第一个位置（即ak）、请求的起点和终点（即sr和dr），以及加油站点的位置（即i ∈ V˜）。E′定义为{(i, j)|i, j ∈ V′}，使得在G中存在一条从i ∈ V到j ∈ V的最短路径。对于(i, j) ∈ E′，其对应的cij和tij分别为构成G中相应最短路径的所有边的成本之和与时间之和。在后续计算中，我们专注于G′(V′, E′)而非G(V, E)。我们采用此转换的原因有两个：首先，建模所需的变量数量可以大幅减少。集合V\V′并不重要，因为所有关于车辆和请求所指定位置的约束条件仅限于V′。这样可以显著提高求解调度问题的效率。其次，这可以提高行程计划的灵活性。假设自动驾驶车辆k从顶点1前往顶点4，并存在两条连接它们的路径：路径1：1→ 2→ 4，路径2：1→ 3→ 4。假设顶点1和4属于V′，但顶点2和3不属于。为了满足对k提出的要求，我们只需确定k到达顶点1和4的时间，即tk1和tk4。如果在建模中也包含顶点2和3，并最终选择路径1，则tk2将在求解调度问题时被确定，因此k需要分别在tk1、tk2和tk4之前到达这些顶点。否则，仅tk1和tk4被确定，我们可以给予k到达顶点2的时间更大的灵活性。tk2可以是在tk1和tk4之间的任意时间，只要考虑了(1, 2)和(2, 4)上所需的行驶时间即可。这种灵活性为k应对可能干扰其原始行车计划的突发交通事件提供了空间。同时，这也允许k在需要时切换至路径2，而无需更改原始行车计划。

如果直接从G(V, E)构建的调度问题能够高效地求解，则可以跳过预处理步骤。然而，如果需要通过预处理来简化调度问题，则可以将其视为大量的结果查找。由于cij通常指不变的行驶距离，因此最短路径计算的结果也是不变的。事实上，在系统运行之前，我们可以先为V中每一对位置计算最短路径。当在某个间隔内触发预处理时，我们只需查找预先计算好的最短路径结果。因此，预处理的时间成本可以视为可忽略不计。

B. 问题表述

我们基于G′(V′, E′)来构建调度问题。该问题的给定参数数据包括图G′(V′, E′)，其成本为cij’s，行驶时间为tij’s，运输请求集合R，以及自动驾驶车辆集合K。我们为该问题定义了若干变量。二进制变量xkij’s用于表示车辆将经过哪些连接，
$$ xkij=\begin{cases}1 & \text{if vehicle } k \text{ traverses }(i, j) \ 0 & \text{otherwise}\end{cases} $$

我们为车辆对请求的分配定义二进制变量yrk，即
$$ y^k_r=\begin{cases}1 & \text{if request } r \text{ is assigned to vehicle } k \ 0 & \text{otherwise}\end{cases} $$

对于i ∈ V˜，使用二进制变量gki来表示车辆结束其路线的加油站点，
$$ g^k_i=\begin{cases}1 & \text{if vehicle } k \text{ ends at station } i \ 0 & \text{otherwise}\end{cases} $$

我们需要指定路线中各个位置的时间和载客状态。设tik为k到达顶点i的最晚时间，fk为k在顶点i处的载客数量。

我们的目标是为自动驾驶车辆制定经济高效的调度，因此我们以最小化总运营成本为目标函数
$$ \sum_{i,j\in V’,k \in K} c_{ij} x^k_{ij} \tag{2} $$

我们定义了一组约束条件，以限定变量的范围，从而满足第三节-B中讨论的要求。每个运输请求仅能被服务一次，因此我们有
$$ \sum_{k \in K} y^k_r = 1, \quad \forall r \in R. \tag{3} $$

如果自动驾驶车辆被分配到一个请求，它将在其中一个加油站点结束。这是由
$$ \sum_{i \in \tilde{V}} g^k_i \leq 1, \quad \forall k \in K \tag{4} $$

如果自动驾驶车辆k未被分配给任何请求，则无需为k确定路径，也无需确定其最终停靠加油站点k。因此，对于某些k，可能出现∑i∈V˜gki = 0的情况。

设N+(i)和N−(i)为顶点i的入邻节点集和出邻节点集，即N+(i)={j ∈ V′|(j, i) ∈ E′}和N−(i)={j ∈ V′|(i, j) ∈ E′}。我们使用网络流模型来建模路径。一条从ak开始并结束于i ∈ V˜的路径可定义如下：
$$ 0 \leq \sum_{i\in N^{-}(a_k)} x^k_{a_k i} - \sum_{i\in N^{+}(a_k)} x^k_{i a_k} \leq \sum_r y^k_r, \quad \forall k \in K \tag{5} $$
$$ 0 \leq \sum_{j\in N^{+}(i)} x^k_{j i} - \sum_{j\in N^{-}(i)} x^k_{i j} \leq g^k_i, \quad \forall i \in \tilde{V}, k \in K \tag{6} $$
$$ \sum_{j\in N^{+}(i)} x^k_{j i}= \sum_{j\in N^{-}(i)} x^k_{i j}, \quad \forall i \in V’\backslash \tilde{V} \cup{a_k|k \in K}. \tag{7} $$

公式(5)定义了k的起始顶点，其中起始顶点具有一个单位的净流出流量。∑rykr定义了k是否被分配了请求。如果k被分配了请求，则∑rykr=1，因此(5)将允许k在ak处具有一个单位的净流出流量。类似地，(6)定义了k的目的地顶点，并由指定路径实际终止于哪一个确切顶点。如果在i ∈ V结束，则(6)将允许i对于k具有一个单位的净流入流量。对于其他顶点，(7)通过使相应的流入流量与流出流量相等来设置流量守恒。

如果请求r被分配给车辆k，则k需要经过r的上车地点sr。这等价于在sr处对k具有正向流出流量
$$ \sum_{i\in N^{-}(s_r)} x^k_{s_r i} \geq y^k_r \tag{8} $$

类似地，当r由k服务时，k需要经过请求r的下车点dr。这要求在dr处对k具有正向流入流量
$$ \sum_{i\in N^{+}(d_r)} x^k_{i d_r} \geq y^k_r \tag{9} $$

需要注意的是，仅指定sr的流入流量是不够的，因为当k恰好在sr开始其路径时，流入流量可能为零。同样，仅指定dr的流出流量也是不够的，因为当k恰好在dr结束其路径时，流出流量可能为零。

无论自动驾驶车辆k前往何处，其行驶时间均不能超过由T˜k规定的运行时间限制。此外，该车辆需要至少花费t0k才能到达其路径的初始顶点。因此我们得到
$$ t^0_k \leq t^k_i \leq \tilde{T}_k , \quad \forall i \in V’ , k \in K. \tag{10} $$

令M为一个足够大的正数。当车辆k traverses边(i, j)时，j处的时间应大于或等于i处的时间加上在(i, j)上的行驶时间，即tij。这可以通过以下方式指定
$$ t^k_j \geq t^k_i + t_{ij} - M(1 - x^k_{ij}) , \quad \forall k \in K, i, j \in V’ . \tag{11} $$

当车辆k被分配给请求r时，从sr到dr的实际乘车时间不应超过r规定的最长乘车时间Tr，即
$$ t^k_{d_r} - t^k_{s_r} \leq T_r + M(1 - y^k_r) , \quad \forall r \in R , k \in K . \tag{12} $$

如果请求r由车辆k提供服务，则k应在r指定的服务开始时间窗口[er, lr]内到达sr。这可以表示为
$$ e_r - M(1 - y^k_r) \leq t^k_{s_r} \leq l_r+ M(1 - y^k_r), \quad \forall r \in R, k \in K. \tag{13} $$

被服务的乘客占用座位，且所有车辆的容量限制在任何时间都应得到满足。因此我们有
$$ 0 \leq f^k_i \leq Q_k, \quad \forall i \in V’, k \in K. \tag{14} $$

在ak，部分由Rk引起的乘客可能会从k下车，同时可能有新的乘客从其他请求上车至k。自动驾驶车辆在其初始顶点ak’处的载客状态由以下给出
$$ f^k_{a_k} \geq \sum_{r|s_r=a_k} q_r y^k_r - \sum_{r|d_r=a_k} q_r y^k_r \tag{15} $$

当k沿(i, j)从i行驶到j时，顶点j可能是某些请求的上车地点，也可能是其他一些请求的下车地点。自动驾驶车辆k在i和j处的载客状态之间的关系可以描述如下：
$$ f^k_j \geq f^k_i - M(1 - x^k_{ij}) + \sum_{r|s_r=a_k} q_r y^k_r - \sum_{r|d_r=a_k} q_r y^k_r \tag{16} $$

当自动驾驶车辆到达加油站时，分配给该车辆的所有请求都应已被处理完毕，且不应有乘客被搭载至路线的终点。这由以下内容描述：
$$ f^k_i \leq M(1 - g^k_i) , \quad \forall i \in \tilde{V}, k \in K. \tag{17} $$

请记住，在当前调度区间之前，已有两类请求被分配给了自动驾驶车辆，即˜。作为一个（近）实时应用，利用更新的信息，我们可以通过调整已分配的请求来进一步提升系统性能。对于那些当前正在服务的请求，例如r ∈ Rk中乘客已上车的k，我们可以将其视为“新”请求，通过设置sr = ak并确认yrk = 1，使其在起始节点ak开始服务。由于k已按照先前确定的调度计划服务r，我们可以通过缩短已耗时间来更新其Tr。服务开始时间窗口已不再重要，因此我们将er = −∞和lr =+∞进行设置。qr保持不变。对于那些先前已分配给k但尚未被服务的请求Rk，如果能够降低成本，我们可以使用其他自动驾驶车辆对其重新调度r ∈ Rk。由于乘客并不关心最终由哪辆车提供服务，将Rk中的这些r重新分配给其他更合适的车辆可能会更加高效。运营成本更低，这增强了系统的灵活性。总体而言，调度问题被定义为

问题1（调度） ：
最小化(2)
约束于 (3)–(17)
over xkij ∈{0, 1}, yrk ∈{0, 1}, gli ∈{0, 1}, tik ∈ R+ fki ∈ Z+, ∀ i, j ∈ V′, l ∈ V˜, r ∈ R, k ∈ K.

问题1具有线性目标函数和线性等式和不等式约束。其部分变量为二进制，其余为实数。因此，该调度问题是一个混合整数线性规划（MILP）。尽管在第IV-A节中讨论的预处理步骤有助于简化问题，但变量和约束的数量仍随R和K的规模增长而增加。由于无效请求已被准入控制（在第五节中讨论）剔除，该MILP始终是可行的，且所有请求必须被服务。只要所有cij均为正值，问题1的解就不会产生零成本，且不服务任何请求的调度永远不会成为解。

C. 完整调度构建

由于车辆是无人的，我们需要提供关于路径和行程计划的完整指令，以便它们知道何时以及何地前往以向客户提供服务。求解MILP可得到xkij、yrk、gli、tik和fki的解。作为二进制变量，xkij和yrk的结果是明确的。后者指明了哪些车辆被分配到请求，前者解释了每个k在G′中从ak出发并最终到达某个加油站点的路线。在G′中确定的路径反过来推导出G中的相应完整路线。回顾一下，我们已经确定了对应于边(i, j) ∈ E′在G中从i到j的最短路径。通过基于G′将每一对相邻顶点之间的最短路径插入到路径中，可以相应地推导出G中的完整路线。

注意，(10)–(13)以不等式的形式定义了tik的范围。由此得到的tik构成了可行的时间表，但可能不够具体，从而导致歧义。例如，如果k在[t′, t′′]时段内的任意时刻到达位置i都是可行的，则一种合理的方式是设置tik = t′，这可以增强后续调度区间 的灵活性。为了构造k的行程计划，我们检查从xkij计算出的路径。对于第一个顶点，我们设置tkak = t0k。对于任何后续顶点，例如从i到j，可以将边(i, j)上的行驶时间加到i的确定时间上，以获得j的确定时间，即tkj = tki + tij。如果顶点j产生一个请求，我们需要满足其服务开始时间窗口，因此有tkj = max{tki + tij, er}。

类似地，(14)–(17)也通过不等式限制了车辆在各个位置的占用情况。从得到的fki中无法得知确切的座位状态。通常，我们只关心客户上下车点的座位状态，即sr和dr。我们可以再次检查由xkij计算出的路线，并确定载客状态。例如，k沿(i, j)从i行驶到j。如果j是请求r的服务起始位置，我们将r所需的座位数加到k在i的占用数上，得到其在j的占用数，即fkj= fki+ qr。如果j是服务目的地位置，则从k在i的占用数中减去r所占用的座位数，得到其在j的占用数，即fkj= fki − qr。通过这种方式，可以确定已分配任务的车辆完整调度计划，车辆只需遵循行程计划即可完成服务。

V. 准入控制

回顾第四节，所有提交调度的请求均被假定为可接受的，并且需要被服务。在本节中，我们研究准入控制问题。我们首先对该问题进行建模，然后研究在存在交通拥堵和乘客失约情况下的变化。

A. 问题表述

准入控制负责确定适合调度的一组请求。换句话说，在准入控制之后，我们将生成一个请求子集R ⊂ R用于后续调度，其中R是所有可用请求的集合，而R将在调度过程中由适当的自动驾驶车辆处理。然而，要判断某个特定请求r是否可接受，不仅需要检查其可行性，还需要评估其盈利性，即服务r是否会产生正净收益。计算r带来的净收益涉及其所产生的成本，而该成本通过调度进行调控。因此，调度与准入控制之间不存在明确的先后关系，这两个过程应当同时考虑。

我们可以将请求和自动驾驶车辆分别解释为交通服务的需求和供给，然后问题1的约束条件定义了需求与供给之间匹配的范围。当K较大而R较小时，这些约束更容易被满足。实际上，K的规模通常是固定的，因为系统不会突然将更多自动驾驶车辆加入车队，也不会突然有大量自动驾驶车辆停止服务。然而，提交的请求完全来自系统外部；系统既无法禁止客户提交请求，也无法修改请求中的属性以匹配自动驾驶车辆的条件。事实上，单个不合适的请求（例如，可容忍乘车时间非常短的请求）就可能导致问题1不可行，从而导致调度失败。为了避免这种情况，系统应在进行调度之前执行准入控制，筛选出任何不合适的请求（见图2）。考虑到接受一个请求会带来收入，尽管系统无法修改已提交的请求，但它有权通过牺牲相应收入来拒绝任何请求。准入控制通过以下目标操纵R：1）生成一个请求子集R ⊂ R，使得调度过程能够执行，即使用ˇR使问题1可行；2）最大化所产生的利润。

考虑我们接纳ˇR用于问题1的调度，可重写为
$$ \text{minimize } \phi(\alpha) \tag{18a} $$
$$ \text{subject to } \alpha \in Z(\check{R}) \tag{18b} $$

其中α ≡{xkij}∪{yrk}∪{gik}∪{tik}∪{fki}, φ(α) ≡∑i,j∈V,k∈K cijxkij，并设Z(ˇR)为关于ˇR的问题1的可行域。令ρr为admitting r ∈ R时产生的收入，并定义
$$ z_r=\begin{cases}1 & \text{if we admit } r \in R \text{ for scheduling} \ 0 & \text{otherwise}\end{cases} $$

我们还定义了准入控制函数σ(R,[zr]r∈R)，该函数根据zr返回R ⊂ R，使得当zr= 1时为r ∈ R。总利润等于总收入与总成本之差，即∑r∈R ρrzr − φ(α)。然后我们将准入控制问题表述为

问题2（准入控制） ：
$$ \text{maximize } \Phi(R,[z_r] {r\in R})=\sum {r\in R} \rho_r z_r - \phi(\alpha) \tag{19a} $$
$$ \text{subject to } \check{R}= \sigma(R,[z_r]_{r\in R}) \tag{19b} $$
$$ z_r= 1, \quad \forall r \in R_k, k \in K \tag{19c} $$
$$ \alpha \in \arg \min{\phi(\alpha): \alpha \in Z(\check{R})}
\tag{19d} $$
over α, Rˇ ∈ R, zr ∈{0, 1}, ∀ r ∈ R \tag{19e}

其中，(19c)确保在先前运行区间内已被接纳的请求在当前区间仍被接纳。我们将准入控制建模为一个双层优化问题，该问题包含上层优化和下层优化。Φ是以上层变量ˇR和zr’s为变量的上层目标函数。φ表示以下层变量α为变量的下层目标函数。方程(19d)实际上是(18)，因此我们将问题1作为问题2的一个约束条件。上层优化的目标是操纵整个请求集合R并确定ˇR，使得ˇR能够最大化总利润。下层优化的目标是调度自动驾驶车辆以服务可接受请求集合ˇR，从而使保留成本最低。这两个层次的优化相互关联：上层优化需要下层优化的结果，即α，才能得到R；而下层优化则需要上层优化的结果，即ˇR，才能输出α。需要注意的是，如果上层优化产生的ˇR导致Z不可行，则相应的α将为(19d)的目标函数返回+∞，这反过来会使目标函数(19a)保留−∞。

双层优化通常难以求解。具有线性目标函数和线性约束条件的双层问题属于NP难[30]。从(19)可以看出，我们在该问题中操作的是离散变量。由于经典的双层优化方法通常假设光滑性或凸性[31],，因此这些经典方法不适用于问题2。受[32],[33],启发，我们决定采用进化启发式方法来解决该问题。进化方法在交通科学中的双层优化问题中得到了广泛应用。例如，在[34],中，差分进化(DE)被用于解决最优收费问题，该问题涉及设置收费以控制拥堵，以及道路网络设计问题，该问题确定网络设施的容量提升。在[35],中，遗传算法被应用于公共交通道路空间优先权问题，通过在私家车和公共交通模式之间重新分配道路空间来优化系统。我们将设计一种基于遗传算法的算法来解决问题2。在讨论算法细节之前，我们定义了可接受性，并给出了一些关于问题2的分析结果，这些结果有助于下一节中算法的设计。

定义1（可接受性） ：请求集合ˇR是可接受的，如果它能产生正利润，即Φ(R,[zr]r∈R) > −∞。

定理1 : 我们得到以下关于可接受性的结果：
1) 考虑一个请求子集R ⊂ R是可接受的。令P(ˇR)为ˇR的幂集。任何ˇR′ ∈ P(ˇR)也是可接受的。
2) 对于任意单元素集合{r} ⊂ R，如果{r}不可接受，则其任何超集ˇR ⊃{r}也不可接受。
3) 考虑请求子集R1, R2 ⊂ R以及车辆子集ˇK1, ˇK2 ⊂ K。假设ˇK1 ∩ ˇK2= ∅。如果ˇR1和ˇR2分别由K1和K2可接受，则R1 ∪ˇR2也是可接受的。

证明 ： 对于陈述1，约束(19b)定义了ˇR，其是约束(19d)的输入。只需证明，如果参与的自动驾驶车辆能够服务R中的所有请求，则移除任意r ∈ R不会导致(19d)不可行。假设从R中移除了r，且如果r已被接纳，自动驾驶车辆k本应被分配来服务r。k仍可沿路径行驶，仿佛r仍然存在。因此，对于ˇR\ r，(19d)仍然是可行的。

对于陈述2，一个不可接受的r意味着无法安排自动驾驶车辆来满足r。我们永远无法为包含r的请求集合提供服务，因为其组成部分r永远无法被服务。

对于陈述3，我们可以将R1 ∪ R2表示为三个互不重叠的集合：ˇR1(ˇR1 ∩ˇR2)、ˇR2(ˇR1 ∩ˇR2)和ˇR1 ∩ˇR2。由于ˇK1和ˇK2互斥，ˇR1(ˇR1 ∩ˇR2)和ˇR2(ˇR1 ∩ˇR2)可以分别由ˇK1和ˇK2同时服务。每个r ∈ R1 ∩ R2可由k ∈ K1或k ∈ K2已接纳。

引理1 ： 系统不会产生负利润。也就是说，对于任意R，问题2必须至少存在一个可行解，其目标函数值为非负。

证明 ： 我们将R分为先前已接纳的和新收到的请求，即{Rk}和R{Rk}。对于新收到的请求，我们始终可以设置zr=0, ∀ r ∈ R{Rk}。然后(19b)给出ˇR= ∅。方程(19d)返回α，其中φ(α)= 0，因为没有请求需要被服务，因此没有自动驾驶车辆被用于提供服务。因此我们有∑r∈R{Rk} ρrzr −φ(α)= 0。对于先前已接纳的请求，由于它们是在之前的某些准入控制过程中被接纳的，因此当它们之前作为新请求被接纳时，必然会产生非负利润。否则，我们一开始就不会接纳它们。

引理1意味着问题2必须是可行的。

定理2 ：考虑两个请求子集ˇR和ˇR′，其中ˇR ⊂ ˇR′ ⊂ R。如果ˇR和ˇR′都是可接受的，则ˇR′将利润不低于ˇR，即supΦ(ˇR,{zr|r ∈ˇR}) ≤supΦ(ˇR′, {zr|r ∈ˇR′})。

证明 ： 假设supΦ(ˇR,{zr|r ∈ˇR})> supΦ(ˇR′,{zr|r ∈ˇR′})。我们记ˇR′= ˇR∪(ˇR′\ ˇR)。于是我们有
$$ \sup\Phi(\check{R}’,{z_r|r \in \check{R}’})= \sup\Phi(\check{R},{z_r|r \in \check{R}}) + \sup\Phi(\check{R}’\backslash \check{R},{z_r|r \in \check{R}’\backslash \check{R}}). $$

根据引理1，supΦ(ˇR′\ˇR,{zr|r ∈ˇR′\ˇR})的值大于或等于零。这导致了一个矛盾。

定理2意味着接纳更多的请求不会减少所获得的利润。

B. 变体

本文研究了交通拥堵和乘客失约对准入控制（及调度）的影响。基本上，我们将看到在这些情况下，所提出的准入控制和调度机制仍然可以应用，但可能需要一些额外的微调来应对各种情况。

1) 交通拥堵 ：交通拥堵会直接影响某些(i, j) ∈ E的行驶时间tij，并进而影响请求的可接受性。回顾一下，系统在固定时间间隔基础上运行，每个间隔通常持续几分钟（见第三节-B）。我们基本假设，在一个间隔内，包括行驶时间在内的参数是恒定的或变化很小，以确保该间隔内完成的准入控制结果仍然有效。如果行驶时间变化较快，则需要缩短间隔时长以使该假设成立。另一方面，如果行驶时间变化较慢，则可以延长间隔时长以降低计算负担。因此，运行间隔的时长取决于部署服务区域的交通状况。

现在考虑tij在当前区间已被更新，其值与前一间隔所使用的值不同。可能的影响分为三种情况：（i）tij未参与所有k的Rk；（ii）tij对某些k参与了Rk；以及（iii）tij对某些k参与了Rk。对于情况（i），由于tij尚未用于服务任何请求，其变化不会影响任何自动驾驶车辆的行程计划，因此仅基于tij无需采取任何操作。对于情况（ii），尽管tij已被用于确定部分自动驾驶车辆的行程计划，但相关请求尚未被服务，我们可以简单地将这些请求视为新提交的请求，并重新进行准入控制和调度。对于情况（iii），tij会影响正在由某些自动驾驶车辆执行的行程计划。在后续时间段中，调度过程将判断是否可通过确定其他最短路径来避免路段(i, j)。如果无法避免，由于乘客正在被服务，要求他们换乘其他车辆可能并不合适，且在操作上无法进一步处理。然而，从营销角度可对乘客进行补偿，例如发放用于未来乘车的现金券。

2) 乘客失约 ：失约是指特定请求中的部分或全部乘客在预定的上车时间未出现的情况。如果乘客无法按时到达上车地点，则视为失约。如果部分但并非全部乘客未到，指定的自动驾驶车辆的行程安排不受影响，但所需座位减少。这些未使用的座位可以在后续时间段释放，用于服务其他合适的请求。如果所有乘客均未出现，则分配给该请求的“资源”可在其原始上车时间之后的后续时间段立即释放。这为自动驾驶车辆在时间和载客量方面提供了更大的灵活性，以服务未来的请求。从商业角度来看，可能会存在一些惩罚政策来抑制此类行为。

VI. 基于遗传算法的解决方案

在本节中，我们提出一种求解方法来应对问题2。我们采用基于遗传算法的框架来构建该方法。其中一些组件是根据第五节中讨论的分析结果设计的。

A. 进化算法的工作原理

进化算法（EAs）指的是一类优化算法，其设计灵感来源于各种自然现象。例如包括GA[36],、DE[37],以及化学反应优化（CRO）[38]。不同的EAs通常具有相似的工作原理：EAs迭代地对问题的解空间进行采样，并在检查了有限数量的候选解后尝试找到全局最优解。在每次迭代中，通过一些算子，它基于前几次迭代获得的候选解及其对应的目标函数值生成一组新的候选解种群。EAs倾向于随着迭代逐步收敛到全局最优解，并在满足停止准则时终止。不同的EAs对其算子有不同的设计。例如，GA的设计基于遗传学中的自然选择思想，而CRO则模拟化学反应过程的本质。与大多数传统优化方法不同，EAs并不要求问题具有凸性或可微性。在每次算法运行中，它们只需对一定数量的候选解进行采样，并使用目标函数评估其解的质量。因此，使用EAs进行搜索通常会引发大量的目标函数调用。如前所述，EAs已被证明在解决交通科学中的双层优化问题方面是有效的。我们将采用成熟的遗传算法框架，以帮助设计一种能够在实际意义上为问题2返回良好解的方法。

B. 分布式调度

当使用进化算法（EA）解决问题2时，将生成许多候选解。为了评估某个特定候选解的质量，我们需要计算一次(19a)，同时也需要检查一次(19d)。换句话说，单次运行EA需要多次求解问题1。当下层优化比较简单时，计算的多次求解的负担可能仍在可接受范围内。然而，对于问题1而言情况并非如此，因为其所需的变量和约束条件数量随着运输请求和服务的自动驾驶车辆数量呈指数级增长。这意味着我们需要一种更有效的方法来求解问题1，以应对问题2。

考虑ˇRk ⊂ R是分配给车辆k的请求集合的子集。假设我们知道请求ˇ到车辆的分配情况，即对所有k都有Rk。由于每个请求仅由一辆自动驾驶车辆服务，因此对于任意k, l ∈ K、k ≠ l和⋃k∈K ˇRk= R，都有ˇRk ∩ˇRl= ∅。在给定ˇRk的情况下，我们考虑以下问题：

问题3（车辆k的调度子问题） ：
$$ \text{maximize } \sum_{i,j\in V’} c_{ij} \overset{\circ}{x} {ij}^k \tag{20a} $$
$$ \text{受限于 } \sum {i\in\tilde{V}} \overset{\circ}{g} i^k \leq 1 \tag{20b} $$
$$ 0 \leq \sum {i\in N^{-}(a_k)} \overset{\circ}{x} {a_k i}^k - \sum {i\in N^{+}(a_k)} \overset{\circ}{x} {i a_k}^k \leq \sum_r \overset{\circ}{y}_r^k \tag{20c} $$
$$ 0 \leq \sum {j\in N^{+}(i)} \overset{\circ}{x} {j i}^k - \sum {j\in N^{-}(i)} \overset{\circ}{x} {i j}^k \leq \overset{\circ}{g}_i^k, \quad \forall i \in \tilde{V} \tag{20d} $$
$$ \sum {j\in N^{+}(i)} \overset{\circ}{x} {j i}^k= \sum {j\in N^{-}(i)} \overset{\circ}{x} {i j}^k, \quad \forall i \in V’\backslash \tilde{V} \cup{a_k} \tag{20e} $$
$$ \sum {i\in N^{-}(s_r)} \overset{\circ}{x} {s_r i}^k \geq \overset{\circ}{y}_r^k \tag{20f} $$
$$ \sum {i\in N^{+}(d_r)} \overset{\circ}{x} {i d_r}^k \geq \overset{\circ}{y}_r^k \tag{20g} $$
$$ \overset{\circ}{t}_k^0 \leq \overset{\circ}{t}_i^k \leq \tilde{T}_k, \quad \forall i \in V’ \tag{20h} $$
$$ \overset{\circ}{t}_j^k \geq \overset{\circ}{t}_i^k + \overset{\circ}{t} {ij} - M(1 - \overset{\circ}{x} {ij}^k) , \quad \forall i, j \in V’ \tag{20i} $$
$$ \overset{\circ}{t} {d_r}^k -\overset{\circ}{t} {s_r}^k \leq T_r+ M(1 - \overset{\circ}{y}_r^k) , \quad \forall r \in\check{R}_k \tag{20j} $$
$$ e_r-M(1- \overset{\circ}{y}_r^k)\leq \overset{\circ}{t} {s_r}^k \leq l_r+M(1-\overset{\circ}{y} r^k) , \quad \forall r \in \check{R}_k \tag{20k} $$
$$ 0 \leq \overset{\circ}{f}_i^k \leq Q_k, \quad \forall i \in V’ \tag{20l} $$
$$ \overset{\circ}{f} {a_k}^k \geq \sum_{r|s_r=a_k} q_r \overset{\circ}{y} r^k - \sum {r|d_r=a_k} q_r \overset{\circ}{y} r^k \tag{20m} $$
$$ \overset{\circ}{f}_j^k \geq \overset{\circ}{f}_i^k - M(1 - \overset{\circ}{x} {ij}^k) + \sum_{r|s_r=a_k,r \in \check{R} k} q_r\overset{\circ}{y}_r^k - \sum {r|d_r=a_k,r \in \check{R} k} q_r \overset{\circ}{y}_r^k , \quad \forall i, j \in V’ \tag{20n} $$
$$ \overset{\circ}{f}_i^k \leq M(1 - \overset{\circ}{g}_i^k), \quad \forall i \in \tilde{V} \tag{20o} $$
$$ \text{over } \overset{\circ}{x} {ij}^k \in{0, 1}, \overset{\circ}{y}_r^k \in{0, 1}, \overset{\circ}{g}_l^k \in{0, 1}, \overset{\circ}{t}_i^k \in R^+ , \overset{\circ}{f}_i^k \in Z^+ , \quad \forall i, j \in V’ , l \in \tilde{V}, r \in \check{R}_k . \tag{20p} $$

仅求解问题3，我们只能获得服务路径、到达路径上各个位置的时刻表，以及车辆k服务请求的容量条件。由Rk表示。问题3看起来与问题1相似，但实际上要简单得多。它不包含(3)，并且涉及的变量更少，因为与k以外的车辆相关的变量未被包括在内。由于变量较少，其约束条件也相应减少。

为简便起见，类似于(18)，我们也分别将问题3的解、目标函数和解空间写为α◦k、φk(αk)和Zk。

定理3 ： 当给定Rk ⊂ R，∀ k ∈ K，使得Rk ∩ˇRl= ∅，对于任意k，l ∈ K、k ≠ l和⋃k∈K ˇRk= R，求解所有k ∈ K的问题3等价于求解问题1，即
$$ \inf_{\alpha\in Z} \phi(\alpha)=\sum_{k\in K} \inf_{\overset{\circ}{\alpha}_k\in Z_k} \phi_k(\overset{\circ}{\alpha}_k) $$
以及xkij= ˚xkij、yrk= ˚yrk、glk= ˚glk、tik= ˚tik和fki= ˚fik, ∀ i,j ∈ V′, l ∈ V˜, r ∈ ˇRk, k ∈ K。

证明 ： 当给定这样的Rk ⊂ R，∀ k ∈ K时，我们可以构造yrk，∀ r ∈ R，k ∈ K，使得(3)成立。通过这种方式，我们可以从问题1中移除约束(3)。在没有约束(3)的情况下，问题1的目标函数和其余约束条件在k上变得可分离：(2)给出了车辆上花费的成本总和；式(4)–(9)描述了车辆经过的路径，每条路径相互独立；式(10)–(13)限制了车辆路径上各个位置的时间要求；式(14)–(17)限制了车辆路径上的乘客容量条件。如果我们对每个k分别将(2)中的项以及约束条件(4)–(17)进行分组，则会得到|K|个问题，每个问题均由(20)给出。

定理3指出，当请求分配给车辆的方案已知时，分布式地求解|K|各个调度子问题可以保留原始调度问题的解。注意，该结果是基于问题建模的一些特性专门开发的，通常不能应用于其他调度问题。与通用分布式优化[39],[40],不同，此处的结果不需要消息传递等技术。因此，|K|子问题可以由|K|计算单元分布式地求解。假设车辆始终通过先进的车载通信技术相互连接，一个显而易见的计算单元选择就是自动驾驶车辆。因此，根据定理3，如果我们能为每辆车辆分配其需要服务的请求，则每辆车均可通过并发求解问题3，自行确定一条成本最低的可行路径per se来服务已分配的请求。然而，当某辆自动驾驶车辆与控制中心之间的通信中断时，相应的子问题可委托给控制中心内未占用的计算单元，甚至云端来处理。当该自动驾驶车辆的通信恢复后，计算得到的调度结果可再返回给该车辆。

C. 算法组件

由于遗传算法（GA）是最流行的进化算法（EAs）之一，我们采用基于遗传算法的设计来解决准入控制问题。遗传算法通过受自然进化启发的操作（例如，遗传、选择）生成一系列候选解。

交叉和变异。在讨论整体算法设计之前，我们先介绍各种算法组件：

1) 染色体 ：染色体指定了问题2的一个候选解。虽然下层优化由标准的混合整数线性规划方法处理，我们的遗传算法方法主要用于处理上层优化。染色体由一个1 × |R|二进制向量z=[z1,…, zr,…, z|R|]以及一个车辆分配向量κ=[κ1,…, κr,…, κ|R|]表示，其中κr表示如果zr为1时分配给r的车辆。注意，引入κ是为了实现第六节B部分中讨论的分布式调度技巧。尽管在应用原始的调度建模(18)时，κ可以在(19d)中确定，但在染色体层面同时操作κ和z并无坏处。这使得分布式调度成为可行，且计算时间节省的好处将在第七节A部分中变得清晰。在搜索过程中，我们维护一个包含Npop个染色体的种群。

2) 适应度评估 ： 我们以分布式方式评估每个染色体的适应度。适应度评估过程如图3所示，包含五个步骤：
(1) 在Rk中对请求进行分组：每个染色体i包含zi和κi。对于那些具有zir = 1的r，基于κi，在控制中心我们可以将R划分为|K|个组，即ˇRk , ∀ k ∈ K。
(2) 请求信息分发：对于每个k，控制ˇ中心通过车载自组织网络等方式将Rk传输给自动驾驶车辆k。
(3) 分布式调度：现代车辆通常配备有计算机，因此每辆车辆可以与其他车辆同时求解个体问题3。那些被分配为空Rk的自动驾驶车辆可跳过计算。
(4) 个体成本返回：各车辆将调度计算得到的成本传回控制中心，例如通过车载自组织网络。
(5) 适应度计算：根据定理3，与染色体相关的成本是目标函数之和问题3由各个自动驾驶车辆确定的函数值，即φ(α)=∑k∈K φk(α◦k|κr= k)。然后染色体的适应度可计算为Φ(z, κ)=∑r∈R ρrzr −∑k∈K φk(α◦k|κr= k)。2当且仅当任意请求r在zr= 1下为不可接受时，Φ(z, κ)变为−∞。执行上述过程的优点有三个方面：
(i) 计算时间可以大幅减少。在算法的所有计算组件中，调度是计算需求最高的部分。如果每辆车辆都能自行计算其行程计划，则所有独立的调度子问题都可以同时得到解决。
(ii) 所有实体仅需管理必要的数据。ρr是客户与控制中心之间协商的结果。在分布式调度下，ρr的使用仅限于控制中心，不涉及任何车辆。此外，当一辆车辆解决其调度子问题后，其计算出的调度仅存储在该车辆中，而不在控制中心或其他任何车辆中。
(iii) 通信量保持最小。在每次评估中，控制中心与车辆之间需要通信的数据仅为分配给各车辆的请求（在步骤2中）以及计算出的调度成本（在步骤4中）。该系统不需要复杂的通信系统来满足通信要求。

3) 禁忌列表 ：我们为每个请求r构建一个禁忌列表τr，以减小搜索空间的规模。τr包含那些无法服务r的车辆k。根据定理1的含义，如果一个请求r对k不可接受，则任何包含r的请求集合也对k不可接受。换句话说，在配置κr时，我们永远不需要考虑τr中的这些k。与禁忌搜索[41],不同，我们不需要在搜索过程中更新禁忌列表。3τr仅在算法的初始化阶段构建，并用于初始种群生成和变异。

4) 选择 ：在每一代中，有Xrate比例的Npop得以保留，其余(1 − Xrate)将通过交叉过程产生的子代进行替换。我们采用加权随机配对[42]来选择保留的染色体以执行交叉。

5) 交叉 ：交叉是遗传算法中用于实现强化的操作符。在每次操作中，它通过操纵两条父代染色体来生成两条后代。后代表承了父代的优点，因此往往具有更优的适应度值，即更高的(19a)的目标函数值。根据定理2，更大的请求集合将提升适应度。

同样基于定理1的陈述3，我们通过交叉操作来处理染色体。父代i和j繁殖产生后代i′和j′。i′以与i相同的一组车辆接纳所有那些r的请求。如果在j中被采纳但在i中未被采纳的任何k存在，则我们在其父代i中未接纳的那些r上随机采纳一个这样的k到i中。我们类似地生成一个主要继承自父代j的后代j′。通过这种方式，后代更有可能接纳更多的请求，从而获得更高的适应度。

6) 变异 ：变异体现了多样化，以防止算法陷入局部最优，我们基本遵循[42]来设计变异。通过变异率μ ∈[0, 1]控制变异的程度。我们对种群中适应度最高的染色体采用精英保留策略，仅其余染色体进行变异。变异发生在染色体i的第zir位，每代发生的变异次数为μ ×(Npop −1) × |R|。如果对zir执行变异，则翻转zir。如果zir由0变为1，我们随机为κr分配一个不在禁忌列表τr中的k。如果zir由1变为0，则设置κr= 0。为了进一步增强多样化，除了精英染色体外，每个染色体都有γ的概率被一个随机染色体替换。

D. 算法设计

我们基本上遵循[42]来设计该算法，该算法包含三个阶段：初始化、迭代和最终阶段。算法的流程图如图4所示。在整个搜索过程中，我们保持染色体为可行候选解。

1) 初始化 ：在初始化阶段，我们定义所有系统参数，例如Npop和Xrate，并为每个r构建禁忌列表τr。然后创建染色体的初始种群，每个染色体被分配一个随机请求r，该请求关联一辆不在其禁忌列表中的车辆τr。这可以确保所有染色体在初始时均为可行解。我们在迭代开始之前评估初始染色体的适应度。

2) 迭代 ：在每一代（或称为迭代）中，我们对染色体所持有的候选解进行操作。在进行任何修改之前，我们先备份上一代产生的可行候选解。然后执行选择、交叉和变异操作来处理染色体，随后进行适应度评估。如果任何染色体包含不可行解，则从备份中保留其原始的可行解。我们检查停止准则，以确定是否继续下一次迭代或进入最终阶段。一个常用的停止准则是经过一定代数后终止。

3) 最终阶段 ： 我们输出在此阶段找到的最佳解决方案。通常，该求解方法在控制中心以集中式方式实现。在评估染色体的适应度时，基于分布式调度将调度任务分配给车辆。

VII. 性能评估

我们进行了一系列仿真，以评估该算法的不同方面。我们考虑了一组来自[43],的真实出租车服务数据，其中包含在波士顿市完成的若干次出租车行程的上下车时间及上下车地点。我们从2012年某一天中上车时间在30分钟时间段内的行程中随机抽取100条行程数据，作为交通请求池。由于目前没有现有交通系统能像我们的系统一样提供灵活的合乘服务，因此我们对数据作如下调整：将数据中的上车时间设为最早服务开始时间，将上车时间加15分钟设为最晚服务开始时间，最长乘车时间为实际行程时间的1.5倍，座位占用率在[1, 5],范围内随机生成，并将实际出租车费用的50%作为收费标准。任意两个位置之间的行驶距离和行驶时间通过谷歌地图API确定。基于[44],，我们假设燃油成本为每英里16美分。我们选择波士顿市内的五个加油站作为自动驾驶车辆的加油站点。每辆车辆假定配备五个座位，并在城市中随机分布。

我们在一台配备3.40吉赫英特尔酷睿i7‐2600处理器和32吉字节内存的计算机上进行仿真。仿真在MATLAB环境中进行，其中调度问题通过YALMIP[45]和CPLEX[46]解决。我们按照[42]设置遗传算法参数：Npop = 16、Xrate= 0.5和μ= 0.15，并设置γ= 0.5。需要注意的是，为了使系统运行一段时间，我们需要对期间内的每个运行间隔执行准入控制。为了对一个间隔执行准入控制，我们需要经历多个调度过程。我们尝试从最小模块开始逐步评估算法的性能。首先，我们评估调度的计算时间。在第二次测试中，我们评估算法在解决准入控制问题上的性能。最后，我们考察系统连续运行一段时间所获得的利润。

A. 调度的计算时间

由于问题1是一个混合整数线性规划问题，我们假设如果该问题可解，则CPLEX能够返回最优解。因此，我们重点关注计算时间。当我们观察问题1时，其变量和约束的数量随着运输请求和车辆数量的问题规模呈指数级增长。因此，调度的计算时间也随着问题规模的增大而迅速增加。为了演示目的，我们专注于小规模问题实例。我们从波士顿数据集中随机生成了9个案例：三个包含3个请求的案例，三个包含4个请求的案例，以及三个包含5个请求的案例。所有案例均使用五辆车提供服务。回顾一下，我们有两种主要方法来解决调度问题：（1）整体求解问题1；（2）联合求解多个问题3。对于第二种方法，我们可以进一步安排子问题在（2.1）en masse控制中心集中求解，或（2.2）在各个车辆上分别求解。因此，总共有三种方法，我们将（1）、（2.1）和（2.2）分别称为集中式、累积式和分布式方法。这三种方法的数据处理、通信和计算过程如图5所示。对于集中式和累积式方法，所有来自乘客和车辆的数据都需要收集并汇聚到控制中心进行处理。调度完成后，计算出的调度将分发给相应的车辆。对于分布式方法，车辆相关数据仅在问题求解代理（即车辆本身）处维护，在对应子问题求解前后均保留在本地。调度完成后，所产生的成本信息会被传回控制中心，用于后续调度决策。当涉及不同数量的车辆时，计算时间可能会有明显差异。为此，针对每个案例I–IX，我们检查了z和κ的所有可能组合（即染色体的候选解），并记录其调度的计算时间。我们认为通信所花费的时间可以忽略不计，因为它通常远小于计算时间。图6显示了每种案例中参与车辆数量不同时可行调度的平均计算时间。由于集中式方法的计算时间增长过快（例如，对于3至5个请求分别为8.30秒、69.25秒和6.72 × 103秒），如果同时展示集中式的数据，则累积式和分布式方法的时间变化将变得难以区分。为更清晰表示，我们在图6中省略了集中式方法的结果。在图6中，部分条形图缺失，是因为在涉及特定数量车辆的情况下无法计算出可行的调度方案。例如，在案例III中，有一项请求无法由任何车辆进行调度，因此案例III在三辆车的情况下没有显示结果。通常情况下，对于累积式方法，随着涉及的车辆数量增加，需要求解更多规模相似的子问题，因此计算时间随车辆数量呈线性增长。而对于分布式方法，不同车辆数量下的计算时间大致相近，因为相关的子问题可以由不同车辆同时处理。而集中式方法的计算时间随请求数量呈指数增长，相比之下，累积式方法的计算时间增长则缓慢得多。

较慢，而分布式方法的速度大致保持稳定。因此，采用集中式方法是不可行的。如果车辆具备足够的通信和计算能力，我们建议使用分布式方法；否则，我们只能推荐采用累积式方法进行调度。

B. 运营间隔中的准入控制

接下来，我们研究该算法在运行区间内解决准入控制问题的性能。每次适应度评估都需要求解一次调度问题，且每次适应度评估的计算时间主要由调度所需时间决定。此外，算法的计算时间取决于所需的适应度评估次数。由于每代的种群规模固定，因此可以根据发生的代数以及第七节A部分中确定的结果来估算算法的运行时间。因此，本文此处主要关注解的质量。

我们对案例I–IX运行了该算法。由于我们已检查了所有候选解，因此可以获得这些案例的最优解。每个案例重复运行算法20次。图7显示了在40代搜索过程中计算出的平均目标函数值。由于绝对值不利于揭示算法的性能，因此将目标函数值相对于相应的最优值进行归一化处理，以实现结果展示的标准化。对于每个数据点，我们也提供了误差4一个最优解的归一化目标函数值等于一。

20次重复实验中计算出的最大值和最小值的误差条。在每种情况下，算法的性能相似。该算法开始时解的质量相对较低，然后在几代内迅速收敛到全局最优。随着迭代代数的增加，误差条之间的差距逐渐减小，这进一步证实了算法的收敛性。当问题规模增大时，算法需要略微更多的代数才能收敛。我们可以得出结论：我们的算法在求解准入控制问题方面非常有效。

我们进一步研究了在不同自动驾驶车辆数量的测试案例中获得的总利润。我们在相同的设置下进行仿真，并对每个测试重复20次。图8显示了针对5、10、15和20辆车辆的平均结果。由于所产生的利润高度依赖于各个请求和车辆的参数，因此来自不同案例的总利润无法直接比较。

图9. 不同车辆数量下准入控制的计算时间。

对于每种情况，我们通过将结果与5辆自动驾驶汽车带来的利润进行归一化，展示利润的百分比变化。由于所有情况表现出相似的趋势，为了更清晰地呈现，我们仅在图8中给出案例I、IV和VII的结果。总体而言，可用车辆越多，所能获得的利润越高。然而，利润的增长幅度较小；与5辆自动驾驶汽车相比，在拥有20辆自动驾驶汽车的情况下，利润仅增加1%至2%。其原因是，更多的可用车辆可能会产生更经济的路线，但总行驶距离并不会显著缩短。图9显示了执行准入控制所需的平均计算时间，对应于图8中给出的情况。车辆或请求越多，计算时间越长。

C. 连续运行区间中的准入控制

这里我们考虑让系统连续运行一段时间，以处理交通请求池中的100个请求。我们考虑两种不同运行区间时长的情况。在情况1中，共有10个区间，每个区间需调度来自请求池的10个随机请求。如果一个请求在某个区间被成功接纳，则该请求将从请求池中移除；否则，它将在后续区间中再次被考虑。情况