一种基于交叉口信号延误的超路径规划方法

杜牧青; 鞠姿彦; 李大韦

doi:10.3969/j.issn.0258-2724.20220387

一种基于交叉口信号延误的超路径规划方法

doi: 10.3969/j.issn.0258-2724.20220387

1.
河海大学土木与交通学院，江苏南京 210098
2.
东南大学交通学院，江苏南京 210018

基金项目: 国家自然科学基金项目（72471083）

详细信息

作者简介:
杜牧青（1986—），男，副教授，博士，研究方向为交通运输规划与管理，E-mail：dumqhhu@hhu.edu.cn

中图分类号: U491.2
计量
- 文章访问数: 263
- HTML全文浏览量: 81
- PDF下载量: 29
- 被引次数: 15
出版历程
- 收稿日期: 2022-05-30
- 修回日期: 2022-09-20
- 网络出版日期: 2024-10-29
- 刊出日期: 2022-09-22

Hyperpath Searching Algorithm Method Based on Signal Delay at Intersections

1.
College of Civil and Transportation Engineering, Hohai University, Nanjing 210098, China
2.
School of Transportation, Southeast University, Nanjing 210018, China

摘要

摘要:
城市道路中交叉口信号周期性变化会导致车辆出行的不确定延误，为降低车辆在交叉口处产生的信号延误，以路段旅行时间和交叉口期望延误最小为优化目标，提出一种改进的超路径规划方法. 首先，根据车辆到达交叉口的概率分布函数，推导出车辆在信号交叉口的期望等待时间和转向比例计算公式；其次，引入标号设定算法构建高性能超路径规划方法；最后，将改进的超路径规划方法应用于南京新街口区域的路网，通过最优超路径集合分析证实其适用性. 研究表明：与最短路出行策略相比，车辆遵循基于超路径规划方法的出行策略，在行进过程时从最优超路径集合中选择变换的行驶路线可降低67.1%的交叉口信号延误和22.3%的总旅行时间；此外，超路径出行策略可优化路网中的出行结构，缓解交通拥堵，实现流量均衡.
- 交叉口信号配时 /
- 概率分布函数 /
- 转向延误 /
- 扩展的前向星结构 /
- 标号设定算法
Abstract:
The periodic change of intersection signals in urban road systems leads to the uncertain delay of vehicle travel. In order to reduce the delays of vehicles at signal-controlled intersections, an improved hyperpath searching algorithm was proposed with the minimization of travel time on the road segments and the expected delay at the intersections as the optimization goal. First, according to the probability distribution function of vehicles arriving at the intersection, the expected waiting time and the turning movement proportion were derived. Then, the high-performance hyperpath searching algorithm was developed with the introduction of the label setting algorithm. Finally, the improved hyperpath searching algorithm was applied to the road network at Xinjiekou area, Nanjing, and the optimal hyperpath set was used to evaluate the applicability of the algorithm. The results show that compared with the shortest path strategy, hyperpath searching algorithm reduces the intersection delay and the total travel time by 67.1% and 22.3%, respectively as drivers shift to a driving route in the optimal hyperpath set. Furthermore, the hyperpath-based strategy can optimize the trip distribution in the road network, alleviating traffic congestion and contributing to flow equilibrium.
- intersection signal timing /
- probability distribution function /
- turning delay /
- extended forward star structure /
- label setting algorithm

HTML全文

随着我国交通行业和互联网信息技术的快速发展，物流服务信息化水平和专业能力得到了大幅度提高. 物流服务行业的迅速发展，有助于提升产品的运输效率，降低企业物流成本，提升企业自身的核心竞争力. 在激烈的竞争中，物流服务需求方的目标是用最低的成本获得最满意的物流服务，而物流服务供给方要在物流需求方满意的同时追求较高的利润，供需双方的交易是典型的不交叉关系，两者的匹配决策为自主自愿的市场化运作，其合作特征符合双边匹配理论基本要求，适用双边匹配理论和匹配决策方法进行研究分析.

在物流服务供需双边匹配决策问题中，通常物流服务供需匹配的供方或需方需要对对方做出一定的偏好排序，即供给方或需求方需要具备对对方的“敏感性偏好”，在该问题的研究中，根据供需双方各自的评价指标给出完全偏好序信息是常见的研究方法. 因此，基于完全偏好序的双边匹配问题研究备受关注，樊治平等^[1]在基于完全偏好序信息的一对一双边匹配问题中,以双边主体的匹配满意度最大构建了多目标优化模型，利用双边主体的最高可接受偏好序算法进行求解获得匹配结果. 孔德财等^[2]针对一对一双边匹配问题，考虑匹配的稳定性、公平性和满意性，以匹配主体的满意度最大及匹配主体间的满意度绝对差异最小建立了多目标优化模型. 姜艳萍等^[3]针对基于偏好序的双边匹配问题,提出了具有抗操作和抗自亏性的匹配方法. 张笛等^[4]在考虑匹配特征基础上，提出了多重偏好下的一对一多阶段双边匹配方法. Dalzell等^[5]认为当用于匹配的分类变量有误差时，可以同时估计回归模型和匹配记录，提出了一种贝叶斯匹配方法. Li等^[6]提出了一种基于双重犹豫模糊偏好信息的一对一双边匹配方法，在稳定匹配约束下，以双方的满意度最大、差异度最小建立多目标优化模型. Yu等^[7]针对人事岗位匹配问题提出了新的直觉模糊Choquet积分聚2集算子，构建了一个直观的模糊一对一双边匹配模型. 李铭洋等^[8]针对基于序值偏好信息的一对多双边匹配问題构建了以匹配主体序值之和最小为目标的多目标优化模型. Zhang等^[9]对多对多双边匹配的匹配因素进行了研究，构建了一种顺序联结反应模型. Chen等^[10]研究了弱偏好序的多对多双边匹配问题，提出了一种新的Pareto稳定匹配算法. Klaus等^[11]利用两阶段非揭示机制研究了多对多匹配问题. Zhang等^[12]提出了一种基于失望理论的不完全模糊偏好序一对一双边匹配决策理论，构建了确定最佳匹配解的双目标优化模型. Jiao等^[13]考虑了多对多双边匹配中的激励相容性问题. Fan等^[14]考虑心理因素将预期的各代理对相对代理的偏好序数基于不确定偏好序数计算，根据失望理论得到可能的匹配结果. Chen等^[15]提出了一种根据参与者的主观偏好修正一些关键目标，有效地提高了双边参与者的满意度. 林杨等^[16-19]也进行了相应的研究.

