基于时间扩展图的旅客联程运输路径规划算法研究

Route Planning Algorithm for Passenger Intermodal Transport Based on Time-expanded Graph

摘要

为发挥旅客联程运输优势，为旅客提供符合旅客出行偏好的方案检索需求，提出基于时间扩展图模式的差异化旅客联程运输网络构建方法以及分层规划策略结合的路径规划算法。首先根据各交通工具运行计划数据以时间扩展图的模式构建原始运输网络，根据站点相对位置、接驳换乘条件、衔接交通工具类型建立差异化的换乘路径，最终形成联程运输网络。其次设计分层路径规划策略，将网络划分为跨城网络与本地网络2层，提出“预处理、路径规划、后处理”3步路径规划算法，满足用户不同的检索需求。通过提取2023年5月5日全国铁路列车、飞机及部分城市地铁数据进行算例分析，研究所提方法具有支持模糊搜索、支持站间换乘、充分考虑时刻表衔接约束的优点，有较高的运算效率，生成的路径合理且可以满足个性化出行规划需求。

Abstract

To provide passengers with solutions leveraging the advantages of passenger intermodal transport so that their travel preferences can be satisfied, a construction method of differentiated passenger intermodal transport network based on a time-expanded graph and a route planning algorithm combining hierarchical planning strategy was proposed. Firstly, the original transport network was constructed in the form of a time-expanded graph based on the operation plan data of various vehicles. Differentiated transfer paths were established based on the relative location of stations, transfer conditions, and types of vehicles for transferring, ultimately forming an intermodal transport network. Secondly, a hierarchical route planning strategy was designed, dividing the network into the intercity network and the local network. A three-step route planning algorithm of "preprocessing, route planning, and post-processing" was proposed to meet the different retrieval needs of users. By extracting data from national trains, airplanes, and some urban subways on May 5, 2023 for example analysis, this study finds that the method has high computational efficiency and reasonable generated paths, and can meet personalized travel planning needs with the advantages of taking fuzzy search, interstation transfer and time connections into consideration.

Graphical abstract

关键词

联程运输 / 路径规划 / 时间扩展图 / 运输网络 / 分层规划算法

Key words

Intermodal Transport / Route Planning / Time-expanded Graph / Transport Network / Hierarchical Planning Algorithm

0　引言

近年来，随着城市化进程的加速和人民生活水平的提高，旅客出行方式越来越多样化，人们对出行的需求也越来越高。在这种背景下，“出行即服务(Mobility as a Service，MaaS)”的概念^[1]应运而生，旨在为旅客提供一种一站式的出行服务方式，综合考虑旅客的时间成本、财务成本和环境影响，提供最优的跨交通方式出行方案。旅客联程运输是MaaS中的一个重要组成部分，为了更好地满足人民群众对美好生活的需要，相关部委的多个重要文件强化了旅客联程运输的地位和作用，明确了发展旅客联程运输的目标和要求。《交通强国建设纲要》明确了“旅客联程运输便捷顺畅”的发展目标，《“十四五”现代综合交通运输体系发展规划》指出旅客联程运输总体处于起步阶段，需做好运力协同、创新一体化联运产品，丰富综合交通运输信息服务产品等要求。随着我国综合立体交通网络的建立以及联程运输服务的不断完善，旅客联程运输将会越来越受到人们的重视和青睐，为旅客提供更合理、更经济、更便捷的跨交通方式出行方案更具有实用意义。

国内外学者围绕联程运输路径规划问题开展了大量研究，主要思路一般为构建网络，搜索最短路径。其中最短路搜索算法研究作为核心问题已经相对较为成熟，如Dijkstra算法^[2]、广度优先(Breadth First Search，BFS)算法^[3]、深度优先(Depth First Search，DFS)算法^[4]、A*算法^[5]等，以及各类启发式算法如蚁群算法^[6]、遗传算法^[7]，还有分层搜索算法HHS算法^[8]等。在此基础上，针对联程运输路径规划问题，出现了基于复杂网络理论^[9]、启发式算法^[10]为主的研究方向。例如，一些研究以站点为节点、车次作为边，通过构建联程运输网络进行路径规划^[11]。传统的路径规划算法大多聚焦于静态网络的快速获得最优路径，但是对于跨交通方式换乘方案规划场景，时刻衔接约束等因素的影响，未得到充分考虑，不能满足实际出行规划需求^[12]，因此一些学者提出了使用时间扩展图(Time-expanded Graph，TEG)来表示换乘联程运输路径规划问题^[13]，被广泛应用于公交线路优化^[14]、换乘策略优化^[15]等方面，取得了较好的效果。

