物流配送车辆优化调度的一种神经网络算法学习资料

1、物流配送车辆优化调度的一种神经网络算法摘要：本文讨论了物流配送车辆优化调度问题的分类，建立了解决非满载车辆卸货路线优化的神经网络模型， 提出了解决配送车 辆优化调度问题的步骤，并进行了具体的调度试验，验证了算法 的可行性。关键词：配送，调度，神经网络0引言据统计，美国2000年的运输费用为5900亿美元，占当年 GDP总值99600亿美元的5.92%,可见，减少运输费用是有效 减少物流成本的重要方面。对于物流中心和第三方物流企业的货 物配送，运输车辆的调度是工作的重点，正确合理的调度可以有效减少车辆的空驶率，实现合理路径运输，从而有效减少运输成 本，节约运输时间，提高经济效益。1配送车辆调度优

2、化问题分类运输车辆的优化调度问题由Dantzig和Ramser于1959年首次提出，由于该问题在交通运输、 工业生产管理等领域具有广 泛而重要的应用，因此 30多年来其研究得到很大重视，国外的 Bodlin , Christofider , Golden , Assad, Ball 等人对该问题进行 了较为深入的研究1 2 3 o总体上看，车辆的优化调度问题一般可根据时间特性和空间特性分为车辆路径规划问题和车辆调度问题。当不考虑时间要求，仅根据空间位置安排车辆的线路时称为车辆路径规划问题(VRP-Vehicle Routing Problem )；考虑时间要求安排运输线路 时称为车辆调度问题

3、VSP (Vehicle Scheduling Problem )。某些 学者将有时间要求的车辆调度问题称为 Vehicle Routing Problem with Time Windows 。车辆优化调度问题可根据不同性 质具体分为以下几类。按照运输任务分为纯装问题、纯卸问题以及装卸混合问题， 所谓的装卸混合问题就是车辆在运输途中既有装货又有卸货。按照车辆载货状况分为满载问题和非满载问题，满载问题是指货运量多于一辆车的容量，完成所有任务需要多辆运输车辆。非满载问题是指车的容量大于货运量，一辆车即可满足货运要 求。按照车辆类型分为单车型问题和多车型问题。按照车辆是否返回车场划分为车辆开放问题

4、和车辆封闭问题，车辆开放问题是指车辆不返回其出发地，车辆封闭问题是指车辆必须返回其发出车场。按照优化的目标可分为单目标优化问题和多目标优化问题， 单目标优化是指某一项指标最优或较优，如运输路径最短。多目标优化则是指同时要求多个指标最优或较优。如同时要求运输路径最短和费用最省。按照货物的种类要求可分为同种货物优化调度和多种货物 优化调度。多种货物优化调度问题是指运输货物的种类多于一种，车辆调度时可能要考虑某些种类的货物不能同时装配运输的 要求，如灭害灵等杀虫剂和食品等不能混装运输等。按照有无休息时间要求可分为有休息时间的优化调度和无 休息时间优化调度问题。实际中的车辆优化调度问题可能是以上分类中

5、的一种或几种的综合，如某配送中心向其多个客户配送货物需要多辆车，这些车的类型不一样，运输的货物种类包括食品、日用品和蔬菜等 多类，调度优化时希望运输费用最省，同时也希望运输时间最短，这样问题变为一个多车型多货种的送货满载车辆的多目标优化 调度问题。车辆的优化调度问题是一个有约束的组合优化问题，属于NP 难题(Nondeterministic Polynomial Problem ),是一个非确 定型的多项式问题。NP问题的解有多个，随着其输入规模的扩 大，问题的求解难度大大增加， 求解的时间呈几何级数上升。目前，尚无有效的多项式时间算法来求解NP难题。在求解车辆优化调度问题时，常常将问题分解或

6、转化为一 个或几个已经研究过的基本问题， 如旅行商问题，最短路径问题， 最小费用流问题，中国邮递员问题等。再用比较成熟的理论和方 法进行求解，以得到原车辆调度问题的最优解或满意解。常用的方法可以分为精确算法、启发算法和智能算法。精确算法主要有分支界定法， 割平面方法，线性规划法，动态规划法 等，启发式算法主要有构造算法、两阶段法、不完全优化法等, 智能算法分为神经网络方法、遗传算法和模拟退火算法等。精确算法的计算量随着车辆优化问题规模的增大呈指数增 长，如当停车卸货点的数目超过20个时，采用一般的精确算法求解最短运输路径的时间在几个小时以上。精确算法不适合于求解大规模的车辆优化调度问题。2配送

7、车辆优化调度的神经网络算法2.1算法概述人工神经网络是对人脑功能的简单和近似模拟，它由大量具有某种传递函数的神经元相互连接而成。人们经常采用Hopfield 网络和自组织特征映射神经网络来解决车辆的优化调度问题。在Hopfield网络中，系统能够从初始状态，经过一系列的状态转移 而逐渐收敛于平衡状态，此平衡状态是局部极小点。采用神经网络来求解车辆调度问题时一般按下列步骤进行4：(1).产生邻接矩阵将车辆的源点、所经过的各个汇点和停点抽象成网络的结 点，它们之间的有向路径抽象成网络的边，由此构成一个有向图G=(N,L,D),其中N表示结点数，L表示边数，D为NXN的矩 阵，可根据优化的目标分别是

