Page 277 - 《软件学报》2025年第8期

3700 软件学报 2025 年第 36 卷第 8 期

G 是连通的. 如图 s(x s ,y s ) 和汇点
证明: 假设路网 G 由 m×n 个路网最小区域组成, 则 4(b) 所示, 构建源点
e(x e ,y e ), 且 ∀v i ∈ V, x s < x i < x e , 令 x min = min{x i }, x max = max{x i }, 构建顶点集 V 1 和 , 使得 ∀v p ∈ V 1 , ∀v q ∈ V 2 , 有
V 2
x p ≈ x min , x q ≈ x max , 将源点 s 与 V 1 的每个顶点建立一条边, 而汇点 e 与 V 2 的每个顶点建立一条边, 权重都为 1. 根据
最大流最小割定理, 图 4 中“竖直”虚线为最小割边, 最大流为 m+1. 此外, 源点 s(x s ,y s ) 和汇点 e(x e ,y e ) 的位置还能
满足条件: ∀v i ∈ V, y s < y i < y e , 令 y min = min{y i }, y max = max{y i }, 此时顶点集 V 1 和 V 2 的顶点满足 ∀v p ∈ V 1 , ∀v q ∈ V 2 ,

有 y p ≈ y min ,y q ≈ y max , 同样地, 将源点 s 与 V 1 的每个顶点建立一条边, 而汇点 e 与 V 2 的每个顶点建立一条边, 权重都
∑
为 1. 同理, 根据最大流最小割定理, 存在某条“水平”线为最小割边, 且最大流为 n+1. 此时, ∈ G 1 , v q ∈ G 2 , A[p,q] =
v p
min{m,n}+1.
定理 1 提供了一种“水平”或“竖直”的划分方法使得通信开销最小, 接下来只需要每个划分的子图节点数相同
S 2 的优化. 目前, 四叉树 (quad tree) 和 KD 树 (KD-tree) 等划分方法沿着“水平”和“竖直”方向将路网划分
即可完成
为若干相等区域, 可以满足通信开销最小的条件, 但对于每个划分的区域, 并不能保证其计算负载是相同的. 为此,
√ √
( n× n) 个分块, 其主要算法包括以下 6 个步骤.
提出了一种两阶段划分方案将路网划分成
(1) 确定每个顶点 (交叉口) 的二维坐标.
(2) 将每个顶点按照 x 坐标排序.
√
(3) 按照排序后的 x 坐标将路网分成 n 个子图, 每个子图包含相同数量的顶点.
(4) 每个子图的顶点按照 y 坐标排序.
√
(5) 按照排序后的 y 坐标对每个子图再次分成更小的 n 个子图, 每个更小的子图包含相同数量的顶点.
(6) 每个子图分配到一个计算节点.
√ |V|
两阶段划分算法第 1 次先将顶点 (交叉口) 按照 x 坐标排序, 并其划分成 n 个子图, 每个子图的顶点数为 √ ,
n
√
第 2 次在每个子图的顶点按照 y 坐标排序, 并将每个子图再次分成更小的 n 个子图, 此时总共分成了 n 个子图,
|V| |V|
每个子图的顶点数为 , 根据 ϵ-Balancing 的定义, ∀i < n, |V i |− = 0, 因此该算法是 0-Balancing 的. 而对于四叉
n n
|V| |V|
树和 KD 树的划分, ∃i < n, |V i |− > 0, 从而存在 ϵ > 0, 使得 ∀i < n, −ϵ ⩽ |V i |− ⩽ ϵ . 综上, 两阶段划分算法相
n n
较于四叉树和 KD 树具有更优的计算负载.

3.2 车辆行驶及其并行优化
车辆在道路上行驶主要遵从 Krauss 模型 (跟驰模型) [25] . Krauss 模型是安全距离类模型, 当一辆车突然进行刹
车或减速时, 安全距离模型假设后面的车辆能够迅速察觉到前车的行为, 并有足够的时间来做出反应. 这包括驾驶
员注意到前车制动的信号、反应时间内减速以及最终停车, 以避免发生碰撞. 具体而言, 假设前车 (before) 与后车
(after) 之间的车距为:

g = x b − x a −l (5)
其中, l 表示车本身长度, 如果要求后车不撞前车, 需要满足:

L(v a )+v a τ < L(v b )+g (6)
其中, L(v a ) 表示后车刹车距离, L(v b ) 表示前车刹车距离, v a 表示后车速度, τ 表示刹车时间, g 表示车间距, 为了计
¯ v
算 v a , 假设在极短时间内, 近似速度可表示为 ¯ v = (v a +v b )/2, 泰勒展开后对 求一阶导数即可得到:

′
L (¯v)v a + v a τ < L (¯v)v b +g (7)
′
假设刹车时加速度为 −b(v), 则有:

∫
d v s v
′
L (v) = ds = (8)
dv 0 −b(s) b(v)
公式 (8) 的积分项表示为刹车距离. 在模拟过程中, 车辆会根据跟驰模型自行判断当前加速和减速, 保证最大
安全跟车速度, 并根据交叉口信号灯模块, 合理规划行车路线, 模拟行驶. 因此, 车辆行驶算法的主要包括以下几个
步骤.