基于 Mapreduce 的大量物流配送线路优化与实现——以贵阳烟草物流配送中心为例

1 绪论

1.1 研究背景和意义

大数据在物流企业中的应用越来越受到人们关注，物流配送路线设计过程中会产生数以百万的数据信息，但大部分企业却未能有效地利用这些数据来进行线路优化。而且传统的路径优化算法无法应对如今复杂的城市道路交通情况下，物流配送路线的有效快速生成。在现有的路径优化算法中加入道路交通信息已成为必然的趋势。而配送客户的急剧增加和考虑道路交通信息，使得不仅数据规模急剧增加，对数据处理的复杂程度也随之增加。传统的单个计算机计算速度越来越不能满足大规模配送路线优化所需的求解质量和运算速度要求。

本文通过在遗传算法模型中加入车道数量、道路是否禁止掉头、车辆速度三个道路交通状况量化因子对配送路线进行优化，对于提高遗传算法的精确性和实时性有一定意义。本文对贵阳烟草物流配送中心的实证分析也为大数据时代到来企业面对大量数据，，如何进行企业物流配送信息化建设提供一个参考的发展方向。对于配送路线优化过程中的大量数据，本文使用 Hadoop 环境下的 Mapreduce对物流配送的动态优化算法进行编程实现，对于大数据分析工具 Mapreduce 在物流配送路线优化中的应用处理有一定的研究参考价值。

.......................

1.2 国内外研究现状

1.2.1 路线优化的国内外研究现状

1.国外研究现状

路线优化研究的核心问题,即 VRP(Vehicle Routing Problem,车辆路径问题)。VRP 最早由 Dantzig 和 Ramser 于 1959 年提出。随后 Clark 和 Wright 在对上述VRP 方法进行改进的基础上提出了改进启发式 Saving 算法。至此以后各学科的研究人员以及物流运输行业的管理者很快便对车辆路径问题开始重视，并对其从多个维度做了比较详细深入的研究。  Bedin  于  1983  年通过发表总结性的论文将前人的各研究成果进行了整理汇总，Daniele  和  Toth  也于 2002  年把各不同学科研究人员对 VRP 问题的研究进展进行汇总编制成书，并进行出版。对车辆路径优化问题的研究已经取得了丰富的且具有代表性的成果,各算法从本质上可分为精确算法和启发式算法两大类。

（1）精确算法

精确算法通过采用数学手段和建立相应的求解模型，表示并计算最优路线。它是解决路径优化问题比较早的一种算法。具体有包括分支定界法以及改进后的结合了下界和分支定界后的改进算法,将 m-TSP 转化为 1-TSP.精确算法的主要特点是通过有严密逻辑且复杂的数学运算，来计算出较高质量的解。而当物流配送规模急剧增加时，精确算法指数爆炸对缺陷就会暴露，这就限制了精确算法的应用范围，使其在实际应中很少发挥实践作用，而只能对规模有限的车辆路径问题进行求解。

（2）启发式算法

启发式算法是通过对过去经验的归纳推理和实验分析从而解决 VRP 问题的方法，它与精确算法的不同也表现在这里。它通常能够在计算的复杂性以及解的优劣性中寻求到平衡，因此被学者广泛的釆用和研究。启发式算法分构造启发式算法、改进启发式算法和亚启发式算法三大类。

.......................

2 大量物流配送线路优化思路

2.1  物流配送区域划分概述

配送区域的划分方法有成千上万种，而采用不同的方法会使区域划分的最后结果千差万别，因此选择一种合理的、符合本论文需要的区域划分算法对各个配送小区域的产生乃至本文最后的优化路线都是极为重要的。选择一种配送区域划分方法首先应该做的是就是透彻理解所要解决的问题，在对问题根本理解的基础上，满足以下几个基本条件：

1）初始划分区域不能叠加，不能覆盖； 

2）每个小区域内的个体位置相距较近，这样能节省车辆运送货物耗费在路上的时间； 

3）为了使配送工作量保持均匀，避免出现配送路程相近却配送量差距较大的不均衡现象，每个小区域的配送量要大概保持相等。

4）每一辆配送车量一次运送所走的总路程应大致保持相等。 

现有的常用区域划分方法有：扫描法和聚类算法。扫描法是 Gillett 和 Miller于 1974 年所提出的求解车辆路线问题(Vehicle Routing Problem，VRP)的方法，此方法采用先分群再排路线的方式。一般分为两阶段性步骤：第一阶段，把各配送户的位置使用极坐标表示，然后将任一配送户作为起点，以配送车容量为客户分群的限制条件，以该配送点为零点按时针的方向，进行客户分群。第二阶段，使用旅行商问题求解算法，解决客户群的配送路线问题。1983 年有专家将此方法应用于求解时窗限制车辆路线问题（vehicle routing problems with time windows，VRPTW），比原扫描法改进的地方是在第二阶段求解客户配送路线问题时，此算法不仅使用了插入法而且还对配送时间可行性进行验证，只要不能满足时间窗约束的配送点，就不能归到一条配送线路中去。当全部客户都归入完成及所有客户都已配送完，此时路线的建立完成；当有顾客没有被归入，则对剩余的尚未被归入的客户重新进行扫描与插入操作，直到所有的顾客点都配送完为止。如上所述，扫描法的每种考虑情况使得其要进行复杂的计算，当客户数骤增时扫描法的计算量呈指数增长，这使其求解的有效性大大的降低。

