删除或更新信息,请邮件至freekaoyan#163.com(#换成@)

随机时间依赖路网中危险品运输路径多准则优化

本站小编 哈尔滨工业大学/2019-10-24

随机时间依赖路网中危险品运输路径多准则优化

代存杰1,2,李引珍2,马昌喜2,柴获1,2

(1.兰州交通大学 机电技术研究所, 兰州 730070; 2.兰州交通大学 交通运输学院, 兰州 730070)



摘要:

为实现动态路网中的危险品运输路径优化,以期为运输商的路径选择提供决策支持,分析了运输网络的随机时间依赖(STD)特征,对分段连续时间区间内各路段的行程时间和受影响人数进行曲线拟合.考虑到达时间窗的约束,以行程时间和运输风险的随机属性值为优化准则,建立0-1整数规划模型.结合STD网络的FIFO性质设计了两阶段多维标号修正算法,得到不同出发时刻以给定置信水平满足时间窗约束的非支配路径集合,并提出准则权重和阈值支配方法,实现计算效率和求解质量的均衡.研究结果表明:危险品在STD路网中的行程时间和运输风险与到达时间窗的设置和出发时刻的选取有关;生成的非支配路径取决于出发时刻和运输商的选择偏好,非支配路径的数量取决于支配阈值的大小;不同类型运输商可根据准时到达置信水平来选择出发时刻与运输路径的最优组合.

关键词:  危险品运输  多准则优化  随机时间依赖  时间窗约束  多维标号修正算法

DOI:10.11918/j.issn.0367-6234.201704050

分类号:U491

文献标识码:A

基金项目:国家自然科学基金(8,9); 兰州交通大学优秀科研团队资助计划(201604)



Multi-criterion path optimization for hazardous materials transportation in stochastic time dependent road networks

DAI Cunjie1,2,LI Yinzhen2,MA Changxi2,CHAI Huo1,2

(1. Mechatronics T&R Institute, Lanzhou Jiaotong University, Lanzhou 730070, China; 2. School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, China)

Abstract:

To optimize the hazardous materials (hazmat) transportation paths in dynamic road networks and make a decision on path selection for carriers, the stochastic time dependent (STD) characteristics of transport networks were analyzed, the travel time and the number of people affected around each link were fitted in piece-wise continuous time interval. The 0-1 integer programming model was formulated by taking the arrival time window as a constraint, and taking the stochastic attribute values of travel time and transport risk as optimization criteria. A two-stage multi-dimensional label correcting algorithm was designed with First-In-First-Out property of the STD road networks, and the non-dominated paths were generated at different departure time to meet the time window constraint with predetermined confidence level. The criterion-weight and threshold-dominate methods were proposed to balance computational efficiency and accuracy. Research results indicate that the travel time and transport risk of hazmat in STD road networks are related to the setting of arrival time window and the selection of departure time. The non-dominated path depends on the departure time and the choice of carrier's preference, and the amount of non-dominated paths depends on the dominated threshold value. Different types of carriers can choose the optimal combination of departure time and transportation path according to the confidence level of arriving on time.

Key words:  hazardous materials transportation  multi-criterion optimization  stochastic time dependent  time window constraint  multidimensional label correcting algorithm


代存杰, 李引珍, 马昌喜, 柴获. 随机时间依赖路网中危险品运输路径多准则优化[J]. 哈尔滨工业大学学报, 2018, 50(3): 156-164. DOI: 10.11918/j.issn.0367-6234.201704050.
DAI Cunjie, LI Yinzhen, MA Changxi, CHAI Huo. Multi-criterion path optimization for hazardous materials transportation in stochastic time dependent road networks[J]. Journal of Harbin Institute of Technology, 2018, 50(3): 156-164. DOI: 10.11918/j.issn.0367-6234.201704050.
基金项目 国家自然科学基金(51408288, 61563029);兰州交通大学优秀科研团队资助计划(201604) 作者简介 代存杰(1982—), 男, 博士研究生;
李引珍(1963—), 男, 教授, 博士生导师 通信作者 李引珍, liyz01@mail.lzjtu.cn 文章历史 收稿日期: 2017-04-11



Contents            -->Abstract            Full text            Figures/Tables            PDF


随机时间依赖路网中危险品运输路径多准则优化
代存杰1,2, 李引珍2, 马昌喜2, 柴获1,2    
1. 兰州交通大学 机电技术研究所, 兰州 730070;
2. 兰州交通大学 交通运输学院, 兰州 730070

收稿日期: 2017-04-11
基金项目: 国家自然科学基金(51408288, 61563029);兰州交通大学优秀科研团队资助计划(201604)
作者简介: 代存杰(1982—), 男, 博士研究生;
李引珍(1963—), 男, 教授, 博士生导师
通信作者: 李引珍, liyz01@mail.lzjtu.cn


摘要: 为实现动态路网中的危险品运输路径优化,以期为运输商的路径选择提供决策支持,分析了运输网络的随机时间依赖(STD)特征,对分段连续时间区间内各路段的行程时间和受影响人数进行曲线拟合.考虑到达时间窗的约束,以行程时间和运输风险的随机属性值为优化准则,建立0-1整数规划模型.结合STD网络的FIFO性质设计了两阶段多维标号修正算法,得到不同出发时刻以给定置信水平满足时间窗约束的非支配路径集合,并提出准则权重和阈值支配方法,实现计算效率和求解质量的均衡.研究结果表明:危险品在STD路网中的行程时间和运输风险与到达时间窗的设置和出发时刻的选取有关;生成的非支配路径取决于出发时刻和运输商的选择偏好,非支配路径的数量取决于支配阈值的大小;不同类型运输商可根据准时到达置信水平来选择出发时刻与运输路径的最优组合.
关键词: 危险品运输    多准则优化    随机时间依赖    时间窗约束    多维标号修正算法    
Multi-criterion path optimization for hazardous materials transportation in stochastic time dependent road networks
DAI Cunjie1,2, LI Yinzhen2, MA Changxi2, CHAI Huo1,2    
1. Mechatronics T&R Institute, Lanzhou Jiaotong University, Lanzhou 730070, China;
2. School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, China


Abstract: To optimize the hazardous materials (hazmat) transportation paths in dynamic road networks and make a decision on path selection for carriers, the stochastic time dependent (STD) characteristics of transport networks were analyzed, the travel time and the number of people affected around each link were fitted in piece-wise continuous time interval. The 0-1 integer programming model was formulated by taking the arrival time window as a constraint, and taking the stochastic attribute values of travel time and transport risk as optimization criteria. A two-stage multi-dimensional label correcting algorithm was designed with First-In-First-Out property of the STD road networks, and the non-dominated paths were generated at different departure time to meet the time window constraint with predetermined confidence level. The criterion-weight and threshold-dominate methods were proposed to balance computational efficiency and accuracy. Research results indicate that the travel time and transport risk of hazmat in STD road networks are related to the setting of arrival time window and the selection of departure time. The non-dominated path depends on the departure time and the choice of carrier's preference, and the amount of non-dominated paths depends on the dominated threshold value. Different types of carriers can choose the optimal combination of departure time and transportation path according to the confidence level of arriving on time.
Key words: hazardous materials transportation    multi-criterion optimization    stochastic time dependent    time window constraint    multidimensional label correcting algorithm    
随着各类危险化学品的社会需求量持续增加,越来越多的危险品运输车辆在路网内行驶,形成流动的危险源,危及社会公共安全.在城市非爆炸品类的危险品事故中,由运输原因造成的事故数量占32%[1],对危险品运输路径优化是降低运输风险的重要途径之一[2].对危险品运输风险评价是实施路径优化的前提,诸多学者对此进行了研究并建立数学模型[3].其中传统风险模型以路段事故发生概率与潜在受影响人数的乘积作为路段风险值,该模型满足经典风险理论和“运输风险评价定理”,应用最为广泛[4].

在危险品运输网络中,不同路径上的行程时间和运输风险存在差异,即使在同一路径上并采用相同车辆在不同时段经由运输,由于交通流量和路段附近人数的变化,车辆行驶时间和运输风险都会改变,使运输时间和运输风险具有时间依赖特征.在实际运输过程中,各路段上的行程时间并不能准确预测,通常设为服从具有某种随机分布特征的变量;同理,各路段附近的人口密度也可采用符合某种随机分布特征的函数表示[5].因此,危险品是在具有随机时间依赖(stochastic time dependent, STD)特征的路网内运输,分析路径的STD特征,对降低运输风险和减少运输时间有重要现实意义.