既有文献对一对一、多对多双边匹配问题进行了一定的研究，主要从整体满意度角度考虑匹配主体进行匹配，而对匹配主体中个体的满意度及其均衡性较少涉及，个体满意度未得到充分满足，很难保证匹配的公平性. 在保证整体满意度前提下，考虑双边匹配主体中个体在匹配中的满意度，主体中个体的匹配满意度较均衡时才能达到公平的双边匹配. 鉴于此，本文充分考虑整体满意度和个体满意度，构建基于完全偏好序物流服务供需多对多双边匹配两阶段优化模型，并基于NSGA-Ⅱ（non-dominated sorting genetic algorithm-Ⅱ）和线性规划方法设计模型求解算法.

1. 问题描述

假设所有物流服务供需双方都要接受决策者的指令，决策者给出多种匹配方案后，物流服务供需方根据各自不同的偏好选择匹配方案. 假设在物流服务供需双方数量充足的情况下，物流服务需求方其集合为 $A = \left\{ {{A_1},{A_2}, \cdots ,{A_m}} \right\}$ $（m\geqslant 2）$ ， ${A_i}$ 表示第 $i$ 个物流服务需求方， $i{\text{ = 1}},2, \cdots ,m$ ；物流服务供给方其集合为 $B = \left\{ {{B_1},{B_2}, \cdots ,{B_n}} \right\}$ $（n\geqslant 2)$ ， ${B_j}$ 表示第 $j$ 个物流服务供给方， $j{\text{ = }}1,2, \cdots ,n$ . 则 $I{\text{ = }}\left\{ {{\text{1}},2, \cdots ,m} \right\}$ ， $J = \{ {{\text{1}},2, \cdots ,n} \}$ . 设 ${{\boldsymbol{R}}_i}{\text{ = }}( {{r_{i1}},{r_{i2}}, \cdots ,{r_{in}}} )$ 为需求方 ${A_i}$ 给出的关于供应方 $B$ 的偏好序向量，其中 ${r_{ij}}$ 为需求方 ${A_i}$ 把供应方 ${B_j}$ 排在第 ${r_{ij}}$ 位. 设 ${{\boldsymbol{T}}_j}{\text{ = }}( {{t_{1j}},{t_{2j}}, \cdots ,{t_{mj}}} )$ 为供应方 ${B_j}$ 给出的关于需求方 $A$ 偏好序向量，其中 ${t_{ij}}$ 为需求方 ${B_j}$ 把供给方 ${A_i}$ 排在第 ${t_{ij}}$ 位.

1.1 参数和变量定义

基于完全偏好序的物流服务供需双边匹配模型中的相关参数与变量定义如下：

${\alpha _{ij}}$ ——第 $i$ 个物流服务需求方 ${A_i}$ 对第 $j$ 个物流服务供应方 ${B_j}$ 的满意度；

${\beta _{ij}}$ ——第 $j$ 个物流服务供应方 ${B_j}$ 对第 $i$ 个物流服务需求方 ${A_i}$ 的满意度；

${p_i}$ ——与第i个物流服务需求方匹配的供应方最大个数；

${q_j}$ ——与第 $j$ 个物流服务供应方匹配的需求方最大个数；

${h_i}$ ——与第 $i$ 个物流服务需求方匹配的供应方个数；

${l_j}$ ——与第 $j$ 个物流服务供应方匹配的需求方个数；

${x_{ij}}$ ——第 $i$ 个物流服务需求方 ${A_i}$ 与第 $j$ 个物流服务供应方 ${B_j}$ 匹配，0-1变量，其中 ${x_{ij}}$ = 0表示 ${A_i}$ 与 ${B_j}$ 不匹配， ${x_{ij}}$ = 1表示 ${A_i}$ 与 ${B_j}$ 匹配.

1.2 物流服务供需方满意度

${\alpha _{ij}}$ 和 ${\beta _{ij}}$ 的表达式如下：

${\alpha _{ij}} = l({r_{ij}}),$

${\beta _{ij}} = g({t_{ij}}),$

式中： $l( {\text{•}} )$ 和 $g({\text{•}} )$ 均为单调递减函数.

按照完全偏好序的物流服务供需方双边匹配问题的描述，本文规定物流服务供需双方偏好序的倒数即为物流服务供需双方对对方的满意度，则满意度 ${\alpha _{ij}}$ 和 ${\beta _{ij}}$ 可分别表示为

${\alpha _{ij}} = \frac{1}{{{r_{ij}}}},$

(1)

${\beta _{ij}} = \frac{1}{{{t_{ij}}}}.$

(2)

基于完全偏好序向量 ${{\boldsymbol{R}}_i}$ 和 ${{\boldsymbol{T}}_j}$ ，分别建立完全偏好序矩阵 ${\boldsymbol{R}} = {\left( {{r_{ij}}} \right)_{m \times n}}$ 与 ${\boldsymbol{T}} = {\left( {{t_{ij}}} \right)_{m \times n}}$ . 依据式（1）和式（2），完全偏好序矩阵R与T分别转化为完全满意度值矩阵 ${{\boldsymbol{S}}_A} = {\left( {{\alpha _{ij}}} \right)_{m \times n}}$ 与 ${{\boldsymbol{S}}_B} = {\left( {{\beta _{ij}}} \right)_{m \times n}}$ .

