面向个性化需求的自动驾驶微公交动态调度方法

摘要

根据个性化出行需求调查，梳理出乘坐资源、合乘意愿以及出行效率3类个性化需求。在此基础上，提出了面向个性化需求的“预约乘车+实时乘车+非固定站点”自动驾驶微公交服务模式，并构建了动态调度模型及求解算法。基于真实路网与随机订单测试集开展的典型案例分析结果表明，在同样的订单需求下，提供轮椅空间和非合乘服务可显著提高订单服务率和社会公平性，但系统成本会增加。

关键词

个性化需求; 自动驾驶; 微公交; 动态调度

自动驾驶微公交作为一种新兴的公共交通模式，具有车辆小型化和多样化、运营灵活化、服务定制化、网联自动化等特点，可满足乘客个性化出行需求，提升公共交通的出行品质。

不同的服务对象具有不同的个性化需求。冯运卿^［1］对不同乘客的出行动机与出行心理进行了分析，按照出行目的、出行距离以及乘客自身属性将乘客划分为不同类别，研究每一类乘客的出行需求。已有研究对共享舒适性^［2-6］和可获得性^［4，7］等因素与出行者的选择行为和支付意愿^［5，7-10］之间的关系进行了分析。共享舒适性是指出行者在出行过程中是否倾向于接受与陌生人共享合乘，不舒适的合乘体验会影响出行者对自动驾驶微公交的选择^［2-6］。可获得性是出行者作为需求方与车辆供给方不平衡关系的体现，受自动驾驶微公交站点规划、车辆规模等因素的影响。若站点规划不合理、车辆规模较小，则可获得性低，难以满足出行者的需求^［4，7］。除此之外，研究表明^［11-13］，服务特性规划、车辆容量设计等差异也会导致自动驾驶微公交服务存在本质的区别，影响出行者的乘坐体验和选择。

需求响应式公交在一定程度上满足个性化需求。Cordeau^［14］提出了需求响应式车辆调度的基本数学模型。Ropke等^［15］考虑了车辆到达延误时间约束。Ho等^［16］根据调度问题的典型特征（包括时间窗口、车辆容量、乘坐时间、路线长度和选择性访问）、车队异质性（即单车型车队与多车型车队）、使用车辆数量（单车与多车）以及目标函数数量（单目标与多目标）、车场数量和一天内允许的行驶里程，对需求响应式车辆调度问题相关研究进行了分类总结。Posada等^［17］面向老年人和残障人士使用公共交通出行的第一和最后一公里问题，研究了传统定站定线公交时刻表和需求响应式运输的综合调度问题，并且为满足该类人群的特殊需求使用了多车型的异质车队。面向老年人和残障人士提供的非盈利出行服务通常以成本最小化为目标，约束包括起终点时间窗、车辆容量和车内的设备布局^［18-20］。面向医疗运输的需求响应式车辆调度更关注时间的紧迫性以及设备或工作人员与运输对象需求的兼容性^［21-22］。Molenbruch等^［23］考虑了部分患者不能共乘的问题。Detti等^［24］则关注病患非紧急运输问题，将病患偏好引入调度模型，优化目标包括车辆运行成本和服务质量。部分学者^［25-27］在需求响应车辆调度问题中考虑了乘客的偏好，效用函数中考虑了行程时间、等待时间、价格等，并以利润最大化为调度的优化目标。

乘客出行需求和出行行为的相关研究成果丰硕，但在公交调度方面，主要从运营者角度出发，在满足乘客起讫点和时间窗约束的前提下关注车场数量和车型的调度优化，缺乏对乘客个性化需求的考虑。在自动驾驶微公交示范运营方面，由于正处于测试运营阶段，运营模式比较局限，因此在灵活、高效率个性化出行需求方面仍有很大提升和改进空间。本文结合自动驾驶微公交灵活特征，重点梳理乘客公交出行的个性化需求，提出面向个性化需求的自动驾驶微公交动态调度方法并构建模型和算法，依托实证案例验证方法的可行性和有效性，旨在为新兴公共交通出行模式的运营和调度提供科学合理的方法支撑。

1 面向个性化需求的自动驾驶微公交动态调度优化模型

1.1　面向个性化需求的自动驾驶微公交动态调度系统设计

1.1.1　个性化出行需求梳理

将出行需求划分为若干类别个性化出行需求，针对不同类别个性化出行需求提供服务方案，包括服务车型、服务站点、服务时间、规划路径等。个性化需求概括为以下3类：

（1） 乘坐资源需求。出行者对自动驾驶微公交车乘坐资源的需求，具体体现为对车型的偏好、乘坐资源（站位、座位或轮椅空间）的选择和预约等。

（2） 合乘意愿需求。出行者在乘坐自动驾驶微公交时是否接受与他人合乘的需求，具体体现为自由选择是否与他人合乘以及合乘对象属性。

