时空可达性及其在交通数据分析中的一些应用研究

Space-Time Accessibility and Some Applications in Traffic Data Analysis

摘要: 在评价交通服务系统中，时空可达性是重要考虑因素，基于时空可达性的交通数据分析，能为决策者在路段建设及公共交通路线设计方面提供合理意见，有助于提高出行者到活动地点的便利程度。本文首先针对城市基础交通网络，从时空棱柱理论框架中构建时空网络，考虑个体在起点及活动地点所受的时间约束及费用约束，构建基于时空可达性交通网络模型，并将该模型进行改进，应用于城市公共交通系统中。并针对模型特点，设计深度遍历算法，得到时空网络中所有的可行路径，从中选出最优解。为更好地适应大规模路网，又设计拉格朗日松弛算法，通过其耦合约束和难约束，将原问题分解为最短路问题及背包问题，并更新拉格朗日乘子协调各子问题。最后，以实际问题为例，验证了模型和算法的合理性。研究结果表明本文提出的模型能有效解决以个体出行需求为目标的交通网络设计问题。

Abstract: In evaluating transportation system, space-time accessibility is an important factor. The transportation data analysis based on space-time accessibility can provide reasonable suggestions for policy-makers in road construction and public transportation route design, which will make it more convenient for travelers. We firstly focus on urban transportation network and build space-time network based on space-time prisms theories by considering the time constraint and cost constraint of traveler heading for destination, and finally building transportation network design models based on space-time-accessibility. Then the improved models are proposed and used to urban public transportation systems. Based on the models’ characteristics, we introduce the depth-first-search algorithm which can calculate all the possible routes in space-time networks and choose the best one from them. Largrangian relaxation algorithm is then designed to better adapt to large-scale road networks. And through the coupling constraints and hard constraints in the relaxation model, the original problem can be decomposed into the shortest-path problem and the knapsack problem, both of them can be solved by updating Largrangian multipliers. Finally, the rationality of the model and algorithm is verified by a practical example. The experimental results show that the proposed model can effectively solve the traffic network design problem aiming at individual travel demand.

1. 引言

由于“车本位”范式的发展导致私家车数目快速增长，造成机动车出行日常化、路网负荷承载量增大、拥堵问题进一步蔓延，为回应能源危机、气候变化、环境保护和历史文化保护等非交通因素的强烈要求 [1]，目前交通规划管理者向区域、城市、出行者的关联特征转变，构建可持续发展的交通网络 [2]。根据新型服务理念和交通政策的要求，城市交通运输规划管理方法应放弃“路本位”和“车本位”范式转而采用“人本位”范式。城市交通网络系统不仅应满足居民出行的基本需求，更应降低居民出行所带来的负面影响 [3]，而个体时空可达性模型以个体活动出行为单元，目标是出行者抵达目标点，度量标准是个体出行的时间及费用约束的可达性 [4]。与传统的空间可达性相比，个体时空可达性更突显时间及费用预算对个体出行的影响、个体活动是否得到满足。因此，以个体时空可达性为出发点的交通数据分析是交通规划的一种新的尝试，对城市交通网络的发展具有促进意义。

在城市交通网络规划领域中，可达性最早由Hansen提出 [5]。个体可达性度量方法最经典的是Kwan的时空法 [6]，他借助于Hägerstrand的时空地理理论框架和时空棱柱 [7]，将活动位置、时空限制及交通因素联系在一起；文献 [8] 开发了基于Logit的两阶段选择模型，该模型与无时间约束模型相比，对经验数据有更好的适应性。之后，文献 [9] 进行的仿真分析在预测精度上取得了更大的进展。目前，可达性度量方法建立的主要模型包括：距离法、累计机会法、重力模型法、平衡系数法、时空法等。

距离法 [10] 是最简单、基础的可达性度量方法。距离越短，可达性水平越高。适用于宏观的可达性评价，但由于其过于简单，尤其采用欧式距离法时忽略了道路的空间形态，所以，不适用于复杂的城市交通运输网络系统。

累计机会法 [11] 是指设定某个出行成本(即距离、时间、费用)，将从某一地点出发接近某一机会的多少作为可达性指标。机会越多，可达性水平越高。

重力模型法 [12] 是将各吸引点与距离点间的距离衰减函数与各吸引点自身的引力规模结合，构成可达性指标。吸引点与距离点间的作用力越大、距离越小，则可达性水平越高。该方法将城市交通运输系统与城市居民生活活动联系在一起，如文献 [13] 的交通规划研究，及文献 [14] 的城镇发展研究。

