混合模因算法在求解带装箱约束的车辆路径问题中的应用①

汪洋广, 陈 振

(中国科学技术大学 管理学院, 合肥 230026)

1 引言

在物流运输系统中, 当需要为车队中的车辆规划最优行驶路线和安排相应的货物装载方案时, 就会涉及到车辆路径问题(VRP)和装箱问题(BPP)的求解.这两个优化问题均属于NP难问题, 虽然文献中已存在了大量的论文对两者进行了研究[1], 但对两者的组合问题进行研究的论文仍然较少.组合后的新问题需要同时进行车辆路径的规划和货物的装载方案的设计, 这将无疑增加了求解的复杂性.

VRP问题中最具代表性的是带容量限制的车辆路径问题(CVRP)[2].CVRP根据一组客户提出的配送需求为车队设计一个最优路线集合, 使总的运输成本最小.CVRP的一个常见扩展是带回程取货约束的车辆路线问题(VRPB)[3,4], 它包括两种类型的客户: 待送货客户, 本文称之为配送客户; 待取货客户, 本文称之为回程客户.VRPB与CVRP不同之处在于它将送货和取货过程结合起来, 从而显著降低了车辆在返程时的空载率, 进而降低了运输成本.

在相关文献中, Iori等人[5]首次考虑了CVRP和二维装箱问题的组合, 提出了2L-CVRP问题, 并给出了一般性的求解算法.在2L-CVRP问题中, 每个货物形状被假设为一个长方体, 并且由于货物的易碎性特征或对堆叠的稳定性的要求而不允许货物的堆叠摆放.在相关文献中, 该问题进一步衍生出了4个变体[6,7]: 根据在装载时是否允许货物旋转和是否有先后次序可将原问题细分为4种具体类型的子问题, 即有序定向装载、有序旋转装载、无序定向装载和无序旋转装载.

在相关文献中, 据我们所知只有Malapert等人和Dominguez等人研究过此类问题[6,8].Malapert等人[8]考虑了2L-VRPB的有序定向装载版本, 并基于调度方法提出了一个多约束规划模型, 但他们没有提出解决该问题的具体算法.Dominguez等人[6]同时考虑了该问题的有序旋转装载和有序定向装载, 并进一步提出了一种基于有偏随机化的邻域搜索元启发式算法, 该算法通过对CWS[9]、Best Fit[10]和MTP[11]算法进行有偏随机化进而成功得到了问题的高质量的解.

在本文中, 我们具体研究2L-VRPB中的两种新变体, 即无序定向装载和无序旋转装载, 这两种变体的应用实例可以在设备维修、家具以及工业机械的运输中找到[6,12].为此, 本文提出了一种新的混合模因算法(Hybrid Memetic Algorithm, HMA), 通过在搜索过程中维持可行种群和不可行种群的迭代和更新, 使得当前最好解不断逼近全局最优解.

本文在相关文献的基础上, 提出了一个具有实际应用价值的带二维装箱约束的车辆路径问题.考虑到新问题所带来的求解复杂性的提升, 我们基于组合化策略、全局优化和有偏随机化策略设计了一个增强型装箱求解算法, 并将其整合到一个模因算法的搜索框架中.最后, 基于VRPB和2L-VRPB问题的标准测试算例的实验表明, 本文提出的HMA算法能在可接受的时间内对VRPB和2L-VRPB问题产出高质量的解,同时本文提出的二维装箱算法同文献中的主流二维装箱算法相比也有明显的性能优势.

2 问题描述与数学模型

令G=(V,E)是一个图, 其中V={0,1,···,N}是顶点集,E={(i,j)|i,j∈V,i≠j}是边集.顶点集V由3个子集V=V0∪Vl∪Vb组成: 子集V0仅包含一个顶点v0, 代表配送中心; 子集Vl和Vb分别代表配送客户集合和回程客户集合, 令Vc=Vl∪Vb.对于边(i,j)∈E, 行驶成本cij定义为从vi到vj或从vj到vi的直接行驶距离.在配送中心, 有K辆同类型的运输车辆组成的车队, 每辆车具有最大装载能力D且其矩形装载面积为S=W×L, 其中W代表车厢宽度,L代表长度.每个客户i∈Vc有mi个矩形货物, 其集合表示为Ii, 并且该mi个矩形货物总质量为di.每件货物Iir∈Ii的宽度和长度分别记作wir(r=1,2,···,mi)和lir(r=1,2,···,mi).因此,Ii中所有的货物所占的总面积为

