基于深度学习的物流配送路径优化算法的研究

张湘博，李文敬，周杰，李松钊

（广西师范学院计算机与信息工程学院，南宁 530023）

基于深度学习的物流配送路径优化算法的研究

张湘博，李文敬，周杰，李松钊

（广西师范学院计算机与信息工程学院，南宁 530023）

针对物流配送过程，传统路径优化算法对交通拥堵、天气状况、环境因素不敏感，导致车辆在物流配送中效率低下、意外状况多的问题，提出基于深度学习的物流配送路径优化算法。首先构建基于自编码网络的模型，依据样本数据对模型进行训练，预测路段代价值ω，然后与城市干道网络相结合，建立带权重交通网络。最后，通过与禁忌搜索物流配送路径优化算法对比实验，该算法在实际配送中配送速度、物流成本与经济效益明显优于禁忌搜索路径优化算法。因此，该算法是物流配送路径优化的一种有效方法。

深度学习；物流配送；路径优化；自编码网络；优化算法

0 引言

物流配送目的是把物资分发给相应的客户手中。在运输过程中，如何在最短时间，最低花销完成配送是物流配送主要研究的问题。物流配送成本在整个环节中占了最大的比例。配送线路安排的合理与否，对配送速度、成本、效益影响很大,特别是在当今道路交通拥堵，车辆增多的情况下，科学地规划物流配送，能很好地提高物流效益，增进经济的发展。

在实际生活中，物流配送活动的关键是物流配送的路径优化,与电子商务的发展也是密切相关的。对货运车辆进行路径优化，可以提高经济效益，实现合理高效物流。对物流配送路径优化的研究，是研发智慧物流、开展现代电子商务、智能调控交通运输的基础。同时路径优化对城市合理的交通指导，因而改善城市的交通环境。因此，对配送路径优化问题进行研究具有重要的科学意义和应用价值。为此，我们运用人工智能的深度学习技术，对物流配送路径人优化算法进行研究，具有非常重要的意义。

1 相关研究工作

物流配送路径优化的研究二十世纪六十年代开始，经历了简单的启发式算法，启发式算法的设计和当前的人工智能算法三个阶段[1]。使用较多的算法有蚁群算法和遗传算法，其中模拟退火算法、粒子群算法和禁忌搜索算法等。

国内，统计最近三年有关物流路径优化的文献，发现使用最多的是蚁群算法，主要原因是蚁群算法原理简单，易于实现，且寻优能力较强[2]，实际应用效果明显，许星[3]在蚁群算法中引入遗传操作、修改信息素更新策略。其次使用较多的是遗传算法，遗传算法有良好的高柔性和鲁棒性[4]，在初始种群的划分和交叉变异环节上易于提出改进，顾志康[5]基于遗传算法特性，设计了新的染色体结构，并运用混合交叉法进行基因重组进行算法改进。傅成红[6]针对一种典型的车辆路径问题禁忌搜索算法，提出用毗邻信息指导的动态候选集规模改进禁忌搜索算法，国外Schmitt[7]解决带时间限制的CVRP（带装载力限制车辆路径问题）利用了交换变异算子和交叉算子的遗传算法，并在以后的研究中做了改进;Ombukib[8]等设计了多目标遗传算法求解带VRPTW（带时间窗约束车辆路径问题）问题;William[9]提出两种混合遗传算法解决VRP（车辆路径问题）。Montane[10]使用分区-路径规划法构造启发式算法产生初始解，然后通过邻域操作设计构造求解VRPPD的禁忌搜索算法;Ho[11]通过节点再分配、节点分裂、节点交换和2-opt等四种邻域设计构造算法求解VRP，根据以往文献分析，总体而言，禁忌搜索在求解VRP方面最为有效，能在最短时间得到最优解，其缺点在于难以确定适当禁忌期限；模拟退火算法竞争力相对较弱，存在方法过于复杂，运算量大，涉及复杂的求解策略等问题，若是允许较长的计算时间，模拟退火是最好的选择；遗传算法性能优良，目标函数值相对变化很小，然而产生初始种群的随机数选择、交叉和变异过程对求解有很大影响;蚁群算法[12]则存在搜索速度较慢、较易早熟等问题，虽经多次改进，但综合比对，其求解速度和解质量仍难让研究者满意;在某些情况下，结合各种算法特点设计的混合算法[13]能取得较好的求解效果，神经网络的发展，深度学习对解决物流配送路径优化问题提供了一种更好的方法。

