救援车辆多目标实时路径规划模型

王晓刚 韩印

摘要：针对救援车辆路径选择的多目标属性，文章从路径安全性、最小化行程时间、行程时间可靠性的角度出发，构建实时环境下救援车辆的多目标实时路径选择模型。采用加权求和法对将多维目标聚合为单个目标，提高路径搜索效率。模型所求得的最优路径为综合最优路径，反映了救援车辆路径选择的多目标属性，克服了以往路径规划单目标属性的缺陷。给出算法，通过算例验证模型的有效性。

关键词：多目标;路径选择模型;加权求和法;A*算法

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

0引言

由于物流供应链的重要性，对于最短路径问题，研究者做了大量的研究。然而，作为最短路径分支的实时最短路径问题研究的并不是很多。在大多数的研究中，将路网简化为简单图，两节点之间的路阻被认为是不变的或者是完全等同于两节点之间的距离。然而，由于事故或交通拥堵，不同节点间的行程时间往往是不同的。所以，实时路径规划问题比较符合实际。Malan-drak首次提出了实时路径规划问题，他提出了路段行程时间的阶跃函数分布，以量化实时路段行程时间。此后，一些研究者开始研究实时路径规划问题。如Ichoua等提出实时车速模型，符合先进先出原则并且使用禁忌启发式搜索算法求解。Hashimoto等提出了带软时间窗的实时最短路径的时间、费用模型。

由于时间资源的限制，救援团队必须尽可能快的到达事故现场，所以紧急救援实时路径选择问题不同于一般车辆成本最小的路径选择，必须满足时效性的要求。紧急救援路径选择问题已经被广泛的研究，最初的研究者Rathi等考虑时间窗约束条件下的多物资供应线性规划模型。陈达强等以出救车辆路径的通行时间最小化及其对应的通行可靠度最大化为目标，建立单出救点单需求点的紧急救援路径优化模型。Qzdamar等提出紧急救援路径规划的数学模型，他们认为实时环境下的救援物资供需关系和救援车队规模是动态促进的关系。Ukkusuri and Yushimito在运输网络存在中断的情况下，对设施位置和救援路径选择问题进行建模。Yuan and Wang针对紧急救援路径选择问题提出了双层规划模型，他们构建的路段行程速度函数是随着时间的增加而减少的。魏航等提出了在紧急救援的情况下建立时间随机变化的随机规划模型，来进行紧急救援车辆的路径选择。在紧急救援物流管理中，有许多其它的研究，如Berkoune。

然而，在紧急救援实时路径选择中，由于交通拥堵、灾后交通基础设施破坏等情况，救援路径的可靠性没有得到研究者的广泛关注。Vitoriano等提出了紧急救援中物资分配的数学模型，综合考虑了成本、时间、公平性、优先级、可靠性和安全性的多准则优化模型。Hamedi等考虑在时间依赖网络上选择可靠的路径来运送救援物资，并采用组合权重法将多目标优化问题转化为单目標优化问题。Wang等针对救援物资分配问题，将行程时间、费用、路段可靠性作为目标函数，并利用非线性整数规划模型进行求解。Liberatore等将救援车辆历史数据的分布转化为路径的安全性、可靠性。王一军等考虑救援车辆车队的规模，并且根据单出救点多救援点为其安排合理的路径。

本研究基于救援车辆多目标实时路径选择，先对路径所满足的先入先出原则进行阐述。然后提出最优路径选择模型，为提高路径搜索的效率，本文采用启发式A*算法进行模型求解。最后通过实际案例进行仿真，以验证路径选择的有效性。

2案例分析

将某城市道路网络简化，利用vIssIM进行仿真，改变各目标权值，寻找最优路径。对65个测试路段和28个节点，车流量、速度等实验数据以文本形式实时读入。为验证本模型的有效性，将多目标最短路径选择模型分别从路径安全性、行程时间可靠性、行程时间等三方面与基于几何最短路径选择模型进行对比。

本文以文本形式实时输入交通量，为验证本文紧急救援多目标实时路径选择模型的有效性，在相同环境下，时间权重系数以0.1为间隔进行取值，在不同的时间权重进行求解。

最终结果，随着时间权重的增加，时间决策的比例在逐渐增大，同时路径平均风险值、路径行程时间可靠度决策变量的所占决策比例在组件变少，所以最优路径的行程时间在逐渐减少，而路径风险值在渐渐增加，路径的行程时间可靠度在逐步下降。而当路径的行程时间权重大于0.7时，路径的行程时间基本不再增加，而路径的风险值却随着路径行程时间权重的增加而不断变大，路径的行程时间可靠度变化不大，这种情况下，由不同的权重系数得到差别不大的优化结果，是结果重合的现象，此时说明最优路径具有唯一性，优化结果更加符合多目标组合优化函数的有效性及合理性。

3结论

对于紧急救援而言，在突发事件不是特别紧急的情况下，可以适当增加路径行程时间可靠度、路径平均风险值的权重，以确保进行有效的救援。而发生重大突发事件的情况下，必须增加时间权重，尽可能以最短的时间进行有效的救援，避免重大的人员财产损失。所以基于多目标的紧急救援实时路径选择更加能满足紧急救援路径选择的多样性。