考虑乘客出行偏好的需求响应公交系统设计

Demand Response Bus System Design Considering Passenger Travel Preferences

摘要: 本文提出了一种需求响应型公交系统的数学模型，以此满足大规模的公交运行网络下密集的乘客乘车需求，并有效提高公共交通系统的服务质量与可达性。此方法的设计原理主要是通过引导乘客到达距离最近的公交车站，并合理安排公交车将乘客顺利送至交通系统中的换乘枢纽站点。为此，本研究提出了一种多目标混合整数线性规划模型，目的是找到能够使乘客步行距离、公交运行时间、乘客偏好乘车时间窗与车辆到达时间窗差值均为最小值的公交运行线路。针对这一混合整数规划模型，进一步提出了基于蚁群算法框架的三阶段混合启发式算法。最后引入一个具体的面向实际路网的案例对本次研究中构建与开发的模型和算法进行有效性分析。

Abstract: In this paper, a mathematical model of Demand Responsive Transit system is proposed considering the intensive passenger demand in large-scale public transport network, to effectively improve the service quality and accessibility of urban transit system. The design logic of this method is to guide passengers to the nearest bus station, and dispatch buses reasonably to transport passengers to the connected station of the major transit system. Therefore, this paper proposes a multi-objective mixed integer linear programming model, which aims to design the bus routes that can minimize the difference between passenger walking distance, bus traveling time, and the difference between the passenger preference time window and vehicle arrival time window. For this mixed integer programming model, a three-stage hybrid heuristic algorithm based on ant-colony algorithm framework is proposed. Finally, a specific case applied to the real road network is introduced to analyze the effectiveness of the proposed model and algorithm in this research.

1. 引言

随着城市规模的扩张和城市形态的多样化，发展相对缓慢的传统公共交通形式已经无法满足个性化乘客出行需求，导致公交运行路线偏离乘客期望乘车地点、乘客等待时间过长、乘客换乘时间过长等问题。在当前的城市发展进程中，随之产生的另一主要现象为城市道路中的私家车数量发生急剧增长，尤其是在早晚高峰时间，城市道路的交通拥堵问题极为严重，制约居民出行效率的同时影响人们的身体健康。因此，我国交通部门正积极思考如何最大程度上避免或减少交通拥堵所造成的影响，确保道路交通高速、安全、舒适的这一问题 [1]。大部分的国家和行政当局已实施以公共交通为导向的城市交通系统，将其作为缓解资源紧张、交通拥堵以及环境污染问题的最有效战略之一 [2]。

随着人们对于选择公共交通工具作为主要出行方式这一倾向性的增强，具有乘车需求的乘客数量不断增加，对于乘车服务的质量也提出了更高的要求，与此同时，城市公交网络也正在迅速发展完善为更大的规模 [3]。面对大规模的公交网络和愈发密集的乘客乘车需求，公交运营机构在设计新一代公交系统时，在需求管理策略中更加关注乘客的可达性需求，为解决城市道路拥挤问题提供了新方向 [4] [5]。近年来，随着城市轨道交通的高速发展已经进入了网络化运营阶段，大运量轨道交通为骨架、常规公交为主体、多种定制化公交为补充的新型发展模式已经在各大城市逐渐发展成型，城市居民随着生活水平的提高对于出行便利性的需求也随之不断增加 [6] [7]。常规公交的服务模式已经不能满足市民日益增长的对公交服务品质的需求，公交服务模式的改革是势在必行的 [8]。