平衡系数法是由Wilson运用统计方法中的熵最大定律推导出的可达性度量方法 [15]。该方法考虑了实际中的竞争因素，因此，更加靠近实际生活。文献 [16] 还提出了基于个体活动的网络平衡模型。

时空法是由Hägerstrand的时空地理理论框架提供的、面向约束的可达性方法 [7]。该方法考虑在时空约束的条件下个体可达的时空区域，以此度量可达性水平，一般采用时空棱柱来计算。文献 [17] 采用引力模型和行程时间预算模型探究交通网络中的时空可达性；文献 [18] 考虑不同出行者的特定时空约束，提出了基于地铁系统的城市时空可达性模型；Harvey的超时空可达性方法，反映了城市交通网络中允许的位置、距离和速度 [19]。文献 [20] 中提出了一种行程时间不确定环境下地点时空效用可达性度量方法；Taylor基于时空可达性交通网络，评价研究交通事故在城市拥堵区域的影响 [21]。

目前有学者从个体时空可达性出发，研究基于时空可达性的交通数据研究，但大多数文献仅将可达性用于点与点的连通性，未考虑出行者的预期成本及预期时间。本文旨在提升交通系统的时空可达性，优化交通网络规划，反映交通设施配置、出行者及土地利用间的相互作用，可以为交通管理者提供更加有利的建议，提高交通运输效益，增强人民生活幸福感。

2. 基于时空可达性的交通网络模型

2.1. 模型描述

在一个有N个结点，E条有向路径的时空网络图中，定义有向图 $G\left(V,P\right)$，其中V为交通网络中所有结点的集合，P为交通网络中所有有向路径的集合。起点为o，活动地点为a，终点为d， $\left(t_o,t_d\right)$ 表示 $t_o$ 时刻从起点出发、 $t_d$ 时刻到达终点， $\left(t_o,t_a\right)$ 表示 $t_o$ 时刻从起点出发、 $t_a$ 时刻到达活动地点。符号定义见表1所示。

Table 1. Symbol definition

表1. 符号定义

2.2. 模型构建

考虑以下三种情形：

1) 当时间有限时，考虑费用最小化、可达范围最大化。

2) 当时间有限时，考虑费用最小化且在最短时间内到达目标地点。

3) 当时间有限、费用有限时，考虑可达地点的吸引率最大化。

根据以上情形，分别建立以下模型。

2.2.1. 情形一

1) 目标函数

为使费用最小化：

$\min {\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{F}_{i,j,t,s}{y}_{i,j,t,s}}\left(o,a,\tau \right)$ (1)

可达范围最大化可以转换为不可达范围最小化，对于时空网络图中，有N个结点，E条有向路径，由于在有限的时空网络中，结点数目是有限的，因此，不可达点的数目也是有限的。由于 $y_{i,j,t,s}\left(o,a,\tau \right)$ 为0-1变量，若 $y_{i,j,t,s}\left(o,a,\tau \right)=0$，表示从起点o至活动地点a的路径未经过时空旅行弧 $\left(i,j,t,s\right)$，若 $y_{i,j,t,s}\left(o,a,\tau \right)=1$，表示从起点o至活动地点a的路径经过时空旅行弧 $\left(i,j,t,s\right)$，令

${y^{\prime }}_{i,j,t,s}\left(o,a,\tau \right)=\{\begin{array}{l}\text{0,}如果y_{i,j,t,s}\left(o,a,\tau \right)=1\\ \text{1,}如果y_{i,j,t,s}\left(o,a,\tau \right)=0\end{array}$ (2)

则最小化不可达点：

$\min {\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{y^{\prime }}_{i,j,t,s}\left(o,a,\tau \right)}$ (3)

本文考虑将最小化出行者费用和最小化不可达地点合并，建立系数 ${\gamma }_1$ 、 ${\gamma }_2$，构建新的目标函数：

$\min \left({\gamma }_1{\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{y^{\prime }}_{i,j,t,s}\left(o,a,\tau \right)}+{\gamma }_2{\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{F}_{i,j,t,s}{y}_{i,j,t,s}}\left(o,a,\tau \right)\right)$ (4)

2) 网络流平衡约束