2. 模型构建

本文构建多对多物流服务供需双边匹配两阶段优化模型，第1阶段以物流服务需求方的整体满意度最大及物流服务需求方个体满意度的方差最小构建匹配模型（同理建立物流服务供给方匹配模型），利用遗传算法进行模型求解得到物流服务供需方理想点的双边匹配Pareto解集；第2阶段构建以供需双方满意度与理想点满意度差最小的多目标优化模型，利用遗传算法进行模型求解得到双边匹配Pareto解集.

2.1 第1阶段优化模型

1）针对物流服务需求方 ${A}$ ，依据满意度值矩阵 ${{\boldsymbol{S}}_A} = {\left( {{\alpha _{ij}}} \right)_{m \times n}}$ ，以物流需求方整体满意度及个体满意度为优化目标，令 ${f_A} = \left({{\displaystyle\sum\limits_i {\sum\limits_j {{\alpha _{ij}}{x_{ij}}} } }}\right)\bigg/{m}$ 为物流服务需求方的个体满意度平均值.

构建第1阶段物流服务需求方优化模型1：

$\max \;{{\textit{Z}}_1} = \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n {{\alpha _{ij}}{x_{ij}}} } ,$

(3)

$\min \;{{\textit{Z}}_2} = \frac{{\displaystyle \sum\limits_i {{{\left( {\displaystyle\sum\limits_j {{\alpha _{ij}}{x_{ij}} - {f_A}} } \right)}^2}} }}{{\displaystyle\sum\limits_i {\displaystyle\sum\limits_j {{x_{ij}}} } }};$

(4)

s.t.

$\quad\displaystyle\sum\limits_{j = 1}^n {{x_{ij}} \leqslant {p_i}},$

(5)

$\quad\displaystyle\sum\limits_{i = 1}^m {{x_{ij}} \leqslant {q_j}},$

(6)

$\quad\sum\limits_{j = 1}^n {{\alpha _{ij}}{x_{ij}}} > \sum\limits_{k = 1}^{{h_i}} {\frac{1}{{n - (k - 1)}}},$

(7)

$\quad\sum\limits_{i = 1}^m {{\beta _{ij}}{x_{ij}}} > \sum\limits_{\lambda = 1}^{{t_j}} {\frac{1}{{m - (\lambda - 1)}}}.$

(8)

第1阶段物流服务需求方优化模型1，只考虑物流服务需求方主体A总体满意度和物流服务需求方 ${A_i}$ 个体满意度方差. 式（3）、（4）为目标函数；式（3）表示在严格双边匹配意义下最大化物流服务需求方主体A关于物流服务供给方主体匹配的总体满意度，式（4）表示在严格双边匹配意义下物流服务需求方个体 ${A_i}$ 与供给方个体 ${B_j}$ 匹配， ${A_i}$ 的个体满意度方差最小；式（5）表示每个物流服务需求方主体可以与多个物流服务供应方主体匹配；式（6）表示每个物流服务供给方主体可以与多个物流服务需求方主体匹配；式（7）保证物流服务需求方个体 ${A_i}$ 匹配的供应方不是最差匹配（例如，与需求方 ${A_1}$ 匹配的供应方数量是2个，这2个供应方不能是需求方 ${A_1}$ 在满意度排序中最后两位的供应方），其中 ${h_i} = \displaystyle\sum\limits_{j = 1}^n {{x_{ij}}}$ ；式（8）保证物流服务供给方个体 ${B_j}$ 匹配的需求方不是最差匹配，其中 ${t_j} = \displaystyle\sum\limits_{i = 1}^m {{x_{ij}}} .$

2）针对物流服务供给方B，依据满意度值矩阵 ${{\boldsymbol{S}}_B} = {\left[ {{\beta _{ij}}} \right]_{m \times n}}$ ，以物流供给方整体满意度及个体满意度为优化目标，令 ${f_B} = \left({{\displaystyle\sum\limits_i {\sum\limits_j {{\beta _{ij}}{x_{ij}}} } }}\right)\bigg/{n}$ 为物流服务供给方的满意度平均值.

构建第1阶段物流服务供给方优化模型2，模型2只考虑物流服务供给方主体B总体满意度和物流服务需求方 ${B_j}$ 个体满意度方差，与模型1类似，这里不再赘述.

2.2 第2阶段优化模型

第2阶段模型中，考虑物流服务供需主体的整体满意度与供需双方在匹配时理想值的差值最小. 构建第2阶段优化模型3：

$\min\; {{\textit{Z}}_5} = Z_1^* - \displaystyle\sum\limits_i {\sum\limits_j {{\alpha _{ij}}{x_{ij}}} },$

(10)

$\min \; {{\textit{Z}}_6} = Z_3^* - \displaystyle\sum\limits_i {\sum\limits_j {{\beta _{ij}}{x_{ij}}} };$

(11)

s.t.

$\quad\sum\limits_{j = 1}^n {{x_{ij}} \leqslant {p_i}} ,$

(12)

$\quad\sum\limits_{i = 1}^m {{x_{ij}} \leqslant {q_j}}.$

(13)

优化模型3中： $Z_1^*$ 为优化模型1中只考虑物流服务需求方主体A总体满意度的理想值； $Z_3^*$ 为优化模型2中只考虑物流服务供给方主体B总体满意度的理想值；式（9）、（10）为目标函数，式（9）表示在严格双边匹配意义下最小化物流服务需求方主体A关于物流服务供给方主体匹配的整体满意度与理想值之间的差值，式（10）表示在严格双边匹配意义下最小化物流服务供给方主体B关于物流服务需求方主体匹配的整体满意度与理想值之间的差值；式（11）表示每个物流服务需求方主体可以与多个物流服务供应方主体匹配；式（12）表示每个物流服务供给方主体可以与多个物流服务需求方主体匹配.