由于传统公交系统现存的诸多问题有待解决，同时在面对大规模的公交网络和密集的乘客乘车需求时，目前还没有一个相对成熟且直接有效的方法实现多样化定制公交系统的设计 [9] [10]。在1984年，Daganzo和Carlos [11] 率先提出需求响应公交的具体概念，并通过对比单一线路的需求响应公交和固定线路公交总成本证明，在需求密度较低时，需求响应公交表现更好，相对于布设固定站点而言，“门到门”的服务将带来更低的成本消耗，这引起了对这类问题研究的热潮。在之后的研究中可以发现，需求响应性公交的路径级优化设计需要考虑诸多关键因素，例如配车数量、松弛时间的设置等，以这些因素作为约束或变量对路径和行车时刻表进行优化，达到系统整体最优的目标。按照响应需求的实时与否，现有研究可以大致分为两类：静态优化设计和动态优化设计。在静态优化设计中，Quadrifoglio等人 [12] 建立了一种混合整数模型解决静态MAST时刻表优化问题，并对乘客的行为给定合理假设来排除部分不可行解以提高算法的求解效率，在部分实例中证明这种方法能够减少90%的计算时间。Aldaihani等人 [13] 在传统路径优化问题上进行拓展，提出来一种面向固定线路公交和需求响应型公交混合网络的路径优化问题，同时考虑乘客上下车需求建立混合整数模型，同时设计了一种基于A*算法的启发式搜索算法进行高效求解。上述研究中，学者们从单个车辆、单个路径的角度出发进行优化设计，但实际运营过程中往往需要多个车辆进行服务。因此，Jaw等人 [14] 以多车为背景，以最小化公交系统运营成本和乘客出行时间成本，通过插入算法先将乘客分配到备选车辆后，进一步优化各个车辆的运行时刻表。Liaw等人 [15] 考虑需求响应型公交和固定线路公交的联合优化，以最小化运营成本为优化目标，通过大量实例测试得到这种联合运营的方式能够增加10%的客流吸引量，同时减少10%的车辆使用。

在动态路径设计问题中，Quadrifoglio等人 [16] 在之前的静态研究上继续改进，针对MAST系统的动态路径优化问题提出插入式启发式算法。最后通过实例仿真发现该方法能够解决实际应用过程中路径和时刻表的实时动态更新，还具有较高的求解效率和质量。Madsen等人 [17] 在Jaw等人 [14] 研究的基础上，提出了一种能够根据乘客随机需求动态更新线路和时刻表，和考虑乘客预计出行时间窗约束的动态插入算法。Novoa等人 [18] 在传统车辆路径规划问题(Vehicle Routing Problem, VRP)中考虑随机需求，尽可能满足所有乘客需求的前提下，减少乘客的等待时间和运营成本，并采用近似动态规划算法进行求解，在保证精确解的基础上具有较高的求解效率。Horn [19] 通过对接受到的出行需求进行预处理，判断该需求是否满足最长运营时间等约束，以最小化额外运营时间和最大化未来车队载客量为目标，将随机产生的需求插入到已有路径中。王力生等人 [20] 则创新性地从图论的角度出发，通过寻找欧拉圈的方法，对路径优化设计进行了尝试。王正武等人 [21] 研究了同接送模式下，需求响应型接驳公交的路径与车辆调度的协同优化问题，同时优化车头时距、所选车型和车辆路径三个决策变量。

综上所述，已有具体而言，针对需求响应接驳公交的路径优化与设计，仍有以下不足亟需深入讨论研究：

1) 已有研究多集中于讨论服务范围、需求分布密度等因素对需求响应接驳公交的影响，忽略了从系统最优和乘客最优的不同角度解析各种设计参数对公交接驳服务的适用性的影响。

2) 由于需求响应型接驳公交对系统稳定性和响应实时性具有很高要求，已有设计思路缺少对不同层次、不同优先级、不同时效性设计参数的整合与优化。

3) 已有研究思路大多为基于乘客时间窗约束进行车辆路径优化，鲜有乘客出行时间窗与车辆路径联合优化的研究，需要同时考虑乘客出行时间窗偏好和实际路网情况多种信息条件，进行乘客登车站点选择、路径优化设计、行车计划设计联合优化的设计机理。

因此，旨在设计一个考虑用户出行偏好性的定制化需求响应公交系统，作为定制公交的一种主要形式，需求响应公交能够及时响应乘客个性化出行需求，基于乘客个性化出行偏好提供优化协调的乘车共享服务，有效利用有限的公交系统资源，尽量节省社会资源的同时最大程度地满足从出发地到目的地的时间敏感型交通服务需求。