2 L-VRPB问题的目标是找到能够为所有配送和回程客户提供服务的一组车辆行驶路线集合, 使得总的服务成本(即车队的总行驶里程)最小.该问题对应的约束可以被分为两个部分, 第一部分是关于车辆路径的相关约束, 第二部分是关于装箱可行性的相关约束.两个部分的约束的语意描述如下:

(1) 每辆车都在配送中心出发, 完成任务后返回该配送中心.

(2) 车队中最多只有K辆同类型的车可供使用.

(3) 每个客户(配送客户或回程客户)仅被访问一次.

(4) 每条路线至少包括一个配送客户.

(5) 对于每条路线, 必须先服务完所有的配送客户才能继续服务回程客户, 即先完成送货任务再考虑取货任务.

(6) 在每一条路线中, 所装载的货物总重量不能超过车辆的最大承载重量.

(7) 分配给同一车辆的所有货物, 在装载时不可堆叠, 并且货物的最终放置位置的边缘必须与车厢的边缘平行.

(8) 根据装载方式的不同, 本文将问题细分为不允许旋转的装载(无序定向装载, UOL)和允许旋转的装载(无序旋转装载, URL).我们使用VRPB-UOL表示无序定向装载的2L-VRPB, VRPB-URL表示无序旋转装载的2L-VRPB.

2 L-VRPB问题的路径规划部分的数学模型如下:

s.t.

约束(1)旨在最大程度地降低总运输成本.约束(2)确保离开配送中心的车辆数量等于返回配送中心的车辆数量.约束(3)和约束(4)确保每个客户只能被一辆车访问一次, 且车辆在访问完客户后必须离开该客户.约束(5)和约束(6)确保仅在服务完所有配送客户之后才能为回程客户提供服务.约束(7)要求使用车辆的数量不超过车队中的最大可用车辆数量.约束(8)和约束(9)确保配送客户的货物总重量和总装载面积必须不超过车辆的最大载重能力和最大装载表面积,约束(10)和约束(11)对回程客户的货物做了同样的约束.

第二部分是关于装箱可行性的约束.在本文中, 我们将车辆的装载表面视为笛卡尔坐标系下的一个矩形区域.因此, 坐标(αir,βir)表示客户i的货物r的左下角在车厢表面的笛卡尔坐标.对于特定路线Rk, 可以将将其分为两个子路线: 一个由配送客户组成, 称为linehaul子路线; 另一个由回程客户组成, 称为backhaul子路线.对一条路线进行装箱可行性检查等同于分别对两条子路线进行检查.为了简化表示, 令R表示其中的一条子路线.此外我们使用二进制变量 μir来表示客户i的货物r在装载时是否允许旋转.涉及子路线R的装箱约束如下:

约束(13)、约束(14)和约束(15)确保每辆车的货物均能被无重叠的放置在装载面上.

3 改进的模因算法设计

改进的模因算法(IMA)是在具有自适应性机制的混合遗传搜索算法(HGSADC)[13-15]的基础上进行改进得到.我们在个体评价方法、本地搜索程序(个体变异)、个体接受标准和种群多样性机制等方面进行了重新设计, 从而显著提升了模因算法对于2L-VRPB问题的求解能力.在本节中我们将介绍IMA算法的各个部分: 第3.1小节简要介绍了搜索空间和新个体的评价方法; 第3.2小节介绍了种群中新个体的产生机制; 第3.3小节介绍了本地搜索(个体变异)机制; 第3.4小节介绍了种群在进化过程中的多样化管理机制.

3.1 搜索空间和种群个体表示

VRP相关的文献表明, 对非可行解的有效利用可以显著的提升解的质量[13].本文中, 我们将模因算法的搜索空间定义为两种类型的解的集合, 即可行解的集合和非可行解的集合, 后者通过放松车辆最大可承载重量约束(8)和装载可行性约束(9)、(13)、(14)和(15)获得.

此外, 为了促进非可行解向可行解的转化, IMA将根据不可行解的可行性偏离程度对其适应度值进行相应的“惩罚”, 偏离程度越大, “惩罚”越严苛.令R(w)表示解w的路线集合, 路线r∈R(w)表示集合中的单条线路.令rl和rb分别表示r的配送子路线和回程子路线,则解w的总适应度值 φ (w)可由约束(16)求得.相关符号的表示如下:d(rl)、d(rb)分别表示rl和rb各自的货物总重量;s(rl)、s(rb)分别表示rl和rb各自所装载的货物占用的面积; ωD和ωS表示相应的惩罚系数, 初始值均设为1; φ (r)表示路线r的适应度值, 它定义为rl和rb的总行驶距离和各自的惩罚值的累加; φ (w)表示为解w的适应度值, 它为所有路线的适应度值的累加和.

3.2 新个体的产生

在每次迭代中, IMA通过二元锦标赛方法[13]从可行种群和不可行种群的联合种群中随机选择两个父代个体.随后, 父代个体的各条线路被依次连接为一条巡回路线, OX交叉方法[13]将作用于两条巡回路线并生成两个新的巡回路线.伯努利分布将选择其中的一个巡回路线, 随后Split算法[16]将作用于该路线并生成一个新的完整的个体, 新个体将进一步通过本地搜索程序予以改进.

3.3 本地搜索

本地搜索程序将对种群个体采用swap, relocate,intra2opt和inter2opt操作算子进行变异操作.由Split算法产生的新个体将先后经历两个阶段.在本文中, 我们将本地搜索程序的首次执行称为“教育过程”,第2和第3次执行则被称为“修复过程”, 其中“修复过程”旨在促使非可行解向可行解的转化.对于一个新个体, 其将首先经历一次本地搜索以提升自身解的质量.随后, 若改善后的解不可行, 则以概率Pm决定是否执行修复过程.在修复过程中, 在第2次执行前会将惩罚参数乘以10, 如果得到的解仍不可行, 则将惩罚系数乘以100再执行第3次.

为了提升本地搜索程序的搜索能力, 我们对变异操作设计了新的接受标准, 当标准中的任一情况得以满足时将接受和执行当前变异操作.同文献中普遍采用的接受标准相比, 本文提出的接受标准显著提升了本地搜索的效率, 其包含以下3种情形(为了简述该标准, 假定变异操作涉及两条路线):

(1)在执行变异操作之后, 相关路线中从回程客户到配送客户的弧的数量减少.

(2)变异操作所涉及的路线的总成本降低, 并且相关路线在执行该操作后均可行.

(3)在执行变异操作之前, 相关路线中至少一条是不可行的.在执行操作之后, 两者路线均可行.

在本地搜索程序的一次执行中, 对于每一次迭代,若变异操作将被接受, 迭代过程将重新开始.该过程将不断重复, 直到无法再产生能够被接受的新的变异操作.

此外, 本文采取了“邻域修剪”策略[13,15]以提升对解的改进效率.对于给定的客户vi, 其相应的“有希望”的客户的集合 Γ (vi)定义为|Γ |个与其最接近的客户.可以将 Γ (vi)所包含的客户视为从vi出发去访问下一站的理想目的地, 对于vj∈ Γ(vi), 弧 (vi,vj)即为“有希望的”边的子集.对某次变异操作, 只有当其产生了至少一个有“希望的”边[15]才会去进一步评估其是否符合接受标准.

3.4 种群管理机制

在进化过程中模因算法会始终维持两个种群, 即可行解种群和非可行解种群.每个种群的个体数量均保持在 λ和 λ +δ之间, 其中 λ表示最小种群数量, δ表示能允许的最大新增数量.在初始化阶段, IMA将随机生成 4 μ个新个体并根据可行性将其添加到对应的种群中.为了避免解的过早收敛和保持种群的多样性, 我们对种群中的个体实行严格的分散化规则, 任何两个个体之间的适应度值 φ (w)的间隔必须大于0.5, 其中违背分散化规则的个体将被丢弃.对于每个种群, 当其种群大小达到最大上限 λ +δ时, IMA将触发筛选机制, 该机制会剔除种群中适应度值最差的 δ 个个体.最后, 当IMA每执行itdiv次迭代而未能更新当前最好解时便会触发一个多样化程序.在该程序中, IMA仅保留每个种群中最好的 λ /3个个体, 然后执行初始化, 即生成 4 μ个新个体并将其添加到对应的种群中.