危险品运输商在选择路径时需要综合考虑运输时间、运输费用以及运输风险大小,危险品的运输路径优化问题可归约为多准则优化问题,需结合路网的STD特征进行研究.文献[3]首次对STD路网中的路径优化问题进行了研究;文献[6-7]分别对时间依赖路网中危险品运输路径优化问题作了研究;文献[8]将危险品运输风险定义为具有时间依赖特征的模糊随机变量,建立了优化模型并提出求解算法;文献[9]对STD路网中的危险品运输问题提出一种逼近预期路径长度的启发式方法,并由[10]扩展到多准则路径优化问题;文献[11]对STD条件下危险品最短路问题进行了研究;文献[12]研究了时间依赖路网中危险品运输路径的双准则优化问题.既有研究通常将路径随机属性的数学期望作为选择标准,而较少地考虑随机属性的方差对决策者的影响.计算随机属性的方差,可反映计算结果与期望值的偏离程度,以满足不同类型决策者的选择需求.针对STD路网内的危险品运输路径优化问题,计算各优化准则对应的随机属性的方差,可对各随机属性的稳定性和运输路径的可靠性进行分析.

在危险品运输过程中设置到达时间窗约束,既可满足企业的无库存生产需求,也可避免因重复装卸或再次存储带来的额外风险.文献[13]对静态路网中有时间窗约束的危险品运输路径优化问题进行了研究;文献[14]研究了STD路网中的危险品运输路径选择问题,建立有时间窗约束的多目标模型;文献[15]考虑时变条件对危险品运输事故率的影响,建立有运输时间约束的路径决策模型.既有研究中所建立的模型以到达时间窗或运输时间作为约束条件,但未界定运输网络的STD属性,也未分析到达时间窗的改变对运输路径的影响.

本文将研究STD路网内的危险品运输路径多准则优化问题,在分析路径STD特征的基础上,考虑到达时间窗约束,分别以运输时间、运输风险的期望值和标准差为优化准则建立数学模型.设计两阶段多维标号修正算法,计算在不同时刻出发并以给定置信水平满足时间窗约束的非支配路径集合,为运输商在不同准则下的路径选择提供决策支持.

1 问题描述与分析危险品在无向路网G=(N, A, I)内运输,N为节点集合,ijG中节点,iN, jNijA为路段集合,(i, j)∈AG中路段,lij为(i, j)的长度,ρij, jk为(i, j)和(j, k)的行程时间相关系数;I={I1, …, Ik}为分段连续的时间段集合;Γ(i)为iG中的邻接节点集合;oN为起点,dN为终点,且odpodtoto时刻从o出发到d的路径,toIcijtoto时刻从o出发在(i, j)上的行程时间,ti为到达i的时刻;xijto为决策变量,当(i, j)∈podto时取值为1,否则为0;x为多个xijto组成的向量.

1.1 行程时间分析在实际交通网络中,影响人们日常出行时间变化的主要因素是道路拥挤或交通管制等,这些因素导致各路段上的行程时间呈周期性变化,可采用正态分布、对数正态分布或移位正态分布等函数来描述变化特征[16].考虑各路段行程时间分布曲线的非对称性,以及观察错误或样本缺乏而导致的估计分布不合理,可采用截断对数正态分布来描述路段行程时间.通过设置截断边界使概率密度曲线与实际分布曲线的贴近度更高,并可排除对数正态分布中右长尾产生的不合理值[17].采用截断对数正态分布模型描述分段连续时间区间内的路段行程时间,可保证行程时间的连续性,使运输网络满足先进先出(first in first out, FIFO)性质[18].

当路段行程时间服从截断对数正态分布时,(i, j)上的行程时间cij的概率密度函数为

$f\left( {{c_{ij}};{\mu _{ij}},{\sigma _{ij}},{a_{ij}},{b_{ij}}} \right) = \frac{{ - {{\left( {{\eta _{ij}}} \right)}^2}}}{{2{\sigma _{ij}}\sqrt {2{\rm{ \mathsf{ π} }}} {c_{ij}}\left( {\mathit{\Phi }\left( {{\alpha _{ij}}} \right) - \mathit{\Phi }\left( {{\beta _{ij}}} \right)} \right)}}.$ (1)

式中:μijσij分别为ln(cij)的位置参数和尺度参数;aij为(i, j)上自由流时的行程时间,bij为(i, j)上最大行程时间,通常设bij=5aij[19]αijβijηij为临时变量,${\alpha _{ij}} = {\rm{ln}}\left( {\frac{{{a_{ij}}}}{{{\mu _{ij}}}}} \right){\sigma _{ij}}^{-1}$${\beta _{ij}} = {\rm{ln}}\left( {\frac{{{b_{ij}}}}{{{\mu _{ij}}}}} \right){\sigma _{ij}}^{-1}$${\eta _{ij}} = {\rm{ln}}\left( {\frac{{{c_{ij}}}}{{{\mu _{ij}}}}} \right){\sigma _{ij}}^{-1}$Φ(·)为标准正态累积分布函数.

cij服从标准对数正态分布时,cij的期望值E[cij]和方差V[cij]为

$E\left[ {{c_{ij}}} \right] = {\mu _{ij}} + \exp \left( {0.5\sigma _{ij}^2} \right),$ (2)

$V\left[ {{c_{ij}}} \right] = \mu _{ij}^2 + \exp \left( {\sigma _{ij}^2} \right)\left[ {\exp \left( {\sigma _{ij}^2} \right) - 1} \right].$ (3)

在设定cij的左右截断边界后,即aijcijbij,对cij修正后的期望值mij和标准差vij分别为

${m_{ij}} = E\left[ {{c_{ij}}} \right]\frac{{\mathit{\Phi }\left( {{\beta _{ij}} - {\sigma _{ij}}} \right) - \mathit{\Phi }\left( {{\alpha _{ij}} - {\sigma _{ij}}} \right)}}{{\mathit{\Phi }\left( {{\beta _{ij}}} \right) - \mathit{\Phi }\left( {{\alpha _{ij}}} \right)}},$ (4)

$\begin{array}{*{20}{c}}{v_{ij}^2 = {{\left( {E\left[ {{c_{ij}}} \right]} \right)}^2}\left\{ \begin{array}{l}\frac{{\mathit{\Phi }\left( {{\beta _{ij}} - 2{\sigma _{ij}}} \right) - \mathit{\Phi }\left( {{\alpha _{ij}} - 2{\sigma _{ij}}} \right)}}{{\mathit{\Phi }\left( {{\beta _{ij}}} \right) - \mathit{\Phi }\left( {{\alpha _{ij}}} \right)}} - \\{\left[ {\frac{{\mathit{\Phi }\left( {{\beta _{ij}} - {\sigma _{ij}}} \right) - \mathit{\Phi }\left( {{\alpha _{ij}} - {\sigma _{ij}}} \right)}}{{\mathit{\Phi }\left( {{\beta _{ij}}} \right) - \mathit{\Phi }\left( {{\alpha _{ij}}} \right)}}} \right]^2}\end{array} \right\} + }\\{V\left[ {{c_{ij}}} \right]\frac{{\mathit{\Phi }\left( {{\beta _{ij}} - 2{\sigma _{ij}}} \right) - \mathit{\Phi }\left( {{\alpha _{ij}} - 2{\sigma _{ij}}} \right)}}{{\mathit{\Phi }\left( {{\beta _{ij}}} \right) - \mathit{\Phi }\left( {{\alpha _{ij}}} \right)}}.}\end{array}$ (5)

1.2 运输风险分析采用传统风险评价模型计算各路段上的风险值,设(i, j)上可能发生事故的概率为rij,潜在受影响人数为Pij,则(i, j)上的风险值zij

${z_{ij}} = {r_{ij}}{P_{ij}}.$ (6)

若不考虑道路等级差异,rij的取值可借鉴文献[20]中的取值方法,用(i, j)的长度数值乘以10-6来近似表示(i, j)上的事故发生概率.在实际运输环境中,rij的值与车辆通过(i, j)的时间段有关,通常认为在夜间或交通高峰时段,rij的取值较大[7].

