多目标指派算法在交通救援里的应用

摘要：交通救援是交通事故研究中最重要一环，是减少交通事故损失的关键阶段。本文通过多目标指派算法应用于交通救援体系中，从而实现交通事故损失最小化，救援总时间最少等多个目标。体现指派算法在多目标交通救援中的优越性。

关键词：多目标指派算法救援最优

中图分类号：U491文献标识码：A

Multi-objective Assignment Algorithm Is Applied To Traffic Rescue

Lizhibing 1Wuerfa

（Guizhou Branch of CCCC Consulants CO. Ltd（HPDI), Guiyang，550003）

Abstract: Rescue is the most important part of Traffic Accident，it is critical stage of the loss of reducing traffic accidents. In this thesis, multi-objective algorithm is used to assign traffic Rescue System, in order to achieve minimum loss of traffic accidents, rescue and other targets at least total time, Assigned to the superiority of the algorithm used in multi-objective traffic rescue.

Keywords: multi-target; assignment algorithm; accident rescue; optimzation

一、引言

随着社会经济的迅速发展，人们的出行次数和汽车保有量急剧增加，加上道路设施和规划发展相对滞后，交通事故不断发生，因交通意外造成的伤亡人数逐年增加。2009年底已超过10万人，其中相当一部分是因为事故救援不力而引起的。同时，由于救援工作的效率欠缺，给原本就十分紧张的交通状况雪上加霜。交通事故救援体系的研究旨在提高效率，减少延误与事故损失。交通事故的发生通常具有偶然性、随机性的特点。

本文着重救援物资的派遣方面来研究交通救援体系，通过多指标指派算法，得出最佳方案，以使救援总成本最少，效益最大。

二、问题的提出

传统的指派问题所求解的目标是单一的，而在实际问题中，往往需要考虑的因素较多。如在城市紧急救援过程中，如何指派n个不同的救援车辆去完成n项不同的救助任务，这时既要考虑各救援车辆完成任务总费用，还要考虑各救援车辆在完成任务过程的总时间，及救援的可靠性、安全性等。这样的问题就属于多目标的指派问题，其数学模型为多目标的0~1整数规划。目前解决多目标问题往往是将多目标转化为单目标来求解，常用的方法有线性加权和法、乘除法、主要目标法等。然而，线性加权和法要求所有目标必须具有相同量纲；乘除法当目标数较多时显得复杂；而主要目标法在几个目标孰轻孰重难以判断时也不便使用。基于此，本文运用模糊数学的思想，将多目标指派问题与模糊数学思想相结合，将各目标下的属性值矩阵转化为模糊关系矩阵，再将模糊关系合成矩阵与解决传统指派问题的匈牙利方法相结合，提出了模糊匈牙利的求解方法，说明了该方法的在救援体系中的应用。

三、多目标指派问题的数学模型

设有n项需同时进行的不同任务，恰好有n个人可承担，完成这些任务需要考虑的指标(目标)有m个，由于每个人的专长不同，在第k个目标下，第i个人完成第j项任务时的目标属性值为。问应指派哪个人去完成哪项任务，可使完成n项任务所考虑的各目标均最优。

取0~1变量 令

这样，多目标指派问题的数学模型可写成

模型（1）：

式中， 值越大越优的目标表示max(取最大值)；值越小越优的目标表示min(取最小值)。

四、多目标指派问题的模糊匈牙利求解方法

由在目标k条件下第i个人完成第j项任务时的目标属性值为 ，得到在目标k条件下的属性值矩阵 ：

，；（1）

根据矩阵 求出在目标k条件下的各属性值对优的相对隶属度 ，对值越大越优目标和值越小越优目标分别按式(2)与式(3)计算

， ， （2）

， ， （3）

式(2)与(3)中， 与 分别表示矩阵 中元素的最大值和最小值。根据式(2)和式(3)将属性值矩阵 变为在目标点条件下关于优的模糊关系矩阵

由德尔斐法(Delphi)或层次分析法(AHP)等方法确定目标权向量 ，令

， ，（4）

称 为综合考虑m个目标后各属性值对优的合成相对隶属度。这样 个 组合成多目标模糊关系合成矩阵。

（5）

将式（5）作为传统指派问题中的效率矩阵，由于式(5)中的元素值越大越优，即使目标值最大，而匈牙利法仅限于最小化的指派问题，故可将模型1转化为以下模型2，再应用匈牙利方法进行求解。

模型2：

其中， 为式（5）中的最大值

五、多目标指派问题在紧急救援中的应用

某区域需要4辆救援车（分别记为A1，A2，A3，A4）向4个救援点（分别记为B1，B2，B3，B4）进行救援。由于救援任务的因素很多，如总费用，到达目的地的总时间，假设各目标经综全考虑后可用百分比量化。设各目标量化值如表所示，研究救援车辆如何指派。

各目标量化值表

总费用（万元） 时间（min）

B1 B2 B3 B4 B1 B2 B3 B4

A1 3 10 2 5.6 20 25 18 27

A2 1.8 12 1.6 4.5 10 15 25 16

A3 2.5 9.5 2.5 3.3 24 28 8 22

A4 2 10 1.5 6.2 30 16 20 19

由表中的数据可得到2个目标条件下的属性值矩阵 ， 分别为

由于时间目标和总费用是值越小越优，所以相对隶属度选用式(3)，目标权向量假设取为等权重，即 。最后分别求出在2个目标条件下关于优的模糊关系矩阵和模糊关系合成矩阵分别为：

运用匈牙利法变换模糊关系合成矩阵 如下

从而可得最优解为：

这表明救援车车辆应A1指派B3，A2指派B1，A3指派B4，A4指派B2最优。从而使救援社会效益费用总大，救援总时间总少。

六．结语

本文针对道路救援问题，采用多目标指派数学模型求解，从实例来看，多目标指派数学模型在多目标救援体系中可以得到最优解，且效益最大，费用时间最省，实际应用较好。本文的研究仅是从一个侧面反映了救援的情况，当引入更多目标变量时，更能体现多目标指派算法的优越性。

参考文献：

[1] 钱颂迪.运筹学[M].北京.清华大学出版社. 2005

[2] 李士勇.工程模糊数学及应用[M].哈尔滨: 哈尔滨工业大学出版社,2004

[3] 刘杨等.应急车辆出行前救援路径选择的多目标规划模型[J].公路交通科技 2009.8

注：文章内所有公式及图表请以PDF形式查看。