基于网络的单应急中心选址问题的三阶段算法


第 11 卷 第 2 期 2009 年 4 月 滁 州 学 院 学 报 JOURNAL OF CHUZHOU UNIVERSI TY Vol. 11 No. 2 Apr. 2009 作者简介: 王 燃( 1966- ) , 男, 安徽滁州人, 徐州建筑职业技术学院经济管理系工程师。 收稿日期: 20081114 基于网络的单应急中心选址问题的三阶段算法 王 燃 ( 徐州建筑职业技术学院 经济管理系, 江苏 徐州 221116 ) 摘 要: 本文以降低应急中心选址费用为目标, 结合重心法、层次分析法和求解 K 短路径算法, 提出了一个求 解单应急中心选址问题的三阶段算法, 并通过实例阐述了算法的求解过程。算法中, 第一阶段使用重心法来缩 小选址范围。第二阶段中, 使用求解 K 短路径算法 KSP, 排除不满足时间紧迫性限制的候选地点。第三阶段 使用层次分析法, 根据选址费用和其它影响选址的因素, 对剩下的少数候选地点进行分析, 确定最终的选址 地点。 关键词: 单应急中心; 选址; 三阶数算法 中图分类号: TP301. 6 文献标识码: A 文章编号: 10035060( 2009) 02005903 1 引 言 消防中心和急救中心等城市应急中心的选址问题是 一类特殊的物流中心选址问题, 该类设施的选址不仅要考 虑建设费用和运输费用, 更重要的是要考虑设施的覆盖范 围和由设施到各需求点的应急时间限制。对应急中心选 址问题的研究主要包括使用重心法[1] 、层次分析法( Ana lytical H ierarchy Process, AHP) [ 2] 以及求解选址模型三种 方法[3- 7] 。 本文在对所有需求点满足时间紧迫性限制的前提下, 以系统费用( 建设费用+ 运行费用) 为指标, 建立一个单应 急中心选址模型。提出了一个解决基于网络的单应急中 心选址问题的三阶段算法, 在考虑时间紧迫性限制情况 下, 综合考虑了影响应急中心选址的各种因素。该算法结 合重心法、求解 K 短路径算法和层次分析法, 充分利用了 重心法简单和层次分析法考虑因素全面的优点, 克服了重 心解不精确和层次分析法工作量大的缺点, 是一个高效的 解决应急中心选址问题算法。最后通过数据实验, 介绍了 算法在基于网络的单应急中心选址中的应用。 2 基于网络的单应急中心选址模型 给定有向图 G= (V , E) , 其中 V = {vi | 1 i n, n 为顶 点数}, 记 V ( G) 为图 G 的顶点集, 顶点 vi 的坐标为( x i , yi ) , 在顶点 vi 建设应急中心所需要的费用为s i ; E= { ei | ei = < vp , vq > , v p 、v q V} , 记 E(G) 为图 G 的有向边集, tij 为 通过边< vi , vj > 所需时间, cij 为通过边< vi , v j > 所需费 用。Pij 为从顶点v i 到v j 的一条路径, C( P) 为通过路径 P 所发生的费用, T (P )为路径 P 所需要的时间, y 为设施的 预计使用年限, p j 为顶点 j 每年可能发生突发事件的次 数。突发事件发生时, 处理人员和设备从应急中心出发, 必须在时间 Time 内赶到事发地。从有限个候选地址中选 择一个以建设应急中心, 则为基于网络的单应急中心离散 选址问题, 其模型为: minF = !i= 1 n s i + 2 ∀ y ∀ !j #i C( Pij ) ∀ p j ∀ f i (1) st . f i = 1 在顶点 vi 建设应急中心 0 否则 (2) ! n i= 1 f i = 1 (3) T( Pij ) Time (j = 1, 2, ∃, n, i # j) (4) 其中式( 1) 为目标函数, 求应急中心建设费用和运行费用 之和为最小。式( 2) 和( 3) 限制只在一个候选地址建设应 急中心。式( 4) 为时间紧迫性限制, 要求从应急中心到每 个需求点的时间不大于给定时间 Time。 3 基于网络的单应急中心选址算法三阶段算法 顶点集合 V 为候选顶点集, 对于较大规模的离散选址 问题, 尽管可以对每个候选地点分别求出目标函数, 并从 中选最优者作为最终的设施建设地点, 但是这样未必能够 满足时间紧迫性要求, 也会使工作量很大。同时, 模型只 把费用作为设施选址的决定因素, 却没有考虑诸如社会、 经济以及技术等因素, 而这些因素也在很大程度上决定了 设施的最终选址。 因此, 作者提出一个三阶段算法来找出合适的选址 地点: 第一阶段将常用于连续选址的重心法应用于离散选 址问题, 找出一个初始地点 v0 , 以 v0 为圆心, 以 r 为半径, 圆内的所有顶点构成一个新的候选顶点集 V%。 第二阶段使用求解 K 短路径算法, 找出 V%中满足时 间紧迫性限制的顶点, 构造新的候选顶点集 V&。 第三阶段, 使用 AH P 方法对 V&进行评估, 找出最合适 的地点作为应急中心最终的建设地点。 3. 1 使用重心法构造候选顶点集 V% 设 Cij 为顶点 v i 到顶点 v j 基于费用的最短路径上的 权值, 若选择顶点 v s 为设施建设地点, 则总的运行费用如 ( 5) 式所示: Z = ! n i= 1 CisP i ( x i - x s ) 2 + ( y i - y x ) 2 (5) 当以下( 6) 式满足时, Z 的值最小。 Z x s = ! n i= 1 CisP i ( x i - x s ) ( x i - x s ) 2 + (y i - y x ) 2 = 0 Z y s = ! n i= 1 CisP i ( y i - y s ) ( x i - x s ) 2 + ( y i - y x ) 2 = 0 (6) 由( 6) 式可得: x s = ! n i= 1 Cis P ix i (x i - x s) 2 + (y i - y x ) 2 ! n i= 1 Cis P i (x i - x s) 2 + (y i - y x ) 2 y s = ! n i= 1 Cis P iy i ( x i - x s ) 2 + (y i - y x ) 2 ! n i= 1 Cis P i ( x i - x s ) 2 + (y i - y x ) 2 (7) 给出一个初始顶点 v0 , 将其坐标值( x 0 , y 0 ) 作为( x s , y s) 的值代入(7) 式, 则可以得到一个新顶点坐标( x s , y s ) 。 但是, 新顶点未必是 V 中的顶点, 这样下次迭代时, C 和 P 的值就没有意义, 为此, 当求出新顶点坐标后, 若该顶点不 是网络中的顶点, 则选取网络中距离该顶点平面距离最近 的顶点作为新的顶点, 以供下一步迭代。当两次迭代所求 得的顶点足够接近时, 迭代结束, 得到 vs * 。以顶点 v s * 为 圆心、r 为半径的圆周内的所有顶点构成新的候选点集 V%。 3. 2 从候选点顶集 V%找出满足时间紧迫性限制的候 选顶点 使用重心法得到的候选顶点集 V%中, 有些顶点可能不 满足时间紧迫性限制, 这些顶点不能成为应急中心的建设 地点。为此, 需要对候选顶点集 V%中的所有顶点作时间紧 迫性评估, 找出所有满足时间紧迫性限制的顶点, 构成新 的候选点集 V&。 为了找出满足时间紧迫性限制的顶点, 作者使用求解 网络中 K 短路径算法[ 8] 评估各候选点到其它所有需求点 时间紧迫性限制满足情况。依次对 V%中的每一个候选顶 点, 求解其到其它所有顶点间的满足时间紧迫性约束的最 短路径, 若某个候选顶点到其它的有顶点之间满足时间紧 迫性约束的最短路径均存在, 则将其置于 V&中。这样 V&中 的所顶点均为满足时间紧迫性约束的顶点, V&为新的候选 顶点集。进入第三阶段, 对 V& 中的顶点进行评估, 以找出 最佳的选址地点。 3. 3 用层次分析法确定最终选址地点 影响应急中心选的因素有很多, 通常可以归结为经济 因素、交通因素和地理因素三个方面。经济因素包括设施 的固定费用和运行费用, 固定费用涉及购买土地、拆迁补 偿以及设施本身的建设费用, 运行费用包括为维护设施的 可用性以及因处理所发生的事件而产生的费用。交通因 素主要考虑所在地的交通拥挤程度以及与外部联系的方 便程度。地理因素主要包括设施对所在地的自然和社会 环境的影响以及所在地的配套公共设施的完备程度等。 3. 3. 1 建立层次结构模型 基于以上分析建立 AH P 模型, 如图 1 所示。 图 1 应急中心选址的 AH P 模型 3. 3. 2 构造判断矩阵 层次结构建立以后, 上下层之间元素的隶属关系就确 定了。这时, 根据下层对上层的重要性赋与相应的权重。 权重若可以定量表示, 则可以直接确定, 否则就需要使用 适当的方法导出它们的权重。常用的导出权重的方法是 通过采用一定标度( 即两两比较的结果的表示方法) , 并通 过判断给出权重。根据1- 9 比例标度[9] 含义, 若同某一上 层有隶属关系的下层有 n 个元素, 分别为 B1 , B2 , ∃, Bn , 则 根据这些元素两两比较所得的值可以构成判断矩阵 A, 如 以表 1 所示。 表 1 判断矩阵 A A B1 B 2 ∃ Bn B1 a11 a12 ∃ a1n B2 a21 a22 ∃ a2n ∃ ∃ ∃ ∃ Bn an1 an2 ∃ an n 其中 aii = 1, aj i = 1 aij 。 3. 3. 3 由判断矩阵计算权重向量 根据 n 个元素 u1 , u2, ∃, un 对于其上层元素的权重 矩阵, 计算出相对权重 w1 , w 2 , ∃, w n , 由这些相对权重构 成了权重向量 = ( w1 , w 2 , ∃, wn ) T 。本文采用方根法[ 9] 求得权重向量的近似值 和权重矩阵的最大特征根的近 似值 max , 计算步骤如下: ( 1) 按以下( 8) 式计算判断矩阵中每行所有元素的几 何平均值, 得到 %= ( w%1, w%2, ∃, w%n ) T 。 w%i = n ∋ n j= 1 aij i= 1, 2, ∃, n ( 8) ( 2) 按以下( 9) 式将 %归一化, 得到 A 的特征向量的 近似值= (w 1 , w 2 , ∃, w n) T , 也就是权重向量。 wi = w%i ! n j = 1 w%j (9) ( 3) 按以下( 10) 式求得 A 的最大特征根。 max = 1 n ! n i= 1 (A) i w i = 1 n ! n i= 1 ! n j = 1 aij w j w i ( 10) 其中( A ) i 为向量 A 的第 i 个分量。 3 3 4 对判断矩阵进行一致性检验 一致性检验[ 9] 用以判断权重分配是否合理, 一致性检 验的步骤如下: ( 1) 按以下( 11) 式计算一致性指标 CI。 CI = max - n n - 1 ( 11) ( 2) 查找相应的平均随机一致性指标 R I( 见表 2) 。 60 王 燃: 基于网络的单应急中心选址问题的三阶段算法 表 2 平均随机一致性指标 RI 矩阵阶数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 RI 0 0 0 52 0 89 1 12 1 26 1 36 1 41 1 46 1 49 1 52 1 54 1 56 1 58 1 59 ( 3) 按以下( 12) 计算一致性比例 CR。 CR = CI RI ( 12) 当 CR< 0. 1 时, 认为判断矩阵的一致性是可以接受 的, 否则需要对判断矩阵进行修正, 即重新评价各元素的 权重, 以修改判断矩阵的元素值。 ( 4) 计算各层元素对目标层的合成权重 在得到每一组元素对其上一层元素的权重向量后, 需 要通过( 合成权重) [9] 得到各元素对于总目标的相对权重, 最终得到各候选地址对于目标的排序权重, 从而进行候选 地址的选择。这个过程是自上而下逐步将单准则权重进 行合成, 并逐层进行总的判断的一致性检验。 若已求出第 k- 1 层上 nk- 1 个元素相对于总目标的排 序权重向量, 记为 k- 1 = ( wk- 1 1 , wk- 1 2 , ∃, wk- 1 nk- 1 ) T , 第 k 层 上nk 个元素对第 k- 1 层上第 j 个元素为准则的排序权重 向量, 记为 p k j = ( p k 1j , p k 2j , ∃, p k nkj ) T , 其中不受支配的元素 的权重为零。令 Pk = ( p k 1 , p k 2 , ∃, p k nk- 1 ), 这是一个 nk ∀ nk- 1 的矩阵, 表示第 k 层元素对第 k - 1 层各元素的排序, 则可通过以下(13) 式或(14)式求得第 k 层元素对总目标的 合成排序向量k 。 k = ( wk1 , wk2 , ∃, w knk ) T = Pkk- 1 ( 13) w ki = ! nk- 1 j = 1 p kij w k- 1j ( i = 1, 2, ∃, n) ( 14) 通过上述步骤( 1) ~ ( 4) , 最终可以得到每个候选地址 对于总目标的权重, 权重最大的候选地址即为所要选择的 应急中心最终的建设地址。 4 数据实验 下面通过在一个有 29 个顶点的无向图中的选址问 题, 说明本文选址算法的操作过程。 在考虑图 1 中所有因素和时间紧迫性限制的情况下, 从这些顶点中选择一个顶点用以建设应急中心, 应急中心 到各顶点之间必须满足的时间紧迫性限制为 11 个单位时 间, 即应急中心到每个顶点的时间不得超过 11 个单位。 在第一阶段, 使用重心法求得顶点坐标为( 97, 134) , 即顶点 v13 , 以 40 为半径, 则 V%= { v1 , v 2 , v4 , v10 , v13 , v15 , v16, v19 , v 20 , v24, v26 }。 第二阶段中, 使用求解 K 短路径算法求得 V%中的各 顶点与其它各顶点之间的限制最短路径。方法为: 通过求 每个顶点到候选顶点之间的基于费用的前 30 短路径。若 某候选顶点到某个需求点的 30 条路径均不满足限制, 则 剔除该候选点。由此, 得到 V&= {v 4 , v 10 , v15 , v16 , v 19 } 。V& 中各候选点到其它顶点的时间及费用见表 3。其中, time 为候选点到其它所有顶点满足时间紧迫性限制的最短路 径所需时间之和, w eight= 2 ∀ 单程费用∀ 顶点需求量。 表 3 候选顶点时间和费用 候选点 tim e w eight v4 176 5 21449 8 v 10 190 3 20509 2 v 15 213 5 25006 4 v 16 162 3 24701 0 v 19 191 9 23722 8 第三阶段, 进行 AHP 分析, 从V&中选一个最佳地点作 为应急中心的建设地址。 根据图 1 的层次模型, 对影响选址的各因素进行综合 评价, 得出各因素的相对权重, 建立判断矩阵、求出权重向 量, 并检验各矩阵的一致性。最终得到: ( 3) = P( 3) ∀ ( 2) = ( 0 25, 0 16, 0 07, 0 33, 0 17) T , 候选地址对目标层的最 大权重为 0 33, 由表 3 可知, 最大权重对应的候选地址为 v16 。因此, 最终选择 v16 作为应急中心的建设地点。这样, v16 的建设费用和运行费用之和即为目标函数式(1)的值。 5 结束语 本文对单应急中心选址问题进行了研究。基于重心 法、层次分析法和求解 K 短路径求解算法, 提出了一个求 解网络中单应急选址问题的三阶段算法。最后通过一个 有 29 个顶点的网络选址实例, 说明了算法的执行过程。 算法中, 第一阶段, 使用重点法缩小候选地址数。将 用于连续选址问题的重心法应用于网络中的离散选址, 以 重心法所求得的地址周围一定距离范围内的候选地址构 成新的候选地址集。第二阶段, 使用求解 K 短路径算法将 候选地址集中不满足时间紧迫性限制的顶点剔除, 从而进 一步缩小了候选地址集。第三阶段, 综合考虑影响应急中 心选址的诸多因素, 使用层次分析法对剩余候选地址集进 行分析, 最终确定选址地点。这一算法充分利用了重心法 和 AHP 的优点, 很好地解决了重心法考虑因素过少以及 使用 AHP 对所有候选点都进行分析工作量过大的问题。 本文的工作可以很好地解决小城市诸如消防中心、 120 急救中心等单一应急中心的选址问题。 对于较大城市中, 存在多个应急中心的选址问题, 由 于较大城市一般都按地域划分成若干个区, 每个区域内建 造一个相应的应急中心, 因此也可以通过多次使用本文算 法来解决较大城市的应急中心选址问题。 [ 参 考 文 献] [ 1] 方 磊, 何建敏. 综合 AH P 和目标规划方法的应急系统选址 规划模型[ J] . 系统工程理论与实践, 2003, 12: 116- 120. [ 2] 方 磊. 基于偏好 DEA 的应 急系统选 址模型研 究[ J] . 系统 工程理论与实践, 2006, 8: 116- 122. [ 3] 方 磊, 何建 敏. 城 市应 急 系统 优 化选 址决 策 模型 和 算法 [ J] . 管理科学学报, 2005, 8( 1) : 14- 18. [ 4] 方 磊, 何建敏. 应急 系统优化 选址的 模型及 其算 法[ J] . 系 统工程学报, 2003, 18( 1) : 49- 54. [ 5] 魏宝红, 杨茂盛. 基于 遗传算法 的应急 系统选 址优 化[ J] . 铁 道运输与科技, 2006, 28( 1) : 76- 80. [ 6] 陈志宗, 尤建新. 重 大突发事件 应急救援 设施 选址的 多目标 决策模型[ J] . 管理科学, 2006, 19( 4) : 10- 14. [ 7] H arew ood S I. Em ergency Ambulance Deploym ent in Barba dos: a Multi- Objective Approach[ J] . Journal of the Opera tional Research Society ,2002, 53, 185- 192. [ 8] 戴树贵, 陈文兰. 一 个求解 k 短路径 实用算 法[ J] . 计 算机工 程与应用, 2005, 36: 63- 65. [ 9] ∗ 运筹 学+教 材 编 写组 编. 运 筹学 [ M ] . 清 华 大 学 出版 社, 1990, ( 2) . 61 王 燃: 基于网络的单应急中心选址问题的三阶段算法
还剩2页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 20 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf