动态物流中多源多点最佳路径算法研究①

毕明华,何利力

(浙江理工大学 信息学院,杭州 310018)

企业物流主要关系到配送的成本和对需求的服务,目前仍处于发展阶段,物流配送的能力直接影响了企业的市场竞争力,如何更快更好的把货物送到目的地并能快速响应市场是一个需要持续解决的问题.企业物流是一个典型的多源多点问题,解决这类问题的关键是对多目标进行优化.这类问题起源于许多实际复杂系统的设计,建模和规划,在很多实际的领域中都存在多目标优化问题[1].与普通的单目标相比,带有多约束条件的多目标路径优化问题更加复杂,且解往往不是唯一的.近年来,关于车辆最短路径问题的研究层出不穷,关于这类问题的解决办法有多种,在目标需求点较多的情况下,往往会使用传统的算法,但这类算法效果差强人意.遗传算法是一种高效的全局寻优算法,从串集开始的搜索最优解,而传统算法只是从单个初始值进行迭代,这是两者的最大区别,另外,遗传算法搜索的覆盖面更广,便于全局择优[2].

在解决车辆配送路径问题的研究上,目前已有了很多的研究成果,但对于多源多点问题并没有得到很好地解决.文献[3]提出了一种带订单选择的车辆路径问题,建立经济效益最大化的目标模型;文献[4]从空间角度进行区域分割和路径优化,实验测试算法性能;文献[5]提出了一种物流配送地理位置规划的成本分析方法,建立包括所有终端成本和运输成本的数学模型;文献[6]从按门店配送和按货物种类2种配送方式,建立相应模型,通过仿真实验比较2种成本;文献[7]以提高车辆满载率为目标构建优化模型,并验证模型和算法的有效性;文献[8] 提出了用于解决容量车辆路径问题的遗传算法,通过实例进行算法测试;文献[9-14]也是通过应用遗传算法来求解不同种类的VRP问题;文献[15]将动态路径求解问题转换为静态VRP序列,使用蚁群系统算法进行研究DVRP问题.

以上文献从不同的方面研究车辆配送路径问题,着重于货物种类分仓存储的装载配送是极少的,这与现实的仓储情况存在一定的差距.实际配送当中,往往是多种货物的混合需求,而现实的企业也是通过分仓分类目进行存储,这就需要解决从多个仓库取货按各种不同货物需求进行分类送货.在以往的配货过程中,通常出现单辆车不能满足需求而多辆车空载率过高的情况,因此,本文提出一种新的配送方式: 不同仓库存储不同种货物,由单辆车完成配送,充分考虑需求量,配送路径,车辆载重之间的关系,建立重量修正车辆优化路径模型,并通过仿真实验进行可行性分析.

1 问题完整性描述

本文着重研究了单辆车承运情况下基于多仓库和多目的地的最佳路径配送,并提出一种基于重量修正的新配送方式.从车辆货物装载仓库路径的选择,到中间路径的优化,找到其费用最低,耗时更少的一条最佳配送路径.配送分两种情况: 一种是车辆非满载情况,即总需求量不大于车辆本身载重量,这种情况下不做重量修正的最短路径配送;另外一种是车辆满载情况,即需求量大于车辆本身载重量,就要从不同需求点对不同种货物的需求量进行分析,确定最开始配货的仓库,选择优先配送的目的地,完成车容量差值的修正后,实现多目的地的共同配送.如图1所示.

图1 配送方式图

2 将实际问题转化为数学模型

多仓库,多目的地的物流配送路径优化问题的数学模型如下.建立成本最小目标函数:

其中,i表示需求点,N表示需求点的总数量,dis(a,b)表示需求点a和b之 间的距离.j表示仓库点,J表示仓库点的总数量.C与C′为互斥变量,当需求总量大于车辆本身载重时,需要计算部分需求点的距离,此时C为1,C′为0;否则,当载重量满足时,只需计算两个仓库之间的距离,此时C为0,C′为1.K表示所有需求点的集合.jk,(j+1)m分别表示仓库j与仓库j+1之间的两个需求点,且假设每两个仓库点之间的k,m取值各不相同,其值根据适应度算法动态生成.多源多点问题的配送路径优化问题有以下约束条件:

1)存在多个仓库j1,j2,j3,···,jn,其存储的产品种类分别为h1,h2,h3,···,hn.

2)各个需求点对不同种产品的需求总和不超过其存储总量:

3)车辆的装载重量不超过该车型的最大载重量

