基于神经网络的烟草物流配送路径优化研究

万贵华，陈昌明，徐 方，高向东，武长征，曾 蕾， 甘 露，李小峰，许军华，邓 敏 ，徐 琼

(1. 湖北省烟草公司孝感市公司 物流中心，湖北 孝感 432000； 2. 湖北工程学院 计算机与信息科学学院，湖北 孝感 432000)

随着我国烟草物流的不断发展，其规模逐年递增，物流建设也越来越受到行业的重视，对烟草物流也有了更多的投资。当今烟草物流的建设工作按照“由小到大、由内到外、由商流到物流”的原则逐步开展[1]。影响烟草行业经济效益的因素众多，其中，烟草物流这一因素对烟草行业总体经济效益影响最为显著。近年来，国家越来越重视烟草物流的建设工作，烟草物流的信息化和智能化有了长足的进展。同时，国家政策也给行业物流提供了大力支持，使得烟草商业交易的网络化、智能化不断完善[2]。

然而，国内烟草物流行业仍存在许多不足。首先，物流环节独立管理和运作无法形成大规模的统一管理模式，从而不能获得大规模物流效益，因此难以由量到质的改变。其次，物流基础设施总体布局不科学、不统一，影响物流效率[3]。最后，长远规划不足，缺少科学的管理，需要有合理的系统管理软件来搭配硬件设施进行高效管理。

物流配送路径优化是国内外学者竞相研究的热点问题。基于最短路径的迪杰斯特拉(Dijkstra)算法是较早提出的著名路径优化算法[4]，该算法是求解图中的一个顶点到图中其他各点的最短路径，使用贪心算法策略最终解决有权图的路径优化问题[5]。基于蚁群的优化算法是模仿蚂蚁寻找食物时进行路径发现的方法[6]，是一种概率型路径优化算法。基于遗传算法[7]的多目标路径优化方法根据生物在自然界中的进化规律而设计[8]，通过模拟自然选择和生物进化的过程搜寻最优路径。基于动态规划思想的Floyd算法可以在加权图中搜寻给定节点到多源点之间的最短路径[9]。但是上述算法都有各自的不足之处，存在学习效率低、收敛速度慢，或者容易陷入局部最优解等问题。为了在烟草物流配送路径规划中克服上述不足，寻找最优配送路径，本文提出了改进的神经网络路径优化算法，提高优化效率，避免算法陷入局部最优解。

1 烟草物流配送概述

烟草物流中最重要的是配送路径的优化问题。主要存在车辆路径问题、旅行商问题、路径优化问题，还需要考虑货物量、车辆的装载量、车辆行驶时间等因素。

1.1 车辆路径问题

车辆路径问题通常是指货物由一个点或者配送中心的一辆或多辆运输车分配到多个需求点的过程(如图1所示)。此过程可能存在时间窗口、负载限制等制约因素。经过合理规划车辆后，能使整个配送过程满足一些目标，例如成本最少或者时间最少等。近年来，车辆路径的优化是各国研究者竞相研究的热点问题，其研究成果有着广泛的应用领域，适用于许多行业的车辆路径规划。该研究成果可以有效降低企业的运输成本，提高运行效率和经济效益，具有较高的研究价值和很好的经济效益。

图1 车辆路径问题示意图

1.2 旅行商问题

旅行商问题的定义可描述为一个商人需要前往多个目的地，其中每个目的地都必须且只能路过一次，当该商人最终返回出发点时，本次旅行结束。而待解决的问题便是如何使该商人的旅行总路径最少，或者花费的时间最短，或者是产生的费用开销最少。

下面对这一问题进行数学建模，商人要去的地点集合可以记为C={C1，C2，…，Cn}，地点Ci与地点Cj之间的距离可以表示为d(Ci，Cj)∈Z+，要求集合C中的每个地点被经过一次，则路径可以表示为(Ck1，Ck2，…，Ckn)，该路径要满足如下表达式的值最小，表达式如下：

(1)

式中：k1，k2，…，kn是1，2，…，n的一个置换。

1.3 路径优化问题

