冷链配送中的优化算法分析及应用

徐清泉　赵夏　尚庆生

摘要：本文针对兰州陇海农产品市场有限公司物流配送数字化集成与示范项目中存在的的难点问题，提出基于地理信息系统（GIS）的车辆路径优化算法问题。对物流配送问题和GIS进行理论研究，得出GIS的地图技术与物流配送结合是可行的。通过相关算法比较分析后，本文中选择使用Floyd算法解决LRP问题，利用数字技术的优势，实现整合现有资源，引进先进的信息处理技术，降低用户的使用难度。在短期内使冷链配送业务实现信息化。解决兰州陇海农产品市场有限公司物流配送的实际问题，为中小企业使用信息化手段进行物流车辆调度管理提供样板和示范作用。

关键词：冷链配送 优化算法 分析应用

中图分类号：TP301 文献标识码：A 文章编号：1007-9416（2016）08-0143-03

1 引言

我国冷链物流的发展相对滞后。蔬菜产业已成为农村经济的支柱产业。但是，由于我国蔬菜的采收和流通设施落后，在流通和消费领域，造成蔬菜严重腐损。不仅造成了巨大的经济损失，还给人们的饮食安全构成了威胁[1]。实现高原夏菜的冷链配送已经成为促进高原夏菜产业长远发展的必然选择。高原夏菜冷链配送数字化技术集成项目建设也就显得尤为迫切，利用数字技术将销售系统、库存管理系统、运输车辆调度系统和配送信息查询系统集成在一起，各系统之间实现数据共享和业务流程协作，提高高原夏菜冷链配送的效率，降低配送成本，建立起适合同类企业借鉴的新型配送模式[2]。甘肃省蔬菜种植面积逐年增加，高原夏菜已经成为多个地方农业生产发展中速度快、效益高的支柱产业之一。实现高原夏菜的冷链配送数字化集成已经成为促进高原夏菜产业长远发展的必然选择[3]。建成完善的高原夏菜冷链物流系统需要长期投入和建设。利用数字技术的优势，整合现有资源，在短期内使冷链配送业务实现信息化，兰州陇海农产品市场有限公司物流配送数字化集成与示范项目中已经进行该领域的积极研究探索和实践应用[4]。

2 冷链配送概述

传统配送、仓储业正在向现代物流业转化，而在这个转化过程中，能否实现信息自动化处理是一大关键。目前大多数学者对定位-路径优化问题研究停留在理论阶段，在实际中运用较少[5]。甘肃省农业产业化重点龙头企业兰州陇海绿色产业集团有限公司现已建成榆中高原夏菜冷链物流基地、红古高原夏菜种苗繁育基地，开展高原夏菜产业的品种选育、种苗繁育、市场交易、冷链物流、净菜配送、技术研究等业务，致力于高原夏菜产业的发展，重视高原夏菜的信息化建设，积累了丰富的业务和技术经验。对物流配送问题和GIS进行理论研究，结合企业应用的实践说明，得出GIS的地图技术与物流配送结合是可行的。

通过企业引进先进的信息处理技术，不仅会提高企业的自动化程度和信息共享度，提高工作效率，降低成本，更重要的是从根本上改变企业的战略发展，使企业经营管理迈上新台阶。将最新的计算机信息技术应用到高原夏菜冷链配送的各个环节，通过信息化手段，提高企业的管理效率，降低运行成本建立适合于冷链物流企业的货物配送模式，并构建相应的软件平台。本系统的关键点就在于物流配送优化算法，即在按需求合理安排车辆，并给出打印和查询的运输单和货物的动态作业信息状态的跟踪，并为卫星定位技术（GPS），地理信息系统（GIS），射频标识技术（RF）等提供接口，支持单物流配送中心和多物流配送中心等组织形式。

如图1所示，通过配送中心将销售系统、冷库库存管理系统、运输车辆调度决策支持系统、配送信息查询系统进行整合，提供订单自动拆分、库存自动查询、自动规划运输路线、实时提供配送信息查询等功能，建成一个自动化、高效率的高原夏菜冷链配送管理平台，为企业发展提供助力。

3 物流配送优化算法比较

目前优化算法有两种：精确算法和启发式算法。精确算法有Floyd算法、割平面法、Dijkstra算法、动态规划算法、分支定界法等。启发式算法有禁忌搜索算法、蚁群算法、节约算法、模拟退火算法、遗传算法[4]、粒子群算法、扫除算法等。

物流配送优化算法，大多数选择蚁群算法、禁忌搜索算法、节约算法、神经网络算法、遗传算法、带时间窗的遗传算法、粒子群算法等，或者选择相互组合和优化改进的启发式算法。对以上算法进行比较[5]如表1所示。

遗传算法参数如下：种群大小为100，城市数量为25，最大迭代次数为100，交叉率为0.8，变异率为0.9。

模拟退火算法有：城市数量，降温次数，每个温度迭代步长，初始温度，降温系数。

蚁群算法参数有：蚂蚁数量，城市数量，运行代数，信息素发挥因子，alpha，beta，rho。

对模拟退火算法、遗传算法、蚁群算法、贪心算法比较可知：针对在百度地图中选取的坐标位数较多，数值较复杂，贪心算法对参数数值要求较高，所以无法得出满意解。模拟退火算法对迭代步数要求高，在有限代数内无法得出有效解。蚁群算法有先天优势，但算法对搜索时间过长，无法在较短的时间内求出最优解。在物流配送过程对时间和算法的效率要求高的前提下，在最短的时间内高效地得出最优解，从而规划出最优路线。因此本文选择遗传算法解决LRP问题[6]。