（3） 出行效率需求。出行者对乘坐自动驾驶微公交出行效率的需求，具体体现为更短的等待时间、更少的停站次数以及更短的步行距离。

1.1.2　自动驾驶微公交系统框架构建

图1给出了自动驾驶微公交服务模式，由乘客订单管理子系统、微公交车辆管理子系统和调度子系统组成。

图1  自动驾驶微公交服务模式示意图

Fig.1  Schematic diagram of service mode of autonomous minibus

乘客订单管理子系统接收乘客通过手机应用软件等提交的出行订单，并负责管理所有历史订单与当前订单状态。微公交车辆管理子系统汇总微公交当前运行与服务状态信息，并管理微公交端的运行数据和状态。调度子系统通过与乘客订单管理子系统和微公交车辆管理子系统进行交互，读取乘客订单信息与微公交运行数据，从全局角度对出行订单与微公交进行高效匹配，并更新乘客订单状态与微公交状态。

1.1.3　自动驾驶微公交调度策略设计

调度方可以采取不同的调度策略来满足以上3类乘客的个性化需求。

（1） 乘坐资源需求。为了满足乘客对乘坐资源的异质化需求，设置3类乘坐资源：站位、座位、轮椅空间。乘客对乘坐资源的个性化出行需求也分为3类：一般需求、座位需求和轮椅需求。乘坐资源与需求类型的匹配规则如表1所示。一般需求的乘客，可使用站位或座位；有座位需求的乘客要求使用座位；有轮椅需求的乘客仅可使用轮椅空间。此外，考虑乘客对车型的个性化出行需求，设置3类微公交车型，包括小型、中型、大型，每一类车型都对应一个非负的固定成本、单位里程运行成本与单位时间等待成本，表2给出了每类车型的内部乘坐资源配置以及对应的成本。

表1  乘坐资源与需求类型的匹配策略

Tab.1  Strategy for matching resources to demand types

需求类型	站位	座位	轮椅空间
座位需求		✓
一般需求	✓	✓
轮椅需求			✓

表2  3类车型乘坐资源配置以及对应的成本

Tab.2  Resource allocation for three types of minibus rides and corresponding costs

车型	乘坐资源	固定成本/ （元·辆-1）	单位里程运行成本/ （元·km-1）	单位时间等待成本/ （元·h-1）
小型	3个座位、1个轮椅空间	$f_{\mathrm{c}}(1)$	$u_{\mathrm{d}\mathrm{c}}(1)$	$u_{\mathrm{t}\mathrm{c}}(1)$
中型	4个站位、6个座位、2个轮椅空间	$f_{\mathrm{c}}(2)$	$u_{\mathrm{d}\mathrm{c}}(2)$	$u_{\mathrm{t}\mathrm{c}}(2)$
大型	6个站位、9个座位、3个轮椅空间	$f_{\mathrm{c}}(3)$	$u_{\mathrm{d}\mathrm{c}}(3)$	$u_{\mathrm{t}\mathrm{c}}(3)$

（2） 合乘意愿需求。对于选择合乘的乘客，系统将根据乘客的出行时空分布进行合乘匹配，判断依据仅为微公交当前可提供的乘坐资源是否满足该乘客的出行需求，不对车内是否载有乘客进行限制。对于选择不合乘的乘客，系统将为其匹配当前车内未载有其他乘客的微公交，并保证在该乘客的行程内不为其他乘客提供出行服务。

（3） 出行效率需求。出行效率需求通过乘客的可接受最大步行距离进行表征。为了使乘客‒站点距离小于乘客可接受的最大步行距离，将微公交站点分为固定站点和聚类站点，如图2所示。固定站点指调度系统中规划设置的站点。聚类站点则是由乘客的出发地和目的地的时空分布以及乘客可接受的最大步行距离获得。聚类站点使用结束后会被调度系统删除以减小系统负荷。系统首先搜索乘客可接受的最大步行距离内最近固定站点，并将其设置为乘客的上车/下车站点。如果在乘客可接受的最大步行距离范围内没有固定站点，就根据乘客的出行需求自动生成满足其步行距离要求的聚类站点。

图2  自动驾驶微公交站点设置策略

Fig.2  Station setting strategy of autonomous minibus

1.2　面向个性化需求的自动驾驶微公交动态调度模型建立

1.2.1　问题描述