${\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{y}_{i,j,t,s}}\left(o,a,\tau \right)-{\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{y}_{j,i,s,t}}\left(o,a,\tau \right)=\{\begin{array}{l}1,i=o,t=\tau \\ -1,i=o,t=\tau +T\left(o,a\right)\\ 0,其他\end{array}$ (5)

3) 出行费用预算约束

${\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{F}_{i,j,t,s}{y}_{i,j,t,s}}\left(o,a,\tau \right)\le K$ (6)

从出行者的角度来看，出行费用的约束将限制了出行者出行选择的交通工具及旅行路程，该约束保证了出行者的出行费用不能超过K。

4) 路段建设约束

$y_{i,j,t,s}\left(o,a,\tau \right)\le z_{ij}$ (7)

路段的建设会影响出行者的路径选择。若该路段未被建设，则该路段不能被任何出行者所选择。

5) 路段建设费用

路段建设费用保证了某个区域的建设总费用不超过政府的预计估计值。

${\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{F}_{i,j,t,s}{z}_{i,j}}\le M$ (8)

6) 决策变量约束

$y_{i,j,t,s}\left(o,a,\tau \right)=\left\{0,1\right\},\forall (o,a)\in N,\tau \in T,\left(i,j,t,s\right)\in V$ (9)

$z_{ij}=\left\{0,1\right\},\forall \left(i,j\right)\in P^b$ (10)

2.2.2. 情形二

1) 目标函数

基于在该情形下，优化目标为在给定的时空约束中最小化出行者费用、最小化时间。因此,构建以下目标函数：

$\min {\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{t}_{ij}{y}_{i,j,t,s}}\left(o,a,\tau \right)$ (11)

$\min {\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{F}_{i,j,t,s}{y}_{i,j,t,s}}\left(o,a,\tau \right)$ (12)

本文考虑将最小化出行者费用和最小化时间合并，建立系数 ${\gamma }_1$ 、 ${\gamma }_2$，认为费用和时间具有同等重要性，因此，取 ${\gamma }_1=1/2$ 、 ${\gamma }_2=1/2$ ：

$\min \left({\gamma }_1{\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{t}_{ij}{y}_{i,j,t,s}}\left(o,a,\tau \right)+{\gamma }_2\min {\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{F}_{i,j,t,s}{y}_{i,j,t,s}}\left(o,a,\tau \right)\right)$ (13)

2) 行驶时间

$t_{ij}={\displaystyle \underset{a_{se}\in r_{ij}}{\sum }{\theta }_{se}}{l}_{se}{v}_{se}^{-1}$ (14)

其中 $a_{se}$ 是节点s与e间的弧， $r_{ij}$ 是位置i和j的最短路径， ${\theta }_{se}\in \left[0,1\right]$ 是弧 $a_{se}$ 的行进比例， $l_{se}$ 是弧 $a_{se}$ 的长度， $v_{se}$ 是在弧 $a_{se}$ 内的行进速度。请注意，根据我们的位置假设， ${\theta }_{se}$ 将除固定活动所在的弧线外，通常等于1。

3) 网络流平衡约束

${\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{y}_{i,j,t,s}}\left(o,a,\tau \right)-{\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{y}_{j,i,s,t}}\left(o,a,\tau \right)=\{\begin{array}{l}1,i=o,t=\tau \\ -1,i=o,t=\tau +T\left(o,a\right)\\ 0,其他\end{array}$ (15)

4) 出行费用预算约束

${\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{F}_{i,j,t,s}{y}_{i,j,t,s}}\left(o,a,\tau \right)\le K$ (16)

5) 路段建设约束

$y_{i,j,t,s}\left(o,a,\tau \right)\le z_{ij}$ (17)

6) 路段建设费用

${\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{F}_{i,j,t,s}{z}_{i,j}}\le M$ (18)

7) 决策变量约束

$y_{i,j,t,s}\left(o,a,\tau \right)=\left\{0,1\right\},\forall \left(o,a\right)\in N,\tau \in T,\left(i,j,t,s\right)\in V$ (19)

$z_{ij}=\left\{0,1\right\},\forall \left(i,j\right)\in P^b$ (20)

2.2.3. 情形三

1) 目标函数

$\max a_j{y}_{i,j,t,s}\left(o,a,\tau \right)$ (21)

2) 效用函数

假设一个人不能离开位置i上的确定活动，直到 $t_i$ 和在 $t_j$ 时必须参加位置j的活动(j和i可能是同一地方)，首先定义在位置k处参与的活动效用为