现有的研究主要关注于在给定的换乘网络基础上高效地寻找符合目标函数最优的方案。然而以上成果在实际运用过程中不能很好满足如下需求。

（1）模糊检索需求。例如旅客查询城市间的出行路径规划、出发或目的地非换乘网络中的某一站点的路径规划需求，无法直接通过指定发/到站点获得路径规划结果。

（2）通过时间、票价等广义成本求解最优方案可能不符合旅客出行习惯。一是便利性方面，旅客通常倾向于换乘次数较少的方案；二是换乘场景方面，不同交通工具间换乘倾向不同，如地铁与铁路列车、飞机间的换乘倾向短距离换乘，铁路列车与飞机间换乘可以接受更长的换乘距离等。

为了解决以上问题，提出了一种差异化网络构建与分层规划结合的算法。在网络构建方面基于时间扩展图根据不同的交通方式和换乘场景采用差异化生成方法；在路径规划方面采用分层搜索策略，在精确或模糊检索的条件下，均能生成符合旅客出行习惯的整体较优路径规划结果。

1　建模方法

1.1　问题描述

旅客联程运输路径规划是指为旅客提供从起点到终点的多模式交通方案，包括了多种交通工具的组合，例如铁路列车、飞机、地铁、驾车等。这种路径规划需要考虑多种交通工具之间的衔接、时间限制等多个因素，以提供最佳的出行方案。研究旨在考虑交通工具差异性和出行偏好的基础上，结合旅客实际检索需求(精确搜索、模糊搜索)得到较优且合理的出行方案。

1.2　基于时间扩展图的旅客联程运输网络

1.2.1　符号说明

为增强模型可读性，对模型主要符号进行说明，主要符号说明如表1所示。

1.2.2　旅客联程运输网络设计

传统交通换乘网络使用带权有向图表示，其中站点作为节点，将站间线路作为边，节点间的旅行时间、费用等因素作为边的权重用于参与两点间的最优路径搜索。此方法无法直接表达交通工具的运行时刻衔接信息以及旅客站内换乘行为，因此需要根据节点两端交通工具的运行时刻衔接状态动态调整边的权重，存在计算方法复杂的问题。

研究将基于时间扩展图对旅客联程运输网络进行建模并形成有向图网络N=(V,W)，其中V为节点集合，用于表示旅客联程运输过程中发生的各类事件；W为边集合，用于表示旅客在事件间的转换过程。S为站点集合，U为交通工具集合。

由4类节点集合组成节点集合V=E\bigcup L\bigcup A\bigcup D，具体说明如下。

（1）旅客进站事件节点集合E=(e_{\mathrm{1}},e_{\mathrm{2}},e_{\mathrm{3}},\dots ,e_s)，其中s\in S，e_s代表旅客进入站点s。

（2）旅客出站事件节点集合L=(l_{\mathrm{1}},l_{\mathrm{2}},l_{\mathrm{3}},\dots ,l_s)，其中s\in S，l_s代表旅客离开站点s。

（3）交通工具到达事件节点集合A=(a_{\mathrm{1}}^{\mathrm{1}},a_{\mathrm{2}}^{\mathrm{1}},a_{\mathrm{1}}^{\mathrm{2}},\dots ,a_s^u)，其中s\in S，u\in U，a_s^u代表交通工具u到达站点s。

（4）交通工具出发事件节点集合D=(d_{\mathrm{1}}^{\mathrm{1}},d_{\mathrm{2}}^{\mathrm{1}},d_{\mathrm{1}}^{\mathrm{2}},\dots ,d_s^u)，其中s\in S，u\in U，d_s^u代表交通工具u从站点s出发。

记事件发生的时刻为t(v)。

事件的转换过程(即边)w可以用(v_i,v_j)表示，并根据首尾节点类型的不同分为以下6类。

（1）进站过程(e_s,a_s^u)，代表旅客从进站并等待交通工具到达的过程。

