基于蚁群算法的应急物资调度系统的研究与开发

符志强++罗丹丹

摘要：近年来，随着工业化及城市化进程的加剧，各种大规模自然灾害、公共卫生事件正越来越频繁地侵袭着我们生存的世界。该文以蚁群算法（Ant Colony Optimization，ACO）和应急物资调度系统相结合，创造一个高效的紧急救援系统。系统主要有物资模块管理，城市信息管理，配送车辆管理，紧急呼救等功能。系统采用模块化设计，采用轻量级企业框架（struts2+spring3+hibernate3）开发，具有结构清晰，易于扩展的优点。

关键词：应急物资调度；蚁群算法；救援系统

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）18-4255-03

The Logistics Distribution Route research of Ant Colony Algorithm

FU Zhi-qiang， LUO Dan-dan

（Information Science And Technology Department Zhongkai University of Agricultural and Technology， Guangzhou 510225， China）

Abstract： In recent years， large-scale natural disasters and public health events are becoming more frequent invasion of the world with the industrialization and city urbanization intensifies. In this paper， ant colony algorithm （Ant Colony Optimization， ACO） is used in emergency supplies scheduling system to create an efficient emergency rescue system. System mainly supplies module management， city information management， vehicle management and call emergency function. The system adopts modular design and has the advantage of clear structure and easy extension.

Key words： emergency supplies scheduling； ant colony algorithm； rescue system

近年来，随着工业化及城市化进程的加剧，各种大规模自然灾害、公共卫生事件正越来越频繁地侵袭着我们生存的世界，影响、威胁着我们的生活甚至生命。这些大规模突发性公共事件具有受影响面积大、范围广、持续时间长、受灾人群多、应急需求点多、应急物资需求量大、应急物资供应不足等特点。这些特点决定了突发事件应急物资的调度的复杂性远远超出通常物资调度的调度。为适应大规模突发事件越来越频繁的现状，研究大规模突发事件应急物资的调度，为大规模突发事件的应急决策提供依据也就成为一项急迫的课题。

大规模突发事件应急物资需求量过大，因此在应急初期的物资调度任务是如何筹集并尽快地把应急物资运送到各应急需求点，调度方式是根据供应量的多少采取推动式的物资调度模式；而随着物资供应渠道的拓宽，在应急中期应急物资供需能基本匹配，这时应急调度的任务是每个出救点应调度多少应急物资到相应的应急需求点；到了应急后期，随着筹集渠道的进一步加宽，应急物资的供应点和供应量更为充分，因此应急物资调度的任务就转化为应急供应点和相应供应量的选择，应急调度的方式也转化为根据应急需求点的需求采取拉动式的物资调度模式。本系统就是采用蚁群算法，将其应用到应急物资的调度上，为物资调度系统提供物资运输及救援的最优路径。

1 蚁群算法优化

蚁群算法模拟蚂蚁群体觅食行为的蚁群，是群智能算法的一种。设有n个被救援点，在一次迭代中有m只蚂蚁，用dij表示当前所在被救援点和下一个目标网点之间的距离，τij（t）表示在时刻t当前所在网点和下一目标网点之间的信息素浓度。蚂蚁k在选择下一网点时，在各条可行的路径上的信息素的浓度以及网点间的距离长度基础上得出每条路径的转移概率，并由随机数来决定蚂蚁k所到达的下一个网点，同时用禁忌表来记录蚂蚁k当前所走过的网点，用pijk （t）表示在t时刻蚂蚁k由当前所在网点转移到下一目标网点的状态转移概率，其表达式为：

ρ为信息素挥发速度系数，其计算方法也可以根据实际的需要进行调整[4-7]。

参数蚂蚁的数目m：在蚁群算法中每一只蚂蚁的运动都是相互独立的，只是通过每一只蚂蚁走过后留下的信息素浓度来相互影响。蚂蚁的数量越多，算法的可参考性越强，但是蚂蚁过多带来的问题是其计算量相应的加大，所以蚂蚁的数量要控制在一定的范围之内。仿真试验结果表明，当网点规模大致是蚂蚁数目的1.5倍时，蚁群算法的全局收敛性和收敛速度都比较好。