在实际运输网络中,由于各路段附近的用地类型、公共服务设施等存在差异,致使人口密度分布不同.对于同一路段,不同时段的人口变化情况具有一定的规律性[21].将Pij的变化分布曲线按照峰谷分布划分,采用移位对数正态分布函数分段拟合,可得Pij的估计数据,其计算表达式为

${P_{ij}} = {\gamma _{ij}} + \exp \left( {{\omega _{ij}} + {\chi _{ij}}{\delta _{ij}}} \right).$ (7)

式中:γijPij的最小取值(不变人口数量);ωijPij中波动人数取自然对数后的期望值;δijPij中波动人数取自然对数后的标准差;χij为服从标准正态分布的随机变量.

由式(6)、(7)可计算zij的期望值εij和方差ψij分别为

${\varepsilon _{ij}} = E\left[ {{z_{ij}}} \right] = {\gamma _{ij}}{r_{ij}} + \exp \left( {{\omega _{ij}} + 0.5{\delta _{ij}}^2} \right){r_{ij}},$ (8)

${\psi _{ij}} = V\left[ {{z_{ij}}} \right] = \exp \left( {2{\omega _{ij}} + {\delta _{ij}}^2} \right)\left( {\exp \left( {{\delta _{ij}}^2} \right) - 1} \right){r_{ij}}^2.$ (9)

2 模型建立与分析在STD路网内运输危险品时,还需考虑运输网络的其他性质,给出如下假设:1)运输网络为无向图结构,各路段均满足FIFO性质;2)运输车辆选择最短路径行驶,不存在绕行或途中停靠现象;3)在不同的时间段内,各路段附近人口密度服从独立的随机分布.

基于问题描述和条件假设,podto上的行程时间T(podto)和累积运输风险Z(podto)分别为

$T\left( {p_{od}^{{t_o}}} \right) = \sum\limits_{\left( {i,j} \right) \in A} {\eta _{ij}^{{t_o}}x_{ij}^{{t_o}}} ,$ (10)

$Z\left( {p_{od}^{{t_o}}} \right) = \sum\limits_{\left( {i,j} \right) \in A} {\zeta _{ij}^{{t_o}}x_{ij}^{{t_o}}} .$ (11)

式中:ηijtoζijto分别为podto中(i, j)上行程时间和运输风险,ηijtoζijto为随机变量.

T(podto)的期望值fe(x)和标准差fv(x)、Z(podto)的期望值ge(x)和标准差gv(x)分别为

${f_{\rm{e}}}\left( \mathit{\boldsymbol{x}} \right) = E\left[ {T\left( {p_{od}^{{t_o}}} \right)} \right] = \sum\limits_{\left( {i,j} \right) \in A} {\iota _{ij}^{{t_o}}x_{ij}^{{t_o}}} ,$ (12)

$\begin{array}{l}{f_{\rm{v}}}\left( \mathit{\boldsymbol{x}} \right) = \sqrt {V\left[ {T\left( {p_{od}^{{t_o}}} \right)} \right]} = \\\;\;\;\;\;\;\;\;\;\sqrt {\sum\limits_{\left( {i,j} \right) \in A} {\nu _{ij}^{{t_o}}{}^2x_{ij}^{{t_o}}} + \sum\limits_{\left( {i,j} \right) \in A,\left( {j,k} \right) \in A} {\nu _{ij}^{{t_o}}x_{ij}^{{t_o}}\nu _{jk}^{{t_o}}x_{jk}^{{t_o}}{\rho _{ij,jk}}} } ,\end{array}$ (13)

${g_{\rm{e}}}\left( \mathit{\boldsymbol{x}} \right) = E\left[ {Z\left( {p_{od}^{{t_o}}} \right)} \right] = \sum\limits_{\left( {i,j} \right) \in A} {\zeta _{ij}^{{t_o}}x_{ij}^{{t_o}}} ,$ (14)

${g_{\rm{v}}}\left( \mathit{\boldsymbol{x}} \right) = \sqrt {V\left[ {Z\left( {p_{od}^{{t_o}}} \right)} \right]} = \sqrt {\sum\limits_{\left( {i,j} \right) \in A} {\vartheta _{ij}^{{t_o}}x_{ij}^{{t_o}}} } .$ (15)

式中:ιijtoνijtoζijto?ijto分别为podto中(i, j)上mijvijεijψij的对应值.

给定到达时间窗为[Te, Tl],建立STD路网内有时间窗约束的多准则路径优化模型为

$F\left( x \right) = \left( {\min {f_{\rm{e}}}\left( \mathit{\boldsymbol{x}} \right),\min {f_{\rm{v}}}\left( \mathit{\boldsymbol{x}} \right),\min {g_{\rm{e}}}\left( \mathit{\boldsymbol{x}} \right),\min {g_{\rm{v}}}\left( \mathit{\boldsymbol{x}} \right)} \right),$ (16)

${\rm{s}}.{\rm{t}}.\sum\limits_{\left( {i,j} \right) \in A} {x_{ij}^{{t_o}}} - \sum\limits_{\left( {j,k} \right) \in A} {x_{jk}^{{t_o}}} = \left\{ \begin{array}{l}\;\;1,j = o;\\\;\;0,j \ne o\mathit{\& j} \ne \mathit{d};\\ - 1,j = d.\end{array} \right.$ (17)

${t_o} + T\left( {p_{od}^{{t_o}}} \right) \in \left[ {{T_e},{T_l}} \right].$ (18)

$x_{ij}^{{t_o}} \in \left\{ {0,1} \right\}.$ (19)

式(16)为不同优化准则的目标函数值构成的决策向量;式(17)为路径的无环约束;式(18)为到达时间窗约束;式(19)为决策变量取值空间.

2.1 路网的STD特征分析危险品在有时间窗约束的STD路网内运输,选择不同的出发时间,既会影响车辆行程时间,也会使运输风险发生变化.因此,计算不同出发时刻对应的行程时间是运输路径优化的必要条件,首先给出STD路网的相关命题.

命题1?在STD的FIFO路网中,若podto为最短路径,则podto中任意i(io, id)对应的子路径poito也为最短路径.

证明?假设podto为最短路径,在to时刻从o出发到达i的时间为ti,到达d的时间为td.若poito非最短路径,则存在poito'(poito'poito),到达i的时间为ti*,有ti* < ti.则在ti*i出发,到达d的时间为td*.根据路网性质有ti*+T(pidtd*)=td* < ti+T(pidti)=td,与podto为最短路径矛盾.

命题2?在STD的FIFO路网中,对于任意节点ij之间的最短路径pijti,到达时间tj是关于出发时间ti的非减函数.

证明?任意节点ij的行程时间关系式为tj=ti+T(pijti),T(pijti)为最短行程时间.对于任意出发时刻ti,当ti>ti时,有tj=ti+T(pijti).因为路网满足FIFO性质,所以有tjtj,可得tj是关于ti的非减函数.

因为路径行程时间具有随机性,设置准时到达置信水平$φ$(0≤$φ$≤1)来满足时间窗约束,表达式为

$\mathit{Pr}\left( {{T_e} \le {t_o} + T\left( {p_{od}^{{t_o}}} \right) \le {T_l}} \right) \le \varphi .$ (20)

对于给定的$φ$,至少存在一个时刻T$φ$,使Pr(TeT$φ$Tl)=$φ$.在[Te, Tl]内,T$φ$取值并不唯一.

命题3?当T$φ$给定时(T$φ$∈[Te, Tl]),至少存在一个出发时间to和相应最短时间T(podto),使T$φ$=to+T(podto);反之则不一定成立.

证明?由路网性质和命题2可知,对于任意出发时刻to,因为T(podto)非负,且to+T(podto)是关于to非减的.当toT$φ$时,对于[Te, Tl]内的给定值T$φ$,总存在to使T$φ$=to+T(podto)成立.相反,对于给定的任意to及其对应的最短行程时间T(podto),结合假设条件(2)可知,to+T(podto)的值不一定在[Te, Tl]之内.

$φ$值给定后,可利用累积分布函数计算路径行程时间的近似值[22]. $φ$T$φ$的关系式为

$\mathit{\Phi }\left( {\frac{{\left( {{T_\varphi } - {t_o}} \right) - {f_{\rm{e}}}\left( \mathit{\boldsymbol{x}} \right)}}{{\sqrt {{f_{\rm{v}}}\left( \mathit{\boldsymbol{x}} \right)} }}} \right) = \varphi .$ (21)