自动驾驶微公交调度问题属于多车型、单车场、灵活站点、带时间窗的动态车辆调度问题。在道路网络$G=(V,A)$内，微公交$B$为$n$个出行订单提供出行服务。其中，$V=\left\{\mathrm{0,2}n+\mathrm{1}\right\}\bigcup P\bigcup D$，$P=\left\{\mathrm{1},\cdots ,n\right\},D=\left\{n+\mathrm{1},\cdots ,\mathrm{2}n\right\}$。点集$P$为乘客的上车节点集合，即订单编号$i$的集合。点集$D$为乘客的下车节点集合。每个订单的上车点为$i$，下车点为（$i+n$），都可用$V$中的节点对表示。节点$i$和（$i$+$n$）都对应相应的物理路网节点。$A=\left\{(i,j),\forall i,j\in V\right\}。$起点车场为0节点，终点车场为（$\mathrm{2}n+\mathrm{1}$）节点。

微公交集合$B$根据乘坐资源配置可分为3类（见表2），即$B=\underset{p\in t}{\cup }B(p),\mathrm{其中}t\in \left\{\mathrm{1,2},\mathrm{3}\right\}$（$p=\mathrm{1}$代表小型微公交，$p=\mathrm{2}$代表中型微公交，$p=\mathrm{3}$代表大型微公交）。每一辆微公交可记为，其中，$p$表示车型；$l$表示微公交当前所在位置；$q(r)$表示微公交$b$当前乘坐资源$r$的最大容量（$r=\mathrm{1}$代表站位，$r=\mathrm{2}$代表座位，$r=\mathrm{3}$代表轮椅空间）；$s_{\mathrm{s}\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{d}}$表示微公交$b$当前的行程计划表，由路网中若干个节点序列组成；$s_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}}$表示微公交的状态，空闲状态值为0，服务状态值为1。

乘客的出行订单可记为

$$w_t(\beta ),\gamma (\beta ),w_d(\beta ),d_t(\beta )>$$

其中，$t(\beta )$表示订单$\beta$的提交时刻；$o(\beta )$表示订单$\beta$的出发地；$d(\beta )$表示订单$\beta$的目的地；$z(r,\beta )$表示订单$\beta$需要占用$r$类乘坐资源的数量；$p_t(\beta )$表示订单$\beta \mathrm{的}$乘客最早上车时刻，即为微公交需要到达出发地的时刻；$w_t(\beta )$代表订单$\beta \mathrm{的}$乘客可接受的最大等待时间；$\gamma (\beta )$表示订单$\beta \mathrm{的}$乘客的合乘意愿；$w_d(\beta )$表示订单$\beta \mathrm{的}$乘客可接受的最大步行距离；$d_t(\beta )$表示订单$\beta$的乘客最晚下车时刻，即微公交需要到达目的地的最晚时刻。模型规定最大绕行时间系数为$\alpha$。

1.2.2　问题假设

自动驾驶微公交的调度模型构建基于以下假设：

（1）所有自动驾驶微公交均在固定且有边界的服务区域内运行，仅接受服务区域内的出行订单，即乘客的出发地与目的地均在服务区域内。

（2）每辆微公交从固定地点车场出发，任务执行完毕后回到固定终点车场。

（3）微公交行程中任意两相邻站点间的行驶距离为两站点间的最短距离。

（4）乘客均能按时到达站点。若微公交早于乘客最早上车时间到达上车站点，则需等待至乘客最早上车时间才能对乘客进行服务。

（5）总上下车时间与上下车乘客人数成正比，且单个乘客的上下车时间为常数$\mathrm{\Delta }t$。

（6）单个订单请求占用的乘坐资源不超过自动驾驶微公交的最大乘坐资源。

（7）不考虑道路拥堵情况，微公交行驶速度相同且恒定。

（8）若微公交当前时段内处于空闲状态，则微公交空驶回到固定终点车场。

（9）微公交接到的新订单，不改变原行程表的订单服务顺序。

（10）在满足微公交容量约束的前提下，单辆微公交可服务于多个订单。

（11）路网中任意两节点之间的路径采用Floyd算法计算的最短路径。

1.2.3　自动驾驶微公交动态调度模型

面向个性化需求的自动驾驶微公交动态调度模型以低运营成本和高服务质量为优化目标，遵循容量约束、时间窗约束、服务约束、合乘约束、绕行约束、访问顺序约束等约束条件。根据前文提出的自动驾驶微公交调度策略，构建自动驾驶微公交调度模型（模型参数定义见表3）。调度优化目标为

表3  模型参数定义

Tab.3  Definition of model parameters