（2）出站过程(a_s^u,l_s)，代表旅客离开交通工具并最终离开站点的过程。

（3）站内等候过程(a_s^u,d_s^u)，代表交通工具到达停靠站点并离开的过程，此时旅客处于交通工具内并未离开。

（4）交通工具在途(d_s^u,a_s^u)，代表交通工具沿线路从上一站离开并到达下一站的过程。

（5）站内换乘(a_s^u,d_s^u{)}_t，代表旅客乘坐前一交通工具到达后经过站内换乘的方式乘坐下一交通工具离开的过程。

（6）站间换乘(l_s,e_s)，代表旅客离开上一站点，经过换乘过程进入下一站点的过程。站间换乘用于表示在换乘过程中必须重新经过进站(安检)流程的换乘过程，前后站点可以是不同站点，也可以是相同站点。

记事件转换过程(即边)的耗时为f(w)。

对于铁路列车、飞机等具有明确时刻表的交通工具，可以基于时刻表设计完整的时间扩展图，基于时刻表的旅客运输网络图如图1所示。

其中a_s^u和d_s^u的事件发生时刻由时刻表确定，根据站点的实际情况设置旅客到达站点e的最晚时刻以及旅客离开站点l_s的最早时刻。

对于没有明确运行时刻表的交通工具(如地铁)，采用结合首、末班发车时间和发车间隔参数生成虚拟班次的方式生成时刻表数据，按照同样方式构建时间扩展图。

1.2.3　建立换乘路径

通过在基于时刻表等基础数据生成的运行网络上设置换乘路径，在不同交通工具的运输网络间建立连接通道以支撑跨交通方式出行方案的生成，其次在同一交通工具的不同站点间建立潜在快速换乘通道，突破同站换乘约束，以支撑更优的出行方案生成。站内换乘与站间换乘的适用条件不同，换乘路径建立策略以及生成的网络结构也不同，需要根据实际情况选择不同策略。

站内换乘策略适用于旅客在同一枢纽内经过快速换乘通道实现的换乘，在运输网络中通过边(a_s^u,d_s^u{)}_t表示，站内换乘模式示意图如图2所示。

站间换乘适用于旅客在不同枢纽间换乘，或在同一枢纽不同交通方式间需要经过安检等步骤的换乘场景，在运输网络中通过边(l_s,e_s)表示，站间换乘模式示意图如图3所示。

1.2.4　差异化换乘路径生成策略

通过建立换乘路径增加了更多可选出行方案，同时也显著增加了既有运输网络的节点和边的数量，使路径规划计算耗时更长。因此合理建立换乘路径对于确保路径规划结果质量和速度十分重要。根据前后衔接交通工具的类型设置差异化路径生成策略。

（1）地铁与地铁间仅适用站内换乘策略，建立换乘路径需符合以下约束。

\begin{array}{c}t\left(d_s^{u_{\mathrm{2}}}\right)-t\left(a_s^{u_{\mathrm{1}}}\right)\ge T\end{array}⑴

式中：T为站内不同交通工具间最小可换乘时间间隔，min；t(d_s^{u_{\mathrm{2}}})表示地铁u_{\mathrm{2}}到达s站的时刻；t(a_s^{u_{\mathrm{1}}})表示地铁u_{\mathrm{1}}到达s站的时刻。

为满足以上条件的节点间建立站内换乘边(a_s^{u_{\mathrm{1}}},d_s^{u_{\mathrm{2}}}{)}_t。

（2）铁路列车、飞机之间的换乘支持站内与站间换乘模式，为保持联程运输网络规模在合理范围内，通过设置铁路车站、机场间可建立换乘路径的合理距离范围来限制建立换乘路径的数量。建立换乘路径需符合以下约束。