利用累积分布函数的逆函数Φ-1(·),计算出发时间to的表达式为

${t_o} = {T_\varphi } - {\mathit{\Phi }^{ - 1}}\left( \varphi \right){f_{\rm{v}}}\left( \mathit{\boldsymbol{x}} \right) - {f_{\rm{e}}}\left( \mathit{\boldsymbol{x}} \right).$ (22)

因此,在to时刻出发并以置信水平$φ$准时到达的路径行程时间T(podto)为

$T\left( {p_{od}^{{t_o}}} \right) = {T_\varphi } - {t_o} = {\mathit{\Phi }^{ - 1}}\left( \varphi \right){f_{\rm{v}}}\left( \mathit{\boldsymbol{x}} \right) - {f_{\rm{e}}}\left( \mathit{\boldsymbol{x}} \right).$ (23)

同理,在to时刻出发,从ij的行程时间为

$c_{ij}^{{t_o}} = T\left( {p_{oj}^{{t_o}}} \right) - T\left( {p_{oi}^{{t_o}}} \right).$ (24)

2.2 模型特征分析对运输路径进行多准则优化,需确定路径间的优劣关系,可根据不同优化准则的目标值采用支配关系比较进行确定[23].

通过路径间的支配关系比较,可在计算过程中决定路径的取舍.当路网规模较大或优化准则数量较多时,完全列出非支配路径并不可取.本文设计准则权重和阈值支配方法,既体现运输商对优化准则的偏好,也可避免对非支配路径的完全枚举.假设各优化准则以取小为优,准则m对应目标函数为hm(·),各准则占优权重的计算过程如下.

步骤1?根据运输商的路径选择偏好,为每个准则m设定权重πm$\sum\limits_{m = 1}^M {{\pi _m} = 1} $M为优化准则总数.

步骤2?设pxpy为待比较路径,w(px)和w(py)分别为pxpy的占优权重,初始值为0.

步骤3?对于任意准则m,若hm(px) < hm(py),则w(px)=w(px)+πm;若hm(px)=hm(py),令w(px)=w(px)+πmw(py)=w(py)+πm;否则w(py)=w(py)+πm.

得到w(px)和w(py)的值后,设置支配阈值Δ,判定pxpy的支配关系.若w(px)-w(py)≥Δ,则称px支配py;若w(py)-w(px)≥Δ,则称py支配px;若|w(px)-w(py)| < Δ,称pypx相互支配.

设计准则权重和阈值支配方法,可实现求解质量和求解效率的有效均衡.

3 求解算法设计由命题1和命题2可知,静态网络中的Bellman最优原理同样适用于STD的FIFO网络.在FIFO网络中,可利用静态网络中的最短路径算法来求解动态网络的最短路径[24].本文设计两阶段多维标号修正算法对模型求解,首先根据各路段的随机行程时间、时间窗[Te, Tl]和准时到达置信水平$φ$来计算出发时间;然后生成关于行程时间和运输风险的非支配路径集合.

命题4?在STD的FIFO路网中,若给定[Te, Tl]和$φ$,则一定存在从o出发的最迟时刻?o,满足Pr(?o+T(pod?o)≤Tl)≥$φ$,且当$\forall $to>?o时,Pr(to+T(podto)>Tl)>$φ$不成立.

证明?假设?o不存在,即对于$\forall $toI,有Pr(to+T(podto)≤Tl)≥$φ$恒成立.则对于任意$φ$,若Pr(to+T(podto)>Tl)=1,则Pr(to+T(podto)≤Tl)≥$φ$恒成立.所以,假设成立的充分条件是在任意to,有to+T(podto)≤Tl.由命题2可知,to+T(podto)是关于to的非减函数,且T(podto)>0(od).因此,当toTl时,一定存在最迟出发时间?o使?o+T(pod?o)=Tl,当to>?o时,to+T(podto)>Tl,与假设矛盾.

根据命题4,?o的计算步骤如下.

步骤1?网络初始化,给定[Te, Tl]和$φ$,设置出发时间区间[λo, ?o](λo < < ?o)和终止判断值${\bar \omega }$,初始化标号队列为空.

步骤2?令出发时间κ=0.5(λo+?o),将起点o从队尾插入队列,并令to=κ;路网中其他节点i标号为ti=∞(iN\{o}).

步骤3?从队头取节点i,并从队列中删除i.根据式(21)、(22)计算jΓ(i)的到达时间tj,与j的原标号tj比较,若tjtj,更新j的标号为tj;若j已入过队列中,则将j从队头插入,否则从队尾插入.

步骤4?若队列为空且td≠∞,根据到达时间td判断to是否为最迟的出发时间:1)若tdTl?oλo>${\bar \omega }$,说明存在大于κ的最迟出发时间,令λo=κ,转步骤2;2)若tdTl?oλo${\bar \omega }$,可认为κ为最迟出发时间,搜索终止,输出κ;3)若td>Tl?oλo${\bar \omega }$,搜索终止,输出?o;4)若td>Tl,说明κ大于最迟出发时间,令?o=κ,转步骤2.若出发时间to小于?o,可能存在多条有效路径podto,能在Tl前到达d.同理,to应有一个下界λo,若要满足到达时间窗约束,to不能早于λo.

命题5?在STD的FIFO路网中,给定[Te, Tl]和$φ$,若podto为最短路径,则一定有最早出发时间λo,满足Pr(λo+T(podλo)≥Te)$φ$,且to < λo时,Pr(λo+T(podλo)≥Te)≥$φ$不成立.

证明?证明过程与命题4类似,不再赘述.

to < λo时,满足Pr(to+T(podto)≥Te)≥$φ$的路径可能存在多条,但这些路径只是可行路径,一定不是最短路径.

推论1?在具有STD属性的FIFO路网中,若存在最短路径podto,则对于给定的[Te, Tl]和$φ$,一定存在对应的出发时间窗[λo, ?o].

得到?o后,令to=?o,设置调整步长λ,使to=toλ,可计算不同出发时刻对应的路径,并计算各路径运输风险的期望值和标准差,构成多准则决策空间,以满足运输商的路径选择需求.

在多维标号修正算法中,$φ$ei$φ$viγeiγvi分别用来记录当前路径中从o到任意ife(x)、fv(x)、ge(x)和gv(x)的临时标号,$\ell$(i)为当前路径中i的前驱节点编号,?(i)标识i是否被访问.路径生成步骤为6步.

步骤1?网络初始化,起点o的标号为($φ$eo=0, $φ$vo=0, γeo=0, γvo=0, to=0, $\ell$(o)=-1),将o插入队列,?(o)=1;其他i(iN\{o})标号为($φ$ei=0, $φ$vi=0, γei=0, γvi=0, ti=∞, $\ell$(i)=-1),?(i)=0.

步骤2?根据[Te, Tl]计算?o,设置各准则权重πm和支配阈值Δ,初始化节点队列和路径链表为空.

步骤3?从队列中取头节点i,并从队列中删除.取节点jΓ(i),扩展当前路径poito,生成路径pojto.由式(12)~(15), (21)、(22)计算节点j的多维标号,令$\ell$(j)=i,?(j)=1,将j存入路径链表.

步骤4?根据πmΔ,将pojto与路径链表中以j为终点的所有pojto进行比较,分3种情况:1)若pojto支配pojto,则从队列、链表中删除pojto及其子路径,并将pojto存入链表和队列;若节点j已在队列中,将j从队头插入,否则将j从队尾插入;2)若pojtopojto支配,则删除pojto;3)若pojtopojto相互支配,将pojto存入链表;若j已入过队列,将j从队头插入,否则插入队尾.

步骤5?如果队列非空,转步骤3;否则检查链表中节点d对应的各podto的属性值,删除td不在[Te, Tl]内的路径,剩余路径构成非支配路径集合.

步骤6?调整to的取值,执行步骤1~5,直至无可行路径生成,得到满足[Te, Tl]约束的路径集合.

4 实验及结果分析某市部分区域的危险品运输网络结构及路段长度lij见图 1,并设危险品运输事故发生后波及范围的半径为1.0 km.

Figure 1
图 1 路网结构图(km) Figure 1 Structure of road networks(km)