4 MultiPack启发式装箱算法设计

本文在5种基本的装箱构造算法的基础上提出了MultiPack启发式算法来检查装载的可行性, 它通过采用5种装箱构造算法和2种额外的提升策略来生成货物放置方案.MultiPack算法由3个部件构成, 每个部件均可独立的产生可行的装载方案.这3个部件会依次被调用, 只有当当前部件无法生成可行装载方案时才会调用下一个更复杂的部件.第1个部件采用了5种启发式装箱构造算法, 第2个部件是在对第1个部件采用全局最优策略进行改进得到, 第3个部件通过对最大接触边界(MTP)装箱启发式算法采用有偏随机化改造得到.

对于单条路线上的客户集Rset,Rseq表示按照某种排序规则将客户集Rset的所有货物进行排序之后的序列.freeList表示车辆装载表面上的空闲矩形列表.在装载之前,freeList中只有一个矩形, 即车辆的矩形表面,之后每装载一件货物, 所选的目标矩形将从freeList中删除, 同时新生成的空闲矩形将被添加到freeList中,随后freeList中的所有可用矩形将经历一轮检查, 以删除不必要的矩形.

在MultiPack的第1个部件中, 5种构造算法Heuri(i=1,2,···,5)将依次被调用.对于任一个构造装箱算法Heuri, 将依据货物在Rseq中的先后次序依次安排其所对应的最佳放置位置.不同的基本装箱构造算法具有不同的“最佳匹配”评估标准, 相关描述如下:

Heur1: 对于所有在freeList里的可放置的空闲矩形, BL (Bottom-Left)启发式方法[17]总是选择一个左下角的横纵坐标最小的矩形.

Heur2: 在所有freeList里的可放置的空闲矩形中,BAU (Best Area Utilization)启发式方法[18]选择表面积最小的矩形, 使得所选矩形在放置货物之后的面积利用率最高.

Heur3: 在freeList里的可放置的空闲矩形中, BSEM(Best Short-Edge Match)选择“剩余边”较短的最短矩形.令和表示其中一个空闲矩形的宽度和长度,wi和li分别表示当前待放货物的宽度和长度.BSEM启发式方法将在可放置的空闲矩形中选择目标值min(w′j-wi,-li)最小的矩形.

Heur4: 在freeList中的可放置的空闲矩形中, BLEM(Best Long-Edge Match)启发式选择目标值max(,-li)最小的可行空闲矩形来放置当前货物.

Heur5: 在freeList的所有可行的空闲矩形中, MTP(Maximum Touch Perimeter)[11]选择一个使接触周长最大的空闲矩形来放置新货物.

在第1个部件中, 每种基本的装箱构造算法Heuri(i=1,2,···,5)将根据货物序列Rseq进行装载.这些算法的优势是运行效率很高, 但是在某些极端情况下, 其效果可能会很差.因此, 第1个部件中的5种基本启发式方法适用于处理简单的装箱情况.

为了应对更复杂的情况, 我们采用全局最优策略来改进第1个部件中的5种基本算法.在第2个组件中包含5种改进后的装箱算法, 标记为impHeuri(i=1,2,···,5),每种impHeuri都 是通过对Heuri采用全局最优策略进行改进得到.改进后的impHeuri将不再根据输入序列Rseq来进行装载, 而是在每一次装载时将对每个待装载的货物和该货物的所有可放置位置进行评估, 然后选择最佳位置.

对于给定的货物集合, 第2个部件中的改进启发法算法极大地扩展了给定货物及其相关可行位置的搜索范围, 因而可以生成更好的装载方案.我们采用类似Burke等人[10]的算法实现方式来提升算法的运行性能.