目前的车辆路径优化算法可分为两类，分别是精确算法和启发式算法。启发式算法是目前研究的热点，它又可以细分为传统启发式算法和现代启发式算法。对于精确算法来说，它的主要优点在于，处理较小规模问题，能较快获得最优解。然而在处理大规模问题时，这种类型的算法需要大量的运算时间，不能应用于实时性要求高的场景。这种类型的算法主要有切平面法、Dijkstra算法、动态规划法和和分支定界法。

启发式算法是相对于精确算法而提出的，是根据工作经验的积累或受到自然现象的启发来寻求解决方案，采用全局概率搜索法求解问题。传统启发式算法的主要特点是更倾向于在可接受范围内寻求最优解。这些算法主要有：两阶段法、插入算法、节约算法、扫描算法等。然而，现代启发式算法在阶段计算的结果中允许次优解。这方面的典型算法有遗传算法[10]、模拟退火算法[11]、蚁群算法[12]、禁忌搜索算法[13]和比较流行的神经网络算法。启发式算法虽然不能保证问题的最优解，但在大规模问题的场景求解时可以快速找到较好的解。

2 神经网络路径优化算法

人工神经网络采用许多电子元器件模拟生物神经网络中的神经元，这些电子元器件进行大规模的连接以适应于并行处理模式，并组建神经网络模拟人脑的运行方式，实现人脑的部分功能。由于它可以通过大量样本的学习训练来处理复杂事物关系，特别适合解决各类预测、分类、评估匹配、识别等问题，因此在金融、 航空、医学、环保等领域都有应用的前景。

2.1 Hopfield神经网络

在上世纪80年代，美国科学家霍普菲尔德将能量函数相关的内容引入到对称网络的研究中，进而研究出了Hopfield模型。这种方式对网络的稳定性有较大的改善，对于当前神经网络的发展有非常大的促进作用。下面的图2为离散Hopfield神经网络结构图。

图2 三层离散Hopfield神经网络结构图

图2中的第0层是网络的输入，并非神经元，因此不参与计算；真实的神经元是从图中第1层开始，因此从该层开始根据第0层的输入信息执行函数处理产生输出。该模型将会比较其输出结果与阈值函数f，如果输出结果大于阈值θ，则模型输出值等于1；否则，模型输出值等于0。

对于二值神经元，它的计算公式如下

(2)

式中：Xj为外部输入，且

(3)

2.2 神经网络与路径优化

区域物流网络与神经网络有着许多相同之处，在神经网络模型中，神经元是区域物流网络中的节点，而神经网络中的边则是各节点之间的关系，输入是商户地理位置信息和车辆信息，输出则是配送路径和时间预测信息。因此，本文利用神经网络的高容错性和智能处理能力，采用改进的人工神经网络模型来推理优化物流配送路径，将有效提高物流配送效率，带来更大的经济效益。

当前已有一些神经网络模型被应用于物流配送路径优化中，Caulfield等学者成功的将脉冲耦合神经网络模型应用于解决迷宫中的最短路径问题，但这种求解方式需要每个节点都与神经元一一对应，但是神经元数量庞大；为了克服这一问题，提出了时延脉冲耦合神经网络[14]，它既保持了脉冲耦合神经元的优点，又能减少神经元数量；多输出脉冲耦合神经网络[15]采取线性阈值和多输出，有效减少了迭代频率，从而降低计算复杂度，使它仅仅和最短路径的长度有关；三态级联脉冲耦合神经网络[16]通过并行方式且有效的处理了信号在神经元之间的传输方向，增加了神经网络的计算速度[17]。上述方法都不太适合于烟草物流的特定场景，但受上述研究基础的启发，本文提出了改进的神经网络的路径优化算法。

2.3 改进的神经网络路径优化算法

图3 神经网络模型基本结构

在该神经网络模型中，网络的输入为：

x(k-1)=[x1(k-1)，…，xn(k-1)，xn+1(k-1)，…，xni(k-1)]Tni=n+m+1

(4)

输出为：

(5)

式中：N1，N2是第1、2层神经元数；wij为第一层到第二层的权值系数，w1j1是第2层到第3层的权值系数；θij和θ2是偏置值。