信息素挥发速度ρ表示在蚂蚁搜索过程中的经验与探索对路径影响的比重，表1是α=1，β=5时，各种ρ值计算出的30个城市最优值和平均值。

从表1中的数据可以得知，ρ值总体来说在0.1到0.2之间达到最优。为了实现尽快收敛并保证不陷入局部最优，对ρ值在计算中进行动态调整。在算法开始时为了避免蚂蚁很快陷入局部最优，调整ρ=0.2，减少历史因素对蚂蚁探索路径的影响，避免局部最优解；在算法后期调整ρ=0.1，使算法能够快速收敛，达到即时给出最优解的要求。endprint

在CPU为i3 530的计算系统上，当网点数目少于30个规模时，算法均在5秒内给出计算结果。

2 系统设计

灾害发生时需要大量的应急物资救助伤员、安置灾民，在赈灾时人们面对的一个重要问题便是如何有效地利用有限的运输工具向受灾区域及时运输大量赈灾物品，如药品、医疗器械、救生设备、食品、衣物、帐篷等，以最大程度的缓解灾情，降低群众的损失。为此，将系统分为以下四个模块。

1）路径优化模块，将蚁群其封装成代码以便调用，测试该代码的效率，将代码进行优化，此部分主要要是测试和优化蚁群算法的收敛性。

2）物资管理模块的设计：包括物资分类的管理，物资信息的管理及物资进出仓的管理。一个物资分类下有多个物资信息，一张物资进出仓单中有多份进出仓明细单，每张明细单都有一类物资信息。每类物资都有规定最小库存量，当某物资库存量小于最低库存量时，系统应该自动提示警告，通知物资管理员尽快添加该物资。

3）城市管理模块：主要包括了城市信息管理，城市间距离管理（即时调整受灾不能通行道路的距离和恢复通行的道路）。城市信息设置最核心的内容便是标记受灾城市以及受灾城市的优先级，标记受灾城市是通过改变城市的状态属性来实现的，被标记为受灾城市将参与获取最优路径的计算。城市的优先级主要是用来确定哪个城市优先进行物资配送救援的。优先级越高的表示灾情越严重，救援越优先。

4）车辆管理模块：主要包括车辆信息管理和车队信息管理，车辆管理最主要的功能是对其状态的管理。使用车辆时一般是先构建一个车队，一个车队有一到若干辆车，车队的构建必须填写车队任务，并且在任务结束后自动将车辆状态改回原来的“空闲”以便下次使用。

3 系统的实现

应急物资调度系统前台页面主要为普通用户提供服务，主要实时救灾信息和一键呼救功能，包括即时消息，灾区新闻，滚动新闻，一键呼救，自救知识，救援知识，物资调度情况等。如图1所示。

后台主要为救灾调度中心服务，主要有以下功能

1）物资分类管理

衣/食/住/行—根据物资类型判断物资优先级，即是物资所需的紧急程度。物资优先级高的在运送时应较快安排调度，在库存紧张时应优先补充。一种物资分类下有一到若干种物资。

2）物资基本资料管理

物资的名称、单价、库存量等管理。每个物资都有自己所属的物资分类，该物资的优先等级等于其物资分类的优先等级，其最主要的管理便是物资库存量和最低库存量的管理。国家规定紧急救援物资的储存数量必须不小于该物资最大需求量的1.3倍，否则若因物资不足导致无法进行及时救援，那么将依法追究管理人员的责任。

3）物资进出仓管理

物资每一次进/出仓都有一个进出仓记录（称进/出仓单），每张进/出仓单下有包括一张或多张进/出仓明细单，记录此次进/出仓的物资量。

物资进仓：只有系统中存在的物资类别才能进行进仓设置，若是新物资种类进仓，必须先在物资信息管理模块中添加该物资信息；物资出仓：出仓的物资数量不能高于该物资的库存量，若是该物资出仓数量巨大，导致物资库存量小于最低库存量时，应该提醒系统管理员及时补充该物资。

系统的功能有物资分类管理，城市管理，车辆管理，最优路径管理，如图2所示。

根据受灾情况的信息，先取出所有受灾城市及所有断开的路径。对道路受到灾情影响的城市，根据其道路的受损程度，实时更改其网点间的距离。距离改变后，即刻调用蚁群算法进行新的路径计算，给出最优路径，如图3所示。实验表明，受灾网点规模在30个以下时，取蚁群算法迭代次数为80次，系统可在5秒钟内得到最优值。

