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

多目标指派算法在交通救援里应用 　　摘要：交通救援是交通事故研究中最重要一环，是减少交通事故损失的关键阶段。本文通过多目标指派算法应用于交通救援体系中，从而实现交通事故损失最小化，救援总时间最少等多个目标。体现指派算法在多目标交通救援中的优越性。 　　关键词：多目标指派算法救援最优 　　中图分类号：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)等