最后, 为了提升MultiPack算法对更为复杂的装箱情形的处理能力, 本文采用了有偏随机化技术[6]来改进MTP装箱构造算法, 标记为Biased-MTP, 它构成了MultiPack算法的第3个部件.在每一次装载时, Biased-MTP会评估每个未装箱的货物及其对应的所有可行放置位置, 对所有生成的可行放置将基于接触周长来排序,随后将使用几何分布来决定执行哪个可行装载.Biased-MTP使用两个参数 θ和PackIter来校准算法: 前者表示单次伯努利实验成功的概率, 后者表示为某个货物寻找其放置位置时, 若一直无法找到可行的放置位置, 则随机MTP启发式算法将会被调用的最大次数.

为了降低调用MultiPack带来的时间开销, 本文使用了特殊的数据结构(Trie)[19]来记录已检查路线的装箱可行性.在这里, 我们将Trie树中的最大存储数量限制为10 000 000.当Trie树中的数量达到上限时, 将仅保留最近生成的2/3部分的元素.

5 数值实验

在本节中, 我们首先测试HMA算法在经典VRPB基准算例上的性能表现, 并将实验结果与其他最新启发式算法进行比较.然后, 我们进一步在2L-VRPB算例上进行测试, 检验HMA算法针对本文提出来的2L-VRPB问题的求解性能.HMA算法基于C++编程语言实现,运行平台为Windows 10, 硬件环境为3.4 GHz Intel i7 6700处理器和16 GB RAM.

5.1 VRPB的计算结果

由于2L-VRPB问题是在经典的VRPB问题上的扩展, 故我们首先检验HMA算法在求解原VRPB问题的求解性能, 这将体现HMA的路径规划的能力.基于Goetschalckx和Jacobs-Blecha发布的VRPB基准算例[20], HMA的求解结果同文献中的相关算法的求解结果的对比如表1所示.所引用文献中的算法的描述如下: LS12表示Zachariadis等人提出的本地搜索算法[21],ILS14表示由Palhazi Cuervo等人提出的迭代局部搜索算法[22], DILS16表示Brandão等人提出的确定性局部迭代搜索算法[4], HMA表示本文提出的混合模因算法.HMA的参数设置和终止条件与Vidal等人[13]的设置相同.

在表1中, 对于每个实例, BKS指的是所列出文献中得到的已知最好解[12], Gap列表示HMA的求解结果同已知最好解的百分比偏差, Time表示HMA的平均耗时.在所有的测试算例中, 只有3个实例(C1、G1、I5)没有达到已知最好水平, 其对应的百分比偏差均小于0.5%.综合来看, HMA对于求解VRPB问题是一种极具竞争力的元启发式算法, 它拥有很强的路径寻优能力.

表1 （续） VRPB的计算结果

表1 VRPB的计算结果

5.2 2L-VRPB的计算结果

2 L-VRPB是2L-CVRP的扩展, Toth等人采用了一种从经典VRP数据集生成VRPB数据集的方法[23].本文采用Dominguez等人[6]的方法从Gendreau等人[24]的经典2L-CVRP基准算例来生成2L-VRPB算例.具体而言, 即在2L-CVRP的每个算例中, 每隔4个客户便将最后1个客户指定为回程客户, 前面的3个指定为配送客户.生成的新的2L-VRPB数据集中包含180个算例, 总共分为5个类别, 每个类别包含36个算例, 算例中的客户规模从10到255.在第1个类别中,由于所有的货物的长宽均设置为单位1, 故其可以视为纯VRPB问题.对于第2类到第5类, 每个客户对应着一组不同尺寸的矩形货物, 且装箱复杂程度依次增加.

针对2L-VRPB基准算例, 我们选取部分中等规模的算例进行初步实验以校准HMA算法的参数.这里,itmax用来设置停机条件, 表示HMA在交叉了itmax次之后终止运行.在对解的质量和求解时间进行权衡之后,我们给出了最终的参数设定值: λ=12, δ=20, |Γ|=40,Pm=0.5, 4μ=50,itdiv=600,itmax=6000.