各路段可双向通行,在同一时段内不同方向上的行程时间和路段附近受影响人数相同.按照实际交通流量获取各路段在整个时间区间内行程时间的变化曲线,根据峰谷分布将时间区间I分为6段, 分别定义为I1= (00:00, 05:30],I2= (05:30, 10:30],I3= (10:30, 14:30],I4= (14:30, 17:00],I5= (17:00, 21:30],I6= (21:30, 24:00].基于各路段上的行程时间变化曲线,对不同时段内的行程时间数据整理,利用截断对数正态分布函数和最小二乘法进行数据拟合,得到各时段内cij的相关参数值见表 1.

表 1
表 1 不同时段内的路段行程时间参数 Table 1 Travel time parameters of each link in different time intervals 路段μij, σij, aij

I1 I2 I3 I4 I5 I6

1-2 0.18, 0.12, 0.15 0.32, 0.29, 0.20 0.22, 0.36, 0.18 0.22, 0.48, 0.21 0.36, 0.39, 0.26 0.27, 0.15, 0.16

1-4 0.16, 0.29, 0.13 0.24, 0.33, 0.16 0.19, 0.24, 0.15 0.19, 0.44, 0.16 0.22.0.42, 0.21 0.16, 0.21, 0.14

1-5 0.28, 0.11, 0.25 0.36, 0.49, 0.31 0.27, 0.48, 0.26 0.30, 0.43, 0.29 0.39, 0.28, 0.35 0.30, 0.16, 0.26

2-3 0.22, 0.17, 0.20 0.20, 0.51, 0.22 0.24, 0.36, 0.25 0.22, 0.35, 0.24 0.18, 0.49, 0.32 0.19, 0.22, 0.22

2-6 0.26, 0.15, 0.31 0.32, 0.41, 0.36 0.25, 0.21, 0.39 0.36, 0.18, 0.35 0.26, 0.37, 0.36 0.25, 0.18, 0.32

3-7 0.30, 0.09, 0.32 0.22, 0.48, 0.35 0.29, 0.27, 0.38 0.36, 0.11, 0.37 0.29, 0.42, 0.38 0.28, 0.19, 0.32

4-5 0.13, 0.21, 0.10 0.18, 0.44, 0.13 0.16, 0.22, 0.13 0.15, 0.33, 0.14 0.21, 0.29, 0.15 0.13, 0.25, 0.10

4-9 0.30, 0.19, 0.27 0.45, 0.36, 0.30 0.36, 0.19, 0.35 0.41, 0.29, 0.36 0.45, 0.32, 0.30 0.32, 0.26, 0.28

5-6 0.20, 0.32, 0.18 0.28, 0.52, 0.21 0.22, 0.43, 0.19 0.21, 0.15, 0.18 0.25, 0.36, 0.27 0.20, 0.41, 0.16

5-8 0.25, 0.13, 0.19 0.32, 0.46, 0.23 0.29, 0.39, 0.27 0.31, 0.13, 0.28 0.35, 0.52, 0.30 0.26, 0.35, 0.25

6-7 0.18, 0.21, 0.16 0.29, 0.45, 0.24 0.28, 0.47, 0.24 0.29, 0.11, 0.24 0.32, 0.48, 0.28 0.25, 0.19, 0.22

6-10 0.30, 0.11, 0.23 0.42, 0.39, 0.36 0.40, 0.42, 0.36 0.38, 0.17, 0.38 0.45, 0.34, 0.35 0.36, 0.15, 0.35

7-11 0.29, 0.15, 0.26 0.45, 0.28, 0.39 0.43, 0.39, 0.40 0.41, 0.20, 0.41 0.49, 0.41, 0.40 0.34, 0.22, 0.27

8-9 0.17, 0.22, 0.12 0.26, 0.37, 0.18 0.25, 0.32, 0.21 0.26, 0.14, 0.22 0.34, 0.47, 0.21 0.22, 0.29, 0.15

8-10 0.20, 0.13, 0.16 0.38, 0.45, 0.22 0.35, 0.41, 0.25 0.35, 0.11, 0.26 0.38, 0.42, 0.29 0.24, 0.17, 0.17

8-12 0.26, 0.11, 0.23 0.45, 0.52, 0.39 0.40, 0.37, 0.38 0.38, 0.16, 0.36 0.47, 0.39, 0.36 0.38, 0.22, 0.35

9-12 0.30, 0.19, 0.36 0.40, 0.55, 0.38 0.38, 0.35, 0.35 0.36, 0.21, 0.35 0.43, 0.32, 0.36 0.32, 0.15, 0.30

10-11 0.18, 0.10, 0.16 0.35, 0.42, 0.21 0.32, 0.41, 0.25 0.30, 0.11, 0.25 0.36, 0.39, 0.26 0.22, 0.13, 0.20

10-13 0.30, 0.15, 0.28 0.48, 0.36, 0.45 0.45, 0.51, 0.40 0.42, 0.23, 0.40 0.48, 0.32, 0.42 0.32, 0.16, 0.30

11-13 0.25, 0.14, 0.21 0.36, 0.49, 0.32 0.32, 0.36, 0.30 0.32, 0.19, 0.30 0.35, 0.29, 0.30 0.31, 0.15, 0.28

12-13 0.30, 0.11, 0.28 0.49, 0.34, 0.40 0.45, 0.37, 0.42 0.44, 0.13, 0.40 0.48, 0.51, 0.42 0.36, 0.22, 0.30



表 1 不同时段内的路段行程时间参数 Table 1 Travel time parameters of each link in different time intervals


考虑I1I6处于夜间时段,I2I5为交通流量高峰时段,将这4个时段的rij修正为rij=rij(1.0+rand(0.28, 0.51))[25].

利用手机网络数据动态感知技术来获取各路段附近可能受影响人数,得到给定区域内分人口数量在整个时间区间内的变化曲线.利用最小二乘法对各时段内人口数据变化曲线进行移位对数正态分布拟合,计算出Pij的估计参数值见表 2.

表 2
表 2 不同时段内的路段运输风险参数 Table 2 Transport risk parameters of each link in different time intervals 路段γij, ωij, δij

I1 I2 I3 I4 I5 I6

????1-2 1 420, 6.13, 0.26 ??760, 5.26, 0.62 ??806, 4.38, 0.47 ??786, 6.18, 0.39 1 120, 5.39, 0.66 1 380, 5.88, 0.31

??1-4 ??946, 4.27, 0.31 1 020, 5.85, 0.51 ??860, 3.26, 0.21 ??850, 6.14, 0.41 1 030, 6.18, 0.26 ??820, 0.67, 0.42

??1-5 1 560, 5.27, 0.35 1 720, 6.93, 0.62 1 680, 4.47, 0.66 1 680, 5.21, 0.33 1 690, 5.89, 0.53 1 580, 5.38, 0.42

??2-3 1 120, 6.21, 0.18 1 240, 5.47, 0.52 ??896, 6.13, 0.32 ??820, 5.35, 0.49 1 280, 6.22, 0.47 1 150, 5.85, 0.24

??2-6 1 750, 5.83, 0.39 1 530, 6.28, 0.72 1 210, 5.44, 0.35 ??920, 6.13, 0.52 1 480, 5.31, 0.44 1 620, 5.15, 0.33

??3-7 ??965, 4.16, 0.42 1 360, 5.11, 0.47 1 450, 4.86, 0.39 1 390, 6.07, 0.29 1 220, 6.34, 0.65 ??940, 6.12, 0.46

??4-5 ??720, 4.86, 0.48 ??960, 4.82, 0.39 1 120, 5.27, 0.42 ??980, 4.89, 0.33 1 150, 5.87, 0.44 ??680, 5.39, 0.40

??4-9 1 048, 5.82, 0.33 1 260, 5.94, 0.41 ??930, 6.16, 0.52 ??850, 6.07, 0.45 1 320, 4.96, 0.41 ??960, 5.77, 0.32

??5-6 1 650, 4.19, 0.42 1 320, 5.75, 0.47 1 360, 6.04, 0.39 1 280, 5.25, 0.32 1 440, 5.88, 0.37 1 660, 4.82, 0.36

??5-8 1 076, 4.45, 0.85 1 210, 4.93, 0.72 ??890, 5.38, 0.46 ??880, 4.94, 0.62 1 170, 5.39, 0.48 ??990, 5.13, 0.38

