文摘
危险品物流的优化路线(ORHML)属于一个类称为np难的问题,和一个严格的约束使其更难解决。为了处理ORHML,一种改进的混合蚁群算法(HACA)设计。平衡风险和成本的目的,实现路线基于ACA,用来解决TSP的原则,改进HACA设计。考虑道路网和最大期望风险的能力限制,路线优化模型的总成本最小化建立基于网络流理论。改进路线建设规则和信息素更新规则算法的基础上采用前者。分析一个例子来演示应用程序的正确性。证明改进解决ORHML HACA是有效的和可行的。
1。介绍
有害物质,它有不同的物理和化学性质,在运输有很高的风险,因为在这个过程中可能出现的一系列问题。路线优化是一个复杂的组合优化问题,是一个典型的np完全问题,很难想出一个直接的答案。这是一个实际的问题急需解决,我们可以很快找到限制下的最优计划,准确、安全、经济。
危险品物流的优化路线(ORHML)可以描述如下。给定一组组成的有害物质和底层网络的节点数量和生产弧,我们希望找到一个最优路由计划船舶有害物质通过网络以最低的成本在不违反限制的能力。ORHML模型也显示为子问题在更复杂的模型,如配电系统设计和生产配送网络设计。
ORHML吸引了许多或研究人员的注意。卡拉et al。1]介绍了几路的路线规划模型。胆量和绿色2)给许多铁路的路线规划模型。Iakovou [3)提供路线规划模型的水。Miller-Hooks [4]ORHML建模作为一个随机时变网络的路径选择问题。戴尔'Olmo et al。5)发现的一个来源和目的地之间的空间不同的路径也可以被认为是在这个领域。金和出差费6)提出了一个模型,该模型考虑了风险依赖前面路段的阻抗。Erkut和绿色7]提出的边的集合的一个叫做危险品运输路线,乘坐这条路可以被视为一个概率的实验。它被认为是最小化给定OD对危险品运输网络是一个最短路径问题容易解决,即使是大型网络。他们的工作还指出,这种近似可能会导致一个非常小的测量误差发生概率在危险品运输路线(8]。
一般来说,尽管他们更现实的假设,大部分的风险模型的具体版本有一些令人费解的属性和这些模型可能并不适合危险品运输规划。我们建议研究人员和从业人员仔细地考虑风险模型的属性。
成功的蚁群算法开发了几个组合优化问题,如旅行商问题(TSP)和车辆路径问题(VRP)。
基于蚁群算法的成功应用TSP,采用一个新的ACA解决ORHML。一个协作metaheuristic方法是觅食行为的启发,真正的蚂蚁的殖民地。基本ACA应用程序是一个大量的简单人工代理能够建立良好的解决方案,通过基于底层通讯困难的组合优化问题。真正的蚂蚁在寻找食物的存放化学合作痕迹(信息素)在地板上。
2。模型分析
ORHML优化模型可以证明如下: 在哪里代表实际道路网络中,节点的集合代表了道路交叉口,电弧集表明之间的连接部分的交集。如果表示部分,那么很明显和。代表一组不同的有害物质流;代表了有害物质。代表危险物质使用弧;当有害物质代表了单位成本使用弧;当有害物质代表了单位风险使用弧。代表道路的容量约束。代表了node-arc关联矩阵作为参数(9]。
代表了供应数量或数量的需求点的有害物质,意味着供应,这意味着需求。
基于风险分析的理论,有害物质的风险在可以通过以下公式计算10]: 在哪里代表危险材料的交通事故在;代表危险物质的泄漏事故在;代表危险物质的意外损失在。={沿路的伤亡,车辆伤亡,财产损失,交通中断,疏散,环境破坏}。代表伤害所造成的损失的风险。
(1)沿路的伤亡: 在哪里代表道路的长度;代表对事故影响区域的半径灾难;代表了路边的人口密度;代表生命损失的价值。
(2)车辆的人员伤亡: 在哪里代表了公共汽车的交通流;代表汽车的交通流;代表总线的赞助;代表汽车的赞助。
(3)财产损失: 在哪里代表总线的损失价值;代表汽车的损失价值。
(4)交通中断: 在哪里代表了交通中断时间;表示单位时间内;代表的价值损失。
(5)疏散: 在哪里代表平均疏散成本。
(6)环境破坏: 在哪里代表了环境破坏的单位面积的价值。
3所示。解决的策略
HACA目标是找到最短的旅游。在HACA蚂蚁并行构建旅游,是一个参数。每只蚂蚁是随机分配到一个起始节点和建立一个解决方案,也就是说,一个完整的旅游。旅游是建立节点通过节点:每只蚂蚁迭代添加新节点,直到所有节点访问。改进过程的解决方案的策略是在算法;这种策略可以将单个蚂蚁路径解决问题。给定的多个源点,墨水点,和相应的流程,构造一个蚁群;在初始状态,蚂蚁随机分布在每个源点;蚂蚁的下一个点是随机选择。更新根据流从源点下沉点重量。当蚂蚁去源点和相应的水池,把蚂蚁到另一个源点,开始下一个搜索过程,直到所有源和汇完了,然后完成一个周期的蚂蚁。 As can be seen in Figure1(11]。
当蚂蚁位于节点选择下一个节点概率在可行的节点的集合。
HACA,原始版本的公式是
下一个节点蚂蚁的数量在节点可以选择用。在基本蚁群算法,,表示节点的数量。的价值应调整动态:
蚂蚁为代表的总和;有小路从节点;蚂蚁通过节点的数量是,是分布在轨迹与数量:
使用ant的想法,供参考精确的算法,改善的路线建设规则可以表示如下 ,称为储蓄;。变量引起的考虑时间约束。
构造两个蚁群算法实现优化的目标:最小化危险品运输的成本和风险。这两个蚁群HACA-RISK HACA-COST,用于确定最优路线。考虑到这两个在一起,我们可以找到更好的解决这个问题。在得到改进的解决方案,整个信息素更新将用于交换的信息关于解决方案的优点和缺点12]。
HACA-RISK优化过程获得可行的解决方案,使用一个更少的风险比。HACA-RISK过程是用来确定在这种情况下更短的路径。一旦发现一个新的更好的可行的解决方案,应该被更新。这两个过程将结束如果解决方案使用更少的成本。与此同时,一种新的蚁群可以建立在这个新的解决方案的基础上,重新启动一个新的互动优化过程。
如果最低成本已经想出了这个算法,HACA-RISK优化过程可以停止,然后转向HACA-COST优化过程。
HACA-COST我们引入一个整数向量;意味着倍点尚未覆盖的解决方案。这个参数应该更新相应的最优解。每当一个新的解决方案被发现,整个信息素更新应该应用于重置。
HACA-COST优化过程类似于传统HACA优化过程,是优化利用的负载能力和规模的风险。
优化过程可以分为两个部分:首先,蚂蚁之间移动的各个点在搜索最优解;第二,最优解分解为子集根据原始节点的位置,然后分配货物的风险。
蚂蚁的运动HACA-COST和HACA-RISK彼此相似。初的算法,蚂蚁是随机分布在所有节点。从初始节点,蚂蚁确定下一步行动范围内可用的点,根据概率和负荷容量和体积的限制风险。所有节点的时间和成本的虚拟原点节点0,和虚拟源节点之间没有直接的联系。一旦蚂蚁到终端节点,从而开始建设的下一个子集。遍历所有节点后,蚂蚁返回到初始节点形成一个循环,也就是说,可行的解决方案。
在HACA-COST优化过程中,一个可行的解决方案通过合作形成的蚁群。比较与如果更好,更新的值。
上述过程完成时,得到的解决方案可能仍然是不完整的(和可能错过点),插入过程是需要进一步优化。插入过程主要是处理,并没有包括在现有的解决方案。过程决定了最优可行的插入位置(每个点的最短路径),直到塞无法找到一个可行的位置(13]。
4所示。例子和分析
我们可以看到在图2,有两种危险材料(易燃液体)和(有毒气体):,从注意注意H,流是60个单位;,从注B G,流是20单位。b (A) = 60, b (H) =−60 b (b) = 20, b (G) =−20。相关的数据值如表所示1。
设置运费= 0.5元/公里/单位,元/人,人/车,人/车,元,元,h,h,元,元/小时。
,公里;,公里。风险损失的概率表中可以看到吗2。
总期望风险表所示3。
集惊吓= 0.5元/公里/单位。成本可以见表4。
针对这一问题的复杂性,整体水平优化解决方案得到了随机搜索和演化过程的基础上改进的蚁群算法。解决方案图中可以看到3。
5。总结
解决ORHML是确定路线计划,可以最低的风险和安全的前提下位置的限制。,寻求一个安全的路由方案,可以获得成本最低的条件已经知道。
一种新的基于蚁群优化的方法来解决ORHML被引入。特别是,该算法被设计来解决ORHML安全和成本之间的平衡。确定这个问题的特点,算法引入了一个新的优化多个目标函数的方法。我们考虑安全、成本的优化在同一时间。分析了差异的蚁群算法在解决ORHML限制。为了应对ORHML,改进HACA设计。确定这个问题的特点,我们一起考虑成本和风险的优化。基本思想是协调不同的蚁群的活动,它们中的每一个优化目标不同。这些殖民地的工作通过使用独立的费洛蒙但他们合作通过交换信息。此外,综合使用HACA-SAFE和HACA-COST已经应用的改进解决策略。
最后,该方法的可行性和有效性受到了实际例子。测试的问题,从结果我们可以得出结论,模型和启发式程序在解决ORHML相当成功。
承认
的研究基础科学研究的资金支持北京交通大学(项目名称:协作优化危险品运输路径选择和物流中心位置)。