3. 模型求解

3.1 第1阶段模型求解

模型1为双目标非线性0-1规划问题，优化目标分别为整体满意度 ${Z_1}$ 和个体满意度 ${Z_2}$ ，由于 ${Z_2}$ 为非线性表达式，因此，该问题没有精确算法. 解决此类问题的最好方法是基于NSGA-Ⅱ的多目标优化算法^[20]. 本文将从以下3个方面进行算法设计.

1）个体编码

如图1所示，个体采用多层0-1编码，总长度为 $m \times n$ ，第 $i$ 行第 $j$ 列的编码值如果为1表示需求方 $i$ 和供应方 $j$ 匹配，否则为两者不匹配. 对于第 $i$ 行编码，其和必须小于等于 ${p_i}$ ，表示与物流服务需求方 ${A_i}$ 匹配的供给方个数最多不超 ${p_i}$ ；同理，对于第 $j$ 列编码，其和必须小于等于 ${q_j}$ .

图 1 个体编码

Figure 1. Individual encoding

下载: 全尺寸图片幻灯片

2）适应度函数

针对物流服务需求方， ${Z_{\text{1}}}$ 为整体满意度，优化目标为整体满意度最大，可采用 $1/{Z_1}$ 作为该目标的适应度函数， ${Z_2}$ 为个体满意度，优化目标为个体满意度差异最小，可采用 ${Z_2}$ 直接作为该目标的适应度函数.

3）种群进化策略

一般情况下，通过交叉获得新个体的方法来保证在进化过程中群体多样性. 由于本模型中个体的行和列均有约束，个体的合法性采用惯常的交叉方法无法得到保证，基于上述考虑，设计一种能够满足模型中约束条件的行（列）交叉算子，计算步骤如下：

步骤1　随机选中两个父个体，交换其奇数行（列）生成两个子个体；

步骤2　针对每一个子个体，从0到 $n$ （ $m$ ）循环检查其第 $j$ 列（第 $i$ 行）是否满足条件　　 $\displaystyle\sum\limits_{i = 1}^m {x_{ij}} \leqslant$ ${q_j} \left ( \displaystyle\sum\limits_{j = 1}^n {{x_{ij}} \leqslant {p_i}}\right )$ ，如果全部满足，则所有子个体均为合法个体；

步骤3　对于非法个体，选择不满足步骤2中条件的列（行），定位其奇数行中第1 次出现元素1的行列值，尝试与本行（列）第1个元素0交换位置，交换后分别检查交换列（行）是否满足步骤2中条件，如果满足，则修正后的子个体合法，如果不满足，重新尝试与本行（列）其他元素0交换位置，再次检查，直到条件满足.

以某物流供需服务为例，共有4个物流服务需求方和6个物流服务供给方，4个物流服务方可匹配的供给方个数分别不超过2、3、2、2，6个物流服务供给方可匹配的需求方个数分别不超过2、2、2、2、2、1. 以如图2所示两个父个体的行交叉为例，首先将父个体1和父个体2的第1、3行交换，生成子个体1和子个体2，下一步分别检查子个体1和子个体2的合法性.

图 2 行交叉示例

Figure 2. Example of row-cross operator

下载: 全尺寸图片幻灯片

对于子个体1，第6列的元素和为2，不满足可匹配的需求方个数约束，需要进行修正，第6列第1个元素1出现在第1行，首先与第1行第2列的元素0交换，交换后分别检查第2列和第6列，第6列元素和为1，满足要求，但第2列元素和为3，不满足可匹配的需求方个数约束，再次尝试第1行第3列的元素0交换，交换后分别检查第3列和第6列，均满足可匹配的需求方个数约束，子个体1合法. 同理，对于子个体2，行交叉后也不满足可匹配的需求方个数约束，将第3列第3行的元素1和第1列第3行的元素0交换后，个体合法.

为防止早熟收敛，在交叉的基础上引入适度的变异. 变异操作采用行（列）交换变异法得到新个体，核心思想是随机选择个体，同时基于随机方法选择两行（列），将被选个体的选中行进行交换，生成一个新个体，并检查个体的合法性. 如果个体非法，从导致个体非法的行中找到第1个元素1，与被交换行中的相同位置元素交换位置，交换后分别检查交换列（行）是否满足步骤2中条件，如果满足，则修正后的子个体合法，如果不满足，继续在导致个体非法的行中查找元素1，与被交换行中的相同位置元素交换位置，再次检查，直到条件满足.

以图3所示个体为例，选中个体的2、3行，进行交换，交换后第2行满足可匹配的需求方个数约束，但第3行元素之和为3，不满足可匹配的需求方个数约束，在第3行中查找第1个元素1，其位于第3行第1列，与第2行第1列元素进行交换，交换后2、3行同时满足可匹配的需求方个数约束，个体合法.

3.2 第2阶段模型求解

针对第1阶段优化得到的Pareto最优解中，根据对整体满意度和个体满意度的偏好，供需双方决策者分别选择合理的整体满意度作为第2阶段模型的理想点 $Z_1^*$ 和 $Z_3^*$ ，多目标函数的最优值与理想点的距离越接近越好，利用线性规划方法求解.

加权将多目标优化模型转化为单目标优化模型4：

图 3 行变异示例

Figure 3. Example of row variation operator

下载: 全尺寸图片幻灯片

$\begin{split} &\min \;F = \varepsilon \left(Z_1^* - \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^m {{\alpha _{ij}}{x_{ij}}} } \right) + \hfill \\ &{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} (1 - \varepsilon )\left(Z_3^* - \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^m {{\beta _{ij}}{x_{ij}}} } \right); \end{split}$