\begin{array}{c}\left\{\begin{array}{c}d(s_i,s_j)\le D\\ t(d_{s_j}^{u_{\mathrm{2}}})-t(a_{s_i}^{u_{\mathrm{1}}})\ge T{s}_i=s_j,u_{\mathrm{1}}\ne u_{\mathrm{2}}\\ t\left(d_{s_j}^{u_{\mathrm{2}}}\right)-t\left(a_{s_i}^{u_{\mathrm{1}}}\right)\ge g{\left(s_i,s_j\right)}^{*}+f\left(a_{s_i}^{u_{\mathrm{1}}},l_{s_i}\right)+f\left(e_{s_j},d_{s_j}^{u_{\mathrm{2}}}\right)s_i\ne s_j,u_{\mathrm{1}}\ne u_{\mathrm{2}}\end{array}\right.\end{array}⑵

式中：d(s_i,s_j)为站点s_i与站点s_j间的直线距离，km；D为根据前后站点类型设置的最大可建立换乘路径距离，km；g{\left(s_i,s_j\right)}^{*}为从站点s_i到站点s_j的预估最短导航时间，min；f(a_{s_i}^{u_{\mathrm{1}}},l_{s_i})为旅客从乘坐交通工具u_{\mathrm{1}}到达站点s_i直到离开该站点的耗时，min；f(e_{s_j},d_{s_j}^{u_{\mathrm{2}}})为旅客从进入站点s_j直到乘坐交通工具u_{\mathrm{2}}离开该站点的耗时，min。

为满足以上条件的节点间建立站间换乘边(l_{s_i},e_{s_j})。

1.3　数学模型

在时间扩展图中，旅客的出行方案必须开始于进站节点e_s，结束于出站节点l_s，节点间所经过的路径体现为旅客出行方案，记路径规划方案表示如下。

P=\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)+\left(v_{\mathrm{3}},v_{\mathrm{4}}\right)+\dots +\left(v_{m-\mathrm{1}},v_m\right)⑶

其中“+”表示各段事件间转换过程的衔接。

设计边的广义成本函数C\left(w\right)，w=\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)时的广义成本函数如下所示。

C\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)=\left[\mathrm{1}+{\alpha }_{\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)}+{\beta }_u^{\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)}\right]\times f\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)⑷

{\alpha }_{\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)}表示换乘成本系数，若(v_{\mathrm{1}},v_{\mathrm{2}})不为换乘边，则{\alpha }_{\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)}=\mathrm{0}，若(v_{\mathrm{1}},v_{\mathrm{2}})属于换乘边且旅客出行偏向于换乘次数尽量少，则取{\alpha }_{\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)}>\mathrm{1}。{\beta }_u^{\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)}表示交通工具u在\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)的成本系数，若\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)对应的交通工具类型符合旅客选择偏好，则令，反之则令{\beta }_u^{\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)}>\mathrm{1}。总之，除了基本出行时间成本外，在符合旅客出行偏好的路径上将有更低的附加成本。

求进站节点e_s和出站节点l_s间的成本最低路径，即将路径规划方案P中的各段边的广义成本求和表示换乘方案总成本，记为\left|P\right|。

\left|P\right|=C\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)+C\left(v_{\mathrm{3}},v_{\mathrm{4}}\right)+\dots +C\left(v_{m-\mathrm{1}},v_m\right)⑸

综上所述，旅客联程运输路径规划问题一般叙述如下：基于给定交通工具运行时刻数据，构建基于时间扩展图的旅客联程运输网络G，设置广义成本函数C，从用户检索需求中匹配进站事件节点e_s以及出站事件节点l_s，求解联程运输出行方案P，使旅客换乘方案的费用\left|P\right|最小化。

2　算法设计

2.1　路径规划

由于建立全国范围内的铁路列车、飞机、地铁的交通换乘网络规模较大，直接开展路径规划效率不高。为获得更高检索效率以及满足模糊搜索需求，设计分层路径规划算法，具体说明如下。

2.1.1　网络分层

将换乘网络从逻辑上分为跨城网络与本地网络2层，其中跨城网络包含铁路列车、飞机，本地网络包含铁路列车、地铁。当进行同城路径规划时仅在本地网络进行；当进行跨城路径规划时，先在跨城网络搜索主路径，并于主路径的发到两端根据实际情况在本地网络搜索衔接路径，最终形成完整路径，换乘网络分层示意图如图4所示。

2.1.2　流程设计

整体算法框架分为预处理、路径规划、后处理3大阶段。

预处理阶段：用于解决模糊搜索问题，将模糊搜索需求处理为精确搜索集合。在实际应用场景下，旅客输入的出发与目的地参数类型可以分为区域(如城市)和经纬度(如车站、机场、旅客定位)2类。针对旅客所输入的出发与目的地类型进行综合处理，最终形成一系列运输网上的路径规划需求。