针对乘客换乘过程中接驳距离长、等待时间长、换乘时间长等问题，本研究以乘客接驳步行距离最短和乘客换乘等待时间最短为优化目标，实现乘客乘车行为引导；并根据乘客登车地点和时间偏好合理调度公交车，将乘客准时高效地运送到主要轨道线路上的换乘站点，提供“门到门”的公共交通出行服务。与传统公交线路相比，需求响应式服务模式能够更好地适应特殊出行群体的需求，具有便捷、舒适、“门到门”灵活的运营线路和更灵活的服务时间等特点。对于公共交通运营商而言，需求响应型公共交通服务在满足旅客需求的前提下，能够更好地实现资源的优化配置，有效降低不必要的公共交通运营成本。综上，需求响应式公交系统的开发与优化对于城市居民和公共交通运营商来说是一个双赢课题，值得更多的学者去挖掘其他可能的系统模型与算法。

2. 研究方法

本文提出的需求响应公交系统设计框架如图1所示，该系统包括三个子模块，每个模块的职能如下：

1) 乘客端：乘客通过网络或手机软件提前提出出行申请，系统采集乘客预计登车时间窗信息，以及预计登车位置信息；

2) 需求响应公交设计端：基于需求响应公交系统设计模型，以乘客出行便捷性与需求响应公交系统运营成本综合最优为目标，实现需求响应公交运行线路与时刻表设计；

3) 系统控制端：完成系统历史数据的储存，进行系统内乘客端与公交设计端双方的信息双向反馈。

Figure 1. Design of operation mechanism of demand response bus system

图1. 需求响应公交系统运行机制设计

3. 混合整数模型建立

3.1. 系统描述

本文所提出的需求响应公交系统如图2所示，考虑乘客出行时间窗与接驳距离偏好，将乘客需求分配到最优需求响应公交站点，将候选公交站点与公交始发站与终点站串联形成需求响应公交线路。该混合整数模型的优化目标为：

1) 最小化乘客步行距离；

2) 最小化需求响应公交运行时间；

3) 基于终点站(接驳轨道站点)发车时刻设计需求响应公交运行时刻表。

为保证所提出模型符合实际运营条件，并适用于各种路网类型和离散乘客需求，提出以下假设：

1) 系统内所有时间，包括乘客步行时间与需求响应公交各线路运行时间固定，各路段上公交运行时间通过历史数据获得；

2) 终点站(接驳轨道站点)无乘客容量限制；

3) 系统内候选公交停靠站点位置及乘客容量已知且固定。

Figure 2. Demand response bus design scenario

图2. 需求响应公交设计场景

3.2. 系统目标函数的建立

为设立考虑乘客出行偏好性的需求响应公交系统，本研究提出了一种混合整数规划优化模型，其优化目标为乘客步行时间、公交线路运行时间、预定义时间窗(即乘客预计出行时间窗)与服务时间窗(即车辆到达时间窗)之间的差距最小的公交运行线路方案。因此，建立混合整数规划模型的目标函数如式(1)所示：

$\min f={\displaystyle {\sum }_{j\in M}{\displaystyle {\sum }_{i\in I}\frac{X_{ij}\cdot D_i\cdot d_{ij}}{W_s}}}+{\displaystyle {\sum }_{j\in D\cup M}{\displaystyle {\sum }_{m\in M\cup MS}{\displaystyle {\sum }_{k\in K}{Z}_{jm}^k\cdot t_{jm}}}}+{\displaystyle {\sum }_{j\in M}{\displaystyle {\sum }_{k\in K}\left(P_j^k-A_j^k\right)}}$ (1)

式中， $j,m$ ——公交运行线路网络中的公交站点；

M——候选公交车站的集合；

MS——在整个公交运行路径中的终点公交车站，在本研究中设定仅有一个终点车站；

D——此模型中的公交车总站；

k——模型中的公交线路；

K——该公交网络中公交行驶路线的集合；

i——模型中的需求点；

I——模型中需求点的集合；

