基于蚁群算法的速冻蔬菜配送路径优化研究

吴雨婷，叶 勇，骆宏敏

(安徽农业大学 信息与计算机学院，安徽 合肥 230001)

中国是农产品大国，随着社会进步、人民生活水平提升，速冻蔬菜以其无需复杂的加工过程和不亚于新鲜蔬菜的营养程度等优势悄然兴起。速冻蔬菜是指从采摘处理到加工处理整个过程控制在4～12 h内，并确保在30 min以内其中心温度从-1 ℃降到-5 ℃再降到-15 ℃以下，同时整个流通环节控制在-18 ℃以下的蔬菜。因此，如何合理的安排速冻蔬菜的配送就显得尤为关键。

禁忌算法可以用来求解车辆路径问题，但这种算法只是对由遗传算法得出的初始解进行优化；模拟退火算法具有全局搜索、收敛速度快等特点，也可以求解车辆路径问题；但当解决带时间窗车辆路径问题时应选择具有求解组合优化问题良好特性的遗传算法[1]。蚁群算法属于仿生算法，是最近几年迅速发展的一类算法，具有分布式、启发式、鲁棒性等特点，快速高效，原理简单，相较而言不易陷入局部最优解或过早收敛，搜索能力强，相对缺点不太突出。将蚁群算法结合时间窗建立配送优化模型，通过对冷链物流配送路径优化的研究，构建安全有效的冷链物流配送系统，对农业、物流业以及民生都具有十分重要的意义[2]。

1 安徽某公司速冻蔬菜配送背景介绍

1.1 速冻蔬菜的市场需求

速冻蔬菜不仅可以保留其原料的各种生化形态和营养价值，同时解冻后的汁液中还含有无机盐、有机酸和骨胶等可溶性营养物质[3]。

中国报告大厅出版的2017-2022年中国保鲜速冻蔬菜行业市场发展现状及投资前景预测报告对2017年1-10月中国速冻食品制造出口交货值统计表(如表1所示)，直观地表明了速冻食品的市场空间[4]。

中国速冻蔬菜的出口市场主要有日本、德国、韩国、泰国等国家，其中日本是最主要的市场，其次是德国，两者之和占出口总量的90%。中国速冻蔬菜出口的前景仍十分乐观[5]。

1.2 安徽某公司现状

安徽某公司地处某市某县开发区，主营进出口速冻蔬菜及蔬菜粉，海外市场开阔；地理位置相对比较优越，距附近两大机场只有100 km的路程；公司设备较为全面，技术较为先进，原料获取较为便捷。

表1 2017年1-10月中国速冻食品制造出口交货值统计表

在采购过程中，由于各生产基地与工厂有一定距离，所以新鲜蔬菜在进行简单的保湿处理后就被运往工厂，途中各种生化反应导致的货物损耗一直难以避免；在加工过程中，由于员工都是就近招募的农民，学历水平低下，工作中难免会出现差错而不自知，也会导致货物出现损耗。而在运输配送过程中，由于公司的地理位置不够优越，无论是就近的机场还是港口，都需要不近的一段距离，而速冻蔬菜的价格并不比新鲜蔬菜的价格昂贵多少，所以空运是极为不经济的；水运会因为配送时间过长而增加冷藏集装箱的使用成本；对于相对来说最经济的陆运，由于公司没有配备专门的物流人才，货物的运输路径往往都是由经验丰富的驾驶员决定，也会导致配送时间、配送路线和配送成本不经济的情况发生。

综上所述，在速冻蔬菜发展极为迅猛的今天，安徽某公司虽然作为一家主营进出口速冻蔬菜的公司，实际上其盈利空间并不高。

2 案例分析

蚂蚁在运动过程中，会留下一种称为信息素的东西，信息素的浓度决定着蚂蚁的运动方向，同时其本身具有一定的挥发作用[6]。利用蚁群算法解决安徽某公司速冻蔬菜配送至华东九大海关出口国外路径优化问题，可简化为利用蚁群算法解决旅行商问题。

安徽某公司速冻蔬菜的华东配送目的地有福州、杭州、合肥、南昌、南京、宁波、青岛、上海、厦门9个海关。使用在线地图开放平台坐标拾取器功能，确定安徽某公司与华东配送地区九大海关实际地理坐标。根据两两城市实际配送路线，确定安徽某公司与华东配送地区九大海关实际地理距离，如表2所示。根据安徽某与华东地区九大海关实际地理坐标画出他们的地理位置，如图1所示。

安徽某公司向华东地区九大海关配送速冻蔬菜在和县以北、无须过江的海关如合肥、青岛为第一批次；须过江但距和县地理位置不远的海关如杭州、南昌、南京、宁波、上海为第二批次；距和县地理位置稍远的海关如福州、厦门为第三批次。

表2 安徽某公司与华东地区九大海关实际地理距离 km

图1 安徽某公司与九大海关实际地理位置 图2 安徽某公司现在实施的配送路径

根据表2中安徽某公司与华东地区九大海关实际地理距离，得出安徽某公司公司正实施的速冻蔬菜配送里程数为：

147.5+698.5+600.6+904.2+257.6+1 088.4+70.2+582.9+522.9+155.9+221.4+378.1=5 628.2(km)

3 基于蚁群算法的速冻蔬菜配送路径优化研究