$u_{ij}\left(a_k,T_k,t_k\right)=a_k^{\alpha }{T}_k^{\beta }\exp \left(-\lambda t_k\right)$ (22)

其中

$t_k=\left(d\left(x_i,x_k\right)+d\left(x_k,x_j\right)\right)v^{-1}$ (23)

$x_i=i$ 的位置矢量。

$d\left(x_i,x_k\right)=$ 位置i到位置k的距离。

$v=$ 旅行的恒定速率

$T_k=\{\begin{array}{l}{t}_j-t_i-t_k>0\\ 0,其他\end{array}$ (24)

3) 网络流平衡约束

${\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{y}_{i,j,t,s}}\left(o,a,\tau \right)-{\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{y}_{j,i,s,t}}\left(o,a,\tau \right)=\{\begin{array}{l}1,i=o,t=\tau \\ -1,i=o,t=\tau +T\left(o,a\right)\\ 0,其他\end{array}$ (25)

4) 路段建设约束

$y_{i,j,t,s}\left(o,a,\tau \right)\le z_{ij}$ (26)

5) 出行费用预算约束

${\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{F}_{i,j,t,s}{y}_{i,j,t,s}}\left(o,a,\tau \right)\le K$ (27)

6) 路段建设费用

${\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{F}_{i,j,t,s}{z}_{i,j}}\le M$ (28)

7) 决策变量约束

$y_{i,j,t,s}\left(o,a,\tau \right)=\left\{0,1\right\},\forall \left(o,a\right)\in N,\tau \in T,\left(i,j,t,s\right)\in V$ (29)

$z_{ij}=\left\{0,1\right\},\forall \left(i,j\right)\in P^b$ (30)

3. 模型求解算法及算例分析

离散网络设计模型为NP-困难问题，这种模型的计算量较大，尤其将时空可达性模型应用于实际交通网络中，其求解更加困难。本文在求解时空可达性模型，考虑使用深度遍历算法，得到图中从初始点到目标点的所有路径，据此得出最优方法。但由于该方法不适用于大量计算，本章又提出构造拉格朗日松弛算法，求出尽量接近最优解的可行解。

3.1. 深度遍历算法

深度遍历算法 [22] 是一种用于遍历树或图的算法。当节点v所在的边均被探寻过或不满足搜索条件，搜索将回溯到发现节点v的那条边的起始节点。不断重复该过程直至所有节点均被访问。这种算法时间复杂度为 $O\left(n\right)$。

深度优先遍历图的方法是，从图中某顶点v出发：

第一步：访问顶点v；

第二步：依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点均被访问；

第三步：若图中还有顶点 $v^{\prime }$ 没有被访问，则选一个未被访问的点 $v^{\prime }$，从 $v^{\prime }$ 点出发重复第二步。直至图中所有点均被访问。

3.2. 拉格朗日松弛算法

拉格朗日松弛算法 [23] 的基本原理是：将造成问题难解决的约束条件吸收到目标函数中，并使得目标函数保持线性性质，以此得到更易求解的拉格朗日松弛问题。

观察原问题，约束(5)、(6)、(9)与 $y_{i,j,t,s}\left(o,a,\tau \right)$ 相关，约束(8)、(9)与 $z_{ij}$ 相关，约束(10)与 $y_{i,j,t,s}\left(o,a,\tau \right)$ 和 $z_{ij}$ 均相关，因此，将其吸收到目标函数中，可以分别得到关于变量 $y_{i,j,t,s}\left(o,a,\tau \right)$ 和 $z_{ij}$ 相互独立的问题，引入拉格朗日乘子 ${\lambda }_{i,j,t,s}\left(o,a,\tau \right)$，将约束条件(7)松弛，将原问题转化为如下拉格朗日问题：

$\begin{array}{c}{Z}_{LR}=\min {\displaystyle \underset{o,a\in V}{\sum }{\displaystyle \underset{\tau \in T}{\sum }{\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }\left({\gamma }_1{y^{\prime }}_{i,j,t,s}\left(o,a,\tau \right)+{\gamma }_2{F}_{i,j,t,s}{y}_{i,j,t,s}\left(o,a,\tau \right)\right)}}}\\ -{\displaystyle \underset{o,a\in V}{\sum }{\displaystyle \underset{\tau \in T}{\sum }{\displaystyle \underset{\left(i,j,t,s\right)\in V,\left(i,j\right)\in P^b}{\sum }{\lambda }_{i,j,t,s}\left(o,a,\tau \right)\left(z_{ij}-y_{i,j,t,s}\left(o,a,\tau \right)\right)}}}\end{array}$ (31)