??6-7 ??974, 5.47, 0.48 1 160, 5.12, 0.36 1 080, 4.68, 0.42 1 020, 4.82, 0.31 1 210, 5.63, 0.42 ??940, 5.82, 0.27

??6-10 ??2 160, 3.88, 0.39 1 570, 5.83, 0.42 1 220, 4.41, 0.48 1 170, 4.92, 0.33 1 480, 5.93, 0.41 1 820, 4.31, 0.32

??7-11 ??460, 5.42, 0.33 ??690, 5.13, 0.48 ??530, 5.84, 0.47 ??550, 5.29, 0.42 ??720, 5.56, 0.39 ??460, 4.88, 0.47

??8-9 1 040, 5.22, 0.36 1 170, 4.83, 0.49 1 210, 5.25, 0.36 ??820, 4.38, 0.44 1 250, 5.27, 0.46 ??960, 5.38, 0.44

??8-10 1 156, 4.25, 0.37 ??940, 5.36, 0.52 1 040, 5.33, 0.39 ??980, 4.92, 0.41 1 100, 5.69, 0.48 ??990, 5.77, 0.52

??8-12 ??630, 4.33, 0.48 ??990, 5.27, 0.41 1 120, 4.95, 0.58 1 080, 4.36, 0.62 1 030, 5.44, 0.39 ??700, 5.22, 0.37

??9-12 ??880, 5.21, 0.52 1 160, 4.83, 0.39 1 240, 5.27, 0.42 1 110, 5.64, 0.27 1 280, 4.39, 0.41 ??900, 5.02, 0.28

??10-11 ??846, 5.32, 0.33 ??920, 6.18, 0.52 ??820, 5.65, 0.44 ??790, 6.04, 0.32 ??810, 5.33, 0.46 ??860, 4.98, 0.31

??10-13 1 240, 4.62, 0.31 1 410, 5.21, 0.32 1 180, 5.67, 0.38 1 020, 4.49, 0.32 1 360, 5.15, 0.47 1 160, 5.36, 0.27

??11-13 ??730, 5.32, 0.28 ??820, 5.39, 0.46 ??980, 5.97, 0.45 ??790, 5.20, 0.39 ??890, 5.37, 0.44 ??750, 4.33, 0.29

??12-13 ??690, 4.71, 0.35 ??920, 5.42, 0.46 ??960, 5.39, 0.41 ??950, 4.92, 0.63 ??920, 5.87, 0.44 ??720, 4.96, 0.53



表 2 不同时段内的路段运输风险参数 Table 2 Transport risk parameters of each link in different time intervals


危险品运输时间区间是连续的,根据不同的时间窗来计算to时,若to < 00:00,则令to=to+24:00.以节点1为起点,节点13为终点,设fe(x)和fv(x)的权重分别为π1=0.4和π2=0.15,ge(x)和gv(x)的权重分别为π3=0.35和π4=0.1,支配阈值Δ=0.4;ρij, jk取值为(-0.2, 0.2)内均匀分布的随机数;调整步长λ=30 min.设置不同场景s1s2,在s1中设置[Te, Tl]=16:00, 18:00,s2中[Te, Tl]=[21:00, 22:00],准时到达置信水平均为τ=0.95.

首先计算各场景中的出发时间窗,设λo=00:00,?o=TL,搜索终止判断值${\tilde \omega }$=0.01,可计算出s1s2中的出发时间窗分别为[λo, ?o]=[12:46, 14:41]和[λo, ?o]=[16:49, 17:50].当to分别取λo?o时,得到不同to对应的最短路径及其属性值见表 3.

表 3
表 3 不同场景下的最早/最迟出发时间及路径 Table 3 Path and the earliest/latest departure time under different scenes 场景 to podto fe(x)/h fv(x)/h gev(x)/10-3gv(x)/10-3T(podto)/h td

s1 12:46 1-4-9-12-13 1.57 1.00 52.04 6.25 3.23 16:00

14:41 1-5-6-10-13 1.58 1.03 55.92 1.76 3.27 17:57

s2 16:49 1-2-6-10-13 1.89 1.39 69.88 8.36 4.19 21:00

17:50 1-5-6-10-13 1.94 1.36 74.45 6.92 4.18 22:00



表 3 不同场景下的最早/最迟出发时间及路径 Table 3 Path and the earliest/latest departure time under different scenes


由表 3可知,运输车辆在不同时刻出发,对应的路径及其属性值不同.在同一场景内,路径间的随机属性值变化较小,不同场景间的对应属性值变化较大,因为两种场景的到达时间窗不同,决定了出发时间的可选范围不同.在s2中,危险品的运输需经过交通晚高峰时段,其行程时间、运输风险的期望值和标准差均高于s1中路径的对应值.因此危险品运输商应尽量避免车辆经由交通高峰时段,以减少运输风险并缩短行程时间.

得到出发时间窗口后,可根据λ来计算不同to对应的非支配路径,生成运输路径集合.以s1为例,生成不同to对应的非支配路径及各条路径的属性值见表 4.

表 4
表 4 不同出发时间对应的非支配路径 Table 4 Non-dominated paths with different departure time to podto fe(x)/h fv(x)/h ge(x)/10-3gv(x)/10-3T(podto)/h td

14:41 1-5-6-10-13 1.58 1.03 55.92 1.76 3.27 17:57

14:11 1-2-6-10-13 1.61 0.99 42.63 2.46 3.25 17:26

14:11 1-5-6-10-13 1.56 1.04 55.47 1.84 3.26 17:26

14:11 1-5-8-10-13 1.57 1.03 45.31 1.47 3.27 17:27

14:11 1-5-8-12-13 1.62 0.98 45.25 2.09 3.24 17:25

14:11 1-4-5-6-10-13 1.55 1.08 56.08 2.88 3.33 17:31

14:11 1-4-5-8-10-13 1.57 1.07 45.92 2.51 3.34 17:31

13:41 1-4-9-12-13 1.51 0.89 49.72 5.03 2.97 16:40

13:41 1-4-5-8-10-13 1.55 1.04 42.83 1.12 3.27 16:57

13:41 1-4-5-8-12-13 1.59 0.99 42.78 1.74 3.23 16:55

13:11 1-4-9-12-13 1.51 0.89 49.72 5.03 2.98 16:10

13:11 1-4-5-8-10-13 1.62 1.19 43.81 1.33 3.37 16:45

13:11 1-4-5-8-12-13 1.66 1.14 43.75 1.94 3.55 16:44



表 4 不同出发时间对应的非支配路径 Table 4 Non-dominated paths with different departure time


由表 4可知,在出发时间窗内对to取不同值时,存在多条满足[Te, Tl]约束的非支配路径,由多个topodto组成决策矩阵,使运输商根据优化准则进行有偏好的路径选择.

为直观表示不同优化准则下运输路径属性差异,取to=13:11时的路径p1(1, 4, 9, 12, 13)和p2(1, 4, 5, 8, 12, 13),以及to=14:11时的路径p1(1, 4, 5, 6, 10, 13)和p2(1, 2, 6, 10, 13)进行数据对比分析,得到各路径的属性值如图 2所示.

Figure 2
图 2 不同出发时间的路径属性 Figure 2 Path attributes with different departure time


在图 2(a)中,p2p2相比较,两者的fe(x)的值相差甚小,但p2fv(x)值变化较大.对保守型运输商来说,p2的行程时间更为可靠.

由图 2(b)可知,如果运输商以风险值最小为优化准则,p1明显优于p1p1上的运输风险在最坏情况下也低于p1上的风险.若在p2p2中进行选择,两者的ge(x)值近似相等,但p2gv(x)值较小,说明p2上风险值的稳定性更好.

在给定[Te, Tl]后,τ值的改变会影响不同类型(保守型、中间型和冒险型)运输商的出发时间选择.以s1为例,令τ分别取值0.95、0.5和0.2,计算?o和对应的路径属性值,计算结果见表 5.

表 5
表 5 不同置信水平下的最迟出发时间及路径 Table 5 Paths and the latest departure time with different arrival confidence level τ to podto fe(x)/h fv(x)/h ge(x)/10-3gv(x)/10-3T(podto)/h td

0.95 14:41 1-5-6-10-13 1.58 1.03 55.92 1.76 3.27 17:57

0.5 16:19 1-5-6-10-13 1.68 1.12 33.11 3.21 1.68 18:00

0.2 16:51 1-4-5-8-10-13 1.94 1.36 45.47 6.92 1.14 18:00



表 5 不同置信水平下的最迟出发时间及路径 Table 5 Paths and the latest departure time with different arrival confidence level


由表 5可知,保守型运输商的出发时间较早,路径行程时间的标准差较小,表明其可靠性性较好,能以较大的置信度准时到达;而冒险型运输商的出发时间较晚,路径行程时间的标准差较大,说明行程时间的可靠性较差,准时到达的可信度较低.计算结果符合实际运输过程中不同类型运输商对出发时间的选择方式.

考虑运输商的路径选择偏好,改变πmΔ的取值,分6种场景来分析参数变化对运输路径的影响,所有场景中令τ=0.95,to=14:30.在场景1和场景2中,假设运输商追求fe(x)和fv(x)取值最小,给出各πm的值为(0.45, 0.30, 0.15, 0.10),Δ分别为0.5和0.1时,得到2种场景下的非支配路径集合及路径属性值见表 6.

表 6
表 6 不同准则权重和支配阈值对应的路径 Table 6 Paths with different criterion weight and dominate threshold value 场景 (π1, π2, π3, π4; Δ) podto fe(x)/h fv(x)/h ge(x)/10-3gv(x)/10-3td

1 (0.45, 0.30, 0.15, 0.10;0.5) 1-4-9-12-13 1.58 0.99 48.76 4.83 17:43

1-5-6-10-13 1.56 1.04 55.47 1.84 17:46

1-5-8-10-13 1.58 1.03 45.31 1.47 17:46

1-5-8-12-13 1.62 0.98 45.26 2.09 17:44

1-4-5-6-10-13 1.55 1.08 56.09 2.88 17:50

2 (0.45, 0.30, 0.15, 0.10;0.1) 1-5-8-12-13 1.62 0.98 45.26 2.09 17:44

1-4-5-6-10-13 1.55 1.08 56.09 2.88 17:50



表 6 不同准则权重和支配阈值对应的路径 Table 6 Paths with different criterion weight and dominate threshold value


同理,采用相同的计算方式,分别计算以下4种场景下的非支配运输路径.在场景3和4中假设运输商追求ge(x)和gv(x)最小,各πm取值为(0.15, 0.10, 0.45, 0.30),Δ分别为0.5和0.1;在场景5和6中假设运输商无选择偏好,各πm取值为(0.25, 0.25, 0.25, 0.25),Δ分别为0.5和0.1.

由6种场景下的计算结果可知,改变πmΔ的取值,可生成不同的非支配路径.当Δ值相同时,πm的取值越平均,各准则之间的占优关系越不明显,产生的非支配路径数量较多.当πm取值不变时,Δ值越小,路径间的支配关系越明确,但是计算过程中被删除的可行路径数量增多,导致最终的非支配路径数量减少,求解效率提高.因此,调整πmΔ的取值,可为不同偏好的运输商提供路径选择决策支持,并实现求解质量和求解效率的有效均衡.

5 结论1) 根据危险品运输网络的动态特征,对运输路径的行程时间和运输风险的STD属性进行了分析,建立了基于到达时间窗约束和准时到达置信水平的多准则路径优化模型.

2) 根据STD路网的FIFO性质,设计了两阶段多维标号修正算法对模型求解.首先根据各路段的随机属性值、准时到达置信水平和给定的到达时间窗,利用可信性理论求解出发时间区间,并设定调整步长得到多个出发时刻;然后设计准则权重和阈值支配方法,计算不同出发时刻对应的非支配路径集合,并实现求解质量和求解效率的均衡.

3) 文中假设危险品运输网络为非可等待的FIFO网络,具有一定的局限性.在具有STD属性的FIFO网络或非FIFO网络中设置可等待节点,是下一步要研究的内容.


参考文献
[1] 杨信丰, 李引珍, 何瑞春, 等. 多属性时间依赖网络的城市危险品运输路径优化[J]. 中国安全科学学报, 2012, 22(9): 103-108.
YANG Xinfeng, LI Yinzhen, HE Ruichun, et al. Route optimization for urban hazardous material transportation in time-dependent networks with multi-attributes[J]. China Safety Science Journal, 2012, 22(9): 103-108.


[2] 冯树民, 殷国强. 规划层面的危险品运输路径优化模型[J]. 哈尔滨工业大学学报, 2012, 44(8): 53-56.
FENG Shumin, YIN Guoqiang. Transport route optimization model of dangerous goods at the planning level[J]. Journal of Harbin Institute of Technology, 2012, 44(8): 53-56. DOI:10.11918/j.issn.0367-6234.2012.08.011


[3] HALL R W. The fastest path through a network with random time dependent travel times[J]. Transportation Science, 1986, 20(3): 182-188. DOI:10.1287/trsc.20.3.182


[4] 任常兴, 吴宗之, 李晋. 基于风险分析的危险品道路运输多目标Pareto最优选线[J]. 中国安全生产科学技术, 2008, 4(2): 9-13.
REN Changxing, WU Zongzhi, LI Jin. Risk analysis based Pareto-optimal paths of hazardous materials transportation by road[J]. Journal of Safety Science and Technology, 2008, 4(2): 9-13.


[5] DESAI S, LIM G J. Solution time reduction techniques of a stochastic dynamic programming approach for hazardous material route selection problem[J]. Computers & Industrial Engineering, 2013, 65(4): 634-645.


[6] SUBRAMANIAN S. Routing algorithms for dynamic, intelligent transportation networks[D]. Virginia: Virginia Polytechnic Institute and State University, 1997.


[7] TOUMAZIS I, KWON C. Routing hazardous materials on time-dependent networks using conditional value-at-risk[J]. Transportation Research Part C: Emerging Technologies, 2013, 37(3): 73-92.


[8] WEI M, LI X, YU L. Time-dependent fuzzy random location-scheduling programming for hazardous materials transportation[J]. Transportation Research Part C: Emerging Technologies, 2015, 57: 146-165. DOI:10.1016/j.trc.2015.06.012


[9] FU L, RILETT L R. Expected shortest paths in dynamic and stochastic traffic networks[J]. Transportation Research Part B: Methodological, 1998, 32(7): 499-516. DOI:10.1016/S0191-2615(98)00016-2


[10] CHANG T S, NOZICK L K, TURNQUIST M A. Multi-objective path finding in stochastic dynamic networks, with application to routing hazardous materials Shipments[J]. Transportation Science, 2005, 39(3): 383-399. DOI:10.1287/trsc.1040.0094


[11] MILLER-HOOKS E, M AH, ASSANI H. Optimal routing of hazardous materials in stochastic, time-varying transportation networks[J]. Transportation Research Record: Journal of the Transportation Research Board, 1998, 1645(1): 143-151.


[12] ANDROUTSOPOULOS K N, ZOGRAFOS K G. Solving the bi-criterion routing and scheduling problem for hazardous materials distribution[J]. Transportation Research Part C: Emerging Technologies, 2010, 18(5): 713-726. DOI:10.1016/j.trc.2009.12.002


[13] CHANG T S, WAN Y, OOI W T. A stochastic dynamic traveling salesman problem with hard time windows[J]. European Journal of Operational Research, 2009, 198(3): 748-759. DOI:10.1016/j.ejor.2008.10.012


[14] 魏航. 时变随机网络下有时间窗的有害物品运输路径选择研究[J]. 中国管理科学, 2009, 17(3): 93-100.
WEI Hang. Hazardous materials transportation path problem in stochastic, time-varying network with constrain of time windows[J]. Chinese Journal of Management Science, 2009, 17(3): 93-100.


[15] 贺政纲, 宋金玉. 时变条件下危险废弃物运输路径选题研究[J]. 中国安全科学学报, 2014, 24(12): 44-50.
HE Zhenggang, SONG Jinyu. Route planning for hazardous waste transportation as time varies[J]. Journal of Safety Science and Technology, 2014, 24(12): 44-50.


[16] SRINIVASAN K K, PRAKASH A A, SESHADRI R. Finding most reliable paths on networks with correlated and shifted Lognormal travel times[J]. Transportation Research Part B: Methodological, 2014, 66(8): 110-128.


