考虑时空相异的危险品运输车辆安全调度

柴获; 何瑞春; 代存杰; 马昌喜

doi:10.19818/j.cnki.1671-1637.2019.03.015

考虑时空相异的危险品运输车辆安全调度

doi: 10.19818/j.cnki.1671-1637.2019.03.015

兰州交通大学交通运输学院, 甘肃兰州 730070

基金项目:

国家自然科学基金项目 71861023

兰州交通大学青年科学基金项目 2015026

详细信息

作者简介:
柴获(1982-), 男, 甘肃静宁人, 兰州交通大学副教授, 工学博士, 从事危险货物道路运输网络设计与车辆调度研究

通讯作者:
何瑞春(1969-), 女, 甘肃临洮人, 兰州交通大学教授, 工学博士

中图分类号: U492.3
计量
- 文章访问数: 1039
- HTML全文浏览量: 192
- PDF下载量: 353
- 被引次数: 14
出版历程
- 收稿日期: 2018-12-12
- 刊出日期: 2019-06-25

Safety scheduling of hazardous materials transportation vehicle considering spatio-temporal dissimilarity

School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China

More Information

Author Bio:
CHAI Huo(1982-), male, associate professor, PhD, chaihuo@mail.lzjtu.cn

Corresponding author: HE Rui-chun(1969-), female, professor, PhD, herc@mail.lzjtu.cn

Article Text (Baidu Translation)

摘要

摘要: 为确保危险品运输车辆间的安全距离, 从时空角度优化了危险品运输车辆的行驶路径和发车时间间隔; 分析了危险品运输车辆发生事故对其他车辆的影响及其与时空距离的关系, 提出了危险品运输车辆间时空安全距离评价方法, 并以时空安全距离为约束, 提出了车辆安全出发时间间隔计算方法; 建立了满足时空相异约束的危险品运输车辆调度模型, 设计了用于生成车辆调度时刻表的两阶段求解方法, 第1阶段采用NSGA-Ⅱ算法优化车辆行驶路径, 第2阶段分别设计了遗传算法和基于插入思想的近似算法以优化发车时间间隔; 为了验证车辆调度模型与算法的有效性, 对比了每个阶段中不同算法的优劣, 并分析了危险品事故影响系数和事故影响接受度对车辆调度结果的影响。研究结果表明: 提出的方法可针对不同危险品事故影响系数获得危险品运输车辆调度时刻表, 生成的车辆调度时刻能够保证车辆在行驶过程中始终保持安全距离; 遗传算法和近似算法获得的平均运输总时间分别为2.45和2.49 h, 表明近似算法获得的解劣于遗传算法, 但运行时间仅为遗传算法的1/10 000~1/5 000;危险品事故影响系数或事故影响接受度越小时, 车辆发车时间间隔越大, 导致运输总时间变长; 考虑时空相异性的车辆调度可以弥补相异路径方法仅从空间上考虑相异性的不足, 同时能够避免采用相异路径方法可能遗漏最佳运输路径的问题。
- 交通运输规划 /
- 车辆调度 /
- 时空相异 /
- 危险品运输 /
- 相异路径 /
- 运输安全
Abstract: To ensure a safety distance between the hazardous materials transportation vehicles, the travel routes and departure time intervals of hazardous materials transportation vehicles were optimized in term of space-time. The impact of hazardous material transportation vehicle accident on other vehicles and the relationship between the hazardous material transportation vehicle accident and the spatio-temporal distance were analyzed, an evaluation method of spatio-temporal safety distance between vehicles was proposed, and taking the spatio-temporal safty distance as a constraint, the calculation method of vehicle safety departure time interval was proposed. A scheduling model of hazardous material transportation vehicle satisfying the spatio-temporal dissimilarity constraint was established. A two-stage solution method was designed to generate the vehicle scheduling timetable. The NSGA-Ⅱ optimization algorithm was used to optimize the travel route of vehicle at the first stage. The genetic algorithm and approximation algorithm based on the inserting thought were designed to optimize the departure time interval at the second stage. To verify the effectiveness of vehicle scheduling model and algorithm, the advantages and disadvantages of different methods at each stage were compared, and the influences of hazardous material accident impact factor and accident impact acceptance on the scheduling results were analyzed. Research result shows that the proposed method can obtain hazardous material transportation vehicle scheduling timetables with different hazardous material accident impact factors, and always ensure the vehicles a safe distance during driving. The average total transportation times obtained by the genetic algorithm and approximation algorithm are 2.45 and 2.49 h, respectively, indicating that the optimal solution of approximation algorithm is inferior to that of genetic algorithm, but the run time is only 1/10 000-1/5 000 of that of genetic algorithm. The smaller the hazardous material accident impact factor or the accident impact acceptance, the larger the vehicle safety departure time interval is, which leads to a longer total transportation time. The vehicle scheduling considering the spatio-temporal dissimilarity can compensate for the deficiency of dissimilar routing method only considering the spatial dissimilarity. At the same time, using the dissimilar routing method can prevent the problem of missing the optimal transportation route.
- transportation planning /
- vehicle scheduling /
- spatio-temporal dissimilarity /
- hazardous material transportation /
- dissimilar route /
- transport safety

HTML全文

0. 引言

中国每年通过道路运输的危险品总量达3亿吨, 约占道路上货物运输总量的30%以上。随着危险品道路运输量的增加, 危险品道路运输的安全问题不容忽视。通过统计2011~2015年的危险品事故可知, 77%的事故发生在运输阶段, 而其中72%由交通事故引发^[1]。有部分交通事故发生在危险品运输车辆之间, 或发生事故后波及附近其他危险品运输车辆而发生二次事故, 2011年甘肃4·8兰临高速新七道梁隧道溶剂油爆炸事故中, 由于车辆之间的距离不够, 导致2辆溶剂油运输车辆发生交通事故引起爆炸; 2014年山西3·1晋济高速岩后隧道甲醇燃爆事故中, 其中一辆甲醇运输车发生事故后导致甲醇泄露起火引燃同向行驶的另一辆甲醇运输车并发生爆炸。这类事故的破坏力呈现级联特征, 事故造成的损失往往成倍增加, 其根本原因是危险品运输车辆之间距离不足, 导致多车同时运输时潜在风险增加。

相异路径可从空间上将危险品运输车辆隔离, 减小多车同时运输时的潜在风险, 同时还能兼顾风险分布公平性^[2]。Akgün等针对危险品运输问题, 提出了一种相异路径获取方法^[3], 并与已有方法^{[4, 5]}进行了比较; 何瑞春等针对最佳相异度的相异最短路径问题设计了遗传算法^[6]; Dell’Olmo等针对危险品运输问题, 提出了一种多准则最短路径算法(Multicriteria Shortest Paths Algorithm, MSPA), 用于求解多目标相异路径, 可获得运输距离和运输风险的Pareto解^[7]; Li等考虑决策者的不同偏好, 提出了相异路径测度计算方法, 建立了以路径总长度最短和相异性最好的双目标优化模型, 并设计了遗传算法求解^[8]; 李引珍等针对双目标相异路径问题, 设计了基于小生境共享竞争复制算子的遗传算法^{[9, 10, 11]}; Lim等针对应急疏散问题, 提出了一种避免疏散路径重叠的最短路径算法^[12]; Kang等针对大规模危险品运输网络, 提出了一种在k最短路径集(k-Shortest Paths, KSP) 中获取相异路径的方法^[13]; Talarico等提出了一种k相异路径问题(k-dissimilarVehicle Routing Problem, k-d-VRP) 求解方法, 可用于在车辆路径问题(Vehicle Routing Problem, VRP) 中获取备选路径^[14]; Pushak等提出了空间相异路径双向搜索算法^[15], 通过与其他算法^{[3, 16, 17, 18]}进行比较, 认为该算法效率最高且鲁棒性最好; Liu等提出了一种基于贪婪随机自适应的模拟退火算法^[19], 用于求解多目标相异路径问题, 与文献[20]中提出的算法相比, 运算时间和解的质量均有提高; Constantino等针对运钞车回收现金的VRP问题, 在优化运输总时间的同时, 在获得的路径组合中随机选择路径运输以减小运输风险^[21]。

