第10期 盖文妹等：应急救援物资车辆运输路线多目标优化 ·1385· “12·23”重庆天然气井喷事故以及“415”重庆天原 由于运输行程中不同路段的道路环境、地形条件差 化工总厂氯气泄漏事故习.为积极应对上述各种 异及灾害事态严重程度不同，各路段的风险不同，为 紧急态势，国家有关部门制定了相应的紧急救援预 保证物资运送人员的安全，应尽量选择风险较小的 案，其中应急救援物资运输是救援工作的重要内容， 路段行驶：此外，合理的运输调度方案有利于减少运 而应急救援物资车辆的调度问题是确保这一工作顺 输周转量，从而降低运输费用，但是在紧急态势下， 利进行的关键回.近年来现代地理信息服务、远程 由于运量大和运输时间集中等原因，常常会发生运 监测、传感器技术等信息技术的发展为建立动态实 力紧张的状况，追求运输调度的经济性目标，能够有 时的应急救援物资车辆最佳运输路线选择系统提供 效缓解运力不足的矛盾B.10-.因此，紧急态势下 了必要的技术支持O.在GS上以图形形式直观显 的应急决策者在选择救援物资车辆运输路线时，可 示应急救援物资车辆最佳运输路线的前提是建立合 能要求从救援物资支持保障中心到受灾地点运输路 理的运输路线优化模型，并设计出适合模型的算法. 线的时效性、安全性和经济性目标等多个目标的最 目前求解避灾路线与救灾路线等灾变条件下路 优化：从受灾地点返回支持保障中心时可能只要求 线选择的单目标优化研究己有所论述，多利用最短 运输路线的安全性和经济性实现最优化即可，虽然 路模型求解，但利用最短路模型求解灾变条件下救 也是起点到终点再返回起点的一条回路，但是救援 援物资运输调度多目标优化问题的研究还为数不 物资车辆由起点到终点的路线和由终点返回起点的 多B-).Current和Marsh网对于多目标最短路问题 路线优化目标内容和数量并不统一，显然无法借助 的研究现状进行分类和概括后指出，一般地，对于多 旅行商模型求解，需要根据灾变时期路线选择的特 目标的最短路算法，通常的处理方法是对不同的目 点建立合理的模型 标进行线性加权或是将某些目标转化为约束条件， 1.2模型建立 但是对于线性加权法而言，其权重的确定是一件很 地面错综复杂的道路易于用图形的形式直观地 困难的事情：而对于有约束的最短路问题，已经被证 描述与表达，数学上把这种与图相关的结构称为网 明是NP(non-deterministic polynomial)完全问题，有 络，路段抽象为图的边，路段之间的交点抽象成图的 时因为其算法复杂性太高使得无法进行求解.本文 点的集合，组成网络图的顶点，与路段相关的优化决 运用运筹学中图论和多目标优化的理论和方法建立 策指标作为有向边的权重.紧急态势下救援物资车 了应急救援物资车辆运输路线多目标优化模型，并 辆运输路线的选择虽然需要考虑多个优化目标，但 从应急决策的角度降低计算最优解的复杂度，设计 在任何情况下，保障人员的安全都是首要的目标，相 出适合求解该模型的算法 对而言，路线的时效性、经济性等要求均可看作次要 优化目标.为便于描述，令G=(V,E)表示一张道路 应急救援物资车辆最佳运输路线数学 网络图，V={}为G的节点集，E={(:,)|(:, 模型 )≠(，），)为G的有向边集，其中1V1= 1.1问题描述 n,IE1=m;为(：U)赋予多个不同的权重，和a, 灾变条件下的救援物资运输调度与正常环境下 T为车辆在路段(，y)上安全通过的概率，0<r< 的企业运输调度，优化目标之间差异明显.对于正 1,a为车辆在路段(：，，)上行驶的时间、成本等除 常情况下的企业运输调度而言，优化目标主要从经 安全性指标以外的其他决策指标，a证≥0，其中k= 济性角度考虑，通常简化为从起点出发，通过所有给 1,2,·,X,X为次要优化目标的数量.根据前述分 定的需求点之后，最后再回到原点运输成本的最小 析的应急救援物资车辆最佳运输路线选择的特点， 化，只在少数情况下才考虑时间约束，可转化为运筹 可将救援物资车辆最佳运输路线的选择分为“往” 学中的旅行商问题(traveling salesman problem, (支持保障中心→物资需求点)和“回”（物资需求 TSP),求解旅行商问题的算法已有较为深入的研 点→支持保障中心)两个过程来求解，每个过程均 究，分为完全算法和近似算法两类回.在灾变时期， 属于一个，→路线选择的多目标优化问题，其中 为保证安全高效的救灾，救援物资车辆运输路径的 ,和)分别表示选定的起点和终点.当"，表示物资 选择往往需要同时考虑多个优化目标，比如时间、成 支持保障中心时，表示受灾地点：当，表示受灾地 本和风险.首先，时间是任何紧急态势下不可忽视 点时，表示物资支持保障中心.由于最佳运输路 的决策属性，尤其是灾变条件下，争取时间能够抢得 线的各个优化目标之间通常存在冲突，某个目标下 主动，最大限度地挽救生命和减少财产损失；其次， 的最优解对于另一个目标可能并非最优，因而需要第 10 期 盖文妹等: 应急救援物资车辆运输路线多目标优化 “12·23”重庆天然气井喷事故以及“4·15”重庆天原 化工总厂氯气泄漏事故［1--2］． 为积极应对上述各种 紧急态势，国家有关部门制定了相应的紧急救援预 案，其中应急救援物资运输是救援工作的重要内容， 而应急救援物资车辆的调度问题是确保这一工作顺 利进行的关键［3］． 近年来现代地理信息服务、远程 监测、传感器技术等信息技术的发展为建立动态实 时的应急救援物资车辆最佳运输路线选择系统提供 了必要的技术支持［4］． 在 GIS 上以图形形式直观显 示应急救援物资车辆最佳运输路线的前提是建立合 理的运输路线优化模型，并设计出适合模型的算法． 目前求解避灾路线与救灾路线等灾变条件下路 线选择的单目标优化研究已有所论述，多利用最短 路模型求解，但利用最短路模型求解灾变条件下救 援物资运输调度多目标优化问题的研究还为数不 多［5--7］． Current 和 Marsh［8］对于多目标最短路问题 的研究现状进行分类和概括后指出，一般地，对于多 目标的最短路算法，通常的处理方法是对不同的目 标进行线性加权或是将某些目标转化为约束条件， 但是对于线性加权法而言，其权重的确定是一件很 困难的事情; 而对于有约束的最短路问题，已经被证 明是 NP( non-deterministic polynomial) 完全问题，有 时因为其算法复杂性太高使得无法进行求解． 本文 运用运筹学中图论和多目标优化的理论和方法建立 了应急救援物资车辆运输路线多目标优化模型，并 从应急决策的角度降低计算最优解的复杂度，设计 出适合求解该模型的算法． 1 应急救援物资车辆最佳运输路线数学 模型 1. 1 问题描述 灾变条件下的救援物资运输调度与正常环境下 的企业运输调度，优化目标之间差异明显． 对于正 常情况下的企业运输调度而言，优化目标主要从经 济性角度考虑，通常简化为从起点出发，通过所有给 定的需求点之后，最后再回到原点运输成本的最小 化，只在少数情况下才考虑时间约束，可转化为运筹 学中的旅行商问题 ( traveling salesman problem， TSP) ，求解旅行商问题的算法已有较为深入的研 究，分为完全算法和近似算法两类［9］． 在灾变时期， 为保证安全高效的救灾，救援物资车辆运输路径的 选择往往需要同时考虑多个优化目标，比如时间、成 本和风险． 首先，时间是任何紧急态势下不可忽视 的决策属性，尤其是灾变条件下，争取时间能够抢得 主动，最大限度地挽救生命和减少财产损失; 其次， 由于运输行程中不同路段的道路环境、地形条件差 异及灾害事态严重程度不同，各路段的风险不同，为 保证物资运送人员的安全，应尽量选择风险较小的 路段行驶; 此外，合理的运输调度方案有利于减少运 输周转量，从而降低运输费用，但是在紧急态势下， 由于运量大和运输时间集中等原因，常常会发生运 力紧张的状况，追求运输调度的经济性目标，能够有 效缓解运力不足的矛盾［3，10--12］． 因此，紧急态势下 的应急决策者在选择救援物资车辆运输路线时，可 能要求从救援物资支持保障中心到受灾地点运输路 线的时效性、安全性和经济性目标等多个目标的最 优化; 从受灾地点返回支持保障中心时可能只要求 运输路线的安全性和经济性实现最优化即可，虽然 也是起点到终点再返回起点的一条回路，但是救援 物资车辆由起点到终点的路线和由终点返回起点的 路线优化目标内容和数量并不统一，显然无法借助 旅行商模型求解，需要根据灾变时期路线选择的特 点建立合理的模型． 1. 2 模型建立 地面错综复杂的道路易于用图形的形式直观地 描述与表达，数学上把这种与图相关的结构称为网 络，路段抽象为图的边，路段之间的交点抽象成图的 点的集合，组成网络图的顶点，与路段相关的优化决 策指标作为有向边的权重． 紧急态势下救援物资车 辆运输路线的选择虽然需要考虑多个优化目标，但 在任何情况下，保障人员的安全都是首要的目标，相 对而言，路线的时效性、经济性等要求均可看作次要 优化目标． 为便于描述，令 G = ( V，E) 表示一张道路 网络图，V = { vi} 为 G 的节点集，E = { ( vi，vj) | ( vi， vj ) ≠( vj ，vi ) ，vi，vj"V} 为 G 的有向边集，其中 | V | = n，| E | = m; 为( vi，vj) 赋予多个不同的权重 rij和 aijk， rij为车辆在路段( vi，vj ) 上安全通过的概率，0 ＜ rij ＜ 1，aijk为车辆在路段( vi，vj ) 上行驶的时间、成本等除 安全性指标以外的其他决策指标，aijk≥0，其中 k = 1，2，…，X，X 为次要优化目标的数量． 根据前述分 析的应急救援物资车辆最佳运输路线选择的特点， 可将救援物资车辆最佳运输路线的选择分为“往” ( 支持保障中心→物资需求点) 和“回”( 物资需求 点→支持保障中心) 两个过程来求解，每个过程均 属于一个 v1→vn路线选择的多目标优化问题，其中 v1和 vn分别表示选定的起点和终点． 当 v1表示物资 支持保障中心时，vn表示受灾地点; 当 v1表示受灾地 点时，vn表示物资支持保障中心． 由于最佳运输路 线的各个优化目标之间通常存在冲突，某个目标下 的最优解对于另一个目标可能并非最优，因而需要 · 5831 ·