[17] WANG Y, DONG W, ZHANG L, et al. Speed modeling and travel time estimation based on truncated normal and log-normal distributions[J]. Transportation Research Record: Journal of the Transportation Research Board, 2012, 2315(1): 66-72. DOI:10.3141/2315-07


[18] NIE Y, WU X, DILLENBURG J F, et al. Reliable route guidance: A case study from Chicago[J]. Transportation Research Part A: Policy & Practice, 2012, 46(2): 403-419.


[19] SETAK M, HABIBI M, KARIMI H, et al. A time-dependent vehicle routing problem in multigraph with FIFO property[J]. Journal of Manufacturing Systems, 2015, 35(35): 37-45.


[20] ABKOWITZ M, CHENG P D M. Developing a risk/cost framework for routing truck movements of hazardous materials[J]. Accident Analysis & Prevention, 1988, 20(1): 39-51.


[21] 王云鹏, 孙文财, 李世武, 等. 基于Arc GIS的危险品城市运输路径优化模型[J]. 吉林大学学报(工学版), 2009, 39(1): 45-49.
WANG Yunpeng, SUN Wencai, LI Shiwu, et al. Route optimization model for urban hazardous material transportation based on Arc GIS[J]. Journal of Jilin University (Engineering and Technology Edition), 2009, 39(1): 45-49.


[22] ZENG W, MIWA T, WAKITA Y, et al. Application of Lagrangian relaxation approach to α-reliable path finding in stochastic networks with correlated link travel times[J]. Transportation Research Part C: Emerging Technologies, 2015, 56: 309-334. DOI:10.1016/j.trc.2015.04.018


[23] LIU L, MU H, YANG J. Simulated annealing based GRASP for Pareto-optimal dissimilar paths problem[J]. Soft Computing, 2017, 21(18): 5457-5473. DOI:10.1007/s00500-016-2137-7


[24] WU J, JIN S, JI H, et al. Algorithm for time-dependent shortest safe path on transportation networks[J]. Procedia Computer Science, 2011, 4(4): 958-966.


[25] LOZANO A, ANGELES M, MACIAS L, et al. Hazardous materials transportation in Mexico City: Chlorine and gasoline cases[J]. Transportation Research Part C: Emerging Technologies, 2011, 19(5): 779-789. DOI:10.1016/j.trc.2010.09.001



相关话题/优化 兰州交通大学 网络 人数 规划

  • 领限时大额优惠券,享本站正版考研考试资料!
    大额优惠券
    优惠券领取后72小时内有效,10万种最新考研考试考证类电子打印资料任你选。涵盖全国500余所院校考研专业课、200多种职业资格考试、1100多种经典教材,产品类型包含电子书、题库、全套资料以及视频,无论您是考研复习、考证刷题,还是考前冲刺等,不同类型的产品可满足您学习上的不同需求。 ...
    本站小编 Free壹佰分学习网 2022-09-19
  • 316H堆焊UNS N10003合金参数优化、组织和硬度的研究
    316H堆焊UNSN10003合金参数优化、组织和硬度的研究杨飞1,2,黎超文2,李志军2,蒋力2,叶祥熙2,刘芳1(1.上海理工大学材料科学与工程学院,上海200093;2.中国科学院上海应用物理研究所,上海201800)摘要:研究异种合金焊接可以降低熔盐堆结构材料的成本并确保其安全性,本文采用钨 ...
    本站小编 哈尔滨工业大学 2020-12-05
  • 基于BP神经网络遗传算法的高强钢成形研究
    基于BP神经网络遗传算法的高强钢成形研究郭强1,郑燕萍1,朱伟庆1,晋保荣2(1.南京林业大学汽车与交通工程学院,南京,210037;2.南京南汽冲压件有限公司,南京,211100)摘要:对新材料DP-780高强钢依据国家标准GB/T228.1-2010进行室温拉伸试验,获得材料的力学性能参数;依据 ...
    本站小编 哈尔滨工业大学 2020-12-05
  • 响应面分析法优化不锈钢激光切割工艺参数
    响应面分析法优化不锈钢激光切割工艺参数李永亮1,2,3,王敬1,3,梁强1,3(1.重庆工商大学机械工程学院,重庆400069;2.重庆工商大学工程训练中心,重庆400069;3.制造装备机构设计与控制重庆市重点实验室(重庆工商大学),重庆400069)摘要:为了获得良好的不锈钢激光切割质量,确定合 ...
    本站小编 哈尔滨工业大学 2020-12-05
  • 汽车六角球头冷锻工艺优化与数值仿真
    汽车六角球头冷锻工艺优化与数值仿真陈凌翔,李月超(新乡职业技术学院汽车工程系,河南新乡453000)摘要:冷锻成形工艺是一种少无切削的净近成形工艺,以其精度高、生产效率高、低耗节能等优点,大量使用在汽车零配件的生产。六角球头销是汽车转向系统中的关键零件,其六角成形的质量直接影响到产品的使用性能。本文 ...
    本站小编 哈尔滨工业大学 2020-12-05
  • 通过miRNA基因表达谱的基因共表达网络构建对星形细胞瘤的基因靶标进行预测
    通过miRNA基因表达谱的基因共表达网络构建对星形细胞瘤的基因靶标进行预测邵嘉敏(石门县人民医院神经外科,湖南,常德415000)摘要:星形细胞瘤为浸润性生长肿瘤,生长缓慢,多为隐形症状,难以早期发现。多数肿瘤切除后有复发可能,且复发后肿瘤可演变成间变性星形细胞瘤或多形性胶质母细胞瘤。因此寻找其生物 ...
    本站小编 哈尔滨工业大学 2020-12-05
  • 双足爬壁机器人三维壁面环境全局路径规划
    双足爬壁机器人三维壁面环境全局路径规划卢俊华1,朱海飞1,梁经伦2,管贻生1(1.广东工业大学机电工程学院,广州510006;2.东莞理工学院机械工程学院,广东东莞523808)摘要:为求解双足爬壁机器人在三维壁面环境中的全局路径,提出了一种结合壁面可过渡性分析、全局壁面序列搜索和壁面过渡落足点优化 ...
    本站小编 哈尔滨工业大学 2020-12-05
  • 磷虾群优化的改进粒子滤波算法
    磷虾群优化的改进粒子滤波算法朱震曙,蒋长辉,薄煜明,吴盘龙(南京理工大学自动化学院,南京210094)摘要:标准的粒子滤波存在着权值退化问题,重采样可以解决权值退化问题,但也会带来样本贫化现象.为解决样本贫化问题,提出了一种利用磷虾群优化的改进粒子滤波算法.该算法结合粒子滤波的求解过程,以磷虾个体的 ...
    本站小编 哈尔滨工业大学 2020-12-05
  • 车辆运行风险贝叶斯网络量化分级方法
    车辆运行风险贝叶斯网络量化分级方法马艳丽1,范璐洋1,2,吕天玲3,郭琳3(1.哈尔滨工业大学交通科学与工程学院,哈尔滨150090;2.中国电建集团成都勘测设计研究院有限公司,成都610072;3.黑龙江省劳动安全科学技术研究中心,哈尔滨150040)摘要:为评估自然驾驶过程中车辆运行存在的交通风 ...
    本站小编 哈尔滨工业大学 2020-12-05
  • 城市快速路小间距路段出口预告标志优化设置
    城市快速路小间距路段出口预告标志优化设置黄利华1,2,3,赵晓华1,2,李洋1,4,荣建1,2(1.北京工业大学城市交通学院,北京100124;2.北京市交通工程重点实验室(北京工业大学),北京100124;3.北京城市系统工程研究中心,北京100035;4.北京警察学院,北京102202)摘要:为 ...
    本站小编 哈尔滨工业大学 2020-12-05
  • 变信赖域序列凸规划RLV再入轨迹在线重构
    变信赖域序列凸规划RLV再入轨迹在线重构宗群,李智禹,叶林奇,田栢苓(天津大学电气自动化与信息工程学院,天津300072)摘要:针对可重复使用运载器(RLV)的再入轨迹重构问题,提出一种基于变信赖域序列凸规划的RLV再入轨迹快速求解方法.首先,通过离散化及对非凸约束的线性化处理,将RLV的非凸轨迹优 ...
    本站小编 哈尔滨工业大学 2020-12-05