路径规划阶段：既有研究对于在给定有向图中搜索最短路的算法已十分成熟，研究使用改进的Dijkstra算法作为最短路搜索核心算法获取给定2点的前K最短路径。

后处理阶段：将最终路径规划生成的所有结果进行汇总，根据旅客实际查询需求，针对换乘次数、行程时间等因素进行排序，形成最终的方案列表。路径规划计算流程设计如图5所示，以下进行详细说明。

步骤1：获取出发地、目的地在运输网络上的备选站点集合。对于同城路径规划场景，旅客输入的出发地与目的地均非区域类型，搜索距离出发地(或目的地) 2 km内的地铁站、30 km内的铁路车站或机场；对于跨城路径规划场景，若出发地(或目的地)为区域类型，则搜索该区域内的所有铁路车站与机场。出发地备选站点集合表示为A=\{a_{\mathrm{1}},a_{\mathrm{2}},a_{\mathrm{3}},\dots \}；目的地备选站点集合表示为B=\{b_{\mathrm{1}},b_{\mathrm{2}},b_{\mathrm{3}},\dots \}。

步骤2：生成路径规划需求。将步骤1中的A与B中的站点对应的路径规划节点两两组合可以得到初步路径规划需求列表，用R=\{r_{\mathrm{1}},r_{\mathrm{2}},r_{\mathrm{3}},\dots \}表示，其中r_x=r(e_{a_n},l_{b_m})，a_n\in A，b_m\in B。

步骤3：精简搜索需求。在A与B中的站点数量较多的情况下，步骤2生成的需求组合太多，逐一处理耗时太长，因此需要对规划需求进行精简。通过设计需求权重指标，按权重排序并截取部分需求使路径规划耗时总体可控。权重计算函数如下所示。

W\left(r_x\right)=\alpha \times O_{a_n}^u+\beta \times \frac{\mathrm{1}}{{\delta }_{a_n}}+\alpha \times O_{b_m}^u+\beta \times \frac{\mathrm{1}}{{\delta }_{b_m}}⑹

式中：O_{a_n}^u为当日从站点a_n发出的交通工具u的班次数量，\mathrm{个；}{\delta }_{a_n}与{\delta }_{b_m}分别为旅客实际输入的出发地、目的地与备选站点的直线距离，km；\alpha为班次因素权重；\beta为距离因素权重。

若旅客输入的出发地(或目的地)为区域类型，则\beta =\mathrm{0}，即站点距离用户搜索地点越近权重越大，经过站点的线路越多权重越大。若用户搜索的参数类型为区域，则忽略距离因素。

步骤4：采用改进Dijkstra算法计算前K最短路径。确定旅客原始输入的出发地与路径规划需求中的出发地(或旅客原始输入的目的地与路径规划需求中的目的地)满足如下条件：二者相距30 km及以上，且前后两端在2 km范围内存在地铁站，如果是，转入步骤5。

步骤5：计算衔接路径。搜索旅客原始输入的出发地与路径规划需求中的出发地(或旅客原始输入的目的地与路径规划需求中的目的地) 2 km范围内存在的地铁站，两两组合后采用Dijkstra算法计算最短路径，并与原始路径合并。

步骤6：将步骤4、步骤5的规划结果根据总行程时间、换乘次数进行综合排序，获得路径规划推荐结果列表。

3　案例分析

3.1　基础数据及参数标定

采用2023年5月5日铁路列车时刻表、航班班次、北京及上海地铁数据作为测试数据。设置最小可换乘时间间隔T=\mathrm{30}\mathrm{m}\mathrm{i}\mathrm{n}，结合全国铁路车站平均距离以及机场平均距离，设置最大可建立换乘路径距离参数如表2所示。

通过以上数据与参数建立旅客联程运输网络，对路径规划算法有效性进行验证。

3.2　结果及分析

3.2.1　方案有效性分析

算法代码采用Java编写，运行环境是CPU Intel i7-10700 2.90 GHz，内存16 G的计算机。首先构建旅客运输网络，共加载铁路车站2 974个，机场248个，地铁站933个；加载铁路列车线路13 959条，航班线路2 776条，地铁线路(根据时刻表扩展)41 820条；生成换乘路径83 157条。由于建立换乘路径过程需要逐一计算站点间直线距离，对符合距离约束的站点预估最短导航时间，计算量较大，因此总体网络构建耗时约30 min。路径规划计算方面，跨城网络路径规划平均计算时间不超过0.5 s，考虑前后衔接的分层路径规划总体计算时间不超过1.7 s，算法具有较高的求解速度。