(15)

s.t.

$\quad \sum\limits_{j = 1}^n {{x_{ij}} \leqslant {p_i}} ,$

(16)

$\quad \sum\limits_{i = 1}^m {{x_{ij}} \leqslant {q_j}}.$

(17)

在现实的物流服务双边匹配问题中, $\varepsilon$ 和1− $\varepsilon$ 可被分别视为物流供需双方主体的重要程度，通常由中介依据物流供需双边主体的地位来考虑如何确定权重. 若认为物流供需双边主体在匹配过程中处于平等地位，则有 $\varepsilon$ = 0.5. 若认为物流供需双边主体在匹配过程中的地位不同，即一方主体与另一方主体相比在匹配过程中显得更重要，则有 $0 \leqslant \varepsilon \leqslant 1$ ， $\varepsilon$ 取值从0.0001～1.0000，以步长0.0001循环，通过线性规划方法进行求解，可获得多对多物流服务供需双边匹配的Pareto解集.

4. 算例分析

某地区的中介公司收到( ${A_1},{A_2},{A_3},{A_4},{A_5},{A_6}$ )6个物流服务外包公司的相关需求信息，而中介公司里有( ${B_1},{B_2},{B_3},{B_4},{B_5}$ ) 5个物流企业的信息. 相关供需双方的满意度排序见表1和2.

表 1 需求方A对供给方B的排序

Table 1. Preference list of demand A versus supply B

需求方	B₁	B₂	B₃	B₄	B₅
A₁	2	1	3	4	5
A₂	1	5	4	3	2
A₃	4	2	5	1	3
A₄	2	4	1	5	3
A₅	4	1	5	2	3
A₆	3	1	5	2	4

下载: 导出CSV

| 显示表格

表 2 供给方B对需求方A的排序

Table 2. Preference list of supply B versus demand A

供给方	A₁	A₂	A₃	A₄	A₅	A₆
B₁	3	1	2	5	4	6
B₂	6	4	1	5	2	3
B₃	4	3	2	5	6	1
B₄	5	4	1	3	6	2
B₅	1	3	4	6	5	2

下载: 导出CSV

| 显示表格

针对表1和表2的排序信息，假设每个物流服务需求方A可选择服务供应方最大数量分别为2、3、2、4、2、1，而物流服务供应方B可向需求方提供匹配的最大数量为3、2、2、2、1. 根据求解方法，在第1阶段考虑个体满意度，分别针对需求方A和供给方B进行优化，可分别获得供需双方的整体满意度和个体满意度Pareto前沿（如图4、5所示）.

图 4 需求方A的整体满意度与个体满意度Pareto最优前沿

Figure 4. Pareto optimal front of overall satisfaction and individual satisfaction of demand A

下载: 全尺寸图片幻灯片

假设需求方A和供给方B可接受的个体满意度阈值均为0.22，则供需双方可选择的方案如图4、5所示，供需双方整体满意度的理想点为5.98和5.23，在此理想点下，根据基于理想点的模型求解方法，可获得如图6所示的整体满意度Pareto最优前沿.

对于图6中整体满意度Pareto最优解，可获得需求方A对供给方B间的匹配关系，假设供需双方可接受的整体满意度值为(5.93,5.20)，则匹配关系如图7所示.

图 5 供应方B的整体满意度与个体满意度Pareto最优前沿

Figure 5. Pareto optimal front of overall satisfaction and individual satisfaction of supply B

下载: 全尺寸图片幻灯片

图 6 供需双方个体满意度限制下的整体满意度Pareto前沿

Figure 6. Pareto optimal front of overall satisfaction constrained by individual satisfactions of supply and demand sides

下载: 全尺寸图片幻灯片

图 7 供需双方整体满意度为(5.93,5.20)下的匹配关系

Figure 7. Matching results of supply and demand sides with overall satisfaction (5.93,5.20)

下载: 全尺寸图片幻灯片

当不考虑个体满意度时，可以构建多对多物流服务供需双边匹配整体满意度优化模型，以供需双方匹配满意度最大为目标函数的多目标优化模型，求解中先求出物流服务供需双方不考虑对方满意度的情况下自身的理想点满意度，再通过物流服务供需双方实际最大满意度与理想点满意度的差距最小建立多目标优化模型，利用线性规划方法进行模型求解得到双边匹配Pareto解集. 基于NSGA-Ⅱ的多目标优化算法获得整体满意度和个体满意度的Pareto解，为决策者提供了体现整体和个体满意度不同偏好的决策方案，指导决策者获得供需双方满意的匹配关系.

根据基于理想点法对算例求解，其理想点为(7.33,6.75)，可获得如图8所示的整体满意度Pareto最优前沿.

图 8 供需双方整体满意度Pareto前沿

Figure 8. Pareto optimal front of overall satisfaction of supply and demand sides

下载: 全尺寸图片幻灯片

从图8中可以看出：需求方A对供给方B的整体满意度和B对需求方A的整体满意度是此消彼长的关系，即需求方A对供给方B取最大整体满意度时，供给方B对需求方A的整体满意度最低，因此，在决策过程中，需要供需双方谈判以获得彼此可接受的满意度.

对于图8中任意解，可获得需求方A对供给方B间的匹配关系，如供需双方可接受的满意度值为(5.10,6.75)，则匹配关系如图9所示. 在此匹配关系下，需求方A和供给方B的个体满意度方差分别0.57和0.22，个体满意度越小，表示个体之间的差异越小，对于本方案，需求方A的个体满意度差异较大，选择此方案导致需求方之间满意度不公平，容易导致矛盾产生.