2 深度学习基本原理与物流路径问题

2.1 深度学习

最近，随着Master在围棋上的不断连胜，深度学习也变得广为人知，深度学习本质[14]上就是多层神经网络，常用来解决分类、回归、关联规则挖掘、动态系统应用等问题。深度学习常用的模型[15]有：限制玻尔兹曼机模型是个二部图，模型的的隐藏节点条件独立；自动编码器模型，它的输出值设定为输入值，这样训练得到的参数可以最大程度提取数据的共性特征。;深信度网络（DBN）有多个限制玻尔兹曼机组成，先预训练得到权值，训练时间有效的减少；卷积神经网络（CNN），它的原理是实现数据在空间上变换，从而减少维数，降低训练时间。在图形识别应用上，不用复杂的特征提取和重建数据，直接作为网络模型的输入。

考虑到每天都有大量的交通监控数据生成，道路的交通状况会周期性的重复，在庞大交通数据里面，必然存在着一定的共性特征。自编码网络与DBN和CNN模型相比，结构简单，且训练时间短。自编码网络训练的原理是依据相同的输入输出节点，因此在交通数据训练上，可以有效的提取共性特征，在道路交通预测中采用自编码网络的方法可以快速有效的训练模型。

2.2 物流配送难点

物流配送是依据客户指定的目的地和货物，在规定的时间内送达，中间过程是在配送中心分货、转运。在众多研究中[16-18]，大家把物流配送路径选择作为旅行商问题来解决，但以前的研究基于一个静态的交通网络，但现在我国物流业高速发展，交通压力变大，必须要考虑道路交通状况对物流配送路径选择的影响。

配送的难点：传统配送中，司机在物流配送过程中，路径的选择主要依靠过往的经验或者同事的建议，可以快速有效地将货物送达，如果在一个新的配送区域，可能要花很多的时间去熟悉道路；在预警天气面前，有些路段受影响严重，既定路线无法通行，运输时间无法保证；上下班高峰时，部分路段拥堵严重，道路施工时，路段封闭等意外情况都会造成配送的困难。

例如；大家在使用百度地图或高德地图时，经常遇到导航的路线无法通行，因为城市每天都有大量的道路施工，影响着路段的交通。

2.3 路径优化模型

解决2.2节中物流配送问题，关键在于准确预测当前时间段，物流配送经过路段的道路交通情况，依据预测的道路状况选择合理的物流配送路径。物流配送路径优化模型如下图:

图1

交通数据按时段分为多个样本组，其中白天5-22点交通数据具有研究价值，因此把样本按时刻划分为17组，道路交通网络主要考虑其拓扑结构。配送信息需要出发时间、配送地点。道路的拓扑结构附加上预测的各时刻路段通行代价权重，就构成了分时带权交通网络模型。这时的物流配送路径优化问题就转化成了旅行商问题，根据网络模型的复杂程度，选择合适的算法，最后求解最优配送路径。

交通状况的预测需要考虑天气、道路施工、节假日和上下班高峰等，考虑到同样的天气情况下，路段的道路交通受影响程度不同。例如在下中雨的时候，有的路段地势高，道路宽敞，交通受影响较轻。有的路段地势低，且道路狭窄，道路交通受影响严重。因此，如果对天气气象设定通用的影响值，是不妥当的。需要分路段设置天气影响值。

新版气象灾害预警信号从五个等级改成了四个等级，分别用蓝色、黄色、橙色和红色来表示，表示一般、较重、严重和特别严重，同时以中英文标识，与国家的所有应急处置等级和颜色保持一致。因此我们把天气影响值Ti依照预警等级分为四个值，设定工作日正常天气交通代价值为标准值T0、预警天气代价值为Tq，天气影响值为预警天气时路段代价值与正常天气时代价值之比。公式如下：