.......................

2.2 k-means 聚类算法在物流配送区域划分过程中的应用

2.2.1 k-means 聚类算法介绍

J.B.MacQueen 在 1967 年提出了 K-means 聚类算法，其特点是同一聚类内各点之间尽量紧密，不同聚类之间各点尽可能的分开。算法的好处是能有效的处理大量数据中各不同信息之间杂乱的关系。K-means 聚类算法进行的基础是要已知聚类的具体个数，在此基础上，再对大量数据信息采用聚类计算，最后计算所得解是 k  个聚类中心及其计算后得出的包含在各个聚类中的的具体数据。K-means聚类算法不可能只计算一次就得出最佳结果，而是需要通过不断的迭代修正，其计算结果才会越来越接近于最优解，才能有较好的聚类结果。

k-means 聚类算法在物流配送区域划分过程中的应用 配送区域划分的具体过程：

1）首先收集整个物流配送区域内各个配送点的地理位置（即经纬度坐标）；

2）根据配送点的密集程度把配送区域划分为 k 个聚类，并选取相应的初始聚类中心 K=1，2，3…k； 3）计算除聚类中心外其他配送点到各个聚类中心的欧式距离。按照与聚类中心距离的远近及聚类规模的大小完成对象的分配。

4）对各个聚类内点的经纬坐标求平均值，得出新的聚类中心。

5）新计算出的聚类中心与之前的聚类中心进行比较，如果聚类中心发生明显变化，重复 3）的操作，否则转

6） 6）输出聚类结果。

......................

3 大量物流配送路线的 Mapreduce 实现 ................ 23

3.1Hadoop 技术构架 ............... 23

3.2 分布式文件系统（HDFS） ................... 23

4 实证分析 ................... 30

4.1 贵阳烟草物流配送中心配送活动现状 ............... 30

4.2 贵阳烟草配送路线优化思路 .................. 30

5 结束语 ....................... 42

5.1 研究结论及本论文的创新点 ...... 42

5.2 展望 ...................... 42

4 实证分析

4.1 贵阳烟草物流配送中心配送活动现状

贵阳市烟草物流配送中心负责贵阳市七个市区及贵阳市所辖三县一市烟草的配送。配送终端既有大型超市、便利店等需求量大而集中的地方，也包括酒店、零售铺等需求量小而散的地方。配送总用量有 2 万户左右。现有配送路线 160 余条，配送车辆 30 量。每日根据营销中心传递的订单数据分多个波次进行配送，配送量、配送范围和配送复杂性均较大，卷烟送货任务十分艰巨。贵阳市卷烟现行送货体系存在着以下一些问题：

（1）路线重叠设置现象较为严重。现在使用的路线，主要是靠配送管理人员的实际经验逐渐调整、增加形成的，线路间有一定的重复，实际配送中司机以及配货员按照经验挑选合适的路径进行配送，虽然有优化作用，但是不具有理论依据，没有使用信息化技术手段进行精确计算，缺乏整体考虑，尚未实现最佳的配送路线设置。

（2）油耗大，成本较高。由于路线重复、空驶距离过长，以及送货波次间缺乏整体调度等原因，造成配送线路加长，配送效率降低，因此必然导致有关的送货成本包括汽车油耗，人员费用等的增加，带来总的配送成本的增加。同时，因为卷烟销售存在明  显的季节波动性，容易造成忙闲不均，平时冗余车辆和人工的闲置也会导致成本的增加，因此如何对配送路线进行优化，减少车辆和人员配置是提高效率同时降低成本的关键。

（3）不同线路人员配送量差距大，导致分工不平衡。由于现有线路划分基本按照传统经验来划分，造成有的车辆线路过长，有的车辆线路却过短。不同的配送路程量严重失衡。

.....................

5 结束语

5.1 研究结论及本论文的创新点

本论文通过：首先，定性的结合传统的配送线路和定量的采用 k-means 聚类算法对配送区域进行分区；其次，构建考虑了道路情况、交通情况的配送路线优化模型，使用粗粒度并行遗传算法实现大规模配送路线的计算实现；再次，采用大数据处理工具 mapreduce 对 k-means 聚类算法和粗粒度并行遗传算法进行编程实现。最后，以贵阳烟草物流配送中心为实例，选取部分数据对其物流配送线路进行生成。在配送区域划分方面，由原来的单纯按行政区域划分为七个，合并整理为五个。即将云岩区、南明区、小河区归类为一个，统称为南明片区；乌当区、白云区、金阳新区和花溪区仍沿用行政区域的名称，但是，有部分商户在分区是被归类到了与行政区不一致的片区当中。在配送线路优化方面，本文采用的样本数据为南明片区部分数据，最后产生了 30 条配送线路。与以前贵阳烟草的云岩、南明、小河三个区 33 条的线路相比，优化了 3 条线路。说明遗传算法并结合Mapreduce 编程技术可以得出大量物流配送的具体线路，而且在总的配送工作量差不多的情况下，减少了配送线路数量，也就可以减少配送车辆的数量和配送人员的配置，说明本论文对于优化大量数据的物流配送路线有一定的促进作用。

本论文的创新点为：1、在大量物流配送线路的优化模型中考虑了交通情况和道路情况，使优化模型更贴近现实也更准确；2、将配送路线优化方法运用到贵阳烟草物流配送中心的路线优化中，有一定的实践意义。

参考文献（略）