其中,I表示仓库j到仓库j+1之间的需求点总数量.q(i)表 示需求点i的需求量.当车辆到达下一个仓库时,假设上一个仓库与下一个仓库之间需求点的货物需求总量小于该车的最大载重量.

4)仓库只经过一次.

cj表示仓库经过的次数.源于贪心策略和现实运输情况,这里规定仓库只经过一次,即将所有需求点对此仓库存储的货物需求总量一次性装车,减少其配送成本.

5)每个需求点经过次数最少一次且不能超过两次.

ci表示需求点经过的次数.需求点每多经过一次,其成本多增加一份,因此这里规定需求点最少经过一次且不能超过2次,若需求总量大于车辆本身载重且此需求点适应度值较高,允许经过一次部分卸货以减少需求点的总量,之后第二次经过时满足剩余需求.否则,只允许经过一次且满足此需求点所有种类的货物需求.

3 对模型求解

3.1 编码方式

遗传算法的进化过程是建立在染色体编码结构基础上的,编码的好坏对算法的性能有很大的影响,相比二进制0-1的编码方式,自然数编码更加直观,简洁,尤其在多源点,多目的地的求解问题中更具优势.因此,本文采用自然数编码.其编码方式如下: 每个需求点编码都大于0,其编号分别为 1,2,···,n;表示形式为r1,r2,···,rn;每个仓库的编码都不大于0,其编号分别为0,-1,-2,···,m,表示形式为s0,s1,s2,···,sm.

通过预定义数组的方式定义仓库所在城市,当检测为仓库时,将编号值取反作为数组下标来获取相应的仓库城市.具体的染色体编码表示如图2所示,其中t,k,p表示待定需求点,由具体的函数动态计算确定.

图2 染色体编码

3.2 初始种群的产生

遗传算法的初始种群对最终解的优劣有很大的影响,选择合适的初始种群并确定合理的规模大小是很必要的,因此,本文采用了如下方法来产生初始种群并绘制了产生初始种群的流程图如图3所示.

1)首先,计算出所有目的地的需求总量与汽车载重量之间的差值C.

2)将染色体编码表示为数组chromosome,chromosome中的下标为0的位置为0,表示从某一仓库出发.

3)使用Random函数生成随机数,用来检测下一个到达的点是否为仓库点.其概率为: 仓库点数/(需求点数+仓库点数),当小于此值时,即为仓库点.

4)当判定为仓库点时,若为最后一个仓库点且差值C大于0,转步骤3)若为最后一个仓库点且差值C不大于0,则说明汽车载重量已经满足,执行步骤5);若非最后一个仓库点且差值C不大于 0,则将剩余仓库点依次加入数组chromosome并执行步骤5);若非最后一个仓库点且差值C大于0,判定此随机数是否已经加入过数组chromosome,即: 是否此需求点已经经过一次,若此随机数未加入过数组chromosome,则取反加入并计算每个需求点对此仓库货物的需求量的和将其加入差值C.若已加入,则判断相邻数是否加入,直到找到未加入的仓库点,并取反加入数组chromosome.当判定不为仓库时,则重新生成随机数为下一次到达的需求点.若此需求点已经加入数组chromosome,处理方式与仓库相同,并将差值C的值减去此需求点需求的值.完成后执行步骤3)继续查找下一次需要经过的仓库点或需求点.

5)到此阶段说明当前的差值C已经不大于0,后续只需要在各个需求点之间寻找一条最优路径即可.

图3 产生初始种群的流程图

3.3 适应度函数的确定

在遗传算法中,适应度函数是遗传操作的重要衡量指标,依赖适应度函数值进行区别种群个体的优劣,适应值越大说明染色体性能就越好,反之越差.因此,适应值越高被选择进入下一代的机会越大,本文适应度函数的模型建立分为以下两种情况:

1)当车辆由仓库到达第一个需求点时的适应度函数如下:

式中,N(sj,hj)表示适应度值,M表示需求量的阙值,K表示距离的阙值,Pn(hj)表示需求点n对 货物hj的需求量,dis(sj,pn)表示仓库sj到需求点pn的距离.

2)当车辆离开第一个需求点转至下一个需求点(或仓库)时适应度函数如下:

其中,C表示其需求总量与车辆载重之间的差值,T为常数,其值大于1,目的是用于提高适应度.

3.4 选择算子

根据上面确定的适应度函数求出种群中个体的适应值,然后对个体的适应度进行排序,选择前50%的较优个体进行下一步.采取精英保留策略,把群体在进化过程中迄今出现的最好个体直接进入到下一代中,并将最小适应度的个体淘汰.