8、边(i,j)对应的长度、费用或时间，这样可定义距离邻接矩阵、 费用邻接矩阵和时间邻接矩阵。如果两个结点间存在路径，则相应矩阵元素的值为路径的长度或运费或运时；如果两个结点间不存在路径， 则相应矩阵元素的值为 8。(2),约束的处理对于车辆调度中的约束，将其作为神经网络的一个能量项来 处理，将其施加一个惩罚项后加入到网络的能量方程式中，这样随着网络的收敛，约束的能量也逐渐趋于稳态，使约束得到体现。(3) .神经网络计算设邻接矩阵中的每个元素对应着一个神经元，定义位于位置(x,i)的神经元的输出为 Vxio首先确定网络的能量函数，该能量 函数包括网络的输出能量函数和各个约束转化的能量函数，进而，确

9、定神经元的传递函数和状态转移方程，经过网络的反复演化，直至收敛。当网络经过演化最终收敛时，可形成一个由0和1组成的换 位阵，阵中的1所在位置即表示所经过的结点， 这些结点间的距 离、费用和运时之和即为最短距离、最少运费和最小运时。(4) .调度方案的形成根据换位阵所形成的最短距离、最小运费和最小运时路径， 最终来确定车辆调度的方案。2.2非满载配送车辆优化路径的 Hopfield网络求解算法2.2.1 约束条件为确保网络稳态时的输出能量是一个有效的换位阵，网络必须同时满足以下约束条件(1)有效路径约束为防止不存在的路径被选中，设定如下的约束函数:_ 11边(/不存在式中：-1匚U1为惩罚系数(

10、2)输入输出路径约束为保证网络的结点有输入路径，必有输出路径，设定如下的约束函数：2凡=学£ £九- £匕上L dTI式中：u2为惩罚系数(3)为保证网络的状态收敛到超立方体2n(n-1)中的一个，设定如下的约束函数：工 一L d-L 工M式中：u3为惩罚系数(4)为保证最短路径源于规定的起点s,终止于规定的终点 d,约束函数设定如下:(4)式中：u4为惩罚系数2.2.2 能量方程网络的目标函数设定为:6- nl ff j(5) ="心式中：u5为惩罚系数网络的能量函数为：(6)£ / + & +号 4 Em + %学力 力？入:争火

11、力尸号力忸八-£4今£三，。-叱“号。-七)£ JE-I d-1« xaL II士 M-l *-LM-lL l-L J-L金ll*fRn-Ial* i“M同kMW/1各神经元的输出为：白"一涸" 一 .1模型的运动方程为:展-詈-A翌具-3口 A噂（ -“-JT(8)W fl = t其他将式（6）带入式（9）得到神经网络的运动方程:(10)北五川)”0日)%-3'+W3+式中8规定为：吟山"1必）*4"/弧）/吟/弧>若CU）.d-守心力心-与其他/d 4 I Z64比较式（8）和式（10）中的系数，

12、可以得到如下的连接权重和偏 置电流为:(12)上 一 V七（1 -九九）-y Pm 0 -丛丛）一 U十£即九£i上含上(13)若冗。=（£力其他将式（12）和式（13）中的Txi,yiIxi代入式（8），然后交替求解网 络的运动方程式（8）和代数方程式（7）,当神经网络趋于稳态时， 就可得到一个优化解，即最短路径。4试验深圳市科技园的实际部分路网如图1所示，针对此路网，设定由沃尔玛商场先向华润超市后向清华深圳研究生院配送商 品，运输车辆为一辆小型皮卡车，要求运输路径最短。假设先送华润超市，后送清华研究生院，以沃尔玛商场为起点，以华润超 市为终点，将其间所有路网点

13、编号，如图 1所示。国1试骑跻网图及踊馁距离采用Hopofield网络来1点到12点之间求最短路径。首先,生成的距离矩阵：0511160Bco-do00a>"5000042004X>00o>0co田12000100D00CDco88co8L000100203027D0)008coco0*2W200H298080OP8883041033162688880027圆330g08242*000togIC0138i0310000如013010088002000BDOCD810011CO80COco082*co0110128伯3322+3】w8120用Hopfild神经网络对以

14、上的有向图进行计算，选取各惩罚系数如下： 1000; 1 1= 4000;1500,1000;550o网络的时间常数r=1弁假定每个神经元的具有相同的传递函数，即gxi = g;入xi=；入网络的初始电压 Uxi=0。对图1的网 络图进行计算，其神经网络的最终输出的换位阵如下所示.0 0 0 10 0 0 00 0 0 00 0 0 0。0 0 。0 o o 00 0 0 00 0 Q 0 0 o 00 Q 0 o10 0 00 0 II c 0 0 II 0 0 0 n 00 0 L fl 。口 。 G0 0 D 4 o o a o o o a o o o d o 0 0 0 0 o o d o o o (J o0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 o o db 0 0 。0 0 0 1 oooo 5 0 0 0 oooo0 Q 0 Q 0 0 0 0根据换位阵，得到的最短路径为：1 4 7 12同理，在求由华润超市到清