面向长途客运公交化服务的高速公路网路径选择优化模型

吕明， 丁文龙， 李赤谋， 陈丰， 张宁

(1.中交文山高速公路建设发展有限公司， 文山 663099； 2.同济大学道路与交通工程教育部重点实验室， 上海 201804; 3.加州大学洛杉矶分校土木与环境工程学院， 洛杉矶 90095)

随着中国城市化及城镇化进程的不断发展，城际之间以及市郊的出行需求持续增加，而传统的出行方式已经不能满足乘客日益增长的出行需求。在这种背景之下，长途客运公交受到越来越多出行者的青睐。长途客车公交是依托于城市道路网及高速公路网，为来往于城际之间的乘客提供便捷、迅速、高效服务的可在高速服务区上下客的公交系统[1]。长途客运公交不但方便了乘客的出行，而且和传统公交相比，长途客运公交在中远途旅客运输中则更加安全。

长途客运公交隶属于公共交通的范畴。目前很多学者都从不同角度对这一领域展开了多方面的研究。程立勤[2]根据城乡客流需求特征和城乡发展实际，提出了公交主干线、公交次干线和公交支线分层的城乡公交网络结构优化方法，使城乡公交线网优化更符合城乡一体化的发展实际；并进一步提出了利用公交走廊进行“先主后次，先粗后细，分层调整，逐层优化”的城乡公交线网优化方法。陆化普等[3]、徐行方等[4]对环渤海京津唐、长江三角洲和珠江三角洲三大经济区域城际铁路线网规划进行研究，对其客运量做了初步预测，而后对城际客流基本特征、客运需求、出行规律等因素进行分析，得出要加大城际列车的开行密度即实现城际列车公交化的结论。邓天民等[5]结合旅客自身特征、旅客的出行特征以及运输方式特征等角度，通过构建非集计的多元Logistic模型，来对中长途客运旅客的出行选择行为进行了研究。

很多学者还对客运公交运营管理问题进行了研究。Nesheli等[6]以乘客总出行及换乘时间最短为目标函数，采用建模和仿真的方法对客运公交运营管理问题进行研究。 Fonseca等[7]构建了一个基于时间成本和调度成本为目标的双目标优化模型，以此来对公共交通调度优化中的成本问题进行研究。Wu等[8]构建了一个双层规划模型对客运公交选线问题进行了研究。Dakic等[9]以乘客出行时间最小为目标函数，构建了客运公交运行管理优化模型。Gardner等[10]对公共交通运营管理中从起点到终点的旅行时间分布问题进行了研究，并运用马尔可夫链进行优化建模。

部分学者还对公共卫生事件影响下的公交出行及公交调度问题进行了研究。周继彪等[11]针对新冠肺炎疫情影响下宁波市城市交通系统中存在的问题，制定了基于问题驱动的公共交通防疫策略。李健等[12]提出了一种公共卫生事件影响下的公共交通运行管理系统框架，在此基础上设计了不同的模型和算法。茹小磊等[13]对公共卫生事件影响下的城市公交管控策略进行了研究。Chen等[14]以乘客出行期间接触次数最少为目标函数，构建了新冠肺炎疫情影响下的定制公车运行管理优化模型。

除此之外，很多学者还对乘坐公交出行的旅客的选择行为进行了研究。冯焕焕等[15]通过前景理论和乘客最优理论构建了居民乘坐公共交通的出行选择行为模型，并通过实地调研数据对模型的有效性进行了验证。杨艳妮等[16]通过多层多项Logit模型对公共交通票价对乘客的出行选择行为进行了研究，通过研究得出了不同出行群体的时间价值(volue of time, VOT),在此基础上对不同变量的敏感性进行了分析。王子甲等[17]在基于多元数据融合的基础上通过多项Logit选择模型对轨道、公交复合网络中乘客的选择行为进行了研究，研究结果表明乘客在出行选择方面更加倾向于选择出行总时间最短的路径。钟异莹等[18]在计划行为理论的基础上，构建了公共交通出行选择行为模型，并通过重庆市居民的出行数据对模型的结果进行了分析。