道路施工可能造成路段拥堵，甚至路段封闭。例如，最近众多城市都在修地铁和高架，对城市道路交通影响非常严重，依靠导航经常遇到无法通行的情况。因此，对路段状态值的判断也是很重要的，路段状态判断在交通样本数据分组时进行，如果发现在该路段中一天内都无车辆经过信息，即判定道路封闭。

国家交通有关法规规定:城市无中心线道路限速30公里每小时，公路为40公里每小时，为了方便自编码网络模型的训练和道路状况的区分，按最高速40公里每小时，最低速为0，平均划分十等分，设定道路状态值为RbR，具体数据通过对关注区域的路段固定周期测得。

因为数据的训练是按小时划分的，因此不需要再考虑上下班高峰的问题，周末和节假日，人们出行情况变动较大，道路状态值受影响情况明显。节假日影响值Ji，影响值即与正常天气路段代价值之比，故公式如下：

3 物流路径的优化

3.1 深度学习与物流配送的结合

本文采用了基于自编码网络的深度学习模型[19]，模型只计算隐藏层的权重参数，不进行分类操作，用合适的函数来分类，这样很大程度上提高了分类的精度，但是文献19中的模型数据分组不够精细，对天气因素的处理不够合理，因此我们对数据按时段分组，使得预测更为精准，对天气因素处理先按天气分组，对比训练后计算出天气影响值，同理求解出周末和节日影响值。训练流程如图2所示。

图2

自编码模型如图3所示。

图3

模型权重参数求解采用常见的梯度下降法，通过迭代逼近求取隐层权重ω，输入特征向量V与输出节点一一对应，因此采用Sigmoid函数为隐藏层的变换核函数[19]，输入特征向量v与权重ω计算后加上偏置数b得到输出特征值，求解过程归结如下：

在分类问题上，采用基于Softmax的预测模型[19]，设定类标签y（i）∈{1，2，…，10}，分类标签代表预测模型要输出的10个路段代价值，估算概率值p=（y=j|x），于是假设函数hθ（x）如下：

其中：θ1，θ2，…，θk为要求取的模型参数，同理，代价函数则为：

求取最小j（θ）时参数值θj的值，通过迭代的方法算出模型参数θk。求解出最终的路段预测器。

3.2 交通网络权重

物流配送最优路线应该是：路途最近，即经过路段长度最短；时间最短，最短时间内把物品送到目的地；路线可行，即选择的路线没有路段封闭或者严重拥堵。由此定义路段权重式子如下：

W=S×Ti×Ji×j（θ）σ（6）

S为路段长度，σ为固定系数，经学习可以获得。路段权重为标准路段代价值、影响值和路段长度系数的积。

3.3 算法选择

城市内的交通网络规模相对较小，运算量较少，采用禁忌算法最为合适。如果在多个城市之间物流中转时，可以采用混合算法求解。

3.4 优化算法描述

基于带权重交通网络的物流配送路径优化算法如下：

输入：配送货物要到达的地点，所在地的最近时期道路交通信息和路段长度，配送出发时间。

输出：当前时段最合适的物流配送路线。

Step1首先对数据样本进行有效数据筛选和按时段分组，按正常天气工作日（标准）、预警天气工作日、正常天气节假日进行分类。

Step2用标准组数据对自编码网络模型进行训练，由公式（3）确定输出特征，完成模型的预训练。依据公式（4）（5）预测得到标准路段代价值T0。

Step3然后按照图2的方式再进行分类数据的训练，求解各个预测代价值，分别代入公式（1）（2）中求出天气影响值Ti和节假日影响值Zi、Ji。

Step4按照标准分时数据，对自编码模型监督学习，求解出各时段路段代价值T0，和系数σ的值。

Step5依据配送信息，选择对应的时刻路段代价值T0（Step4）和影响值（Step3），代入公式（6）中求得路段权重W，结合交通网络的拓扑结构，构建带权重交通网络。

Step6在带权重交通网络中，采用禁忌搜索算法求解最优路线。

Step7输出配送路线

交通信息样本的分组，依据节假日，上下班高峰期，天气信息分组训练，使得预测的代价函数值更为准确、可靠。依据获得的最新的交通数据样本，更新自编码网络的参数值，使得对当前路段交通状况预测更加准确、可靠，为物流配送路径的选择提供依据。