由图6与图8的Pareto前沿对比可以看出：考虑个体满意度差异的情况下得到的整体满意度明显劣于未考虑个体满意度的情况，相对未考虑个体满意度情况，引入个体满意度时会导致双方整体满意度下降，即为使每个个体能够得到满意、公平的匹配结果，需要牺牲双方的整体的满意度. 表明考虑个体满意度最优时，整体满意度会受到一定的影响，但其结果更贴近现实情况，并能得到公平的匹配结果，因为个体满意度离理想点越近，匹配结果越接近个体对匹配结果的期望.

图 9 供需双方整体满意度为(5.10,6.75)下的匹配关系

Figure 9. Matching results of supply and demand sides with overall satisfaction (5.10, 6.75)

下载: 全尺寸图片幻灯片

5. 结　论

本文中同时考虑整体满意度和个体满意度均衡性的供需双方多对多双边匹配两阶段优化模型，能够刻画物流服务中供需双方的利益关系，既能考虑物流服务供需方整体满意度，又兼顾供需方匹配个体满意度的均衡性. 后续研究将考虑物流服务供需方个体差异化和优先级的稳定匹配问题，以提高实用性和适应性.

图 1 公交超路径概念示意

Figure 1. Concept of hyperpath in public transport

下载: 全尺寸图片幻灯片

图 2 道路网络考虑路段延误的最优超路径^[15]

Figure 2. Optimal hyperpath in the road network with the consideration of delays on road segments^[15]

下载: 全尺寸图片幻灯片

图 3 交叉口的转向行为

Figure 3. Turning movements at intersection

下载: 全尺寸图片幻灯片

${y_{{r_{X,m}}}}$ 的分布函数

Distribution function of ${y_{{r_{X,m}}}}$

下载: 全尺寸图片幻灯片

图 5 不相邻转向的组合（单位：s）

Figure 5. Combination of non-adjacent turns （unit:s）

下载: 全尺寸图片幻灯片

相位不相邻 ${y_X}$ 的分布函数

Distribution function of ${y_X}$

下载: 全尺寸图片幻灯片

图 7 交叉口信号配时图（单位：s）

Figure 7. Intersection signal timing diagram (unit: s)

下载: 全尺寸图片幻灯片

图 8 相邻转向绿灯时间的组合

Figure 8. Combination of the green time for adjacent turns

下载: 全尺寸图片幻灯片

相位相邻 ${y_X}$ 的分布函数

Distribution function of ${y_X}$

下载: 全尺寸图片幻灯片

图 10 相邻两相位时间段分割

Figure 10. Segmentation of two adjacent phases

下载: 全尺寸图片幻灯片

图 11 不相邻两相位时间段分割

Figure 11. Segmentation of two non-adjacent phases

下载: 全尺寸图片幻灯片

图 12 局部方格网络示意（单位：s）

Figure 12. Local grid-type network （unit: s）

下载: 全尺寸图片幻灯片

图 13 超路径网络中的标号定义

Figure 13. Definitions of labels in the hyperpath network

下载: 全尺寸图片幻灯片

图 14 起点38到终点37的最短路径和最优超路径

Figure 14. Shortest path and optimal hyperpath from origin 38 to destination 37

下载: 全尺寸图片幻灯片

图 15 网络流量分配

Figure 15. Traffic distribution in the network

下载: 全尺寸图片幻灯片

图 16 进口道(7,9)处转向选择对总旅行时间的影响

Figure 16. Total travel time versus the set of turns on entrance (7,9)

下载: 全尺寸图片幻灯片

图 17 进口道(19,20)转向选择对总旅行时间的影响

Figure 17. Total travel time versus the set of turns on entrance (19,20)

下载: 全尺寸图片幻灯片

表 1 信号配时变化对超路径集合元素的影响

Table 1. Influence of signal timing on hyperpath set

序号	交叉口	周期/s	相位 1/s	相位 2/s	相位 3/s	路径 1 时间/s	路径 2 时间/s	组合期望/s	最优超路径
1	A	110	40	50	20	131.4	149.3	121.6	A—B—C, A—D—C
1	C	80	60	20	0	131.4	149.3	121.6	A—B—C, A—D—C
2	A	150	80	20	50	202.6	127.1	130.1	A—D—C
2	C	120	30	90	0	202.6	127.1	130.1	A—D—C
3	A	47	12	15	20	124.4	138.8	125.1	A—B—C
3	C	110	95	15	0	124.4	138.8	125.1	A—B—C

下载: 导出CSV

表 2 参数定义

Table 2. Parameters definition

符号	含义
$G(N,A)$	有向网络图，其中N、A分别为网络中的节点集合、路段集合
${\varGamma ^ - }(i)$	流入节点 $i$ 的路段集合
${\varGamma ^ + }(i)$	流出节点 $i$ 的路段集合
j	节点 i 的下游节点标号
k	节点 j 的下游节点标号
s	终点
r	起点
${m_k}$	转向节点 k 的转向行为
H	超路径的路段集合
${M_{i,j}}$	进口道 $(i,j)$ 处，属于超路径的转向行为集合
$u_{i,j}$	进口道 $(i,j)$ 到终点的期望旅行时间
$p\{ (j,k)\|i\}$	由节点 i 转向路段 $j—k$ 时，节点 $j$ 被选择的概率
$p\{ k\|j\}$	由节点 j 转向节点 k 时，节点 k 被选择的概率
${P_{ {i,j} }}$	在节点i处，路段 $i—j$ 被选择的概率
$c_{i,j}$	路段 $i—j$ 的旅行时间
$\xi_{i,j,m_k}$	从节点 i 经过节点 j 转向节点 k 的期望延误时间
$w_{i,j}$	进口道为 $\left(i,j\right)$ 时，在节点 j 处的组合延误期望值
注： $\displaystyle \sum\nolimits_{(i,j) \in {\varGamma ^ + }(i)} {P_{{i,j} }} = 1$ .