通过对文献进行梳理，发现绝大多数文献侧重于公交线网规划、公交运营管理、公共卫生事件下的公交出行管理以及公共交通乘客选择行为方面的研究，但是针对长途客运展开的研究相对而言还很不充分。因此现对长途客运公交化服务中的高速公路网络路径选择问题进行研究。研究过程中，采用单源-单汇的路径选择方法，在给定服务需求下限和时间上限的条件下，使用Dijkstra算法找到不同需求状态下的最优路径，在保证需求服务的前提下，进一步找出服务效率最高的路径。研究成果可以为长途客运公交的发展提供一定的理论支撑。

1 问题描述及模型假设

1.1 问题描述

随着交通运输体系和城镇化的不断发展，市郊和城际客运交通需求也不断增加。高速公路作为全国公路网的核心组成部分，在长途客运中起着举足轻重的作用。在此条件下，通过发挥具有运量大、速度快、安全性高的长途客运公交的优势来提升高速公路在客流运输中所起的作用，对方便居民日常出行具有重大意义。

由此定位，对基于长客公交化需求的最优路径问题进行研究。可以描述为：已知服务起点和终点，按照长途客运服务需求，长途客车从起点出发，以服务效率最大化为优化目标，在有服务需求的高速公路路网中搜索有效的行车路线，最终顺利到达终点，完成运输任务。

1.2 模型假设

因高速路网形式复杂，一路段可与其他两、三条路段相交或相连，且一般为双向连通。为简化高速网络拓扑结构，明确每个节点和路段的计算方式，现对长客公交化服务需求可靠性研究做以下假设。

(1)路网采取有向赋权图来表示，对应的网络为有向赋权网络。

(2)高速网络中的互通交叉口、高速出口及具有一定规模或有规划发展成一定规模的服务站均可作为节点。

(3)本文中各个区域均使用就近的交通节点代替。

(4)根据节点对周边各节点的出行需求来计算每个节点对实现长客公交化服务需求的权重值，并分配到连接两节点间的路段上。

(5)每条路段之间是相互独立的，任意一条边的需求状态不会引起其他路段状态的改变。

(6)无向边路段两个方向的状态相同。

2 模型构建

2.1 最优路径模型构建

为保证长途客运实现公交化后能最大可能地满足各个区域对其服务的需求，需要路网中找到一条能够满足各点服务需求的最有效路径，通常也称为最优路径。对于高速路网，若确定了服务的起点和服务目的地，最优路径就是在指定网络中两结点间找一条整体服务需求最大的路径，属于“单源-单汇”类型，也称为最“短”路问题。

研究最“短”路径问题通常将其抽象为图论概念下的网络问题，问题的核心就成为求网络图中的最优路径问题。最短路径不单指“纯距离”意义上的最短路径，而是综合了服务需求和时间意义上的最优路径问题。

对于有向图G={V,E,W}，其中，V={v1,v2,…,vn}为图G的节点集；E为图G的弧集，表示为eij=(vi,vj)，图G中每一条弧eij上的权值为w(eij)=wij,且wij≥0。wij表达式为

(1)

假定路径的起点为vs，终点为vt，P为从vs到vt的一条路，vs到vt的距离w(P)满足关系

w(P)=min{w(P)|P为vi到vj的路}

(2)

2.2 基于长客公交化需求的最优路径模型构建

交通运输网由点和连接点之间的路径构成[19],因此可以用图与网络理论来对高速路网进行建模[20]。假定某高速路网结构为G={V,E,W},w(eij)=wij表示该路段e的需求权数。对于实现长途客运公交化的高速路网，其长客通行与以往的交通通行状态有一定的区别，在建立路径优化模型前，首先对长途客运车辆的出行做以下假设。