$X_{ij}$ ——将需求点i分配给了候选公交车站j时 $X_{ij}=1$，否则 $X_{ij}=0$ ；

$D_i$ ——在需求点i处的乘客数量；

$d_{ij}$ ——乘客从需求点i到候选公交车站j的步行距离；

$W_s$ ——乘客平均步行速度；

$Z_{jm}^k$ ——当j、m两个站点都被选择时 $Z_{jm}^k=1$，并将其串联成公交线路k，否则 $Z_{jm}^k=0$ ；

$t_{jm}$ ——公交车从公交站点j到站点m的行驶时间；

$P_j^k$ ——在公交车站j的预计发车时间；

$A_j^k$ ——预计到达公交车站j的时间。

3.3. 需求响应公交系统设计模型建立

综合考虑乘客端与需求响应公交运营端多方面的约束条件及需求，建立该混合整数规划模型的约束方程：

1) 从各个需求点的要求以及乘客数量等角度来建立以下约束方程：

在所提出的公交运行系统中，为确保公交线路的可行性，并保证该模型中的每一个需求点必须被分配一个候选公交车站，另外要求公交车必须成功接走各个需求点的所有乘客，具体约束方程见式(2)、(3)、(4)：

$X_{ij}\le y_j,\forall i\in I,\forall j\in M$ (2)

${\displaystyle {\sum }_{j\in M}{X}_{ij}}=1,\forall i\in I$ (3)

${\displaystyle {\sum }_{i\in I}{D}_i\cdot X_{ij}}={\displaystyle {\sum }_{m\in M\cup MS}{\displaystyle {\sum }_{k\in K}{C}_{jm}^k}},\forall j\in M$ (4)

式中， $y_j$ ——当候选公交站点j被选择时， $y_j=1$，否则 $y_j=0$ ；

$C_{jm}^k$ ——在候选公交车站j的乘客中分配到从站点j到站点m这一行车路径k的乘客数。

乘客与公交线路间的匹配关系如式(5)和(6)所示：

$C_{jm}^k-Z_{jm}^k\ge 0,\forall j\in M,\forall m\in M\cup MS,\forall k\in K$ (5)

$Q_k-{\displaystyle {\sum }_{j\in M}{\displaystyle {\sum }_{m\in M\cup MS}{C}_{jm}^k}}\ge 0,\forall k\in K$ (6)

式中， $Q_k$ ——在公交运行路线k上的公交最大载客量。

对于乘客的偏好乘车时间窗进行以下定义：对于任意候选公交车站，在公交运行路线k上站点j的预计发车时间需满足分配到站点j的所有乘客的时间窗偏好下界；同时，在公交运行路线k上站点j的预计到站时间需满足分配站点j所有乘客的时间窗偏好上界，如式(7)、(8)：

$P_j^k=e_i\cdot X_{ij},\forall i\in I,\forall j\in M$ (7)

$A_j^k=l_i\cdot X_{ij},\forall i\in I,\forall j\in M$ (8)

式中， $P_j^k$ ——公交运行路线k上站点j的预计发车时间；

$A_j^k$ ——公交运行路线k上站点j的预计到站时间；

$e_i$ ——在需求点i处并选择了站点j的乘客的偏好乘车时间窗下界；

$l_i$ ——在需求点i处并选择了站点j的乘客的偏好乘车时间窗上界。

2) 从公交线路与时刻表设计的角度出发建立以下约束：

$Z_{jm}^k$ 作为需求响应公交线路的设计变量，与公交停靠站点选择变量之间存在以下约束关系，如式(9)所示：

$2\cdot Z_{jm}^k\le y_j+y_m,\forall j\in M,\forall m\in M\cup MS,\forall k\in K$ (9)

需求响应公交始发站与终点站约束及站点进出平衡约束如式(10)、(11)、(12)：

${\displaystyle {\sum }_{p\in D}{\displaystyle {\sum }_{j\in M}{Z}_{pj}^k}}=1,\forall k\in K$ (10)