选取有代表性的出行OD，计算出行路径，方案有效性验证结果如表3所示。

从表3结果可以看出路径规划算法可以有效地对地点和区域2类查询条件给出路径规划结果。其中北京大兴站—福州站的OD路径规划结果为地铁+铁路列车的出行方案，说明算法通过跨城网络与本地网络分层搜索生成了有效出行方案，并且在北京南站使用了站内换乘模式衔接。鹤岗市—乌鲁木齐市的OD路径规划中，算法分别从鹤岗市和乌鲁木齐市选取了佳木斯站和乌鲁木齐地堡国际机场作为路径规划站点并实现了空铁联运方案，其中在佳木斯站实现站内换乘，在沈阳北站和桃仙国际机场实现站间换乘。

3.2.2　广义费用参数分析

通过设置不同广义成本费用参数，对比相同OD下路径规划计算结果，验证广义费用参数对路径规划的影响。

（1）维持换乘成本系数{\alpha }_t不变，改变交通工具成本系数{\beta }_u，交通工具成本系数设置方案如表4所示。

以六里桥到福州南站为例，分别使用以上参数组合得到路径规划结果，不同交通工具成本系数设置方案路径规划结果对比如表5所示。

对比参数组合1与参数组合2可以看出，在跨城网络的规划结果均为G45从北京南站到福州站，但是本地网络中参数组合1使用地铁换乘方案本地换乘耗时45 min，参数组合2中由于地铁成本系数变大导致地铁换乘方案耗时大于驾车方案，因此在参数组合2的路径规划结果中给出了驾车+铁路列车的方案。对比参数组合1和参数组合3，铁路列车的成本系数增大将增加选择铁路列车出行的广义费用，因此算法将尽量避免选择铁路列车出行，参数组合3生成的路径规划方案以飞机为主，但是由于出发地与目的地间距离机场较远，行程前后分别使用了地铁+铁路列车与驾车+铁路列车的衔接方案。

（2）维持交通工具成本系数{\beta }_u不变，改变换乘成本系数{\alpha }_t，换乘成本系数设置方案如表6所示。

以北京大兴站到福州站为例，分别使用以上参数组合得到路径规划结果，不同换乘成本系数设置方案路径规划结果对比如表7所示。

对比参数组合1与参数组合2可以看出，在相同查询条件下参数组合1的路径规划结果包含了3段行程，行程总耗时504 min，参数组合2的路径规划结果包含了2段行程，行程总耗时517 min。说明换乘成本系数增大将增加换乘过程产生的广义费用，因此算法将尽量避免换乘，更倾向于换乘次数少的方案。

综上，与既有算法相比，本研究提出的方法具有如下优势：一是考虑了预处理步骤并支持模糊搜索；二是加入了换乘路径生成策略，支持站内换乘和站间换乘方案，更贴合实际需求；三是基于时间扩展图的网络结构设计，在充分考虑时刻表衔接约束的前提下极大简化了处理逻辑；四是同时考虑换乘偏好与交通工具偏好的广义费用函数模型更能体现旅客选择倾向差异，具备支撑个性化路径规划的能力。

4　结束语

随着联程运输服务的不断完善，为满足旅客联程运输出行路径规划查询的需求，基于时间扩展图模式构建旅客联程运输网络，并提出分层搜索策略，在精确或模糊检索的条件下，均能生成符合旅客出行习惯的整体较优路径规划结果。该方法已基于全国铁路列车、飞机以及部分城市地铁数据进行实例分析，验证了算法的有效性。目前算法仅考虑了时刻表衔接约束、行程耗时、交通方式选择偏好、换乘偏好等因素，可以进一步考虑将票价因素、舒适度因素等加入模型。其次，当前建立换乘路径的参数取值单一，后续可以根据各城市当地交通以及各换乘枢纽的实际情况，对参数进行差异化设置，使路径规划结果更合理。

参考文献

[1] 李　晔，王　密，舒寒玉. 出行即服务(MaaS)系统研究综述[J]. 综合运输，2018，40(9)：56-65.