4 实验结果与分析

实验环境是：Win7操作系统个人版，CPU为Intel i7 4790，内存为金士顿16G×2的计算机，编程工具用MATLAB。网络模型为三层结构，如图4所示。

图4

4.2 模型的训练和测试

模型的训练与测试基于南宁市30条主干道路的某局部区域监控数据。交通数据采样主要依据该区域的道路监控数据，气象数据和城市道路拓扑结构来自网络收集。数据首先进行分类和筛选，筛选是选出错误数据和异常数据，异常数据比如车辆信息无，该路段1天内无车辆通行，即可判断该道路封闭。分类如3.1节所示，分为两个对比组，一个标准组。每组数据均为10000个样本进行训练。得出特征信息，然后预测权值，再计算出天气、周末和节日影响因子。最后进行测试，检验预测权值与实际权值的差距。流程如下：

预测准确率如图5所示。

T0是工作日正常天气下的道路代价值，Ti为预警天气下的道路代价值，Zi为周末道路代价值。从图5可以观察到正常天气情况下，准确率较低，预警天气下准确率最高，分析其原因，正常情况下，道路的交通状况随机性较强，当出现预警天气时，道路交通受影响明显，预测变得简单。分析其内在原因，很大的可能是因为学习集包含了较多的拥堵时段数据，因此系统在预测真实拥堵时，准确率偏高。总的来说，路段交通状况的预测是成功的，所以说，应用自编码网络的特征学习在对交通数据认知层次确实具有可挖掘的深度辨识能力。

图5

4.3 配送仿真与验证

为了验证本文算法在实际物流配送中的效果，在南宁市随机设置6组配送任务样本，在各个时段执行配送任务，分别用本文算法和禁忌搜索算法[12]求解配送路径，最后与测试结果相对比、验证。

表1

任务样本选取如表1所示，任务样本分为两组，一组为城区内配送，一组为不同城区间配送，周一为小雨，周三晴天，周末部分道路施工。在仿真测试中，不考虑货物的装卸时间。时间单位为分钟，两种算法物流所用平均时间如下图：

图6

4.4 实验分析

通过图4看以发现自编码网络模型对拥堵和突发状况比较敏感，表1中可以发现在上下班高峰时段，传统的TS算法所选择的路径时间大大地增加了，原因有高峰期拥堵和一些主干道的施工影响。周一和周三的物流配送时间相似度较高，明显可以观察到天气对道路交通影响，在周日，物流配送时间规律与工作日浮动明显。施工影响道路交通，物流配送时间增长明显。

对于整个交通道路状况来说，此次训练的数据量还是较为偏少，但在训练结果上，该算法显示了在拥堵、天气、意外状况下路况预测上的巨大优势。随着未来的经济发展，道路状况在很长的一段时间内都处于高压状态，通过深度学习的方法，对大量的交通信息进行分析，预测道路交通状况，为物流配送选择合适的行程路线，因此对深度学习在交通运输的应用研究是很有必要和有意义的。

5 结语

针对城市的快速发展，车流量的快速增长，城市的拥堵时常发生，通过对过往车流量的数据分析，准确预测主要干道的道路交通状况，依据路段状况合理选择行驶路线，为城市交通带来帮助。深度学习现在仍处于研究阶段，但在很多行业都显示了极大的潜力。相信未来它对交通运输的帮助更加有力。

[1]ChaoWang Mohammed A Quddus*，GIson.Impact of Traffc Congestion on Road Accidents:A Spatial Analysis of the M25 Motorway in England[J].Accident Analysis and Prevention，2009，41（4）:798-808.

[2]陈迎欣.基于改进蚁群算法的车辆路径优化问题研究[J].计算机应用研究，2012，29（6）:2031-2034.

[3]许星.物流配送路径优化问题的研究[D].杭州:浙江大学，2006.

[4]王辉.基于改进遗传算法的物流配送路径优化研究田[D].青岛：山东科技大学，2010.