4 结论

应急物资调度系统以蚁群算法为核心，基于struts2+Spring+Hibernate框架开发，创造一个高效的紧急救援系统。系统主要有

物资模块管理，城市信息管理，配送车辆管理，紧急呼救等功能。在实际的应急物资调度过程中，由于时间与车辆的受限，同时也受限于交通状况和通讯状况的影响，所以还要考虑各种受限参数，这就需要对路况和车辆拥挤情况进行统计分析，合理调整参数，这些工作有待进一步深入研究。

参考文献：

[1] Groves G，Roux J le，van Vuuren JH.Network service scheduling and routing[J]. International Transactions in Operational，2004（11）：613-643.

[2] Dorigo M，Stützle T.Ant Colony Optimization[M].Cambridge MA： MIT Prcss，2004.

[3] Wang Yuting，Sun Jian，Li Junqing.Hybrid Heuristics Based on Harmony Search and Simulated Annealing Algorithm for Traveling Salesman Problem[J].Computer Applications and Software， 2009（10）.

[4] Zhao Jidong， Hu Xiaobing， Liu Haobin.Improved ant colony algorithm and its application in TSP[J].Computer Engineering and Applications，2010，46（24）：51-52.

[5] Merkle D，Middendorf M.Modeling the dynamics of ant colony optimization[J]. Evolutionary Computation. 2002，10（3）：235-262.

[6] Fu Zhiqiang，Liu Leian.Improved Ant Colony Optimization and Application on Tsp[J]. American Journal of Engineering and Technology Research， 2011（11）.

[7] 符志强，刘磊安.基于蚁群算法的物流配送优化系统设计[J].现代计算机，2014（2）.endprint

在CPU为i3 530的计算系统上，当网点数目少于30个规模时，算法均在5秒内给出计算结果。

2 系统设计

灾害发生时需要大量的应急物资救助伤员、安置灾民，在赈灾时人们面对的一个重要问题便是如何有效地利用有限的运输工具向受灾区域及时运输大量赈灾物品，如药品、医疗器械、救生设备、食品、衣物、帐篷等，以最大程度的缓解灾情，降低群众的损失。为此，将系统分为以下四个模块。

1）路径优化模块，将蚁群其封装成代码以便调用，测试该代码的效率，将代码进行优化，此部分主要要是测试和优化蚁群算法的收敛性。

2）物资管理模块的设计：包括物资分类的管理，物资信息的管理及物资进出仓的管理。一个物资分类下有多个物资信息，一张物资进出仓单中有多份进出仓明细单，每张明细单都有一类物资信息。每类物资都有规定最小库存量，当某物资库存量小于最低库存量时，系统应该自动提示警告，通知物资管理员尽快添加该物资。

3）城市管理模块：主要包括了城市信息管理，城市间距离管理（即时调整受灾不能通行道路的距离和恢复通行的道路）。城市信息设置最核心的内容便是标记受灾城市以及受灾城市的优先级，标记受灾城市是通过改变城市的状态属性来实现的，被标记为受灾城市将参与获取最优路径的计算。城市的优先级主要是用来确定哪个城市优先进行物资配送救援的。优先级越高的表示灾情越严重，救援越优先。

4）车辆管理模块：主要包括车辆信息管理和车队信息管理，车辆管理最主要的功能是对其状态的管理。使用车辆时一般是先构建一个车队，一个车队有一到若干辆车，车队的构建必须填写车队任务，并且在任务结束后自动将车辆状态改回原来的“空闲”以便下次使用。

3 系统的实现

应急物资调度系统前台页面主要为普通用户提供服务，主要实时救灾信息和一键呼救功能，包括即时消息，灾区新闻，滚动新闻，一键呼救，自救知识，救援知识，物资调度情况等。如图1所示。

后台主要为救灾调度中心服务，主要有以下功能

1）物资分类管理

衣/食/住/行—根据物资类型判断物资优先级，即是物资所需的紧急程度。物资优先级高的在运送时应较快安排调度，在库存紧张时应优先补充。一种物资分类下有一到若干种物资。

2）物资基本资料管理