[2] LI Ye， WANG Mi， SHU Hanyu. A Study Review of Mobility as a Service (MaaS)[J]. China Transportation Review，2018，40(9)：56-65.

[3] CHEN J C.Dijkstra's Shortest Path Algorithm[J].Journal of Formalized Mathematics，2003，15(9)：237-247.

[4] GOLDFARB D， HAO J X， KAI S R. Shortest Path Algorithms Using Dynamic Breadth-First Search[J]. Networks，1991，21(1)：29-50.

[5] ARANSKI A W. Depth First Search Algorithm in Solving the Shortest Route Using the Concept of Generate and Test[J]. IJISTECH (International Journal of Information System and Technology)，2022，6(3)：353-360.

[6] WAYAHDI M R， GINTING S H N， SYAHPUTRA D. Greedy，A-Star，and Dijkstra's Algorithms in Finding Shortest Path[J]. International Journal of Advances in Data and Information Systems，2021，2(1)：45-52.

[7] 许　健，许　峰. 基于迭代局部搜索的路径规划蚁群算法[J]. 软件导刊，2018，17(8)：31-34.

[8] XU Jian， XU Feng. Path Planning Ant Colony Algorithm Based on Iterated Local Search[J]. Software Guide，2018，17(8)：31-34.

[9] 吴晓涛，孙增圻. 用遗传算法进行路径规划[J]. 清华大学学报(自然科学版)，1995，35(5)：14-19.

[10] WU Xiaotao， SUN Zengqi. Using Genetic Algorithm for Path Planning[J]. Journal of Tsinghua University (Science and Technology)，1995，35(5)：14-19.

[11] KNOPP S， SANDERS P， SCHULTES D，et al. Computing Many-to-Many Shortest Paths Using Highway Hierarchies[C]//Proceedings of the Meeting on Algorithm Engineering & Experiments. 6 January 2007，New Orleans，Louisiana. ACM，2007：36-45.

[12] 魏　航，李　军，刘凝子. 一种求解时变网络下多式联运最短路的算法[J]. 中国管理科学，2006，14(4)：56-63.

[13] WEI Hang， LI Jun， LIU Ningzi. An Algorithm for Shortest Path with Multi-Modal in Time-Varying Network[J]. Chinese Journal of Management Science，2006，14(4)：56-63.

[14] 王　琴，李引珍，李海军，等. 不确定条件下的低碳多式联运路径优化研究[J]. 铁道运输与经济，2023，45(3)：62-69，120.

[15] WANG Qin， LI Yinzhen， LI Haijun，et al. Research on Route Optimization of Low Carbon Multimodal Transport under Uncertainty Condition[J]. Railway Transport and Economy，2023，45(3)：62-69，120.

[16] 胡必松. 大规模复杂铁路网中多路径搜索技术研究[J]. 铁道运输与经济，2015，37(7)：71-77.

[17] HU Bisong. Study on Multi-Path Search Technology in Large-Scale Complex Railway Network[J]. Railway Transport and Economy，2015，37(7)：71-77.

[18] ABU-RYASH H， TAMIMI A. Comparison Studies for Different Shortest Path Algorithms[J]. International Journal of Computers and Applications，2015，14(8)：5979-5986.

[19] FISCHER F， HELMBERG C. Dynamic Graph Generation for the Shortest Path Problem in Time Expanded Networks[J]. Mathematical Programming， 2014， 143(1)： 257-297.

[20] 崔建勋，安　实，崔　娜. 基于时间扩展网络的区域疏散公交路径规划[J]. 华南理工大学学报(自然科学版)，2010，38(3)：64-69.

[21] CUI Jianxun， AN Shi， CUI Na. Route Planning of Public Transit for Regional Evacuation Based on Time-Expanded Network[J]. Journal of South China University of Technology (Natural Science Edition)，2010，38(3)：64-69.

[22] 张铱莹，彭其渊. 综合运输旅客换乘网络优化模型[J]. 西南交通大学学报，2009，44(4)：517-522.

[23] ZHANG Yiying， PENG Qiyuan. Optimization Model of Passenger Transfer Network for Integrated Transportation[J]. Journal of Southwest Jiaotong University，2009，44(4)：517-522.

基金资助

中国国家铁路集团有限公司科技研究开发计划课题(N2022S003)