${\displaystyle {\sum }_{j\in M}{\displaystyle {\sum }_{m\in M\cup MS}{Z}_{jm}^k}}=1,\forall k\in K$ (11)

${\displaystyle {\sum }_{m\in M\cup MS}{\displaystyle {\sum }_{k\in K}{Z}_{jm}^k}}-{\displaystyle {\sum }_{p\in M}{\displaystyle {\sum }_{k\in K}{Z}_{pj}^k}}\ge 0,\forall j\in M$ (12)

对于公交运行线路的行驶时间、行驶距离以及公交时刻表可行性做出了以下约束，如式(13)、(14)、(15)：

$T_{\max }-{\displaystyle {\sum }_{j\in M}{\displaystyle {\sum }_{m\in M\cup MS}{Z}_{jm}^k\cdot t_{jm}}}\ge 0,\forall k\in K$ (13)

${\displaystyle {\sum }_{j\in M}{\displaystyle {\sum }_{m\in M\cup MS}{Z}_{jm}^k\cdot d_{jm}}}-L_{\min }\ge 0,\forall k\in K$ (14)

$A_m^k-P_j^k\ge t_{jm},\forall j\in M,\forall m\in M\cup MS,\forall k\in K$ (15)

式中， $T_{\max }$ ——每条线路的最长行驶时间；

$L_{\min }$ ——每条线路的最小行驶距离；

$d_{jm}$ ——j，m两站点之间的行驶距离。

综上，以乘客端与需求响应端系统综合最优为目标，本研究分别从乘客角度与公交运行线路角度进行分析，融合实际运营场景和约束，构建考虑乘客出行偏好性的需求响应型公交系统设计的混合整数规划模型。由于该模型属于NP-hard问题，尤其是面对实际大规模路网环境和离散化乘客出行需求时，已有算法难以实现高效求解，因此需贴合问题本身构建个性化启发式算法。接下来将基于蚁群算法框架，通过分解复杂问题为较容易求解的子问题，设计三阶段混合启发式算法，以此在可接受时间范围内求得近似最优解。

4. 求解算法

本研究基于所提出的混合整数模型，开发了一个基于蚁群算法框架的三阶段混合启发式算法，算法的基本流程如图3所示。

Figure 3. Three-stage hybrid heuristic algorithm flow design

图3. 三阶段混合启发式算法流程设计

4.1. 阶段一：蚁群算法

在求解模型的第一阶段中，采用蚁群算法获取需求响应公交候选路径，以需求响应公交始发站为起点，换乘枢纽站点为终点，将乘客出行需求数据中乘客出行需求点按照时间窗先后顺序排序并串联，获得候选路径。

在蚁群算法中，首先我们需要数量为N的蚂蚁，将其置于乘客出行时间窗的序列初始点。初始化过程中，设 $t=0$，此时 ${\tau }_{ij}\left(0\right)$ 初始化为常数值， $\Delta {\tau }_{ij}\left(0\right)$ 初始化为0。并利用pheromone矩阵记录随机分布于公交车站旁的所有需求点之间的信息素，分配需求点的最短路径为bestLength。同时每只蚂蚁用allowed存储它可以继续访问的需求点，即需求响应公交候选路径集，如式(16)所示：

$allowed=\left\{k\left(|\frac{e_{\psi \left(k\right)}+l_{\psi \left(k\right)}}{2}+t_{\psi \left(k\right)i}\right)\le \frac{e_i+l_i}{2},\forall k\in K\right\}$ (16)

式中，i、j——分别表示访问需求点的起点和终点；

${\psi }_{\left(k\right)}$ ——路径k上紧邻需求点i的下一个候选站点；

$t_{\psi \left(k\right)i}$ ——由i到 ${\psi }_{\left(k\right)}$ 之间的行程时间；

$e_{\psi \left(k\right)}$ ——候选站点 ${\psi }_{\left(k\right)}$ 对应的时间窗上界；

$l_{\psi \left(k\right)}$ ——候选站点 ${\psi }_{\left(k\right)}$ 对应的时间窗下界。

随后，根据候选路径集，采用伪随机比例规则确定每只蚂蚁的个体转移路径，取伪随机数q，并预