物资的名称、单价、库存量等管理。每个物资都有自己所属的物资分类，该物资的优先等级等于其物资分类的优先等级，其最主要的管理便是物资库存量和最低库存量的管理。国家规定紧急救援物资的储存数量必须不小于该物资最大需求量的1.3倍，否则若因物资不足导致无法进行及时救援，那么将依法追究管理人员的责任。

3）物资进出仓管理

物资每一次进/出仓都有一个进出仓记录（称进/出仓单），每张进/出仓单下有包括一张或多张进/出仓明细单，记录此次进/出仓的物资量。

物资进仓：只有系统中存在的物资类别才能进行进仓设置，若是新物资种类进仓，必须先在物资信息管理模块中添加该物资信息；物资出仓：出仓的物资数量不能高于该物资的库存量，若是该物资出仓数量巨大，导致物资库存量小于最低库存量时，应该提醒系统管理员及时补充该物资。

系统的功能有物资分类管理，城市管理，车辆管理，最优路径管理，如图2所示。

根据受灾情况的信息，先取出所有受灾城市及所有断开的路径。对道路受到灾情影响的城市，根据其道路的受损程度，实时更改其网点间的距离。距离改变后，即刻调用蚁群算法进行新的路径计算，给出最优路径，如图3所示。实验表明，受灾网点规模在30个以下时，取蚁群算法迭代次数为80次，系统可在5秒钟内得到最优值。

4 结论

应急物资调度系统以蚁群算法为核心，基于struts2+Spring+Hibernate框架开发，创造一个高效的紧急救援系统。系统主要有

物资模块管理，城市信息管理，配送车辆管理，紧急呼救等功能。在实际的应急物资调度过程中，由于时间与车辆的受限，同时也受限于交通状况和通讯状况的影响，所以还要考虑各种受限参数，这就需要对路况和车辆拥挤情况进行统计分析，合理调整参数，这些工作有待进一步深入研究。

参考文献：

[1] Groves G，Roux J le，van Vuuren JH.Network service scheduling and routing[J]. International Transactions in Operational，2004（11）：613-643.

[2] Dorigo M，Stützle T.Ant Colony Optimization[M].Cambridge MA： MIT Prcss，2004.

[3] Wang Yuting，Sun Jian，Li Junqing.Hybrid Heuristics Based on Harmony Search and Simulated Annealing Algorithm for Traveling Salesman Problem[J].Computer Applications and Software， 2009（10）.

[4] Zhao Jidong， Hu Xiaobing， Liu Haobin.Improved ant colony algorithm and its application in TSP[J].Computer Engineering and Applications，2010，46（24）：51-52.

[5] Merkle D，Middendorf M.Modeling the dynamics of ant colony optimization[J]. Evolutionary Computation. 2002，10（3）：235-262.

[6] Fu Zhiqiang，Liu Leian.Improved Ant Colony Optimization and Application on Tsp[J]. American Journal of Engineering and Technology Research， 2011（11）.

[7] 符志强，刘磊安.基于蚁群算法的物流配送优化系统设计[J].现代计算机，2014（2）.endprint

在CPU为i3 530的计算系统上，当网点数目少于30个规模时，算法均在5秒内给出计算结果。

2 系统设计

灾害发生时需要大量的应急物资救助伤员、安置灾民，在赈灾时人们面对的一个重要问题便是如何有效地利用有限的运输工具向受灾区域及时运输大量赈灾物品，如药品、医疗器械、救生设备、食品、衣物、帐篷等，以最大程度的缓解灾情，降低群众的损失。为此，将系统分为以下四个模块。

1）路径优化模块，将蚁群其封装成代码以便调用，测试该代码的效率，将代码进行优化，此部分主要要是测试和优化蚁群算法的收敛性。

2）物资管理模块的设计：包括物资分类的管理，物资信息的管理及物资进出仓的管理。一个物资分类下有多个物资信息，一张物资进出仓单中有多份进出仓明细单，每张明细单都有一类物资信息。每类物资都有规定最小库存量，当某物资库存量小于最低库存量时，系统应该自动提示警告，通知物资管理员尽快添加该物资。