将上述问题分解为两个子问题：一个是带有路径选择变量的费用最小化问题，该问题可转化为最小路径费用问题，另一个是关于路段建设的问题，可转化为背包问题。这两种问题均为经典问题，如下所示：

$\begin{array}{c}{Z}_{LR1}=\min {\displaystyle \underset{o,a\in V}{\sum }{\displaystyle \underset{\tau \in T}{\sum }{\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }\left({\gamma }_1{y^{\prime }}_{i,j,t,s}\left(o,a,\tau \right)+{\gamma }_2{F}_{i,j,t,s}{y}_{i,j,t,s}\left(o,a,\tau \right)\right)}}}\\ +{\displaystyle \underset{o,a\in V}{\sum }{\displaystyle \underset{\tau \in T}{\sum }{\displaystyle \underset{\left(i,j,t,s\right)\in V,\left(i,j\right)\in P^b}{\sum }{\lambda }_{i,j,t,s}\left(o,a,\tau \right)y_{i,j,t,s}\left(o,a,\tau \right)}}}\end{array}$ (32)

$Z_{LR2}=-{\displaystyle \underset{o,a\in V}{\sum }{\displaystyle \underset{\tau \in T}{\sum }{\displaystyle \underset{\left(i,j,t,s\right)\in V,\left(i,j\right)\in P^b}{\sum }{\lambda }_{i,j,t,s}\left(o,a,\tau \right)z_{ij}}}}$ (33)

其中 $Z_{LR1}$ 满足约束(5)、(6)、(9)， $Z_{LR2}$ 满足约束(8)、(9)。通过分解，将结构复杂的模型分解为更易求解的子问题，使求解难度降低。

拉格朗日乘子的变化规律为：

${\lambda }_{i,j,t,s}^{k+1}\left(o,a,\tau \right)=\max \left\{{\lambda }_{i,j,t,s}^k\left(o,a,\tau \right)+{\theta }_k\left(y_{i,j,t,s}^k\left(o,a,\tau \right)-z_{ij}^k\right),0\right\}$ (34)

其中：

k为迭代次数；

${\lambda }_{i,j,t,s}^k\left(o,a,\tau \right)$ 为第k次迭代拉格朗日乘子 ${\lambda }_{i,j,t,s}\left(o,a,\tau \right)$ 的值；

${\theta }_k$ 为第k次迭代时的步长；

$y_{i,j,t,s}^k\left(o,a,\tau \right)$ 为第k次迭代路径选择变量 $y_{i,j,t,s}\left(o,a,\tau \right)$ 的值；

$z_{ij}^k$ 为第k次迭代路径建设变量 $z_{ij}$ 的值。

步长 ${\theta }_k$ 满足 ${\theta }_k=\frac{Z_{UP}\left(k\right)-Z_{LB}\left(k\right)}{{\Vert y_{i,j,t,s}^k\left(o,a,\tau \right)-z_{ij}^k\Vert }^2}{\beta }_k$。其中， $Z_{UP}\left(k\right)$ 为原问题的上界，可以由一个可行解的目标值确定，也可以由估计的方法得到，可根据k进行修正； $Z_{LB}\left(k\right)$ 为原问题的下界，取 $Z_{LB}\left(k\right)=Z_{LR}\left({\lambda }_{i,j,t,s}^k\left(o,a,\tau \right)\right)$ ； $\Vert \cdot \Vert$ 为二范数； ${\beta }_k\in \left[0,2\right]$，当 $Z_{LR}\left(\lambda \right)$ 上升时， ${\beta }_k$ 不变，当 $Z_{LR}\left(\lambda \right)$ 在若干步内没有变化，则取一半。表2为拉格朗日乘子变化。

Table 2. Lagrange multipliers change table

表2. 拉格朗日乘子变化表

综上，可以建立基于情形一的拉格朗日算法，具体步骤如下：

第一步：初始化 ${\lambda }^0$， $k=0$，设定拉格朗日乘子 ${\lambda }_{i,j,t,s}^{\text{0}}\left(o,a,\tau \right)=\text{0}$ ；