3.5 模拟细胞分裂

对于求解本文最佳路径问题,因每个个体是由多需求点与多仓库点构成,若使用交叉方式,当交叉两个个体的需求点或仓库点时,极易破坏个体的最佳基因片段,因此本文提出了一种模拟细胞分裂的方法产生下一代.细胞分裂是指活细胞增殖由一个细胞分裂为两个细胞的过程,而在分裂过程中会发生基因重组.因此,本文采用这一方式,将父代个体的全部信息复制到子代个体之中,并在生成子代个体时重组基因序列.其重组规则如下:

1)若只有两个仓库点,则随机选择两个仓库点之间的任意一个需求点,判定其到其他需求点的适应度值,找到适应值最大的需求点,将其与该需求点之后的第一个需求点交换.判定交换后的总适应度值与交换之前的总适应度值大小,若小于交换之前的总适应度值,则舍弃此次基因重组.否则,则标记该需求点,下次重组时若随机到该需求点,则计算之后的需求点.

2)若仓库点数大于2,则每个仓库点之间重复步骤1).

3)对于最后一个仓库点之后的所有需求点,采用步骤1)的方式判定其重组后的位置.

3.6 选择变异方式

变异算子的基本内容是通过改变群体中个体染色体的某些基因值,来加快最优解的收敛速度并提高种群多样性.本文使用交换需求点的方式来进行变异操作,首先生成此个体的变异概率P(n)m,将此概率与设定的总变异概率Pm进 行比较,若P(n)m＜Pm,则生成两个随机数用来标识两个需求点并进行交换;否则,进行下一个个体的判定.对于总变异概率,使用阶段性的值,即随世代数越来越大,其总变异概率越来越小,这样可以确保在种群的最后的阶段不会破坏其中的优秀个体.

3.7 结束标识

若种群达到规定的遗传代数,则结束迭代,否则从选择算子开始下一轮循环.

4 实验分析

假设各个仓库存放的货物为表1,各个需求点对每种货物的需求量为表2,各仓库与各需求点之间的距离为表3,各个仓库点之间的距离为表4,汽车载重量为3000 kg.

表1 各仓库存放的货物类型

表2 各需求点对每种货物的需求量(kg)

表3 各仓库与各需求点之间的距离(km)

表4 各需求点之间的距离(km)

表中仓库编号s0,s1,s2分别对应城市杭州,南京,合肥.表中需求点编号R1,R2,R3,R4,R5,R6,R7分别对应城市宁波,上海,上饶,南昌,石家庄,济南,北京.

本文设置初始种群数量为1000,世代数为200,初始变异概率为0.1,通过执行100次仿真运算,从结果中随机取10次,如表5所示.

表5 10次测试生成的最短路程(km)

从表5中可以看出在初始种群中使用的随机数对结果并无较大影响.在第3,5,6,9,10次测试中,其标准遗传里程为0 KM,原因是标准遗传算法未考虑重量修正的情况,在最终结果中因不能完成客户点的需求,导致发生异常退出程序.对应状态如图4所示,由图4得出,改进的遗传算法比标准的遗传算法路程减少约一半且10次测试结果变化幅度较平稳,其最短路程为4555.231 KM,生成的路径如下:s0,s1,R2,R1,R3,s2,R4,R3,R1,R2,R6,R5,R7.对应的城市为: 杭州,南京,上海,宁波,上饶,合肥,南昌,上饶,宁波,上海,济南,石家庄,北京.

图4 10次测试生成的最短路程(单位: KM)

图5为需求总量与汽车载重的差值随经过城市数的变化图.由图5可以分析得出,当汽车经过第4个城市后,其汽车载重量已经满足需求总量的条件.此时,汽车将前往其他仓库点装载货物,之后按照最佳路径完成每个需求点的配送.

图5 需求总量与汽车载重的差值随经过城市数的变化图

5 结论

在大规模多源多点仓储物流的配送问题中,因其存在多约束条件和多优化目标,使得优化问题相当困难.本文提出的基于重量修正的物流配送新方式,优化了初始种群的产生,且提出了模拟细胞分裂的方式来产生下一代,有效地避免了传统遗传算法中“早熟收敛”等问题,经实验验证增强了遗传算法的收敛速度,在有限的计算能力下,缩短了寻优时间.该算法对于实际运输中一辆车负载过重多辆车空载率较高问题是一种较好的解决方案.