(1)假设各条高速公路均由双向车道构成，行驶过程通畅，无交通管制。

(2)假定长途车辆在某一路段上的行驶速度恒定。

(3)整体路网均可使用，无通行限制。

基于此，以通过路径所需的服务效率为优化目标，建立服务需求路径选择问题的数学模型为

(3)

(4)

(5)

xij=0,1;i=1,2,…,n;j=1,2,…,n

(6)

(7)

Tr,s≤Tmax，r,s∈V

(8)

式中：Tr,s表示车辆在路段(r,s)上行驶的时间；rij表示路段(i,j)上的服务需求值。

模型中，式(3)为目标函数，表示选择的路网中路径服务效率最大化；约束式(4)表示xij的取值构成从源节点到目的节点的一条可行需求路径，保证了从指定的出发点能够连续不间断地找到指定的终点；约束式(5)表示服务路径中不含回路；约束式(6)表示决策变量取值约束，xij=0或1；约束式(7)表示长途客运车辆通行的路段xij在路段服务需求值rij不小于指定阈值Rmin的范围；约束公式(8)表示车辆在路段(r, s)上的行程时间不大于服务时间阈值Tmax。

实现长客公交化后，各个路段会有不同程度的需求，因此，长途客运通行时，需判断路段的需求值，路段预测服务需求值与交通通行关系如表1所示。当rij在服务需求等级Ⅴ级范围内，路段需求较高，对长途客运经过该路段通行的要求高；当rij在需求等级Ⅲ～Ⅳ范围内时，需求值降低，对长途车辆经过该段通行的要求仅满足一般水平；当rij在需求等级Ⅰ～Ⅱ级范围内，基本对长途客运经过该段通行的需求不大，车辆实际运行时可不经过该路段。

表1 路段预测服务需求值与交通通行关系Table 1 The relationship between the predicted service demand value of the road section and the traffic flow

2.3 效率函数的使用

(9)

3 求解算法

Dijkstra算法求解最短路径问题，通常使用基于网络结构的相关矩阵，即对于含有n个节点的网络，运算时需要定义n×n阶矩阵，并根据节点之间的连接情况赋予特定的权值[21]。针对指定两点间的最优路径搜索，Dijkstra是目前公认最好的算法，该算法完全基于路网图，主观因素少，是目前解决最优路径问题采用的理论基础。

设有向赋权图G={V,E,W}，根据邻接矩阵规则，假设u、v为两个顶点，当uv∉E时，规定W(uv)=+∞。

针对本文需求模型，改进Dijkstra算法步骤如下。

(1)令l(u0)=0,u∈V-{u0},l(v)=+∞,

S0={u0},i=0。

(3)判断R(uiv)是否满足要求，如果满足要求，则进行步骤(4)，否则转入步骤(2)。

(4)若l(v)取到l(ui)+d(uiv)，则在v旁边记下(ui)；计算min{l(v)}，并将达到最小值的该顶点记为ui+1；令Si+1=Si∪{ui+1}。

(5)若i=p(G)-1，则停止。否则i=i+1，并转入步骤(2)。

算法结束时，从u0到v的距离由最终标记l(v)展示给出，并可依次根据各个顶点旁边的(ui)追回到从顶点v到u0的最终最短路。

根据上述算法，则求解长客公交化服务需求最优路径算法的实现步骤如下。

(1)输入道路网络图，设定服务的起讫点为O、D。

(2)确定服务邻接矩阵R和行程时间邻接矩阵C，设定路段服务阈值Rmin和路径救援行程时间阈值Tmax。

(3)建立长途客运公交化服务模型，更新路网，得到更新后的邻接矩阵。

(4)采用Dijkstra 算法搜索出最优路径PO,D。

(5)按照设定的路径救援行程时间阈值，判断满足要求的最优路径PO,D(s)。