第二步：求解拉格朗日对偶问题。求解费用最小化问题LR1，得到 $y_{i,j,t,s}^k\left(o,a,\tau \right)$ 和子问题的目标值；求解关于路段建设问题LR2，得到 $z_{ij}^k$ 和子问题的目标值。

第三步：次梯度法更新拉格朗日乘子。若 $y_{i,j,t,s}^k\left(o,a,\tau \right)-z_{ij}^k=0$，则 ${\lambda }_{i,j,t,s}^k\left(o,a,\tau \right)$ 达到最优解停止计算；否则 ${\lambda }_{i,j,t,s}^{k+1}\left(o,a,\tau \right)=\max \left\{{\lambda }_{i,j,t,s}^k\left(o,a,\tau \right)+{\theta }_k\left(y_{i,j,t,s}^k\left(o,a,\tau \right)-z_{ij}^k\right),0\right\}$， $t:=t+1$，重复第二步。

3.3. 算例分析一

本算例有21个结点，已建20条有向路径，其中圆圈代表活动地点，实线代表现有物理路段，圆圈中的数字代表结点序号，线段上的数字代表路段费用，且路段所需时间与路段费用成正比，当在平峰时与路段费用间呈1:1关系，当在高峰时段与路段费用呈2:1关系。但由于在现实过程中并非每条路段都会受时间影响，因此本文选定部分路段设定为受事变交通影响的路段。算例网络中各路段及其所对应的路段费用如图所示，其中，为突出表示网络中受到时变交通状态影响的路段，在图1中标红。

根据深度遍历算法知，共有10条可供选择的路径，若在平峰时段，从节点1出发，给定出行的预算时间为15个时间长度，出行的预算成本为15个费用单位，则可在规定的时间及预算成本范围内，可达地点15个，路径有8条，在情形一的情况下，当时间有限时，考虑费用最小化、可达范围最大化。在该算例下，应选择路径1-3，该情形下目标函数值最小。在情形二的情况下，当时间有限时，考虑费用最小化且在最短时间内到达目标地点，若目标地点为9号，则应该选择路径1-2-6-7-10-9，其中所需的费用为8个费用单位，所需的时间为8个时间单位。在情形三的情况下，当时间有限、费用有限时，考虑可达地点的吸引率最大化，则应该选择路径1-2-6-7-10-9，其吸引化率最大化为25，所需的费用为8个费用单位，所需的时间为8个时间单位。

若在高峰时段，从节点1出发，给定出行的预算时间为15个时间长度，出行的预算成本为15个费用单位，则可在规定的时间及预算成本范围内，可达地点11个，路径有5条，在情形一的情况下，当时间有限时，考虑费用最小化、可达范围最大化。在该算例下，应选择路径1-3，在该情形下目标函数值最小。在情形二的情况下，当时间有限时，考虑费用最小化且在最短时间内到达目标地点，若目标地点

Figure 1. Road section diagram

图1. 路段示意图

为9号，则应该选择路径1-2-6-7-10-9，其中所需的费用为8个费用单位，所需的时间为14个时间单位，可达点吸引率和为20。在情形三的情况下，当时间有限、费用有限时，考虑可达地点的吸引率最大化，则应该选择路径1-2-6-7-10，其吸引化率最大化为25，所需的费用为7个费用单位，所需的时间为13个时间单位。

若该算例下利用拉格朗日分解，分解为最短路问题和背包问题，由于未设未建设路段，因此只需要计算最短路问题，将三个模型均化为最短路问题，经过计算，和深度遍历算法所得方案相同，但该方法运算效率较深度遍历法运算效率快。

3.4. 算例分析二

本算例有14个结点，已建21条有向路径。其中，为突出表示网络中受到时变交通状态影响的路段，在图2中标红。

Figure 2. Road section diagram

图2. 路段示意图

为判断应该先建设哪些未建设路段，其中路径费用不能超过10，利用拉格朗日松弛算法进行迭代计算，迭代结果如下：

Table 3. Iteration table

表3. 迭代表

由表3知应该优先建设路段(3, 10)和(7, 12)，这样在时间一定、路径费用一定时可以到达更多地方。

4. 城市公共交通网络设计模型

4.1. 模型构建

1) 目标函数

本文的目标是最大化被服务乘客的数目，即最小化未被服务的乘客数目。 $c\left(p,k\right)$ 表示乘客p未被公交车k服务的阈值，定义若乘客p被公交车k服务， $c\left(p,k\right)=0$，否则为0； $F_{i,j,t,s}$ 表示旅行费用，加权系数w表示损失一个乘客与旅行费用间的关系。模型目标函数如下：