下载: 导出CSV

表 3 路径选择概率

Table 3. Path choice probability

路径	路径走行路段	路径被选择概率
路径 1	38—7—9—10—14—17—18— 19—20—44—22—26—32—37	0.45
路径 2	38—7—9—13—16—17—18— 19—20—44—22—26—32—37	0.55

下载: 导出CSV

表 4 两种路径出行策略对比

Table 4. Comparison between two routing strategies

出行策略	路径	总旅行时间/s	总旅行时间降低率/%	总延误时间/s	总延误时间降低率/%
最短路	路径 1	1 010.0	317.0
超路径	路径 1 或路径 2	784.8	22.3	104.2	67.1

下载: 导出CSV

表 5 进口道(7,9)的相关参数

Table 5. Related parameters of entrance (7,9)

下游路段	转向行为	距终点的总旅行时间/s	路段旅行时间/s	延误时间/s	选择概率/%	组合延误时间/s	组合总旅行时间/s
9—10	左转	555.3	79.0	22.1	45	8.5	655.2
9—13	直行	582.3	52.0	19.2	55	8.5	655.2

下载: 导出CSV

表 6 进口道(19,20)的相关参数

Table 6. Related parameters of entrance (19,20)

下游路段	转向行为	距终点的总旅行时间/s	路段旅行时间/s	延误时间/s	选择概率/%	组合延误时间/s	组合总旅行时间/s
20—21	直转	283.6	13.0	31.1	13.8	0	307.6
20—44	右转	255.3	40.0	0	86.2	0	307.6

下载: 导出CSV

参考文献(23)

[1]	王芬芬. 合理的多路径算法研究[D]. 西安:长安大学,2017.
[2]	段征宇,雷曾翔,孙硕,等. 随机时变车辆路径问题的多目标鲁棒优化方法[J]. 西南交通大学学报,2019,54(3): 565-572. doi: 10.3969/j.issn.0258-2724.20170617 DUAN Zhengyu, LEI Zengxiang, SUN Shuo, et al. Multi-objective robust optimisation method for stochastic time-dependent vehicle routing problem[J]. Journal of Southwest Jiaotong University, 2019, 54(3): 565-572. doi: 10.3969/j.issn.0258-2724.20170617
[3]	HOFFMAN W, PAVLEY R. A method for the solution of the N th best path problem[J]. Journal of the ACM, 1959, 6(4): 506-514. doi: 10.1145/320998.321004
[4]	刘辉平. 基于路网的路径规划问题研究[D]. 上海: 华东师范大学,2018.
[5]	DROSOU M, PITOURA E. Search result diversification[J]. ACM SIGMOD Record, 2010, 39(1): 41-47. doi: 10.1145/1860702.1860709
[6]	YEN J Y. Finding the K shortest loopless paths in a network[J]. Management Science, 1971, 17(11): 712-716. doi: 10.1287/mnsc.17.11.712
[7]	TORRIERI D. Algorithms for finding an optimal set of short disjoint paths in a communication network[J]. IEEE Transactions on Communications, 1992, 40(11): 1698-1702. doi: 10.1109/26.179933
[8]	YALLOUZ J, ROTTENSTREICH O, BABARCZI P, et al. Minimum-weight link-disjoint node-“somewhat disjoint” paths[J]. ACM Transactions on Networking, 2018, 26(3): 1110-1122. doi: 10.1109/TNET.2018.2823912
[9]	GOMES T, CRAVEIRINHA J. Efficient calculation of the most reliable pair of link disjoint paths in telecommunication networks[J]. European Journal of Operational Research, 2007, 181(3): 1055-1064. doi: 10.1016/j.ejor.2006.03.005
[10]	GOMES T, MARTINS L, FERREIRA S, et al. Algorithms for determining a node-disjoint path pair visiting specified nodes[J]. Optical Switching and Networking, 2017, 23: 189-204. doi: 10.1016/j.osn.2016.05.002
[11]	倪明放,高石云,马峰,等. 多约束最短链路不相交路径的启发式算法[J]. 解放军理工大学学报(自然科学版),2013,14(1): 79-83. NI Mingfang, GAO Shiyun, MA Feng, et al. Heuristic algorithm for multi-constrained shortest link-disjoint paths[J]. Journal of PLA University of Science and Technology (Natural Science Edition), 2013, 14(1): 79-83.
[12]	LAI C N. Optimal node-disjoint paths in folded hypercubes[J]. Journal of Parallel and Distributed Computing, 2021, 147: 100-107. doi: 10.1016/j.jpdc.2020.09.005
[13]	周加全. 基于改进遗传算法路径规划问题的研究[J]. 微型电脑应用,2021,37(11): 1-3,8. doi: 10.3969/j.issn.1007-757X.2021.11.002 ZHOU Jiaquan. Research of path planning problem based on improved genetic algorithm[J]. Microcomputer Applications, 2021, 37(11): 1-3,8. doi: 10.3969/j.issn.1007-757X.2021.11.002
[14]	SPIESS H, FLORIAN M. Optimal strategies: a new assignment model for transit networks[J]. Transportation Research Part B: Methodological, 1989, 23(2): 83-102. doi: 10.1016/0191-2615(89)90034-9
[15]	BELL M G H. Hyperstar: a multi-path Astar algorithm for risk averse vehicle navigation[J]. Transportation Research Part B: Methodological, 2009, 43(1): 97-107. doi: 10.1016/j.trb.2008.05.010
[16]	MA J S, FUKUDA D, SCHMÖCKER J D. Faster hyperpath generating algorithms for vehicle navigation[J]. Transportmetrica A: Transport Science, 2013, 9(10): 925-948. doi: 10.1080/18128602.2012.719165
[17]	高明霞,贺国光. 考虑交叉口延误和转向限制的弧标号最短路径算法[J]. 兰州交通大学学报,2011,30(6): 111-114. doi: 10.3969/j.issn.1001-4373.2011.06.026 GAO Mingxia, HE Guoguang. An arc labeling algorithm for shortest path problem considering turn penalties and prohibitions at intersections[J]. Journal of Lanzhou Jiaotong University, 2011, 30(6): 111-114. doi: 10.3969/j.issn.1001-4373.2011.06.026
[18]	JU Z Y, DU M Q. Hyperpath searching algorithm considering delay at intersection and its application in CVIS for vehicle navigation[J]. Journal of Advanced Transportation, 2022, 2022: 2304097.1-2304097.15.
[19]	杜牧青,程琳. 考虑交叉口转向延误的最短路径拍卖算法[J]. 西南交通大学学报,2010,45(2): 249-254. doi: 10.3969/j.issn.0258-2724.2010.02.015 DU Muqing, CHENG Lin. Auction algorithm for shortest paths in road networks considering delays for intersection movements[J]. Journal of Southwest Jiaotong University, 2010, 45(2): 249-254. doi: 10.3969/j.issn.0258-2724.2010.02.015
[20]	ZILIASKOPOULOS A K, MAHMASSANI H S. A note on least time path computation considering delays and prohibitions for intersection movements[J]. Transportation Research Part B: Methodological, 1996, 30(5): 359-367. doi: 10.1016/0191-2615(96)00001-X
[21]	任刚. 交通管制下的交通分配算法研究[D]. 南京: 东南大学,2003.
[22]	卢顺达,程琳,邵娟. 转向延误和路段容量双约束下的用户均衡模型及算法研究[J]. 道路交通与安全,2017,17(6): 19-24. LU Shunda, CHENG Lin, SHAO Juan. Research on user equilibrium model and algorithm with turning delays and link capacity[J]. Journal of Transportation Engineering, 2017, 17(6): 19-24.
[23]	李晓红. 城市干线交通信号协调优化控制及仿真[D]. 大连: 大连理工大学,2007.