设参数 $q_0$。当 $q\le q_0$ 时，则蚂蚁个体选择令参数 ${\tau }_{i\psi \left(k\right)}\left(t\right){\left[{\eta }_{i\psi \left(k\right)}\right]}^{\beta }$ 的值最大的第k条路径作为下一步的转移路径；若 $q>q_0$，则计算概率值 $p_{ik}^m$，如式(17)所示，蚂蚁个体选择路径集合中概率值最大的第k条路

径作为下一步的转移路径。

$p_{ik}^m=\frac{{\tau }_{i\psi \left(k\right)}^{\alpha }\left(t\right){\eta }_{i\psi \left(k\right)}^{\beta }}{{\displaystyle {\sum }_{k\in allowed}{\tau }_{i\psi \left(k\right)}^{\alpha }\left(t\right){\eta }_{i\psi \left(k\right)}^{\beta }}}$ (17)

式中，q——随机变量，在 $\left[0,1\right]$ 之间服从均匀分布；

$q_0$ ——预定义参数， $q_0\in \left(0,1\right]$, 其大小决定了已有路径与新路径之间的相对重要性；

${\tau }_{i\psi \left(k\right)}\left(t\right)$ ——时间为t时由i到j的信息素因子；

$\Delta {\tau }_{ij}\left(t\right)$ ——时间为t时由i到j的信息素增量；

$\alpha$ ——信息启发式因子；

$\beta$ ——期望启发式因子。

重复以上步骤直到所有需求点均已完成分配为止。综上，阶段一完成了乘客需求点到需求响应公交站点的分配，该阶段输出的结果将直接输入到阶段二，进行需求响应公交运行路径的设计。

4.2. 阶段二：动态规划

动态规划算法也是一种比较常用的算法，其基本原理是以递推的方式去解决将原问题拆分后的各个子问题，最后使得原问题能够得到有效解决。在动态规划的求解过程中，前一个子问题的解会为后一子问题的求解提供有效信息，我们需要通过决策保留那些在求解子问题时的各种可能的局部解，从而丢弃其他局部解，留下最优的局部解。

在第一阶段中，我们已经将需求点与设计的需求响应型公交运行路径进行了连接和排序，在本阶段的目标为在所有乘客的步行速度一定的条件下，根据尽量减少乘客步行时间的原则，为每个需求点选择最合适的候选公交站点。

首先，根据上述混合整数规划模型的约束方程确定候选公交站组 $J_{k\left(i\right)}$。随后，采用回溯法，选取一个换乘枢纽点作为候选路径的终点，从该点出发，根据两个站点间的公交行驶时间以及乘客走到站点候选点的步行时间之和，构建时间成本目标函数，如式(18)所示：

$f_k\left(i\right)={\min }_{\forall j\in J_{k\left(i\right)}}\left[f_k\left(i+1\right)+\alpha \cdot t_{j{u}_k\left(i+1\right)}+\beta \cdot \frac{d_{ij}}{W_s}\right]$ (18)

最后，基于上述候选公交站集合，进行公交停靠站选址。在公交运行路径中所有的需求点均已完成选择后结束，生成需求响应公交运行路径。根据上述算法，我们可以完成需求响应公交路径设计，并保证各需求点上的乘客步行最短的时间到达乘车站点接受乘车服务，这一阶段输出的结果，即需求响应公交运行路径，将直接输入到下一阶段，完成需求响应公交运行时刻表设计。

4.3. 阶段三：多项式算法

在前两个阶段中，我们已经将所有的需求点分配给了路径，并为各个需求点确定了最佳乘车站点，在本阶段中，考虑乘客的出行时间窗偏好，采用多项式算法进行需求响应公交行车时刻表设计，明确路径中公交车到达与离开各个停靠站点的时间，其优化目标为最小化乘客时间窗偏好与服务时间窗的时间差。

首先，根据阶段二的需求响应公交路径设计结果计算各线路到达换乘枢纽站点的预计到达时间，并计算各公交停靠站点的公交预计离站时间。