$z=\min {\displaystyle \underset{k\in K}{\sum }c\left(p,k\right)}+w{\displaystyle \underset{\begin{array}{l}\left(i,j,t,s\right)\in V\\ k\in K\end{array}}{\sum }{F}_{i,j,t,s}{y}_{i,j,t,s}}\left(k\right)$ (35)

2) 网络流平衡约束

根据停车场位置 $O\left(k\right)$ 和 $D\left(k\right)$，以及车的出发时间 $start\left(k\right)$ 和结束时间 $end\left(k\right)$，为每一辆车建立网络流平衡约束，如下所示：

${\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{y}_{i,j,t,s}}\left(k\right)-{\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{y}_{j,i,s,t}}\left(k\right)=\{\begin{array}{l}1,i=O\left(k\right),t=start\left(k\right)\\ -1,i=D\left(k\right),t=end\left(k\right)\\ 0,其他\end{array}$ (36)

3) 运营商盈利约束

从运营商角度，每一辆公交车都要满足最小载客量要求。约束如下：

${\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{F}_{i,j,t,s}{y}_{i,j,t,s}}\left(k\right)\le F$ (37)

4) 公交车承载量要求

公交车有最大承载量，不能超过其承载量，其中 $cap\left(k\right)$ 表示公交车k的最大承载量。

${\displaystyle \underset{\left(i,j,t,s\right)\in V}{\sum }{y}_{i,j,t,s}}\left(k\right)\le cap\left(k\right)$ (38)

5) 目的点约束

公交车k只有经过乘客的出发点 ${\alpha }^o\left(p\right)$ 和目的地 ${\alpha }^D\left(p\right)$ 才可以上车。

$y_{{\alpha }^o\left(p\right),{\alpha }^D\left(p\right),t,s}\left(k\right)=1$ (39)

6) 决策变量约束

$y_{i,j,t,s}\left(k\right)=\left\{0,1\right\},\forall \left(i,j,t,s\right)\in V$ (40)

4.2. 算例分析

本算例有22个点34条有向路段，如图3所示，其中边上的数字表示路径所需时间。有三辆公交车，分别放于1、2、3号停车场，用红色表示，每一辆公交车的承载量为15人，路网中有30名乘客希望通过乘坐公交车完成活动。

Figure 3. Simplify transportation network

图3. 简化交通网络

经过计算得到公交车最佳路线如下，在该路线下能最大程度满足居民出行的任务要求，且符合公交车的最大容纳量，如表4和表5所示：

Table 4. Traffic route table

表4. 交通路线表

Table 5. Passenger demand table

表5. 乘客需求表

表3显示了求解得到的公交车的最优路线，为证明该路线最优，随机选取了30为乘客，每位乘客都有不同的上车点和下车点，表4显示为乘客分配的公交车辆编号以及乘车时间，可以发现有六位乘客未能选取最优路径。

5. 结论

本文建立时空可达性交通网络设计模型，通过结合个体所受的时间约束、空间约束及费用约束间的耦合关系，提供出行者出行的最优路径。通过对交通网络区域化的描述，构建时空可达性交通网络设计模型和理论求解方法，并将模型应用于实际交通网络中，现将本文的研究成果总结如下：

1) 针对城市基础交通网络，考虑个体在起点及活动地点所受的时间约束及费用约束，引入路段选择变量及路段建设变量两个0/1变量，分别建立费用最小化、可达范围最大化模型，费用最下化、最短时间完成出行任务的模型，以及在费用约束下，可达范围最大化且可达点吸引率最大化模型。

2) 本文利用深度遍历算法及拉格朗日松弛算法求解时空可达性交通网络模型。在深度遍历算法中考虑求出在时空网络中所有的可行路径，从中选择在时间约束及费用约束中的可行路段，据此比较分别得到三种模型下的最优路径，但由于该方法计算量颇大，不适用于大规模的交通网络，因此提出利用拉格朗日松弛算法求出最优解。该算法将路段建设关联约束吸入目标函数中，将原问题分解为两个小问题，同时利用次梯度算法不断更新拉格朗日乘子，据此求得最优解。

3) 针对城市公共交通网络，研究了基于时空可达性的公共交通网络问题。考虑公交车最大承载量约束、乘客目的地最短路约束、时空网络流决策约束、公交车最大收益约束等，构建改进模型。