符号	定义
$x(b,i,j)$	微公交$b$是否经过路段$(i,j)$，若经过则$x(b,i,j)=1$，否则$x(b,i,j)=0$
$y(b)$	微公交$b$是否被使用，若是则$y(b)=1$，否则$y(b)=0$
$M$	出行订单集合，$M=\left\{\mathrm{1,2},\dots ,n\right\}$
$B$	微公交集合，$B=\left\{\mathrm{1,2},\dots ,b\right\}$
P	乘客上车节点集合，$P=\left\{1,\cdots ,n\right\}$
D	乘客下车节点集合，$D=\left\{n+1,\cdots ,2n\right\}$
$p$	3种车型，$p\in \left\{\mathrm{1,2},3\right\}$，1代表小型，2代表中型，3代表大型
$r$	3种车内乘坐资源，$r\in R,R=\left\{\mathrm{1,2},3\right\}$，1代表站位，2代表座位，3代表轮椅空间
$B(p)$	车型$p$的微公交集合
$f_{\mathrm{c}}(p)$	车型$p$ 的固定成本，元·辆-1
$u_{\mathrm{d}\mathrm{c}}(p)$	车型$p$的单位里程运行成本，元·km-1
$u_{\mathrm{t}\mathrm{c}}(p)$	车型$p$的单位时间等待成本，元·h-1
$Q(r,b,i)$	离开节点$i$时，微公交$b$内乘坐资源$r$的占用数
$P_{\mathit{t}}(i)$	乘客在节点$i$等待车辆到达的时间，s
$l(b)$	微公交$b$当前位置
$q(r,b)$	微公交$b$的$r$类乘坐资源的最大容量
$s_{\mathrm{s}\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{d}}(b)$	微公交$b$的行程表
$s_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}}(b)$	微公交$b$的状态， 空闲状态$s_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}}(b)=0,$服务状态$s_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}}(b)=1$
$s_{\mathrm{s}\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{d}}(b,i,j)$	微公交$b$的行程表中，从节点$i$到节点$j$的路径所经过的所有节点集合
$A_t(b,i)$	微公交$b$到达节点$i$的时刻，s
$S_t(b,i)$	微公交$b$在节点$i$处开始服务的时刻，s
$W_t(b,i)$	微公交$b$提前到达节点$i$等待乘客的时间，s
$c(b,i)$	微公交$b$在节点$i$处上下客所需的服务时间，s
$D(b)$	微公交$b$的总行驶里程，m
$t(\beta )$	订单$\beta$的提交时刻
$o(\beta )$	订单$\beta$的出发地
$d(\beta )$	订单$\beta$的目的地
$z(r,\beta )$	订单$\beta$需要占用的r类乘坐资源的数量
$p_t(\beta )$	订单$\beta$的乘客最早上车时刻
$w_t(\beta )$	订单$\beta$的乘客可接受的最大等待时间，s
$\gamma (\beta )$	订单$\beta$的乘客的合乘意愿，若愿意合乘则$\gamma (\beta )=1$，否则$\gamma (\beta )=0$
$d_t(\beta )$	订单$\beta$的乘客最晚下车时刻
$e_t(i)$	节点$i$处时间窗的开始时刻
$l_t(i)$	节点$i$处时间窗的结束时刻
$\mathrm{\Delta }t$	单位乘客的上车/下车时间，s
$R_t(b,i)$	订单i中乘客在微公交$b$上的乘坐时间，s
$h(i,j$）	节点$i$到节点$j$的最短距离，m
$h(b,i,j)$	根据微公交$b$行程计划表，节点$i$到节点$j$的实际距离，m
$\mathrm{\Delta }d(i,k,j)$	将节点$k$插入节点$i$与节点$j$之间后产生的额外距离，$\mathrm{\Delta }d(i,k,j)=h(i,k)+h(k,j)-h(i,j)$，m
$v$	微公交运行速度，$\mathrm{m}$·s-1
$\rho$	乘客时间价值
$\mu$	拒绝乘客惩罚系数

$$\mathrm{m}\mathrm{i}\mathrm{n}f={\displaystyle \sum _{p=\mathrm{1}}^{\mathrm{3}}}\sum _{b\in B}{f}_c(p)y(b)+{\displaystyle \sum _{p=\mathrm{1}}^{\mathrm{3}}}\sum _{b\in B}{u}_{dc}(p)D(b)+{\displaystyle \sum _{p=\mathrm{1}}^{\mathrm{3}}}\sum _{b\in B}\sum _{i\in P}{u}_{tc}(p)W_t(b,i)+\rho \left(\sum _{i\in P}{P}_t(i)+{\displaystyle \sum _{b\in B}^{\mathrm{3}}}\sum _{i\in P}{\displaystyle \sum _{r=\mathrm{1}}^{\mathrm{3}}}{W}_t(b,i)(Q(r,b,i)-z(r,\beta ))\right)+\mu \left(\sum _{i\in P}\sum _{r\in R}z(r,\beta )\left(\mathrm{1}-\sum _{j\in P\bigcup D}\sum _{b\in B}x(b,i,j)\right)\right)$$

（1）

第一部分为公交的固定运行成本，第二部分为公交行驶成本，第三部分为车辆提前到达等待乘客的时间成本，第四部分和第五部分为服务质量的量化。其中，第四部分包含乘客在上车点$i$等待车辆到达的时间成本$P_t(i)$和车内乘客由于车辆早到站点等待的时间成本，第五部分为拒绝订单$\beta$乘客上车的惩罚成本，即订单被系统拒绝而产生的惩罚成本。

乘坐资源约束条件为：

$$z(r,\beta )=z(r,n+\beta )\ge \mathrm{0},\forall \beta \in P$$

（2）

$$\sum _{r\in R}Q(r,b,i)+x(b,i,j)\sum _{r\in R}z(r,\beta )\le \sum _{r\in R}q(r,b)$$，

$$\forall i\in \mathrm{0}\bigcup P,j\in P,b\in B,r\in R$$

（3）

$$\sum _{r\in R}Q(r,b,i)-x(b,i,j)\sum _{r\in R}z(r,\beta )\ge \mathrm{0},$$

$$\forall i\in P\bigcup D,j\in D,b\in B,r\in R$$

（4）

$$Q(r,b,i)\ge \mathrm{0},\forall i\in V,b\in B,r\in R$$

（5）

式（2）表示同一个出行订单，在上车节点$i$处占用的和在下车节点$(n+i)$处释放的乘坐资源数相同且非负。式（3）确保只有当订单内各类乘坐资源占用数不超过车辆$b$当前可提供的乘坐资源数，才能被服务。式（4）保证在下车点$j$车内各类资源的下车人数小于等于车内人数。式（5）表示车内乘坐资源占用数为非负。

时间窗口约束为：

$$e_t(i)=p_t(\beta ),\forall i\in P$$

（6）

$$l_t(i)=e_t(i)+w_t(\beta ),\forall i\in P$$

（7）

$$e_t(n+i)=e_t(i)+\frac{h(i,n+i)}{v},\forall i\in P$$

（8）

$$l_t(n+i)=d_t(\beta ),\forall i\in P$$

（9）

$$c(b,i)=\mathrm{\Delta }t\sum _{r\in R}z(r,\beta ),\forall i\in P\bigcup D$$

（10）

$$\sum _{j\in V}x(b,i,j)(S_t(b,i)-A_t(b,i))\ge \mathrm{0},\forall i\in V,b\in B$$

（11）

$$\sum _{j\in V}x(b,i,j)(S_t(b,i)-A_t(b,i))\le \sum _{j\in V}x(b,i,j)W_t(b,i),\forall i\in P\bigcup D,b\in B$$

（12）

$$W_t(b,\mathrm{0})=W_t(b,\mathrm{2}n+\mathrm{1})=\mathrm{0},\forall b\in B$$

（13）

$$e_t(i)\le S_t(b,i)\le l_t(i),\forall i\in P\bigcup D,b\in B$$

（14）

式（6）~（14）主要确保微公交实际到达乘客上车地点$i$的时刻不能超过乘客的最晚上车时刻，且车辆不能晚于乘客最晚下车时刻到达乘客下车地点（$i+n$）。式（6）定义节点$i$处时间窗的开始时刻等于订单$i$乘客的最早上车时刻。式（7）定义节点i处时间窗的结束时刻等于开始时刻加上订单$i$乘客可接受的最大等待时间。式（8）、（9）定义了下车点（$n+i$）的时间窗。式（10）给出了各节点所需服务时间的计算公式，同时规定了服务时间仅在乘客上下车动作时发生。式（11）约束了车辆到达节点后才能开始服务。式（12）定义了车内乘客等待时间，式（13）定义了起点车场和终点车场的等待时间均为零。式（14）表示车辆开始服务的时间必须位于节点的时间窗内。

订单约束为：

$$\sum _{b\in B}\sum _{j\in V}x(b,i,j)\le \mathrm{1},\forall i\in P$$

（15）

$$\sum _{b\in B}\sum _{i\in V}x(b,i,j)\le \mathrm{1},\forall i\in P$$

（16）

$$\sum _{j\in V}x(b,i,j)-\sum _{j\in V}x(b,j,n+i)=\mathrm{0},\forall i\in P,b\in B$$

（17）

$$\sum _{i\in V}x(b,i,j)-\sum _{i\in V}x(b,j,i)=\mathrm{0},\forall j\in P\bigcup D,b\in B$$

（18）

式（15）、（16）约束一个订单最多只被服务一次。式（17）表示任意一个被服务的订单上车地点和下车地点需由同一辆车服务。式（18）为流量守恒约束。

车辆使用约束为：

$$x(b,\mathrm{0},j)=\sum _{j\in V}x(b,j,\mathrm{2}n+\mathrm{1})=y(b),\forall b\in B$$

（19）

$$x(b,i,j)\le y(b),\forall i,j\in V,b\in B$$

（20）

式（19）表示若车辆被使用，则必须从起点车场出发，最终回到终点车场。式（20）表示若车辆未被使用，则不经过路网中任何节点。

合乘意愿约束为：

$$\sum _{j\in V}x(b,i,j)(\mathrm{1}-\gamma (i))(Q(r,b,i)-z(r,\beta ))=\mathrm{0},$$

$$\forall i\in P,b\in B$$

（21）

$$\sum _{j\in V}x(b,i,j)(\mathrm{1}-\gamma (i))Q(r,b,n+i)=\mathrm{0},$$

$$\forall i\in P,b\in B$$

（22）

$$\sum _{j\in V}x(b,i,j)h(b,i,n+i)=\sum _{j\in V}x(b,i,j)h(i,n+i)$$

（23）

式（21）表示不接受合乘的订单只能分配给当前车内无乘客的微公交。式（22）表示不接受合乘的订单在下车后车内乘客为零。约束（23）保证了微公交在服务不愿意合乘订单的过程中不会接受其他订单。

绕行时间约束为：

$$R_t(b,i)=A_t(b,n+i)-(A_t(b,i)+c(b,i))\le \frac{(\mathrm{1}+\alpha )h(i,n+i)}{v},\forall i\in P,b\in B$$

（24）

$$h(b,i,n+i)\le (\mathrm{1}+\alpha )h(i,n+i),\forall i\in P,b\in B$$

（25）

式（24）约束订单i乘客的实际乘车时间不能超过最短行程时间的（$\mathrm{1}+\alpha$）倍。由于本文中假定微公交匀速行驶，因此绕行时间约束（24）可简化为距离约束，如式（25）所示。

访问顺序结束为

$$\sum _{j\in V}x(b,i,j)(A_t(b,n+i)-A_t(b,i))\ge \mathrm{0},$$

$$\forall i\in P,b\in B$$

（26）

同一订单$i$乘客的上车时刻必须早于下车时刻。

2 自动驾驶微公交动态调度模型求解

选择变邻域搜索和插入算法对自动驾驶微公交调度模型进行求解。根据自动驾驶微公交动态调度模型特点，将求解算法分为2个阶段：静态调度阶段和动态调度阶段。在静态调度阶段采用变邻域搜索算法进行求解，在动态调度阶段采用基于剪枝的插入算法进行求解，以提高求解效率。

2.1　变邻域搜索算法

2.1.1　邻域结构

交换邻域结构用于交换2个路径中的订单序列，每个路径上的订单序列长度不能超过当前邻域结构的大小。因此，邻域大小为2的交换由以下步骤组成：①随机选择2条路径；②随机选择2条路径上订单序列的长度（长度不能大于邻域大小），再随机选择2个序列中的第1个节点；③必须保证交换后2条路径上的所有订单序列都与它们所属路径上的车辆兼容（容量约束），否则将重新开始整个过程。在选择好路径和订单序列后，每个序列中的订单将从原来的路径中移除，并插入到目标路径中最合适的位置（需要保持订单序列的顺序）。插入订单的顺序是先插入订单上车节点，再插入订单下车节点。整个过程根据目标函数最小化的原则确定订单的上下车地点在路径中的最终插入位置。

移动邻域结构将一个订单从一条路径移动到另一条路径。若将订单从路径A移动到路径B，则必须确保路径B上的订单序列与该路径上的车辆兼容（容量约束），并且将订单插入到使优化效用函数值最小的位置。选择要移动的订单时，需要随机选择一条路径并随机选择要移动的订单。

修复邻域结构与移动邻域结构类似，但仅对不可行的路径进行操作，将订单从不可行的路径中移除，并将订单插入另一条路径中。首先，从不可行的路径中随机选择一定数量的订单，订单的数量不能超过当前邻域大小。选择完要移动的订单后，随机选择路径并将订单插入其中，具体操作与移动邻域结构和交换邻域结构类似。

链式邻域结构用于在路径中插入一组订单。首先，从路径中选择一个节点作为链的起点；然后，从该节点开始随机选择一定数量的节点，将它们视为一个订单序列并尝试插入到另一条路径中。在选择要插入的路径时，需要确保对应微公交的乘坐资源可满足订单的乘坐资源需求，并且最终插入位置的目标函数值最小。

2.1.2　局部搜索策略

局部搜索策略仅对在扰动阶段发生过变化的路径进行操作。在局部搜索过程中，将路径中所有订单按照原服务顺序使用插入法重新插入路径中，使得插入后产生的微公交行驶里程成本最低。

2.1.3　变邻域搜索算法流程

变邻域搜索算法流程如图3所示。

图3  变邻域搜索算法流程

Fig.3  Flowchart of variable neighborhood search algorithm

2.2　插入算法

2.2.1　剪枝规则

采用基于剪枝的算法将订单的上车点位置和下车点位置高效地插入微公交的当前行程表中，同时通过目标函数最小来确定新发生的订单在路径中的位置。此处新订单的插入不能违背微公交原行程表中待服务订单约束。调度中心将首先根据到达时间窗约束得到候选微公交集合，再对候选微公交集合中的每一辆车，计算订单插入当前微公交行程中各个位置的额外行驶里程成本，获得订单的最佳插入位置和最低额外行驶里程成本。最后，从候选微公交集合中选择额外行驶里程成本最低的微公交与该订单进行匹配。

2.2.2　插入算法流程

插入算法流程如图4所示。

图4  插入算法流程

Fig.4  Flowchart of insertion algorithm

3 案例分析

3.1　数据概况

使用位于上海市嘉定区安亭镇的真实路网（见图5）进行案例分析。该路网包含多条城市主要道路和支路，共26个节点，41条路段，长度30 km，总面积约13 m²，包括住宅区和商业区等。将该路网覆盖区域设置为自动驾驶微公交的运营区域，路网则作为后续距离计算以及微公交路径规划的依据。为了测试自动驾驶微公交动态调度方法的有效性，使用随机生成的出行订单测试集进行案例分析。出行订单测试集为自动驾驶微公交运营区域内各个位置之间的出行需求，包括出发地、目的地、最早上车时间、最晚下车时间、最大等待时间和最大步行距离、所需要的乘坐资源以及合乘意愿等，表4给出了订单的具体信息。

图5  上海市嘉定区部分区域路网

Fig.5  Road network in Jiading District, Shanghai

表4  出行订单详细信息

Tab.4  Details of travel requests

字段	类型	含义	示例
ReqNo	int	订单编号	1
SubmitTime	str	订单提交时刻	2023‒01‒01 08：12：34
PLng	float	出发地经度	121.165 35
PLat	float	出发地纬度	31.270 18
DLng	float	目的地经度	121.164 35
DLat	float	目的地纬度	31.280 69
r1	int	一般乘客数	1
r2	int	座位乘客数	1
r3	int	轮椅乘客数	1
PickupEarlyTime	str	最早上车时刻	2023‒01‒01 08：15：00
DropoffLateTime	str	最晚下车时刻	2023‒01‒01 09：00：00
MaxWaitTime	int	最大等待时间，min	10
ShareWill	int	合乘意愿，1：愿意合乘， 0：不愿合乘	0
MaxWalkDist	int	最大步行距离，m	500

Zhang等^［27］提出了车辆成本和车辆容量的回归方程，车辆的固定成本和运营成本随着容量的增大而成比例增大。自动驾驶微公交的成本相关参数可参考该研究，并按1∶7.65的比例将欧元转换为人民币。乘客时间价值为59.67元·（人·h）^-1。表5给出了自动驾驶微公交动态调度模型参数的取值。此外，假设单个乘客上/下车时间均为1 s。考虑到未来自动驾驶车辆的运行水平应不低于人工驾驶，但受实际城市道路车辆行驶速度限制，本文假设微公交的行驶速度为30 km·h^-1。

表5  自动驾驶微公交动态调度模型参数

Tab.5  Parameters of autonomous minibus scheduling model

参数	定义	单位	值
$f_{\mathrm{c}}(1)$	小型微公交固定成本	元·辆-1	10.56
$u_{\mathrm{d}\mathrm{c}}(1)$	小型微公交单位里程运行成本	元·km-1	1.30
$u_{\mathrm{t}\mathrm{c}}(1)$	小型微公交单位时间等待成本	元·h-1	25.04
$f_{\mathrm{c}}(2)$	中型微公交固定成本	元·辆-1	15.84
$u_{\mathrm{d}\mathrm{c}}(2)$	中型微公交单位里程运行成本	元·km-1	1.95
$u_{\mathrm{t}\mathrm{c}}(2)$	中型微公交单位时间等待成本	元·h-1	37.56
$f_{\mathrm{c}}(3)$	大型微公交固定成本	元·辆-1	23.76
$u_{\mathrm{d}\mathrm{c}}(3)$	大型微公交单位里程运行成本	元·km-1	2.93
$u_{tc}(3)$	大型微公交单位时间等待成本	元·h-1	56.34
$v$	车辆速度	km·h-1	45
$\alpha$	绕行时间系数		0.5
$\rho$	乘客时间价值	元·（人·h）-1	59.67
$\mu$	拒绝乘客惩罚系数	元·人-1	40
$a_1$	绕行约束惩罚系数	元·订单-1	50
$a_2$	时间窗约束惩罚系数	元·订单-1	50
$a_3$	容量约束惩罚系数	元·订单-1	50
$a_4$	合乘约束惩罚系数	元·订单-1	50

3.2　结果分析

3.2.1　车型的影响

为了分析车型对系统的影响，在同样的订单数下设置仅包含中型微公交的单车型车队与多车型车队进行比较（服务率为100%），如图6、7所示。可见，在服务率为100%的情况下，多车型系统的各项成本（总成本与人均成本）均低于单车型系统。系统、运营和乘客等待总成本平均降低27%、29%、11%，表明多车型可以更好地适应个性化需求，提高系统运行效率，降低乘客的等待成本等。

图6  多车型与单车型的系统、运营和乘客等待总成本对比

Fig.6  Comparison of total system, operation and waiting cost between multi-type and single-type

图7  多车型与单车型的人均系统、运营和乘客等待成本对比

Fig.7  Comparison of system, operation and waiting cost per person between multi-type and single-type

3.2.2　乘坐资源的影响

为了分析车内乘坐资源对系统服务的影响，在相同订单和相同规模车队的前提下，比较提供轮椅空间和不提供轮椅空间对乘客服务的影响，如图8、9所示。假设：若微公交内部无轮椅空间，则有轮椅出行需求的订单都会被系统拒绝。

图8  不同乘坐资源配置下系统、运营、乘客等待总成本及服务率对比

Fig.8  Comparison of total system, operation, waiting cost and service rate between different ride source configurations

图9  不同乘坐资源配置下人均系统、运营和乘客等待成本对比

Fig.9  Comparison of system, operation and waiting cost per person between different ride source configurations

由图8可见，由于有轮椅需求的订单会被拒绝，因此不提供轮椅空间的系统服务率大幅降低，仅是提供轮椅空间系统服务率的30%~50%。服务率取决于轮椅需求在总需求中的占比。同时，由于服务率增加，因此提供轮椅空间的系统在同样规模车队的情况下，系统总成本、运营总成本和乘客等待总成本平均增加163%、156%、216%。总成本的增加取决于不同类型需求的占比以及服务率。由图9可见，不提供轮椅空间的人均系统成本会随订单数的增加而降低，并逐渐低于提供轮椅空间的系统人均成本。虽然不提供轮椅空间的系统更具有成本优势，但从社会性角度出发，提供轮椅空间的系统可以为更多的出行需求类别提供服务，更好地服务有轮椅出行需求的弱势群体，更具有社会公平性。

3.2.3　合乘意愿的影响

为了分析乘客合乘意愿对系统服务的影响，在同样订单数量和车队规模的情况下，对仅提供合乘服务和提供非合乘服务的系统进行对比，如图10、11所示。假设：若系统仅提供合乘服务，则不愿与他人合乘的出行订单会被系统拒绝。由图10可见，由于不愿合乘的订单会被拒绝，因此仅提供合乘服务的系统服务率降低。服务率取决于不愿合乘订单的需求量。由于服务率高，因此提供非合乘服务的系统各项总成本都比仅提供合乘服务的系统高，系统总成本、运营总成本和乘客等待总成本平均增加79%、83%、59%。由图11可见，仅提供合乘服务的系统人均乘客等待成本高于提供非合乘服务的系统。仅提供合乘服务的系统人均乘客等待成本和人均运营成本随着订单数的增加，低于提供非合乘服务的系统。满足更多个性化需求会引起人均运营成本的增加。

图10  提供/不提供非合乘服务的系统、运营、乘客等待总成本及服务率对比

Fig.10  Comparison of total system, operation, waiting cost and service rate with amd without providing non-pooling services

图11  提供/不提供非合乘服务的人均系统、运营、乘客等待成本对比

Fig.11  Comparison of system, operation, waiting cost per person with and without providing non-pooling services

4 结论

（1）通过调查梳理了乘坐资源、合乘意愿以及出行效率3类公交出行的个性化需求。

（2）建立了面向个性化需求的“预约乘车+实时乘车+非固定站点”自动驾驶微公交服务模式。

（3）构建了以自动驾驶微公交运营成本以及服务质量为目标，考虑乘坐资源约束、步行距离及绕行约束、时间窗约束、订单和车辆使用约束、合乘意愿约束的自动驾驶微公交动态调度数学模型，并设计了“变邻域搜索算法+基于剪枝的插入算法”的两阶段求解算法。

（4）案例分析结果表明：在同样订单需求和车队规模的前提下，多车型微公交系统可以更好地适应出行需求的变化，提高系统运行效率，降低乘客的等待成本等；在同样的订单需求下，提供轮椅空间虽然会导致系统成本增加，但可以提高乘客服务率，兼顾弱势出行群体，提升社会公平性；在同样的订单需求下，提供非合乘服务的系统各项总成本均比仅提供合乘服务的系统高；系统成本的增加取决于轮椅出行需求的占比和非合乘需求的占比。

作者贡献声明

涂辉招：总体架构、研究方法提出，结果讨论，论文润色。

刘建泉：数据处理，模型构建，实证分析，结果讨论。

郑叶明：研究方法提出，思路梳理，结果分析，结论总结。

李 浩：研究思路提出，指标确定，论文润色。