随后，根据乘客的出发时间 $A_m^k-t_{im}$ 和预计离站时间，生成每个公交停靠站的车辆预计到达时间窗 $\left[l_i-T{D}_{\max },l_i+T{D}_{\max }\right]$。 $l_i$ 为最佳公交停靠站点所服务的乘客出行需求点i的乘客出行时间窗上界， $T{D}_{\max }$

为公交预计离开公交停靠站点候选点j的时间与乘客出行时间窗的上界之间所允许的最大差值。

最后遍历所有公交停靠站点的公交车预计到达时间区间，将最接近乘客偏好时间窗的结果，作为最终的分配结果。若所有的乘客出行需求点的乘客偏好时间窗都被满足，则形成需求响应型接驳公交时刻表。

综上，我们已经完成了复杂问题的分解求解和三阶段启发式算法中的蚁群算法、动态规划以及多项式算法的求解，进一步通过迭代获得系统近似最优解。该算法的求解效率和求解质量将以下案例测试中验证。

5. 实验验证

在本次实际案例中，以大连市春柳站为公交网络中的换乘枢纽站点，设置14个需求点，共计47名乘客，设置25个候选公交车站和3个公交总站。各需求点的乘客出行点及乘客出行时间窗偏好信息如表1所示。

Table 1. Passenger travel demand information table

表1. 乘客出行需求信息表

本案例中各需求点位置、公交站点位置如图4所示。图中，绿色点表示大连市春柳站；红色点表示一定范围内的候选公交车站；紫色点表示线路中的公交总站；蓝色点表示在此范围内的需求点。设置需求点随机分配于各个公交站附近，各随机分配的需求点与候选公交站点之间的距离可以通过设定比例尺求得。

Figure 4. Schematic diagram of bus stops and demand points

图4. 公交站与需求点示意图

根据乘客出行基本信息及站点位置信息，利用所提出的需求响应公交系统设计模型，获得各线路需求响应公交路径及时刻表信息，如表2乘客需求分配结果所示。

Table 2. Passenger demand distribution results

表2. 乘客需求分配结果

结果表明，需三条需求响应公交线路服务所有乘客需求，各线路行驶路径及时刻表信息如表3所示。

Table 3. Demand response bus route and timetable information

表3. 需求响应公交路径与时刻表信息

结果表明，本研究中所提出的方法能够有效地设计公交线路，能够满足各需求在预计登车时间窗范围内接受服务且在换乘枢纽站点换乘等待时间均在可接受范围内；同时，能够实现高效求解，满足城市公交线路的调度要求。其中，需求点D9和D12的服务时间窗与预定义时间窗之间的存在6分钟左右的时间差，为本案例中产生的最大时差，表示了该需求点的乘客最大的等车时间为6分钟，误差较大，但仍属于可接受的范围。因此，该模型与算法能够有效完成考虑乘客时间窗偏好的需求响应公交系统设计。

6. 结论

本文旨在设计一种考虑乘客时间窗偏好的需求响应公交系统设计方法，面向大规模城市路网和离散乘客出行需求，解决乘客出行的“最后一公里”问题，提供从乘客出行点到换乘枢纽站点的高效可靠的公交运输服务。本研究中所提供的个性化三阶段混合启发式算法高效解决了NP-hard问题，在满足乘客时间窗约束的条件下，通过最小化乘客步行接驳距离和系统总出行时间，设计调度需求响应接驳公交线路与发车时刻并实现与干线公交线路相协调，增加对公交站点的选择过程来反映实际需求响应接驳公交运营状态，以基于蚁群算法框架的三阶段启发式算法嵌入动态规划与多项式算法，求解近似最优解，最终实现现实中各种需求响应接驳公交的复杂调度场景，完成需求响应接驳公交系统的实时调度。

通过设计基于实际道路环境的案例，本研究中构建的混合整数规划模型可满足该范围内乘客的乘车需求，并在可接受时间范围内完成需求响应公交路径与时刻表设计。

参考文献

NOTES

^*通讯作者。