对2L-VRPB的每一个算例, HMA算法将执行3次, 每次执行将设置一个不同的随机数种子, 3次执行的结果中的最好值将作为HMA的解.文本将解决2L-VRPB的两个变体, 即无序定向装载(记为VRPBUOL), 和无序旋转装载(VRPB-URL), 最终的求解结果如表2所示.由于两个变体在针对算例中的第1类的结果是一样的, 故不再重复列出.class1为HMA对2L-VRPB在无序装载模式下的求解结果(不再区分定向装载和旋转装载), class2到class5为HMA针对VRPB-UOL的求解结果, class6到class9为HMA针对VRPB-URL的求解结果.在本文所设置的停机条件下, 所有的算例均在可比较的时间内完成了计算.对于同一算例, 旋转装载的解要好于定向装载的解, 这是由于在可旋转的条件下装箱算法有更大的灵活性.

表2 2L-VRPB实验结果

为了进一步验证HMA对2L-VRPB问题的求解性能, 尤其是验证MultiPack算法在复杂装箱情况的求解能力, 我们对VRPB-UOL和VRPB-URL两个变体分别设计了3组对比实验.在IMA算法的基础上, 我们采用3种不同的装箱算法来代替HMA算法中的MultiPack, 并在基准算例上测试其性能.首先, 我们用Leung等人[25]提出的装箱启发式算法(PHB)来代替HMA中的MultiPack.此外, 在PHB装箱算法的基础上, 我们对其基本装箱构造算法采用全局化策略进行改进, 并将改进后的部分同PHB串联, 得到新的装箱算法并记为ImpPHB.最后, 我们将Dominguez等人[6]提出的随机有偏化MTP算法[11]记为BiasMTP.

表3和表4分别给出了4种算法在VRPB-UOL问题和VRPB-URL问题上的平均性能表现, 每一个值都是特定算例在类别2到5的数据上的平均值.BKS表示4种算法所给出的结果中的最好值, Gap表示各个算法同当前最好值之间的百分比偏差, 由于值越小越好, 故百分比偏差越小则表示该算法的性能越优.

由表3和表4可看出, 对于小、中和大规模算例,在4种算法中, HMA对于所有算例均能给出最好解.

表3 VRPB-UOL问题的计算结果

表4 VRPB-URL问题的计算结果

在VRPB-UOL问题中, HMA算法给出的解在所有算例上的平均值为999.52, 该值同所有算例的已知最好解的平均值相同.BiasMTP算法给出的解的平均值同已知最好解的平均值的百分比偏差为0.011%, ImpPHB算法对应的偏差为0.006%, PHB对应的偏差为0.021%,由于0.021%＞0.011%＞0.006%＞0.000%, 4种算法的性能表现为 HMA＞ImpPHB＞BiasMTP＞PHB; 对于 VRPBURL问题, HMA算法在所有算例上的平均值为977.49,BiasMTP算法同其相比的百分比偏差为0.008%,ImpPHB算法为0.004%, PHB对应的偏差为0.014%,可得0.014%＞0.008%＞0.004%＞0.000%, 4种算法的性能表现为 HMA＞ImpPHB＞BiasMTP＞PHB.综合 4 种算法在VRPB-UOL和VRPB-URL问题上的性能表现,HMA算法的性能显著优于ImpPHB算法、BiasMTP算法和PHB算法.由此可得出结论, 本文提出的Multi-Pack算法同文献中的主流二维装箱算法相比很有竞争力, 同时本文提出的混合模因算法(HMA)对于2LVRPB问题是一个高效的求解算法.

6 结束语

本文研究了一个新的组合优化问题, 即带回程取货和二维装箱约束的车辆路径问题(2L-VRPB), 该问题可以在实际物流系统中找到相应的应用实例.本文首次研究了该问题的无序定向装载和无序旋转装载两种变体.为了求出该问题的高质量的解, 本文提出了一种新的混合模因算法(HMA), 该算法通过改进的模因算法(IMA)完成路径规划, 并通过定制化的组合装箱启发式算法(MultiPack)完成特定货物的装载方案的设计.通过在VRPB问题和2L-VRPB问题的基准算例上设计对比实验, 本文提出的混合模因算法对两种问题均能在可接受的时间范围内给出高质量的解, 这表明该算法对VRPB问题和2L-VRPB问题均为一种高效的求解算法.同时, 该算法可进一步应用于其他更复杂的车辆路径和装箱问题相结合的问题的求解中.本文的组合化策略、全局优化和有偏随机化策略对于求解三维装载问题以及其他更为复杂的组合优化问题的算法设计都有很好的借鉴意义.