相异路径方法从空间上考虑路径的相异性, 可能导致部分较优运输路径被遗漏, 车辆调度结果无法达到最优。例如运输风险低但不满足空间相异条件的路径将被舍弃, 而为了达到空间相异性, 一些高风险的路段可能被包含在备选路径内。另外, 相异路径间如果部分路段物理位置靠近, 同时行驶在这些路段上的车辆间的安全距离仍然无法保证, 增加了运输过程中的潜在风险。从时间和空间角度考虑相异性进行车辆调度, 使危险品运输车辆在任意时刻均保持安全距离, 可弥补相异路径方法仅从空间上考虑相异性的不足。目前针对时空相异的研究成果并不多见, 且主要针对单目标优化问题。Thyagarajan等针对军用飞机飞行任务, 从时空角度出发优化了起飞时间和飞行路径^[22]; Yan等为降低运钞车被抢劫的风险, 提出了时空相似性定义, 建立了以最小时空相似为优化目标的运钞车调度模型, 利用时空网络同时优化车辆出发时刻和行驶路径^[23]。

为了在危险品运输中考虑时空相异性, 保证车辆间的安全距离, 本文分析了危险品运输车辆间事故的距离敏感性, 提出了车辆间安全时空距离的概念; 在讨论运输路径间存在共同节点和共同路段等不同情况的基础上, 提出了运输车辆间安全出发时间间隔计算方法; 针对多车运输问题建立了一种考虑时空相异约束的危险品运输车辆安全调度数学模型, 设计了两阶段求解算法, 并通过单节点间危险品运输算例验证了模型和算法的有效性。

1. 危险品运输车辆时空相异性

1.1 危险品运输车辆时空距离

将危险品运输网络视为二维平面^{[24, 25, 26]}, 运输车辆为平面上移动的点。图 1的平面直角坐标系xOy中, 车辆1在[t_b, t_e] (t_b、t_e分别为出发和到达时刻) 时段内从A₁点运输货物到达B₁点, 车辆2在[t_b, t_e]时段内从A₂点运输货物到达B₂点。为了更直观地显示车辆1、2之间的距离随时间的变化过程, 增加时间轴t构成图 2所示的三维坐标系, 在[t_b, t_e]时段内车辆1、2间的欧氏距离d (t) 为

$\begin{array}{l} d (t) = {[x_{1} (t) - x_{2} (t)]^{2} + [y_{1} (t) - \\ y_{2} (t)]^{2}}^{- 2} t \in [t_{b}, t_{e}] (1) \end{array}$

图 1 平面直角坐标系中的车辆位置

Figure 1. Vehicle positions in plane rectangular coordinate system

下载: 全尺寸图片幻灯片

图 2 带时间轴的三维坐标系中的车辆位置

Figure 2. Vehicle positions in 3D coordinate system with time axis

下载: 全尺寸图片幻灯片

式中: (x₁ (t), y₁ (t))、(x₂ (t), y₂ (t)) 分别为t时刻车辆1、2在平面坐标系xOy中的坐标。

d (t) 仅可以表示t时刻车辆1、2之间的欧氏距离, 假设车辆1、2之间的出发时间间隔为Δt (Δt > 0), 车辆2在t_b时刻从A₂点出发, 车辆1在t_b+Δt时刻从A₁点出发, d (t) 无法体现车辆1、2之间的距离与出发时间间隔Δt的关系, 为此, 将两车的位置变换在图 3所示的同一时间坐标系中, 可清晰地显示在车辆2提前出发Δt的情况下两车的位置关系。为了分析车辆在不同出发时刻下的距离变化特征, 引入危险品运输车辆时空距离的定义。

图 3 带时间轴的三维坐标系中不同出发时刻下的车辆位置

Figure 3. Vehicle positions under different departure times in 3D coordinate system with time axis

下载: 全尺寸图片幻灯片

定义1: 车辆1、2分别在t_b+Δt和t_b时刻出发的情况下, t时刻车辆1、2之间的时空距离s (t+Δt, t) 为

$\begin{array}{l} s (t + Δ t, t) = {[x_{1} (t) - x_{2} (t + Δ t)]^{2} + [y_{1} (t) - \\ y_{2} (t + Δ t)]^{2}}^{- 2} t \in [t_{b}, t_{e} + Δ t] (2) \end{array}$

同样, 如果车辆1提前Δt出发, t时刻车辆1、2之间的时空距离为s (t, t+Δt)。两车同时出发时, 即Δt=0时, s (t+Δt, t) =s (t, t+Δt)。

1.2 危险品运输车辆间安全时空距离

Batta等认为危险品运输车辆事故影响存在一个临界值λ, 可根据危险品的特性、运输量及事故发生环境因素等确定。以事故中心点C为圆心, λ为半径的圆形区域为受事故影响区域^[24]。假设L点与事故中心点C之间的欧氏距离为s′, 则L点处事故影响程度可用距离敏感性函数δ表示, 即