3.1 优化分析

通过对安徽某公司与华东地区九大海关实际地理坐标进行 [(横坐标-24)×100，(纵坐标-115)×100] 数据处理。为便于后期模拟，按四舍五入对横纵坐标数据进行取整，获得改进后的相对坐标如表3所示。改进后的安徽某公司与华东地区九大海关相对地理坐标在坐标系中的相对位置如图3所示。

在安徽某公司第一批与第三批衔接过程中需返回公司造成不必要的经济损失的前提下，可以合并第一批次与第三批次；同时每一批次都需要至少两位驾驶员，一次完整的配送任务完成至少需要四位驾驶员；而且并非每批次配送货物都占满冷藏集装箱，三批次货物每周配送总量大致在20 t左右，一辆装有20尺柜冷藏集装箱的货车足够满足需求。故而，将九大海关配送路线整合成用蚁群算法解决旅行商问题的思想。只使用一辆装有20尺柜冷藏集装箱的货车以一个批次完成配送任务。鉴于旅行商问题的特殊性，暂不考虑中心配送点安徽某公司，先得出旅行商问题的最优结果，即9个海关的配送顺序，再从中确定哪两个相邻海关与该公司的总距离最短，断开并将其穿插进去，即可得到车辆路径问题的最优结果。

表3 改进后的安徽某公司与华东地区九大海关相对地理坐标

图3 改进后的安徽某公司与九大海关相对地理坐标

3.2 参数设置

(1)蚂蚁数量m。根据蚁群算法的特性以及大量实验数据得知，蚁群系统算法的性能是否优良取决于蚂蚁数量m是否满足城市规模与m值相等。

(2)信息启发式因子α。根据蚁群算法的特性以及大量实验数据得知，蚁群系统算法的性能是否优良取决于信息启发式因子α是否满足α∈[1,1.5]。

(3)期望值启发式因子β。根据蚁群算法的特性以及大量实验数据得知，蚁群系统算法的性能是否优良取决于期望值启发式因子β是否满足β∈[0,3]。

(4)全局信息素挥发参数ρ。根据蚁群算法的特性以及大量实验数据得知，蚁群系统算法的性能是否优良取决于全局信息素挥发参数ρ是否满足ρ∈[0.1,0.5]。

(5)局部信息素挥发参数ζ。根据蚁群算法的特性以及大量实验数据得知，蚁群系统算法的性能是否优良取决于局部信息素挥发参数ζ是否满足ζ∈[0.1,0.3]。

(6)状态转移公式中的q0。根据蚁群算法的特性以及大量实验数据得知，蚁群系统算法的性能是否优良取决于状态转移公式中的q0是否满足q0∈[0.6,0.9][7]。

综上可知，可对该模型中有关参数进行确定，当城市节点数目为9时，蚂蚁数量为9，信息启发式因子定为1.25，期望值启发式因子定为1.5，全局信息素挥发参数定为0.3，局部信息素挥发参数定为0.2，状态转移公式中的q0定为0.75。

3.3 模型求解

3.3.1 编写代码并运行

图4 基于蚁群算法的冷链物流配送路径优化结果

根据蚁群算法数学模型及算法流程编写代码，同时将城市节点数目N=9、蚂蚁数量M=9、最大循环次数NcMax=200、信息启发式因子alpha=1.25、期望值启发式因子beta=1.5、全局信息素挥发参数rou=0.3、局部信息素挥发参数alpha1=0.2、状态转移公式中的q0=0.75带入。设定安徽某公司速冻蔬菜华东配送地区九大海关编号如下：0代表福州，1代表杭州，2代表合肥，3代表南昌，4代表南京，5代表宁波，6代表青岛，7代表上海，8代表厦门。

安徽某公司速冻蔬菜华东配送地区九大海关坐标如下：

double C[N][2]={

{201,441},{627,514},{778,221},{467,87},{803,380},

{587,654},{1 206,531},{694,679},{46,307}

}；

运行结果如图4所示。

3.3.2 优化结果

图5 改进后的速冻蔬菜配送路径1 图6 改进后的速冻蔬菜配送路径2

优化后的总配送路线长度为：

70.2+559.3+709.8+221.4+155.9+641.7+257.6+630.7+435.8+147.5=3 829.9(km)

根据上文，安徽某公司正实施的速冻蔬菜配送总里程数为5 628.2 km，改进后的基于蚁群算法的冷链物流配送路径优化研究模型得出的配送总里程数为3 829.9 km，是原数值的0.68倍，足够投入实施、完成优化。此外，改进后的基于蚁群算法的冷链物流配送路径优化研究模型完成一次完整的配送任务只需要两位驾驶员，很大程度上节省了人力物力财力，而并没有阻碍公司正常运营。

4 结 语

利用蚁群算法建立了安徽某公司速冻蔬菜在华东地区的配送路线优化模型，通过优化将配送里程节省了32%，配送人员减少了一半，可以很好地为公司节约相关的人力、物力、财力成本。蚁群算法在众多领域中已展现出它独特的魅力与力量，作为新兴仿生进化算法中一种相对简单的新原理，蚁群算法的发展空间相当可观。但同时，冷链物流行业的发展空间也不容小觑，行业的具体实施标准、对设备和技术的投入、行业理念的推广、管理与资金的回收等，都是可以研究的方向。