3）城市管理模块：主要包括了城市信息管理，城市间距离管理（即时调整受灾不能通行道路的距离和恢复通行的道路）。城市信息设置最核心的内容便是标记受灾城市以及受灾城市的优先级，标记受灾城市是通过改变城市的状态属性来实现的，被标记为受灾城市将参与获取最优路径的计算。城市的优先级主要是用来确定哪个城市优先进行物资配送救援的。优先级越高的表示灾情越严重，救援越优先。

4）车辆管理模块：主要包括车辆信息管理和车队信息管理，车辆管理最主要的功能是对其状态的管理。使用车辆时一般是先构建一个车队，一个车队有一到若干辆车，车队的构建必须填写车队任务，并且在任务结束后自动将车辆状态改回原来的“空闲”以便下次使用。

3 系统的实现

应急物资调度系统前台页面主要为普通用户提供服务，主要实时救灾信息和一键呼救功能，包括即时消息，灾区新闻，滚动新闻，一键呼救，自救知识，救援知识，物资调度情况等。如图1所示。

后台主要为救灾调度中心服务，主要有以下功能

1）物资分类管理

衣/食/住/行—根据物资类型判断物资优先级，即是物资所需的紧急程度。物资优先级高的在运送时应较快安排调度，在库存紧张时应优先补充。一种物资分类下有一到若干种物资。

2）物资基本资料管理

物资的名称、单价、库存量等管理。每个物资都有自己所属的物资分类，该物资的优先等级等于其物资分类的优先等级，其最主要的管理便是物资库存量和最低库存量的管理。国家规定紧急救援物资的储存数量必须不小于该物资最大需求量的1.3倍，否则若因物资不足导致无法进行及时救援，那么将依法追究管理人员的责任。

3）物资进出仓管理

物资每一次进/出仓都有一个进出仓记录（称进/出仓单），每张进/出仓单下有包括一张或多张进/出仓明细单，记录此次进/出仓的物资量。

物资进仓：只有系统中存在的物资类别才能进行进仓设置，若是新物资种类进仓，必须先在物资信息管理模块中添加该物资信息；物资出仓：出仓的物资数量不能高于该物资的库存量，若是该物资出仓数量巨大，导致物资库存量小于最低库存量时，应该提醒系统管理员及时补充该物资。

系统的功能有物资分类管理，城市管理，车辆管理，最优路径管理，如图2所示。

根据受灾情况的信息，先取出所有受灾城市及所有断开的路径。对道路受到灾情影响的城市，根据其道路的受损程度，实时更改其网点间的距离。距离改变后，即刻调用蚁群算法进行新的路径计算，给出最优路径，如图3所示。实验表明，受灾网点规模在30个以下时，取蚁群算法迭代次数为80次，系统可在5秒钟内得到最优值。

4 结论

应急物资调度系统以蚁群算法为核心，基于struts2+Spring+Hibernate框架开发，创造一个高效的紧急救援系统。系统主要有

物资模块管理，城市信息管理，配送车辆管理，紧急呼救等功能。在实际的应急物资调度过程中，由于时间与车辆的受限，同时也受限于交通状况和通讯状况的影响，所以还要考虑各种受限参数，这就需要对路况和车辆拥挤情况进行统计分析，合理调整参数，这些工作有待进一步深入研究。

参考文献：

[1] Groves G，Roux J le，van Vuuren JH.Network service scheduling and routing[J]. International Transactions in Operational，2004（11）：613-643.

[2] Dorigo M，Stützle T.Ant Colony Optimization[M].Cambridge MA： MIT Prcss，2004.

[3] Wang Yuting，Sun Jian，Li Junqing.Hybrid Heuristics Based on Harmony Search and Simulated Annealing Algorithm for Traveling Salesman Problem[J].Computer Applications and Software， 2009（10）.

[4] Zhao Jidong， Hu Xiaobing， Liu Haobin.Improved ant colony algorithm and its application in TSP[J].Computer Engineering and Applications，2010，46（24）：51-52.

[5] Merkle D，Middendorf M.Modeling the dynamics of ant colony optimization[J]. Evolutionary Computation. 2002，10（3）：235-262.

[6] Fu Zhiqiang，Liu Leian.Improved Ant Colony Optimization and Application on Tsp[J]. American Journal of Engineering and Technology Research， 2011（11）.

[7] 符志强，刘磊安.基于蚁群算法的物流配送优化系统设计[J].现代计算机，2014（2）.endprint