具体流程如图1所示。

图1 长途客运公交化服务需求最优路径算法总流程图Fig.1 Flow chart of the optimal path algorithm for long-distance passenger transit service demand

4 算例

以中国某高速公路网局部网络为研究对象，路网结构如2所示。

图2 某高速公路网局部网络图Fig.2 The partial network diagram of a freeway network

假设服务起点为1，终点为6，路网基础数据见表2，现按照交通需求等级不同分别搜索1～6之间的最优路径。其中，最优路到径应满足两个条件：①达到高速公路对长途客运实现公交化的需求值下限；②满足总行程时间最短。路网当中路段的长度，车辆运行的速度，服务需求值以及车辆在路段中的行驶时间如表2所示。

表2 局部路网信息统计Table 2 The information statistics of local road network

采用Dijkstra算法搜索出1～6之间在不同的需求状态下的最优路径。

(1)忽略对高速公路在长途客运公交化上的服务需求，计算结果如表3所示。车辆的最优路径如图3所示。

表3 需求值下限为0时的可生成路径及行驶时间Table 3 The route and travel time of the lower limit of the demand value is 0

图3 需求值下限为0时的最优路径示意图Fig.3 The optimal path of the lower limit of the demand value is 0

(2)参照表1中的信息，当交通运行状态为在时间条件允许情况下，可考虑通过时。即区域对高速公路在长途客运公交化上的服务需求具有一般水平，此种情况下的计算结果如表4所示。

表4 需求值下限为0.7时的可生成路径及行驶时间Table 4 The route and travel time of the lower limit of the demand value is 0.7

在需求值下限为0.7情况下车辆最短行驶时间为10.744 min，最优路径如图4所示。

图4 需求值下限为0.7时的最优路径示意图Fig.4 The optimal path of the lower limit of the demand value is 0.7

(3)参照表1信息，当仅考虑高服务需求水平，即区域对高速公路在长途客运公交化上的服务需求具有较高水平，尽量保证每条路段均有通过时的计算结果如表5所示。

表5 需求值下限为0.8时的可生成路径及行驶时间Table 5 The route and travel time of the lower limit of the demand value is 0.8

在需求值下限为0.8的情况下，通过计算一共得到两条路径。而编号为1的路径行驶时间为11.079 min，小于路径编号为2的行驶时间。相比较，路径1要更优。最优路径如图5所示。

图5 需求值下限为0.8时的最优路径示意图Fig.5 The optimal path of the lower limit of the demand value is 0.8

通过具体算例对不同需求状况下的车辆路径最优问题进行了分析，对本文所构建模型和设计算法的有效性进行了验证。分别计算得到了需求值下限为0、0.7和0.8时满足需求的路径和最优路径，并计算得到了不同路径的行程时间以及最优路径情况下车辆的行驶时间。

5 结论

对面向长途客运公交化服务中的路径优化问题进行了研究，建立了考虑服务需求的数学模型，通过对模型求解，得出如下结论。

(1)对基于长途客运公交化服务的高速公路网络路径选择问题进行优化模型，设计了Dijkstra算法对模型进行求解，并通过具体算例验证了模型和算法的有效性。

(2)以时间效率作为目标优化函数，通过设定不同的需求值下限的值，来对模型进行求解，通过对模型求解可以得到不同服务需求情况下的最优路径，在保证需求服务的前提下，可以得到出行时间最短的路径。

(3)实际当中可以将高速公路网中各个服务区所在地的起终点作为本文所建模型的起终点，将有长客客运出行和有服务需求的各服务区作为模型中的节点，在兼顾时间效益、经济效益的前提下选择服务水平最佳的路径出行，以此来提升道路的服务水平。

本文对高速公路长途客运公交化的理论及建模问题进行了研究，研究中并未对高速公路沿线布设公交站问题进行研究。在高速公路沿线布设公交站的理论与方法将是未来研究的重点内容。