神经网络根据样本的输入来调节权值，使输出值更接近期望值，以此获得最优路径。实验结果表明该算法在优化性能方面取得了较好的预测效果，具有一定的有效性和实用性。在上世纪50年代，研究者提出了模拟退火算法。在组合优化领域，后来的研究者引入了模拟退火算法，并成功进行应用。模拟退火算法是一种基于迭代求解策略的、有效的随机寻优算法。它利用了物理中固体物质的退火过程和一般组合优化问题之间具有的某种相似性特征，能够使用求解过程大概率的跳出局部最优解，尽可能地向全局最优解趋近。模拟退火算法可以作为一种通用的优化算法，具有较高的实用价值，目前已经广泛的应用于工业控制和工程技术领域。

本文结合神经网络和经典的模拟退火算法的优势，提出了一种改进的神经网络算法，用于进行烟草物流中的路径规划，优化原有烟草物流配送路径。

本文在传统的神经网络算法中引入模拟退火算法的思想形成了一种改进的神经网络算法。模拟退火算法思想有利于改进算法结果的反馈方式。另一方面，利用Hopfield的能量函数来优化原模拟退火算法的初始值，将两种算法的优势加以融合来弥补各自的缺点。相比于传统神经网络，该算法具有较高的收敛速度和求解速度。其改进的神经网络流程图如图4所示，其中Ek为退火算法的初始值，Ek退火算法得了的另一计算值，p为程序设定的概率阈值，Tk为k时刻的温度，exp表达式为模拟退火算法中的经典表达式。

图4 改进的神经网络算法流程图

改进的神经网络算法在自学习和自适应方面有着较强的能力。因此，在非可控因素(例如路段、车流量、送货时限等)对物流配送造成影响的问题上能进行自我调节。该算法的实现降低物流配送成本、提高效率，从而获得更高的经济效益。

3 实验分析

本文以湖北省烟草公司孝感市公司与湖北工程学院合作的研发项目为实例进行研究。通过对湖北省烟草公司孝感市公司烟草物流中心的配送路径进行研究，充分了解现有车辆信息、配送路径、送货时长等情况，对目前烟草物流中的安排调度和配送路径进行了研究，最终应用在项目组开发的烟草物流配送路径优化系统上。该系统实现了烟草物流配送的智能优化，可根据当前客户的订货量和客户的地理位置分布动态生成最优配送路径。该项目改变了原先利用经验的人工线路规划，利用计算机辅助，使得烟草物流路径规划更加科学合理，从而起到提高效率、减低成本、方便配送的作用。

下面以孝感市孝昌县的烟草物流配送为例。研究者组织人员对该县的烟草物流进行调研。首先，了解现有物流配送的运行情况以及存在的问题；其次，采集每个客户的地理位置，记录其对应的经度和纬度；最后，调研进行路径优化时的约束条件，如对配送时间的要求、线路条数的要求、配送车辆的数量和装载量，等等。通过前期大量的调研，研究者采集到了进行路径优化的所有数据。最后将客户位置信息映射到地理信息系统中，为算法的研究做好准备。将本文提出的算法应用于物流配送的前后进行对比，具体数据如表1所示。

表1 算法应用前后的相关数据对比

从表1中的数据可以看出，在配送客户数和配送周期相同的情况下，在使用本文提出的算法后，孝昌县烟草物流配送的车辆数、配送里程、线路条数都有所减少，其中车辆数减少了25%，配送里程减少了31.8%，线路条数减少了25%。从总体上看，基于本文所提出的路径优化算法开发的系统达到了预期的目的，能为企业降低成本，增加效益。在系统中提供了相关参数的修改模块，以适应不同应用场景的要求，提供系统的可维护性和使用范围。

4 小结

本文首先分析了烟草物流行业的发展背景和趋势，然后描述了烟草物流配送中的三个关键问题，分别是车辆路径问题、旅行商问题和路径优化问题。接着利用神经网络建立了烟草物流路径优化的模型，并引入模拟退火算法对其进行了改进。改进的算法能够避免陷入局部最优解，具有很好的全局收敛性。本文以烟草配送为应用场景，每个配送点都是固定的，线路的起点和终点也都是固定的，在路径生成中使用初始点采用固定值，初始点不参加路径的交换活动。这样使得算法具有较好的可用性。目前算法中的一些参数主要是根据经验进行确定，下一步将利用相关理论和实验分析进行参数的调优，使算法能够输出更好的结果。