[5]顾志康，李旭宏，徐家兵.一种改进遗传算法在物流配送车辆调度中的应用研究[J].公路交通科技，2004，21（11）:118-120.

[6]袁庆达，杜文，周再玲.带软时间窗的混合车队车辆路线问题的模型和算法研究田.西南交通大学学报，2000，36（4）:401-406.

[7]L.J.Schm itt.An Evaluation of a Genetic A lgorithmic Approach to the Vehicle Routing Problem[R].Working Paper，Department of Information Techonogy Management，Christian Brothers University，Memphis，TN，1995.

[8]Ombukib，et al.Multi-Objective Genetic Algorithms for Vehicle Routing Problem with Time Windows[J].Applied Intelligence，2006，24（1）:17-30.

[9]William Ho，George T.S.Ho，Ping Ji.A Hybrid Genetic Algorithm for the Multi-Depot Vehicle Routing Problem[J].Engineering Applications of Artificial Intelligence，2008，21（4）:548-557.

[10]Montane F A T，Galvao R D.A Tabuproblem with Simultaneous Pick-up and Delivery Research，2006，33（3）:595-619.Algorithm for the Vehicle Routing Service[J].Computers&Operations

[11]Ho SC，D.Haugland.A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows and Split Deliveries[J].Computers&Operations Research，2004，31（12）:1947-1964.

[12]彭碧涛，周永务.多时间窗车辆路径问题的混合蚁群算法[[J].计算机工程与应用，2010，46（31）:28-31.

[13]Thangiah SR，Osman IH，Sun T.Hybrid Genetic Algorithm，Simulated and Tabu Search Methods for Vehicle Problems with Time Annealing Windows[R].Technical Report SRU 2CpSc2TR294227.Computer Science Department，Slippery Rock University，1994.

[14]毛勇华，桂小林，李前，贺兴时.深度学习应用技术研究[J].计算机应用研究，2016（06）.

[15]Zouxy，Deep Learning（深度学习）学习笔记整理系列[EB/OL].http://blog.csdn.net/zouxy09.

[16]罗庆，周军.基于混合遗传算法的物流配送路径优化分析[J].中央民族大学学报，2016（08）.

[17]李君，梁昔明，张克.改进的粒子群优化算法在物流配送中的应用[J].北京建筑大学学报，2016（12）.

[18]李静.一种基于蚁群改进算法的单向物流配送路径优化[J].电子设计工程，2016（5）.

[19]谭娟，王胜春.基于深度学习的交通拥堵预测模型研究[J].计算机应用研究，2015（10）.

Research on Optim ization Algorithm of Logistics Distribution Routing Based on Depth Learning

ZHANG Xiang-bo，LIWen-jing

（School of Computer and Information Engineering，Guangxi Teachers Education University，Nanning 530023）

Aiming at the problem of logistics distribution process,traditional path optimization algorithm is not sensitive to traffic congestion,weather conditions and environmental factors,which leads to the problem of low efficiency and unexpected situation in logistics distribution,proposes a logistics optim ization algorithm based on depth learning.Firstly,constructs amodel based on self-coding network.The model is trained according to the sample data,and predicts the expected value of the road segment.Then,the weighted traffic network is established by combining with the urban trunk network.Finally,through the comparison experimentwith the tabu search logistics route optimization algorithm,the distribution speed,logistics cost and economic benefit of the algorithm are better than that of tabu search.Therefore,the algorithm is an effective way to optimize the logistics distribution path.

张湘博（1987-），男，河南许昌人，硕士研究生，研究方向为深度学习、物流配送

李文敬（1964-），男，广西邕宁，教授，硕士，研究方向为并行计算、智能物流

周杰（1992-），男，广西恭城人，硕士研究生，研究方向为并行计算、图像处理

李松钊（1994-），男，广西灵山，硕士研究生，研究方向为深度学习

2017-03-09

2017-05-04

国家自然科学基金（No.61363074、No.61163012）、广西自然科学基金（No.2016GXNSFAA380243）

1007-1423（2017）14-0014-07

10.3969/j.issn.1007-1423.2017.14.003

Depth Learning;Logistics Distribution;Path Optimization;Self-Coding Network;Optimization A lgorithm