基于物流车辆调度算法的研究

1.蚁群算法

蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径。其选择一条路径的概率与该路径上分泌物的强度成正比。因此,由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象:某一条路径走过的蚂蚁越多,后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体间通过这种信息的交流寻求通向食物的最短路径。蚁群算法就是根据这一特点,通过模仿蚂蚁的行为,从而实现寻优。

采用蚁群算法求解车辆优化调度问题的步骤:

1.1将任务点分派到车辆上:

1.1.1选择未用的车辆K;

1.1.2在未分派的任务点在中从角度最小的开始为车辆K指定任务点,直到容量限制不满足为止,如果有剩余任务点,则重复前两个步骤,直到所有任务点都被分配到车辆上。

1.2所分派的任务点集合记为v,而v=m设定有m只蚂蚁,按照蚁群算法求解TSP问题算法的步骤执行。

1.3按照各任务点的极坐标中角度的大小依次和车场来确定n条扫描线,重复n次step1和step2来得到n种调度方案,比较得到最佳的方法就是问题的解。

2.遗传算法

遗传算法是上世纪60年代由美国J.Holland教授首先在《自然结合人工智能系统的适应性》一书中提出的,是一种新兴的自适应随机搜索方法,具有极强的鲁棒性和内在的并行计算机制。遗传算法主要由选择、交叉和变异三个算子组成,分别模仿自然界进化过程中的自然选择和群体遗传过程中发生的交配和突变等现象。

采用遗传算法求解车辆优化调度问题时,一般按照以下步骤进行。

2.1确定染色体的编码和初始群体

采用自然数对可行线路进行编码,如长度为l+m的染色体可写为:

(0,i11,i12,…,i1s,0,i21,…,i2t,0,…,0,im1,…,imn)

其中,ikj表示第ikj项任务,这样的染色体结构可理解为车辆从车场0出发,经过任务i11,i12,…,i1s后回到车场0,形成子路径1;然后又从车场0出发,经过任务i21,…,i2t后返回车场,形成路径2,如此反复,直到所有的m项任务全部被完成为止。在子路径1内交换i11和i12的位置表示行走路径的改变,也使函数目标改变。这样,下面的遗传叠代可使函数目标最小,也即趋向于最佳或较佳的路径。初始群汕头到青海海南物流体的产生广州到德令哈物流采用随机方法,随机产生l个城市的全排列,根据任务的源点和汇点将0标准插入排列中,形成一条初始染色体。如此反复,直到满足群体数,群体数一般大于20个。

2.2确定适应度函数

车辆调度的优化目标有多种多样,常见的目标有总运费最小,总运输时间最短,空载车总运行时间最小,完成任务所需的车辆最小总运输时间最短,空载车总运行时间最小,完成任务所需的车辆最小等,以总运费最小为例,其目标函数为:C=minCX。该式中,Cij为从源点i到汇点j每辆车的单位费用,Xij为每班从源点i到汇点j的满载车的数量。m,n为源点和汇点的数目。

2.3处理约束

为保证车辆调度优化的正确性,约束往往必不可少,常见的约束有汇点处理能力约束,非负约束,车流连续性约束。

一般采用惩罚的方法来处理约束,如果一个染色体对应的解违反了某个约束,根据其违反程度给予一定的惩罚,使其具有较小的适应度值。这样在不损失韶关到绵阳物流群体数目的基础上,随着叠代的进行,使不可行解的数目在群体中所占比例越来越小,可行解的数目则逐渐增加,并趋向最优解。

2.4遗传算子

经典的遗传算子包括复制、交叉、变异。复制算子的目的是保留优良个体,避免基因缺失,提高全局收敛性和效率。目前常用的复制算子有放回式随机复制又称轮盘赌复制,无放回式随机复制等十几种。

2.5确定调度方案

通过上述的遗传操作,产生性能最优的染色体串,根据初始的编码规定将该串解码成最优调度方案。

3.神经网络算法

人工神经网络是对人脑功能的简单和近似模拟,它由大量具有某种传递函数的神经元相互连接而成。人们经常采用Hopfield网络和自组织特征映射神经网络来解决车辆的优化调度问题。在Hopfield网络中,系统能够从初始状态,经过一系列的状态转移而逐渐收敛于平衡状态,此平衡状态是局部极小点。采用神经网络来求解车辆调度问题时一般按下列步骤进行。

3.1产生邻接矩阵

将车辆的源点、所经过的各个汇点和停点抽象成网络的结点,它们之间的有向路径抽象成网络的边,由此构成一个有向图G=(N,L,D),其中N表示结点数,L表示边数,D为N×N的矩阵,可根据优化的目标分别是边(i,j)对应的长度、费用或时间,这样可定义距离邻接矩阵、费用邻接矩阵和时间邻接矩阵。如果两个结点间存在路径,则相应矩阵元素的值为路径的长度或运费或运时;如果两个结点间不存在路径,则相应矩阵元素的值为∞。

3.2约束的处理

对于车辆调度中的约束,将其作为神经网络的一个能量项来处理,将其施加一个惩罚项后加入到网络的能量方程式中,这样随着网络的收敛,约束的能量也逐渐趋于稳态,使约束得到体现。

3.3神经网络计算

设邻接矩阵中的每个元素对应着一个神经元,定义位于位置(x,i)的神经元的输出为Vxi。首先确定网络的能量函数,该能量函数包括网络的输出能量函数和各个约束转化的能量函数,进而,确定神经元的传递函数和状态转移方程,经过网络的反复演化,直至收敛。

当网络经过演化最终收敛时,可形成一个由0和1组成的换位阵,阵中的1所在位置即表示所经过的结点,这些结点间的距离、费用和运时之和即为最短距离、最少运费和最小运时。

3.4调度方案的形成

根据换位阵所形成的最短距离、最小运费和最小运时路径,最终来确定车辆调度的方案。

4.结语

蚁群算法有较强的鲁棒性,只要对该算法模型稍加修改,便可以应用于其它问题,但是由于需要较长的计算时间,容易出现停滞现象,而且没有考虑当连续空间优化问题转换到有向图搜索问题时,信息素分配给可行解带来的尺度变化对于连续解空间搜索效率的影响。遗传算法只有与其他方法如启发式方法和模拟退火算法杂合,以及将调度专家经验融入模型和遗传操作中,才能提高求解的效果。神经网络的问题是对某一个问题构建网络所定义的条件不足而有太多因素需要考虑:训练的算法、体系结构、每层的神经元个数、有多少层、数据的表现等,还有其它更多因素,因此应用于车辆调度不是那么容易。就目前情况而言,我国的VRP研究仍然有限,可以说仍未能满足经济发展的需要。首先是起步较晚,通用理论研究较少;其次,对于具体问题提出的应用研究相对较多,但多为对具体算法的部分改进,且限于各自的适用条件,局限性较强。因此,如何针对各地地形条件、各行业物流配送运输的特点,结合不同的算法进行优势互补和消除缺陷,设计出通用性好、运算速度快、精度高的优良算法,将是研究发展的方向,还有待于各学科专家学者们作深入细致的研究。

指导老师:洪玲

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文