施引文献

期刊类型引用(11)

1.	郝保磊，张笑慰，许钦华，樊刘杨，张健，陈瑞锋，李奇. 变流器气动噪声分析与噪声控制研究. 声学技术. 2024(02): 253-259 . 百度学术
2.	温涛，王琥，彭宣霖，夏亮. 多层SVR选择机制在变流器噪声预测的应用. 噪声与振动控制. 2023(04): 21-26+186 . 百度学术
3.	丁杰，熊英，殷仁述. 动车组牵引变流器冷却风机的噪声异常分析. 噪声与振动控制. 2023(04): 174-180 . 百度学术
4.	丁杰. 地铁车辆辅助变流器的噪声仿真及测试. 华东交通大学学报. 2022(01): 99-107 . 百度学术
5.	张笑慰，郝保磊，王云鹏，范永翔，陈瑞锋，李奇. 地铁车辆辅助变流柜噪声试验研究. 声学技术. 2022(01): 96-102 . 百度学术
6.	丁杰. 地铁车辆整车及设备的噪声测试与指标分析. 机车电传动. 2022(02): 48-54 . 百度学术
7.	袁磊，冉均均. 基于CLES模型的风扇气动噪声数值模拟分析方法. 微型电脑应用. 2022(05): 57-61 . 百度学术
8.	丁杰. 不等距叶轮的永磁电机噪声测试及特性分析. 微电机. 2022(07): 30-36 . 百度学术
9.	宋郭蒙，王雄，黄南，陈燕平，窦泽春，吴智勇. 轨道交通车辆风冷散热器传热优化研究. 中南大学学报(自然科学版). 2021(01): 267-275 . 百度学术
10.	丁杰，尹亮. 地铁辅助变流器的噪声分析及控制. 湖南文理学院学报(自然科学版). 2021(03): 41-48 . 百度学术
11.	丁杰，尹亮，刘奇元. 地铁车辆牵引变流器的噪声测试及仿真分析. 石家庄铁道大学学报(自然科学版). 2021(03): 74-80 . 百度学术

其他类型引用(4)

附加材料(0)

访问统计

点击查看大图

图(17) / 表(6)

计量

文章访问数: 263
HTML全文浏览量: 81
PDF下载量: 29
被引次数: 15

1. 问题描述
1.1 参数和变量定义
1.2 物流服务供需方满意度
2. 模型构建
2.1 第1阶段优化模型
2.2 第2阶段优化模型
3. 模型求解
3.1 第1阶段模型求解
3.2 第2阶段模型求解
4. 算例分析
5. 结　论

一种基于交叉口信号延误的超路径规划方法

doi: 10.3969/j.issn.0258-2724.20220387

作者简介: 杜牧青（1986—），男，副教授，博士，研究方向为交通运输规划与管理，E-mail：dumqhhu@hhu.edu.cn

计量

出版历程

Hyperpath Searching Algorithm Method Based on Signal Delay at Intersections

1. 问题描述

1.1 参数和变量定义

1.2 物流服务供需方满意度

2. 模型构建

2.1 第1阶段优化模型

2.2 第2阶段优化模型

3. 模型求解

3.1 第1阶段模型求解

3.2 第2阶段模型求解

4. 算例分析

5. 结 论

期刊类型引用(11)

其他类型引用(4)

计量

出版历程

目录

1. 问题描述

1.1 参数和变量定义

1.2 物流服务供需方满意度

2. 模型构建

2.1 第1阶段优化模型

2.2 第2阶段优化模型

3. 模型求解

3.1 第1阶段模型求解

3.2 第2阶段模型求解

4. 算例分析

5. 结 论

作者简介:
杜牧青（1986—），男，副教授，博士，研究方向为交通运输规划与管理，E-mail：dumqhhu@hhu.edu.cn

5. 结　论

5. 结　论