tsplib上关于验证TSP问题的数据bayg29，其中1-29是代表29个城市，X，Y代表城市的定位坐标。如表2所示。

为了验证JAVA技术编写遗传算法的性能和可行性，选择使用tsplib上关于验证TSP问题的数据集bayg29在MyEclipse中进行计算，结果如图2所示。

精确算法比较。最短路径的精确算法有Floyd算法、分支定界法、Dijkstra算法、动态规划法等。Dijkstra算法和Floyd算法都是在潜在配送中心和配送点之间的距离拓扑关系图上进行计算，符合本文要求。Dijkstra算法是计算从一个源点到其他节点的单源点最短路径。Floyd算法是计算节点之间的多源点最短路径。本文中的LRP问题属于多源点路径问题，因此选择Floyd算法解决LRP问题[7]。

4 Floyd算法与遗传算法

4.1 Floyd算法

Floyd算法[2]是求出所有节点之间的最短距离，即多源点最短路径算法。设距离图D=（G，E），其中G表示潜在配送中心和配送点，E表示潜在配送中心和配送点之间的距离。Floyd算法的主要思想：首先求出每个节点之间的最短距离，然后计算各个节点到其他节点的最短距离，构造成距离矩阵。每次插入其他点gk，然后将g1到g2之间的最短距离与插入其他点gk后计算的最短距离进行比较，其中最小的作为新的距离矩阵[5]。不断迭代，到达最后一个配送点，得出最终距离矩阵Ak。

4.2 遗传算法

传统遗传算法大都遵行“适者生存，不适者被淘汰”的仿自然法则，Holland早期对遗传算法的理解，认为遗传算法的本质是自适应算法，在最优路径、系统优化等方面应用最多[6]。Wetzel在1983年首先使用遗传算法解决TSP问题。经过多年国内外学者的研究，遗传算法发展迅速，形成一套完善的思想体系，基本思想：从初始种群开始，初始种群决定了。个体是染色体带有特征的实体，决定了个体的形状的外部表现。首先，确定初始种群并对初始种群进行编码，即把实际问题参数表示为遗传中的染色体形式，一般选择十进制编码或二进制编码。利用适应度函数对经过编码的染色体进行评估，适应度值越大，被选择的概率越大。

4.3 Floyd算法求解步骤与应用

Floyd算法求解步骤：

（1）计算距离矩阵，并保存到每次加入插入点后的矩阵，其中

（2）配送中心分配。1个初始配送中心和25个配送点之间的最短距离已经通过百度地图计算得出，运用Floyd算法把配送点按离第一个配送中心由近到远排列，按照距离大小选出配送中心，并分配配送点。

（3）运用遗传算法对分配好的配送中心和配送点寻找最优路线。选取兰州陇海农产品市场有限公司为初始配送中心。从初始配送中心（X：104.061172，Y：35.936717）只分配一辆车到各配送中心配送蔬菜。每个配送中心对每一个配送点只能配送一次，对每个配送点进行随机编号为第1至第25配送点，每个配送点都是潜在配送中心，运用Floyd算法选定配送中心。当配送点被选为配送中心后，编号为1-3。最后根据遗传算法求出最优结果。

根据MyEclipse运行得出结果如图3所示。

5 结语

本文针对兰州陇海农产品市场有限公司物流配送数字化集成与示范项目中存在的的实际问题，提出基于地理信息系统（GIS）的车辆路径优化算法问题。通过Floyd和遗传组合算法解决无拥堵的LRP问题和有拥堵的LRP问题，并在百度地图上对配送中心和配送点进行定位和标记，最后在百度地图上规划配送路线。具体实现对物流配送LRP应用问题进行整体研究和数学建模，通过配送中心将销售系统、冷库库存管理系统、运输车辆调度决策支持系统、配送信息查询系统进行整合，提供订单自动拆分、库存自动查询、自动规划运输路线、实时提供配送信息查询等功能，建成一个自动化、高效率的高原夏菜冷链配送管理平台。提出一种可推广到同类企业的高原夏菜冷链配送模式。能够提高冷链配送的效率，降低配送成本，较好地为企业发展提供助力。

参考文献

[1]国务院.物流发展中长期规划（2014-2020）[J].综合运输，2014，29（10）：78-86.

[2]Goldberg DE，Korb B，Deb K.Messy Genetic Algorithms： Motivation， Analysis and First Results. Complex Systems， 1989（3）：494-525.

[3]Kirkpatrick， Gelatt CD， VechiJr MP.Optimization by Simulated Annealing [J].Science，1983，220（4598）：671-680.

[4]赵夏，张静芳，向万里.基于蔬菜特性的兰州高原夏菜物流运作模式研究[J].甘肃农业，2014，384（06）：7-8.

[5]赵夏，杨逸凡.基于GIS的高原夏菜物流配送问题研究[J].甘肃科技纵横，2015，44（4）：49-51.

[6]李鑫丽.LRP及其图论模型研究中[D].南京信息工程大学，2007.

[7]胡大伟.设施定位和车辆路线问题模型及其启发式算法研究[D].长安大学，2008.