$δ = {\begin{matrix} 1 & s^{'} \leq λ \\ 0 & 其他 \end{matrix} (3)$

Carotenuto等认为布尔值只能表示是否受事故影响, 无法表征受事故影响的程度^[27]。随着距事故中心点距离s′的增加, L点受C点事故影响程度逐渐减弱, L点受C点事故影响程度δ与距离s′的关系为

$δ = e^{- α s^{'}^{2}} (4)$

式中: α > 0, 为危险品事故影响系数, 表示随着距离的增加, 事故影响衰减的速度。

由式(4) 可知: α越大, 事故影响衰减越快, 事故波及范围越小。危险品发生爆炸时, 在距离事故中心1 km处, α=0.8时的事故影响程度相当于事故中心的45%;α=0.5时的事故影响程度相当于事故中心的60%。

除可能引起人员伤亡和环境破坏之外, 危险品运输车辆发生事故也可能对附近其他危险品运输车辆产生影响。当易燃易爆化学品运输车辆发生事故时, 如果附近有其他危险品运输车辆, 极易引发二次事故, 造成更大损失。根据式(4) 可知, 当危险品运输车辆之间达到安全距离后, 其中任意一辆车发生事故对其他车辆不会产生影响或产生的影响可以忽略, 因此, 在车辆2提前出发Δt情况下t时刻危险品运输车辆1、2间的事故距离敏感性函数δ (t) 为

$δ (t) = e^{- α [s (t + Δ t, t)]^{2}} t \in [t_{b}, t_{e} + Δ t] (5)$

式(5) 中的α可根据车辆1和2装载的危险品的理化性质及危险特性确定, 通常情况下可取min{α₁, α₂}, 其中: α₁、α₂分别为车辆1、2所运危险品的事故影响系数。根据式(5), 危险品运输车辆1、2间事故影响随时空距离的增加逐渐减弱, 当影响减弱到一定程度后, 可认为两车间具有安全时空距离, 危险品运输车辆间的时空相异性可定义如下。

定义2: 存在事故影响接受度ε∈[0, 1), 对于任意的t∈[t_b, t_e], 使得δ (t) ≤ε成立, 可认为两车之间保持安全时空距离, 危险品运输车辆1、2在[t_b, t_e]时段内时空相异。

当ε接近于0时, 时空相异性最好, 表示在行驶过程中车辆1、2间的时空距离趋于+∞; 当ε=1即s (t+Δt, t) =0时, 时空相异性最差。在实际运输过程中, 车辆间的实际距离并不能为0, 而是存在阈值θ, 当s (t+Δt, t) ≤θ时, 车辆1、2在[t_b, t_e]时段内其中某辆车发生事故对另一辆车造成最大影响。

根据以上分析, 在车辆2提前Δt出发的情况下, t时刻危险运输车辆1、2间的时空距离s (t+Δt, t) 满足以下条件时, 车辆1与2达到时空相异要求的安全时空距离[α^-1ln (1/ε) ]^1/2, 即

s (t+Δt, t) ≥[α^-1ln (1/ε) ]^1/2t∈[t_b, t_e+Δt] (6)

以α=0.8为例, 当ε=0.01, 时空距离达到2.40 km时, 车辆1与2时空相异, 而当α=0.5时, 车辆1与2的时空距离需要达到3.03 km才能满足时空相异条件。

2. 危险品运输车辆安全出发时间间隔

危险品运输网中的空间因素不可改变, 在车辆行驶速度确定的情况下, 只有通过改变车辆出发时刻来控制不同车辆间的时空距离, 从而使车辆出发时间间隔达到时空相异要求。

2.1 危险品运输车辆出发时间间隔

将车辆1、2同时出发和车辆1延迟出发(图 3) 情况下的车辆位置关系分别投影到xOt (图 4(a)) 和yOt (图 4 (b)) 坐标系中, 可直观地看到车辆1、2的坐标随时间的变化。其中: (x₂ (t+Δt), y₂ (t+Δt)) 为车辆2提前出发Δt情况下t时刻车辆2的坐标。2种情况下t时刻车辆坐标满足以下条件

${\begin{matrix} x_{1} (t) - x_{2} (t + Δ t) \geq x_{1} (t) - x_{2} (t) \\ y_{1} (t) - y_{2} (t + Δ t) \geq y_{1} (t) - y_{2} (t) \\ t \in [t_{b}, t_{e} + Δ t] \end{matrix} (7)$

图 4 车辆1不同出发时刻下的时空距离投影

Figure 4. Space-time distance projections of vehicle 1 under different departure times

下载: 全尺寸图片幻灯片

根据式(2)、(7) 可以得出: 车辆2提前出发Δt情况下, 车辆1、2的时空距离s (t+Δt, t) 与同时出发情况下两车时空距离s (t, t) 之间满足以下条件

$s (t + Δ t, t) \geq s (t, t) t \in [t_{b}, t_{e} + Δ t] (8)$

图 5 存在共同节点的2条路径上的车辆位置

Figure 5. Vehicle positions on two paths with common node

下载: 全尺寸图片幻灯片

由式(8) 可以看出, 当Δt增大时, 车辆1、2间的时空距离增加。然而, 并非所有情况下增大Δt都可使车辆1、2间的时空距离增加。如图 5所示, 车辆1从A₁点出发到达B₁点, 车辆2从A₂点出发到达B₂点, 当车辆1、2同时出发时, 其中任何一辆车到达E点时与另一辆车均保持一定距离, 假设车辆1从A′点到达E点与车辆2从A₂点到达E点用时相等, 车辆1提前出发Δt的情况下, 车辆2出发时车辆1已到达A′点, 则车辆1、2将在E点相遇, 因此, 并不是任何情况下增大Δt都可使车辆间的时空距离增加, Δt对车辆时空距离的影响还需进一步讨论。

2.2 危险品运输车辆安全出发时间间隔

2.2.1 行驶在不同路径上的车辆间的时空相异性

运输网络中的任意路径均可视为路段的有序组合, 车辆需按时间顺序遍历路径中包含的所有路段。假设任意路段可用直线逼近, 或通过增加虚拟节点划分成若干子路段采用多条直线逼近, 则任意路段或子路段(统称为路段) 在带时间轴的三维空间中可用关于时间的线性函数表示, 由路段序列组成的路径可表示为关于时间的分段函数。图 6所示的运输网络中, 节点间存在2条路径i、j, 分别由M和N个路段组成。假设车辆0时刻从起点O出发, t_{i, m}为车辆1沿路径i行驶到达路段m (m=1, 2, …, M) 终点的时刻, t_{j, n}为车辆2沿路径j行驶到达路段n (n=1, 2, …, N) 终点的时刻。如果路径i中任意路段m的起点坐标为(x_{i, m}, y_{i, m}), 终点坐标为(x_{i, m+1}, y_{i, m+1}), 车辆在路段m上的行驶速度为v_m, 则t时刻路径i上车辆1的坐标(x₁ (t), y₁ (t)) 为

${\begin{matrix} x_{1} (t) = x_{i, m} + \frac{v_{m} (x_{i, m + 1} - x_{i, m}) (t - t_{i, m})}{[(x_{i, m + 1} - x_{i, m})^{2} + (y_{i, m + 1} - y_{i, m})^{2}]^{1 / 2}} \\ y_{1} (t) = y_{i, m} + \frac{v_{m} (y_{i, m + 1} - y_{i, m}) (t - t_{i, m})}{[(x_{i, m + 1} - x_{i, m})^{2} + (y_{i, m + 1} - y_{i, m})^{2}]^{1 / 2}} \\ t \in [t_{i, m}, t_{i, m + 1}] \end{matrix} (9)$

图 6 O和D间2条路径的路段分布

Figure 6. Road segment distributions of two paths between O and D

下载: 全尺寸图片幻灯片

同理, 可计算出t时刻路径j上车辆2的坐标(x₂ (t), y₂ (t)), 代入式(2) 可得到车辆2提前出发Δt情况下两车的时空距离s (t+Δt, t), 为了使两车间达到时空相异, 需要时空距离满足式(6), 即

$\begin{array}{l} [x_{1} (t) - x_{2} (t + Δ t)]^{2} + [y_{1} (t) - y_{2} (t + Δ t)]^{2} \geq \\ α^{- 1} \ln (1 / ε) t \in [0, \max (t_{i, Μ}, t_{j, Ν})] (10) \end{array}$

式中: t_{i, M}、t_{j, N}分别为车辆1、2到达终点D的时刻。

满足式(10) 的Δt即为车辆安全出发时间间隔。然而, x₁ (t)、y₁ (t)、x₂ (t) 和y₂ (t) 的表达式均为分段函数, 无法直接通过解不等式得到, 需要进一步探索Δt的求解方法。

2.2.2 车辆安全出发时间间隔计算方法

首先分析2条路径间不存在共同节点或路段的情况。任意路段的函数表达式为关于时刻t的分段线性函数, 则车辆间的时空距离极小值满足命题1。

命题1: 车辆行驶在不存在共同节点或路段的路径上, 车辆到达路段起点(或终点) 时刻的时空距离取得极小值。

证明: 反证法。如图 7所示, 车辆1、2分别行驶在不存在共同节点的路段m、n上, 两车同时出发的情况下, 车辆1在t_{i, m-1}时刻到达路段m的起点, 在t_{i, m}时刻到达路段m的终点, 车辆2在t_{j, n-1}时刻到达路段n的起点, 在t_{j, n}时刻到达路段n的终点。假设图 7中的H为路段m上除起点和终点外的任意一点, 车辆1行驶到H点时(t时刻) 两车间的时空距离取得极小值, 则时空距离满足s (t_{j, n-1}, t_{j, n-1}) ≥s (t, t), 即车辆1、2同时出发的情况下, t_{j, n-1}时刻两车间的时空距离大于t时刻两车间的时空距离, 同时也满足s (t_{i, m}, t_{i, m}) ≥s (t, t), 因此, 要使车辆1、2间的时空距离在t处取得极小值, 车辆1需要在路段w (穿过图 7中阴影部分的任意路段) 上行驶并在t时刻到达H点, H点则成为路段w和m的交点, 即为路段的起点或终点, 与假设矛盾。

图 7 不存在共同节点或路段的2条路径上的车辆距离

Figure 7. Vehicle distance on two paths without common node or road segment

下载: 全尺寸图片幻灯片

以下分析存在共同节点或边的2条路径上的运输情况, 可分为3种情形。

(1) 仅存在共同节点。

如果将共同节点从2条路径中删除, 则等同于不存在共同节点或路段的情况, 车辆间时空距离的极小值仍可在车辆到达某一路段起点或终点的时刻取得, 除此之外, 也可能在车辆到达共同节点的时刻取得。由于共同节点必然为某路段的起点或终点, 因此, 车辆行驶在仅存在共同节点的2条路径上时, 时空距离仍然在到达某一路段起点或终点的时刻取得极小值。

(2) 存在同向经过的共同路段。

在同一路段上车辆行驶速度相同, 车辆间时空距离也保持不变, 同向经过共同路段等同于存在共同的起点和终点, 因此, 车辆同向行驶在存在共同路段的情况类似于存在共同节点的情况。

(3) 存在逆向经过的共同路段。

不同于以上2种情况, 如图 8所示。路径i、j间存在逆向经过的共同路段AB, 车辆分别行驶在路径i、j上时, 可能在路段AB上相遇, 即车辆间时空距离的极小值可能在车辆行驶在共同路段上的某一时刻取得。假设两车同时出发, 车辆1沿路径i行驶到达A、B点的时刻分别为t_{i, m-1}和t_{i, m}, 车辆2沿路径j行驶到达A、B点的时刻分别为t_{j, n}和t_{j, n-1}。车辆2提前出发Δt时, 为了使两车不在共同路段AB上相遇并保持足够的安全距离, 则要满足如下条件。

图 8 存在逆向经过共同路段的2条路径上的车辆间距离

Figure 8. Vehicle distance on two paths when passing through same road segment in reverse

下载: 全尺寸图片幻灯片

车辆1到达A点时, 车辆2已经通过A点并和车辆1保持安全距离, 即满足

$\begin{array}{l} [s (t_{i, m - 1}, t_{i, m - 1} + Δ t)]^{2} \geq α^{- 1} \ln (1 / ε) \\ t_{i, m - 1} + Δ t > t_{j, n} (11) \end{array}$

车辆1到达A点时, 车辆2并未到达B点, 且在车辆1到达B点前这段时间内两车始终保持安全距离, 即满足

$\begin{array}{l} [s (t_{i, m}, t_{i, m} + Δ t)]^{2} \geq α^{- 1} \ln (1 / ε) \\ t_{i, m} + Δ t < t_{j, n - 1} (12) \end{array}$

由式(11)、(12) 可知, 车辆经过逆向共同路段时, 除要考虑车辆到达共同路段的起点或终点时刻的时空距离要求外, 还增加了车辆到达共同路段的起点或终点时刻的约束。

通过以上分析可知, 行驶在任意2条路径上的车辆间满足相异性要求的安全出发时间间隔Δt须满足

${\begin{matrix} [x_{1} (t_{i, m}) - x_{2} (t_{i, m} + Δ t)]^{2} + [y_{1} (t_{i, m}) - y_{2} (t_{i, m} + Δ t)]^{2} \geq α^{- 1} \ln (1 / ε) & t_{i, m} \in [0, t_{i, Μ})] \\ [x_{1} (t_{j, n}) - x_{2} (t_{j, n} + Δ t)]^{2} + [y_{1} (t_{j, n}) - y_{2} (t_{j, n} + Δ t)]^{2} \geq α^{- 1} \ln (1 / ε) & t_{j, n} \in [0, t_{j, Ν})] \\ t_{i, m - 1} + Δ t \geq t_{j, n} 或 t_{i, m} + Δ t \leq t_{j, n - 1} & m 与 n 为共同逆向路段 \end{matrix} (13)$

对式(13) 进行展开处理, 可以得到关于Δt的不超过M+N+2个不等式, 然后对其求解即可获得行驶在路径i、j上的车辆间安全出发时间间隔Δt的取值范围Γ (i, j)。

3. 危险品运输车辆安全调度模型与求解方法

3.1 数学模型

假设在从起点O到终点D间运输危险品事故影响系数为α的危险品。q为运输总量(车辆数); P为筛选的运输路径集合, 共有n条; c_i、r_i和τ_i分别为路径i (i∈P) 上的运输成本、运输风险和运输时间; K={1, 2, …, q}为运输车辆集合; δ_{i, k}为车辆k (k∈K) 是否沿路径i运输; δ_{j, k′}为车辆k′是否沿路径j运输; T_k、T_k′分别为车辆k、k′的出发时刻。可建立优化所有路径上运输总成本f₁、运输总风险f₂和运输总时间f₃的危险品运输车辆调度模型1为

$\begin{array}{l} \min f_{1} = \sum_{i} \sum_{k} c_{i} δ_{i, k} (14) \\ \min f_{2} = \sum_{i} \sum_{k} r_{i} δ_{i, k} (15) \\ \min f_{3} = \max_{i, k} [(Τ_{k} + τ_{i}) δ_{i, k}] - \min_{i, k} (Τ_{k} δ_{i, k}) (16) \\ Τ_{k} δ_{i, k} - Τ_{k^{'}} δ_{j, k^{'}} \in Γ (i, j) \\ k^{'} \in Κ, j \in Ρ, Τ_{k} \geq Τ_{k^{'}} (17) \\ \sum_{i} \sum_{k} δ_{i, k} = q (18) \\ Τ_{k} \geq 0 (19) \\ δ_{i, k} \in {0, 1} (20) \end{array}$

式(14) 为所有路径上的运输总成本最小; 式(15) 为所有路径上的运输总风险最低; 式(16) 中 $\min_{i, k} (Τ_{k} δ_{i, k})$ 为所有路径上第1辆车的出发时刻, $\max_{i, k} [(Τ_{k} + τ_{i}) δ_{i, k}]$ 为所有路径上最后1辆车的到达时刻, 优化目标为运输总时间最短, 指从第1辆车出发到最后1辆车完成运输的时间; 式(17) 表示行驶在路径i、j上的任意车辆k和k′之间的出发时间间隔在区间Γ (i, j) 内; 式(18) 为总运输量约束; 式(19)、(20) 为决策变量。

模型1有3个优化目标, 当问题达到一定规模时, 很难获得Pareto最优解。危险品运输过程中, 决策者优先关注运输风险和运输成本, 为了降低求解难度, 改进模型1, 将运输总风险和总成本转化为约束条件, 将模型划分为2个阶段, 第1阶段优化运输总风险和运输总成本, 第2阶段优化运输总时间。第1阶段建立以δ_{i, k}为单决策变量的双目标优化模型2

$\begin{array}{l} \min f_{1} = \sum_{i} \sum_{k} c_{i} δ_{i, k} (21) \\ \min f_{2} = \sum_{i} \sum_{k} r_{i} δ_{i, k} (22) \\ \sum_{i} \sum_{k} δ_{i, k} = q (23) \\ δ_{i, k} \in {0, 1} (24) \end{array}$

通过求解模型1, 获得2个目标的Pareto最优解后, 即在δ_{i, k}已知情况下, 再建立运输总成本和运输总风险最优情况下以运输总时间最小为目标的单目标优化模型3

$\begin{array}{l} \min f_{3} = \max_{i, k} [(Τ_{k} + τ_{i}) δ_{i, k}] - \min_{i, k} (Τ_{k} δ_{i, k}) (25) \\ Τ_{k} δ_{i, k} - Τ_{k^{'}} δ_{j, k^{'}} \in Γ (i, j) \\ k, k^{'} \in Κ, Τ_{k} \geq Τ_{k^{'}}, i, j \in Ρ (26) \\ Τ_{k} \geq 0 (27) \end{array}$

3.2 求解方法

针对两阶段优化模型, 求解过程也可划分为两阶段, 通过第1阶段求解模型2获得各路径上运输量分配方案, 第2阶段求解改进后的模型3, 根据第1阶段获得各路径上承担运输任务量的情况进行车辆调度。

第1阶段: 运输任务分配。第1阶段为双目标优化问题, 优化目标为运输总成本和运输总风险最小, 决策变量为δ_{i, k}, 可采用NSGA-Ⅱ算法^[28]或启发式算法^[29]求解。算法采用自然数编码, 长度为筛选的运输路径数, 第i位元素值为路径i上分配的运输任务量。令二元组(f₁ (I), f₂ (I)) 为个体I的适应度, 其中f₁ (I)、f₂ (I) 分别为个体I的运输总成本和运输总风险。算法具体步骤参考文献28]和[29]。

第2阶段: 车辆调度。假设存在网络G, 如果δ_{i, k}=1, 网络中的节点Z_{i, k}表示车辆k通过路径i运输, 任意2个节点Z_{i, k}、Z_{j, k′}间存在有向边Z_{i, k}→Z_{j, k′}, 权值为minΓ (j, i), 同时将终点D也视为网络中的一个节点, 节点D与任意节点Z_{i, k}间存在有向边D→Z_{i, k}, 权值为路径i上的车辆行驶时间τ_i。从D点出发遍历所有节点的最短路径则可表示车辆最佳出发次序(倒序), 为指定起点的开放式旅行商问题(Traveling Salesman Problem, TSP), 可采用启发式算法或智能算法求解。

利用遗传算法求解数学模型时, 需根据模型的特征设计合理的染色体编码。针对改进后的模型1, 将分配在路径i上的运输车辆记为i, 染色体表示车辆的出发次序, 长度为运输量q, 以8辆车在3条路径上运输为例来说明染色体的编码和遗传策略。假设阶段1的任务分配结果为: 路径1上2辆, 路径2上3辆, 路径3上3辆。图 9为8辆车的行驶路径和出发次序, 若第1辆车先出发, 行驶在路径1上, 第2辆车再出发, 行驶在路径2上, 以此类推, 设C (·) 为车辆序列的运输总时间, 可采用1/C (·) 表示染色体的适应度函数。

图 9 染色体编码

Figure 9. Chromosome coding

下载: 全尺寸图片幻灯片

通过交叉和变异来实现算法的全局和局部寻优。采用轮盘赌策略选择2条染色体, 随机生成交叉段, 图 10(a)中基因2~4为交叉段, 交叉段元素直接互换, 交叉操作中可能导致每条路径上分配的车辆数发生变化而出现非法染色体, 因此, 同时还要通过二次交叉修复染色体, 图 10(a)中出现在第1条染色体交叉段第1位新元素为3, 找出其在非交叉位第1次出现的位置(位置7), 同样找出第2条染色体交叉段第1位新元素2第1次出现的位置(位置1), 交换2个元素的位置, 以此类推, 直到交叉段中出现的所有元素完成二次交叉, 生成2条新的染色体。变异操作中同样随机生成变异段(图 10 (b)), 将交叉段中元素做逆序操作, 生成新的染色体。

图 10 遗传策略

Figure 10. Genetic strategies

下载: 全尺寸图片幻灯片

染色体长度直接影响算法获得最优解的概率, 即运输量越大时, 为了提高获得最优解的概率, 只有通过增加种群规模和迭代次数, 算法运行时间随之增加。为此, 设计一种近似算法用于求解改进后的模型1。

由于存在若干车辆行驶在同一路径上仅出发时刻不同的情况, 对应网络G中这部分节点遍历次序上两两交换并不影响问题的解。根据这一特点, 基于插入思想设计近似算法求解。分配在某一路径上的车辆采用路径编号标识, 所有编号的集合为V, 其长度为运输量q, V[e]为集合V中第e个元素。例如阶段1的任务分配结果为: 路径1上2辆车, 路径2上3辆车, 路径3上3辆车, 则集合V={1, 1, 2, 2, 2, 3, 3, 3}, 长度为8。算法主要步骤如下。

Step 1:初始化。令车辆出发序列为S, 临时序列为S′, 车辆计数器e=1, 位置计数器p=1, 最佳插入位置p₁=0, 最佳队末车辆位置p₂=0。

Step 2:优化车辆出发次序。在临时序列S′中从第0~q位依次插入V[e], 计算并比较不同插入位置下的C (S′), 记录C (S′) 获得最小值时的插入位置p′₁, 令p₁=p′₁, 在车辆出发序列S中的位置p₁处插入车辆V[e], 如果e < q, 则令e=e+1。重复以上操作直至V中所有车辆均已插入车辆出发序列S, 令S′=S。

Step 3:优化队末车辆到达终点时长。将临时序列S′中前p个元素移至队尾, 计算C (S′) 并记录其值, 如果p < q, 令p=p+1。重复以上操作直至找出C (S′) 取得最小值时的队末车辆位置p′₂, 令p₂=p′₂, 依次交换序列S中S[1]与S[p₂+1]、S[2]与S[p₂+2]、…、S[p₂]与S[q]。

Step 4:输出结果。输出S和C (S)。

针对所有q辆车, 计算C (S) 和C (S′) 时需要判断任意2辆车间出发时间间隔是否满足安全出发时间间隔要求, 时间复杂度为O (q²); 优化车辆出发次序过程中, 需要在当前队列中插入新车辆q (q+1) /2次, 最坏情况下, 每次插入新车辆时需要计算C (S′), 因此, Step 2的时间复杂度为O (q⁴); 优化队末车辆到达终点时长过程中, 需要移动队末车辆q次, 在最坏的情况下, 每次移动操作都需要计算C (S′), 因此, Step 3的时间复杂度为O (q³)。

4. 计算结果分析

以8个节点13条路段的危险品运输网络为例, 每个节点的坐标见图 11。表 1为路段长度和在该路段上运输危险品的运输风险和车辆行驶速度, 表中运输风险指在危险品事故影响系数α=0.92时的潜在风险, 根据事故后果模型^[30]获得, 运输其他类型危险品时的风险根据事故影响半径换算^[31]。假设在节点1~8间运输危险品20车, 第1辆车在08:00由节点1出发, 给出满足时空相异要求(ε=0.01) 的危险品运输车辆调度方案。

图 11 测试运输网络

Figure 11. Test transportation network

下载: 全尺寸图片幻灯片

采用脉冲算法^{[32, 33]}获得节点1~8间Pareto最优运输路径共6条, 见表 2。根据风险偏好^[34]从Pareto最优运输路径集中选择部分或全部路径进行运输, 本算例中假设6条路径全部可用于危险品运输。

4.1 计算结果

根据2.2节中的方法计算车辆安全出发时间间隔矩阵, 第i行第j列元素的值为Γ (i, j), 即

表 1 路段运输距离和运输风险

Table 1. Transportation distances and risks of road segments

路段	运输风险	运输距离/km	行驶速度/ (km·h^-1)
1→4	0.001 8	17.09	45
1→3	0.001 5	8.00	30
1→2	0.001 1	5.66	35
4→8	0.004 0	20.88	40
4→6	0.000 8	10.00	45
3→4	0.000 3	10.00	30
3→6	0.003 5	16.00	30
2→3	0.000 2	5.66	30
2→5	0.000 9	12.37	40
5→7	0.001 2	16.28	40
6→8	0.003 5	12.00	30
6→7	0.000 5	8.94	30
7→8	0.002 2	8.94	35

下载: 导出CSV

| 显示表格

表 2 Pareto最优运输路径集

Table 2. Pareto optimal transportation path sets

路径编号	路径	运输风险	运输距离/km
1	1→2→3→4→6→7→8	0.005 1	49.20
2	1→2→3→4→8	0.005 6	42.19
3	1→2→5→7→8	0.005 4	43.24
4	1→3→6→8	0.008 5	36.00
5	1→4→6→7→8	0.005 3	44.98
6	1→4→8	0.005 8	37.97

下载: 导出CSV

| 显示表格

$[\begin{matrix} [0.08, + \infty) & [0.08, 0.10] \cup [0.23, + \infty) & [0.08, 0.26] \cup [0.41, + \infty) & [0.23, + \infty) & [0.06, 0.22] \cup [0.38, + \infty) & [0.06, 0.22] \cup [0.36, 0.40] \cup [0.53, + \infty) \\ [0.08, + \infty) & [0.08, + \infty) & [0.08, 0.12] \cup [0.24, + \infty) & [0.16, + \infty) & [0.06, 0.09] \cup [0.20, 0.22] \cup [0.36, + \infty) & [0.06, 0.22] \cup [0.36, + \infty) \\ [0.06, + \infty) & [0.06, + \infty) & [0.06, + \infty) & [0.06, + \infty) & [0.06, + \infty) & [0.19, + \infty) \\ [0.08, + \infty) & [0.08, + \infty) & [0.08, 0.10] \cup [0.25, + \infty) & [0.08, + \infty) & [0.27, + \infty) & [0.08, 0.21] \cup [0.37, + \infty) \\ [0.05, + \infty) & [0.05, + \infty) & [0.11, + \infty) & [0.05, + \infty) & [0.08, + \infty) & [0.05, 0.10] \cup [0.23, + \infty) \\ [0.05, + \infty) & [0.05, + \infty) & [0.05, + \infty) & [0.05, + \infty) & [0.06, + \infty) & [0.06, + \infty) \end{matrix}]$

在第1阶段, 如果采用遍历方法, 共需穷举53 130次, 耗时2 800 ms, 共获得156个解(Pareto最优解)。如果采用基于NSGA-Ⅱ的多目标优化算法, 算法参数设置如下: 种群规模为200, 迭代20次, 同样可获得156个Pareto最优解, 见图 12, 本算例第1阶段采用NSGA-Ⅱ算法可获得所有Pareto最优解。

图 12 第1阶段采用NSGA-Ⅱ算法获得的Pareto最优解集

Figure 12. Pareto optimal solution sets obtained by NSGA-Ⅱ algorithm at first stage

下载: 全尺寸图片幻灯片

第2阶段针对第1阶段的任务分配方案进行车辆调度。选择不同运输任务分配方案, 采用遗传算法或近似算法均可获得车辆调度时刻表。例如选择图 12中的方案30, 则路径1~6上分配的车辆数分别为0、0、1、0、2和17, 运输总距离为778.67 km, 运输总风险为0.114 6, 采用近似算法获得的车辆调度时刻见表 3, 从第1辆车出发到最后1辆车到达总历时2.35 h, 采用遗传算法获得的车辆调度时刻见表 4, 总历时2.30 h。

从表 3、4中的结果对比可以看出: 2种车辆调度方案中, 前14辆车的行驶路径和出发时刻均相同, 正是由于后6辆车不同的出发次序导致运输总时间不同, 而后6辆分别行驶在3条不同的路径上, 导致近似算法在处理行驶在不同路径上车辆(车辆15~20) 的情况时获得的解劣于遗传算法。

4.2 结果分析

4.2.1 第2阶段不同优化方法对解的影响

针对本文算例, 在两阶段优化方法中, 第2阶段分别选择遗传算法和近似算法, 2种算法针对所有任务分配方案获得的运输总时间见图 13, 可知: 遗传算法和近似算法获得的平均运输总时间分别为2.45和2.49 h, 两者相差0.04 h, 近似算法劣于遗传算法, 部分情况下只能获得较优解。

表 3 选定运输方案30下的车辆出发时刻(近似算法)

Table 3. Vehicle departure times under selecting transportation programme 30 (approximation algorithm)

车辆编号	路径编号	出发时刻	车辆编号	路径编号	出发时刻
1	6	08:00	11	6	08:40
2	6	08:04	12	6	08:44
3	6	08:08	13	6	08:48
4	6	08:12	14	6	08:52
5	6	08:16	15	6	08:56
6	6	08:20	16	6	09:00
7	6	08:24	17	3	09:04
8	6	08:28	18	5	09:08
9	6	08:32	19	5	09:13
10	6	08:36	20	6	09:27

下载: 导出CSV

| 显示表格

表 4 选定运输方案30下的车辆出发时刻(遗传算法)

Table 4. Vehicle departure times under selecting transportation programme 30 (genetic algorithm)

车辆编号	路径编号	出发时刻	车辆编号	路径编号	出发时刻
1	6	08:00	11	6	08:40
2	6	08:04	12	6	08:44
3	6	08:08	13	6	08:48
4	6	08:12	14	6	08:52
5	6	08:16	15	5	08:56
6	6	08:20	16	6	09:00
7	6	08:24	17	3	09:04
8	6	08:28	18	6	09:16
9	6	08:32	19	5	09:20
10	6	08:36	20	6	09:24

下载: 导出CSV

| 显示表格

图 13 第2阶段采用不同算法获得的运输总时间比较

Figure 13. Comparison of total transportation times obtained by different algorithms at second stage

下载: 全尺寸图片幻灯片

采用2种算法多次运行后取平均运行时间, 遗传算法的平均运行时间为12 275 ms, 而近似算法的平均运行时间仅为30 ms, 近似算法在运行时间方面具有绝对优势。遗传算法更易获得最优解, 而近似算法运行耗时短, 同规模问题约为遗传算法的1/10 000~1/5 000, 但部分情况下仅能获得较优解, 因此, 实际问题求解中, 获得车辆运输任务分配方案后, 可首先利用近似算法快速获得所有方案下运输总时间的近似值, 获得车辆运输总时间变化趋势, 决策者据此选择任务分配方案, 针对选定方案再采用遗传算法优化车辆出发时刻, 即可获得最佳调度方案。

4.2.2 α对运输总时间的影响

不同α取值下车辆运输总时间见图 14, 可知: 随着α的减小, 运输总时间的增长速度变快; 在相同的时空相异要求下, 危险品事故影响系数越小, 即其危害程度越大或影响范围越广时, 只有加大车辆发车时间间隔才能保证车辆间的安全时空距离。

图 14 不同α下运输总时间对比

Figure 14. Comparison of total transportation times under different α

下载: 全尺寸图片幻灯片

4.2.3 ε对运输总时间的影响

不同ε取值下获得的车辆运输总时间见图 15, 可知: 总体上ε越小, 运输总时间越长, 这是由于ε越小时, 为了保持车辆间的安全时空距离, 需要加大车辆发车时间间隔, 导致运输总时间变长; 尽管ε取值不同, 但部分运输任务分配方案下车辆运输总时间存在相等或相近的情况, 因此, 运输总时间除受ε影响外, 还与选择的运输任务分配方案有关。

图 15 不同ε下运输总时间对比

Figure 15. Comparison of total transportation times under different ε

下载: 全尺寸图片幻灯片

5. 结语

(1) 考虑车辆时空相异进行危险品运输车辆调度, 可获得不同危险品事故影响系数下危险品运输车辆调度时刻表, 能够保证车辆在行驶过程中始终保持安全距离; 第2阶段利用近似算法快速获得所有方案下运输总时间的近似值, 获得车辆运输总时间变化趋势, 据此选择任务分配方案, 再针对选定方案采用遗传算法优化车辆出发时刻, 即可获得最佳调度方案; 通过算例分析可知, 危险品事故影响系数或事故影响接受度越小时, 车辆发车时间间隔越大, 导致运输总时间变长。

(2) 时空相异是相异路径思想在时间维度上的延伸, 相异路径的方法适合于危险品运输网络设计或路径规划, 而时空相异则适合于危险品运输车辆安全调度。考虑时空相异性的车辆调度既可以弥补相异路径方法仅从空间上考虑相异性的不足, 同时能够避免采用相异路径方法可能遗漏最佳运输路径的问题。

(3) 下一步可结合车辆定位等技术探索更有利于量化危险品运输网络中车辆间时空距离的方法; 另外, 危险品运输网络交通流等动态因素的影响往往呈动态或时变特征, 需要深入研究考虑时空相异的车辆动态调度问题。

图 1 平面直角坐标系中的车辆位置

Figure 1. Vehicle positions in plane rectangular coordinate system

下载: 全尺寸图片幻灯片

图 2 带时间轴的三维坐标系中的车辆位置

Figure 2. Vehicle positions in 3D coordinate system with time axis

下载: 全尺寸图片幻灯片

图 3 带时间轴的三维坐标系中不同出发时刻下的车辆位置

Figure 3. Vehicle positions under different departure times in 3D coordinate system with time axis

下载: 全尺寸图片幻灯片

图 4 车辆1不同出发时刻下的时空距离投影

Figure 4. Space-time distance projections of vehicle 1 under different departure times

下载: 全尺寸图片幻灯片

图 5 存在共同节点的2条路径上的车辆位置

Figure 5. Vehicle positions on two paths with common node

下载: 全尺寸图片幻灯片

图 6 O和D间2条路径的路段分布

Figure 6. Road segment distributions of two paths between O and D

下载: 全尺寸图片幻灯片

图 7 不存在共同节点或路段的2条路径上的车辆距离

Figure 7. Vehicle distance on two paths without common node or road segment

下载: 全尺寸图片幻灯片

图 8 存在逆向经过共同路段的2条路径上的车辆间距离

Figure 8. Vehicle distance on two paths when passing through same road segment in reverse

下载: 全尺寸图片幻灯片

图 9 染色体编码

Figure 9. Chromosome coding

下载: 全尺寸图片幻灯片

图 10 遗传策略

Figure 10. Genetic strategies

下载: 全尺寸图片幻灯片

图 11 测试运输网络

Figure 11. Test transportation network

下载: 全尺寸图片幻灯片

图 12 第1阶段采用NSGA-Ⅱ算法获得的Pareto最优解集

Figure 12. Pareto optimal solution sets obtained by NSGA-Ⅱ algorithm at first stage

下载: 全尺寸图片幻灯片

图 13 第2阶段采用不同算法获得的运输总时间比较

Figure 13. Comparison of total transportation times obtained by different algorithms at second stage

下载: 全尺寸图片幻灯片

图 14 不同α下运输总时间对比

Figure 14. Comparison of total transportation times under different α

下载: 全尺寸图片幻灯片

图 15 不同ε下运输总时间对比

Figure 15. Comparison of total transportation times under different ε

下载: 全尺寸图片幻灯片

表 1 路段运输距离和运输风险

Table 1. Transportation distances and risks of road segments

路段	运输风险	运输距离/km	行驶速度/ (km·h^-1)
1→4	0.001 8	17.09	45
1→3	0.001 5	8.00	30
1→2	0.001 1	5.66	35
4→8	0.004 0	20.88	40
4→6	0.000 8	10.00	45
3→4	0.000 3	10.00	30
3→6	0.003 5	16.00	30
2→3	0.000 2	5.66	30
2→5	0.000 9	12.37	40
5→7	0.001 2	16.28	40
6→8	0.003 5	12.00	30
6→7	0.000 5	8.94	30
7→8	0.002 2	8.94	35

下载: 导出CSV

表 2 Pareto最优运输路径集

Table 2. Pareto optimal transportation path sets

路径编号	路径	运输风险	运输距离/km
1	1→2→3→4→6→7→8	0.005 1	49.20
2	1→2→3→4→8	0.005 6	42.19
3	1→2→5→7→8	0.005 4	43.24
4	1→3→6→8	0.008 5	36.00
5	1→4→6→7→8	0.005 3	44.98
6	1→4→8	0.005 8	37.97

下载: 导出CSV

表 3 选定运输方案30下的车辆出发时刻(近似算法)

Table 3. Vehicle departure times under selecting transportation programme 30 (approximation algorithm)

车辆编号	路径编号	出发时刻	车辆编号	路径编号	出发时刻
1	6	08:00	11	6	08:40
2	6	08:04	12	6	08:44
3	6	08:08	13	6	08:48
4	6	08:12	14	6	08:52
5	6	08:16	15	6	08:56
6	6	08:20	16	6	09:00
7	6	08:24	17	3	09:04
8	6	08:28	18	5	09:08
9	6	08:32	19	5	09:13
10	6	08:36	20	6	09:27

下载: 导出CSV

表 4 选定运输方案30下的车辆出发时刻(遗传算法)

Table 4. Vehicle departure times under selecting transportation programme 30 (genetic algorithm)

车辆编号	路径编号	出发时刻	车辆编号	路径编号	出发时刻
1	6	08:00	11	6	08:40
2	6	08:04	12	6	08:44
3	6	08:08	13	6	08:48
4	6	08:12	14	6	08:52
5	6	08:16	15	5	08:56
6	6	08:20	16	6	09:00
7	6	08:24	17	3	09:04
8	6	08:28	18	6	09:16
9	6	08:32	19	5	09:20
10	6	08:36	20	6	09:24

下载: 导出CSV

参考文献(34)

[1]	赵岩. 诊治危险品运输事故急症[J]. 中国公路, 2016 (3): 69-71. https://www.cnki.com.cn/Article/CJFDTOTAL-GLZG201603031.htm ZHAO Yan. Diagnosis and treatment of emergency for dangerous goods transportation accident[J]. China Highway, 2016 (3): 69-71. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-GLZG201603031.htm
[2]	KEENEY R L. Equity and public risk[J]. Operations Research, 1980, 28 (3): 527-534.
[3]	AKGÜN V, ERKUT E, BATTA R. On finding dissimilar paths[J]. European Journal of Operational Research, 2000, 121 (2): 232-246. doi: 10.1016/S0377-2217(99)00214-3
[4]	LOMBARD K, CHURCH R L. The gateway shortest path problem: generating alternative routes for a corridor location problem[J]. Geographical Systems, 1993, 1 (1): 25-45.
[5]	KUBY M, XU Z Y, XIE X D. A minimax method for finding the k best "differentiated" paths[J]. Geographical Analysis, 1997, 29 (4): 298-313.
[6]	何瑞春, 李引珍. 最佳相异度相异最短路径的遗传算法[J]. 兰州交通大学学报(自然科学版), 2005, 24 (3): 116-119. https://www.cnki.com.cn/Article/CJFDTOTAL-LZTX200503032.htm HE Rui-chun, LI Yin-zhen. Genetic algorithms for finding dissimilar shortest paths based on best dissimilar measure[J]. Journal of Lanzhou Jiaotong University (Natural Science), 2005, 24 (3): 116-119. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-LZTX200503032.htm
[7]	DELL'OLMO P, GENTILI M, SCOZZARI A. On finding dissimilar Pareto-optimal paths[J]. European Journal of Operational Research, 2005, 162 (1): 70-82. doi: 10.1016/j.ejor.2003.10.033
[8]	LI Yin-zhen, HE Rui-chun, LIU Lin-zhong, et al. Genetic algorithms for dissimilar shortest paths based on optimal fuzzy dissimilar measure and applications[C]//Springer. International Conference on Fuzzy Systems and Knowledge Discovery. Berlin: Springer, 2005: 312-320.
[9]	李引珍, 何瑞春, 郭耀煌, 等. 多目标网络相异路径的Pareto解及其遗传算法[J]. 系统工程学报, 2008, 23 (3): 264-268. https://www.cnki.com.cn/Article/CJFDTOTAL-XTGC200803003.htm LI Yin-zhen, HE Rui-chun, GUO Yao-huang, et al. Pareto solution set and its genetic algorithm for multi-objective network dissimilar paths[J]. Journal of Systems Engineering, 2008, 23 (3): 264-268. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-XTGC200803003.htm
[10]	马昌喜, 何瑞春, 熊瑞琦. 基于双层规划的危险货物配送路径鲁棒优化[J]. 交通运输工程学报, 2018, 18 (5): 165-175. http://transport.chd.edu.cn/article/id/201805016 MA Chang-xi, HE Rui-chun, XIONG Rui-qi. Robust optimization on distributing routes of hazardous materials based on bi-level programming[J]. Journal of Traffic and Transportation Engineering, 2018, 18 (5): 165-175. (in Chinese). http://transport.chd.edu.cn/article/id/201805016
[11]	代存杰, 李引珍, 马昌喜, 等. 考虑风险分布特征的危险品运输路径优化[J]. 中国公路学报, 2018, 31 (4): 330-342. doi: 10.3969/j.issn.1001-7372.2018.04.038 DAI Cun-jie, LI Yin-zhen, MA Chang-xi, et al. Transportation path optimization for hazardous materials considering characteristics of risk distribution[J]. China Journal of Highway and Transport, 2018, 31 (4): 330-342. (in Chinese). doi: 10.3969/j.issn.1001-7372.2018.04.038
[12]	LIM Y, RHEE S. An efficient dissimilar path searching method for evacuation routing[J]. KSCE Journal of Civil Engineering, 2010, 14 (1): 61-67. doi: 10.1007/s12205-010-0061-4
[13]	KANG Y Y, BATTA R, KWON C. Generalized route planning model for hazardous material transportation with VaR and equity considerations[J]. Computers and Operations Research, 2014, 43 (1): 237-247.
[14]	TALARICO L, SÖRENSEN K, SPRINGAEL J. the k-dissimilar vehicle routing problem[J]. European Journal of Operational Research, 2015, 244 (1): 129-140. doi: 10.1016/j.ejor.2015.01.019
[15]	PUSHAK Y, HARE W, LUCET Y. Multiple-path selection for new highway alignments using discrete algorithms[J]. European Journal of Operational Research, 2016, 248 (2): 415-427. doi: 10.1016/j.ejor.2015.07.039
[16]	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
[17]	XU W, HE S, RUI S, et al. Finding the k shortest paths in a schedule-based transit network[J]. Computers and Operations Research, 2012, 39 (8): 1812-1826. doi: 10.1016/j.cor.2010.02.005
[18]	LAWLER E L. A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem[J]. Management Science, 1972, 18 (7): 401-405. doi: 10.1287/mnsc.18.7.401
[19]	LIU Lin-zhong, MU Hai-bo, YANG Ju-hua. 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
[20]	MARTÍ R, VELARDE J L G, DUARTE A. Heuristics for the bi-objective path dissimilarity problem[J]. Computers and Operations Research, 2009, 36 (11): 2905-2912. doi: 10.1016/j.cor.2009.01.003
[21]	CONSTANTINO M, MOURÃO M C, PINTO L S. Dissimilar arc routing problems[J]. Networks, 2017, 70 (3): 233-245. doi: 10.1002/net.21763
[22]	THYAGARAJAN K, BATTA R, KARWAN M H, et al. Planning dissimilar paths for military units[J]. Military Operations Research, 2005, 10 (1): 25-42. doi: 10.5711/morj.10.1.25
[23]	YAN S Y, WANG S S, WU M W. A model with a solution algorithm for the cash transportation vehicle routing and scheduling problem[J]. Computers and Industrial Engineering, 2012, 63 (2): 464-473. doi: 10.1016/j.cie.2012.04.004
[24]	BATTA R, CHIU S S. Optimal obnoxious paths on a network: transportation of hazardous materials[J]. Operations Research, 1988, 36 (1): 84-92.
[25]	陆键, 刘禹杰, 马晓丽. 基于博弈论的危险品运输网络选线[J]. 中国公路学报, 2018, 31 (4): 322-329. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL201804038.htm LU Jian, LIU Yu-jie, MA Xiao-li. Game-theory-based hazardous materials transport network routing[J]. China Journal of Highway and Transport, 2018, 31 (4): 322-329. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL201804038.htm
[26]	王磊, 华珺, 杨云峰, 等. 道路危险货物运输的系统动力学仿真研究[J]. 中国公路学报, 2018, 31 (8): 181-188, 196. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL201808021.htm WANG Lei, HUA Jun, YANG Yun-feng, et al. Study on system dynamics simulation of road dangerous cargo transportation[J]. China Journal of Highway and Transport, 2018, 31 (8): 181-188, 196. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL201808021.htm
[27]	CAROTENUTO P, GIORDANI S, RICCIARDELLI S. Finding minimum and equitable risk routes for hazmat shipments[J]. Computers and Operations Research, 2007, 34 (5): 1304-1327.
[28]	DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6 (2): 182-197.
[29]	PULIDO F J, MANDOW L, DE LA CRUZ J L P. Multiobjective shortest path problems with lexicographic goal-based preferences[J]. European Journal of Operational Research, 2014, 239 (1): 89-101.
[30]	ALP E. Risk-based transportation planning practice: overall methodology and a case example[J]. INFOR: Information Systems and Operational Research, 1995, 33 (1): 4-19.
[31]	GARRIDO R A, BRONFMAN A C. Equity and social acceptability in multiple hazardous materials routing through urban areas[J]. Transportation Research Part A: Policy and Practice, 2017, 102: 244-260.
[32]	MACHUCA E, MANDOW L, DE LA CRUZ J L P, et al. Heuristic multiobjective search for hazmat transportation problems[C]//Springer. Conference of the Spanish Association for Artificial Intelligence. Berlin: Springer, 2011: 243-252.
[33]	DUQUE D, LOZANO L, MEDAGLIA A L. An exact method for the biobjective shortest path problem for large-scale road networks[J]. European Journal of Operational Research, 2015, 242 (3): 788-797.
[34]	GUO X L, VERMA M. Choosing vehicle capacity to minimize risk for transporting flammable materials[J]. Journal of Loss Prevention in the Process Industries, 2010, 23 (2): 220-225.

施引文献

期刊类型引用(9)

1.	欧阳世波，张淼寒，谢俊明，安裕强，韩宇航，周心博，潘楠. 计及多目标约束的成品卷烟销售订单配送调度优化. 中国烟草学报. 2024(02): 80-91 . 百度学术
2.	包丹文，陈卓，姚馨宇，周佳怡. 基于混合策略的机坪车辆主动式实时调度方法. 交通运输工程学报. 2024(03): 251-265 . 本站查看
3.	黄舒. 国内危险品物流领域研究进展与前沿——基于CiteSpace的可视化分析. 物流工程与管理. 2024(10): 100-106 . 百度学术
4.	欧阳世波，黄欣雨，何兆磊，石昆，张淼寒. 供应链系统下的成品卷烟物流调度研究规划. 物流技术. 2023(02): 127-134 . 百度学术
5.	陈冉冉，徐佳力，李健. 基于GPS数据的危险品运输车辆行程链聚类研究. 中国安全科学学报. 2023(09): 157-163 . 百度学术
6.	柴获，何瑞春，贾晓燕，代存杰. 基于相异路径的危险品运输车辆调度. 中国安全科学学报. 2023(09): 181-188 . 百度学术
7.	宫寅林，王民涛. 基于深度卷积神经网络的电力物资运输车辆调度优化算法研究. 机械设计与制造工程. 2023(11): 106-110 . 百度学术
8.	王能民，张萌，何正文. 危险品运输车辆路径优化问题研究综述. 河北工业大学学报. 2021(02): 60-68 . 百度学术
9.	郭健，陶行行，周炜，李臣，胡金瑞. 危险品公路运输安全保障关键技术研究进展. 交通信息与安全. 2020(05): 129-136+152-153 . 百度学术