基于蚁群算法的应急物流配送车辆调度研究

张裕华　潘　郁

摘要：以车辆配送问题为背景，运用了蚁群算法来求解应急物流配送车辆调度模型。在带有时间窗的基础上考虑应急系统各节点的运输距离和费用构造模型。根据模型的特点，设计了蚁群算法求解方法，并针对蚂蚁路径选择做了改进性分析。实例研究结果表明，蚁群算法在应急物流配送车辆调度问题中具有合理性、可行性和有效性。

关键词：应急管理；物流调度；蚁群算法

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

Abstract: Taking the vehicle routing problem（VRP）as background, an emergency logistics distribution VRP model is established, which is solved by ant colony algorithm and considering distribution distance and cost when transport between every two spots on basis of time windows. In the light of the characteristic of the model, the solving procedure based on ant colony algorithm is designed and the improved analysis is been done to aim at ant choosing route. Results of example's researching show the rationality, the feasibility and the validity of using ant colony algorithm here.

Key words: emergency management; logistics distribution; ant colony algorithm

0引言

近些年无论是自然灾害还是各种事故灾害，公共灾害等各类突发事件爆发频繁[1]，而且规模都很大。突发性重大自然灾害[2]和公共卫生事件造成巨大的人员伤亡和财产损失，必然需要大量的应急物资，以解决伤者救助、卫生防疫、恢复生产等，否则受灾面积、人员、损失将会扩大。因此选择距离最短、费用最少和时间最快的配送路径显得格外重要。目前国内关于物流调度方面作了一些研究，但是关于应急物流配送车辆调度问题研究还很少。鉴于物流调度的研究方法，其中有传统的方法，比如，数学规划，分支定界法等。不过这些方法只能基于某些简化的假设因而不能适应实际的需要；智能调度方法，如专家系统、神经网络和遗传算法在使用中尽管有优点，但也有明显的缺点[3]。根据以上问题，本文将结合应急物流的配送车辆优化调度问题，根据应急物流配送的突出特点，对应急物流配送车辆调度路线优化进行研究，建立了应急物流配送车辆调度模型，用蚁群算法进行优化车辆的配送路径。并通过对某区域的实际应用，验证了本文提出的模型、算法的合理性。

1数学模型

本文讨论的是有时间窗[4]的车辆调度优化问题，假设救灾点与各受灾地点、各受灾地点之间的运输距离作为已知量。每个受灾地点对救灾物资的需求是必须在规定时间送到。所有的受灾地点的需求，在物资数量方面和运输时间方面都能够得到满足；同时单个需求节点的需求量小于单车最大载重量。路网为完全网络，即所有节点之间都有线路连通。车辆所在车场到物资储备中心的距离忽略不计。在上述条件下指派运输车辆以期达到总的运输距离最短，从而降低应急物流的运输成本。

应急物流配送车辆调度模型为：

2蚁群算法优化求解

在研究调度问题中，爬山法、遗传算法和模拟退火法取得了一定的成果，但是由文献[5]比较结果显示蚁群算法的计算结果明显优于其他三种。因此本文采用了蚁群算法解决应急物流配送车辆调度问题。蚁群算法是通过信息素传递来选择路径，具有较高的计算效率和稳定性与传统算法相比能够很好地解决连通图结构的问题。

3实例分析

为了考察上述模型的性质和算法的效果，根据上述模型的条件选用某地区所测算的原始数据为依据进行分析。

具体描述如下：

运用本文的蚁群算法对上述问题进行求解。以matlab7.0为工具，在p-4机上运算，参数设置：α、β、Q、τ0根据实验方法确定其最优组合选为α=1；β=3；Q=100；τ0=0.000001；ρ服从0,1分布因此随机选取为ρ

=0.5。最终的应急物流车辆调度情况如表3。

4结论

本文通过蚁群算法对目标函数进行了优化求解，对于应急物流的配送车辆调度进行了优化取得良好的结果。不过进一步地研究方向还需考虑多个救灾物资储备中心，受灾点等待受灾的损失费用[7]等因素。因此本文的研究和结论也为在应急物流配送车辆调度的更深入研究提供了思路。

参考文献：

[1]Megumi Kano, Linda B. Bourque. Correlates of School Disaster Preparedness: Main Effects of Funding and Coordinator Role[J]. Natural Hazards, 2008,9(49):49-59.

[2]Michael K. Lindell, Carla S. Prater, Walter Gillis Peacock. Organizational Communication and Decision Making for Hurricane Emergencies[J]. Natural Hazards, 2007,3(8):50-60.

[3] 钱晓龙，唐立新，刘文新. 动态调度研究方法综述[J]. 控制与决策，2001,2(16):141-145.

[4] 钟石泉，贺国光. 有时间窗约束车辆调度优化的一种禁忌算法[J]. 系统工程理论方法应用，2005,6(14):522-526.

[5] 刘志硕，申金升，柴跃廷. 基于自适应蚁群算法的车辆路径问题研究[J]. 控制与决策，2005,5(20):562-566.

[6] 甄彤，张秋闻，马志. 基于改进蚁群算法的粮食物流调度研究[J]. 河南工业大学学报，2008,3(29):62-65.

[7] 潘郁，余佳，达庆利. 基于粒子群算法的连续性消耗应急资源调度[J]. 系统工程学报，2007,5(22):556-560.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文