进化Hyperheuristics Location-Routing问题同时皮卡和交付

文摘

本文提出一种基于进化的系统,该hyperheuristic (EHH)解决生产location-routing问题(CLRP)和它的一个更可行的变体,即CLRP同时皮卡和交付(CLRPSPD),这是重要的和赋权模型在复杂的物流系统。拟议的方法管理的低级启发式(LLH),实现一套简单,便宜,而且knowledge-poor运营商如“转变”和“交换”来指导搜索。量子(QS),蚂蚁(AS), particle-inspired (PS)高级学习策略(通过)开发的进化选择策略(ESs)改善hyperheuristic框架的性能。同时,随机排列(RP)、禁忌搜索(TS)和健身率rank-based multiarmed土匪(FRR-MAB)介绍了作为比较基准。我们评估配对的九个不同的选择策略和四个验收机制和监控的性能在36对前四个突出对解决三套基准实例从文学。实验结果表明,该方法优于大多数精确定制的最先进的方法在文献中,PS-AM和我有更好的表现相比其他双方面获得良好的平衡解的质量和计算时间。

1。介绍

作为一个复杂系统,物流网络设计带来很多好处的经济,社会和环境。近年来成功应用各种工具对于优化和管理复杂的物流系统来驱动利润和服务质量的货物运输(1]。这样的工具之一是location-routing问题(单体)2),整合两种类型的决策:设施选址问题和车辆路径问题(VRP) [3]。在各种扩展基本的单体,CLRP和CLRPSPD提出为了代表不同的特性的实际问题复杂的物流系统。同时,应该开发一个有效的解决方案方法提供有竞争力的解决方案为基准实例CLRP和CLRPSPD在合理的计算时间。因此,本文提出一种新颖的方法来解决这两个问题。

CLRP和CLRPSPD都是np困难,他们更复杂和耗时的解决,尤其是CLRPSPD。因此,它不太可能实现大型实例证明最优在合理的计算时间内(4]。我们的以前的工作2]小说hyperheuristic框架应用于解决CLRPSPD使用禁忌搜索,FRR-MAB,两者的结合是选择策略和五验收标准。然而,本文的主要区别和我们之前的工作可以获得:(1)高级策略设计灵感来自进化算法代替上面的策略;(2)四个基本验收标准是本文由我们以前不习惯工作;(3)本文旨在解决基准的实例CLRP CLRPSPD,但是我们以前的工作只解决后者;(4)的运营商在我们以前的工作是分类的前提下自然的运营商提前了,但在这篇文章中,运营商的本质是未知的。此外,本文的区别和裁判。4)可以得出,我们的论文都集中在一个不同的解决方案方法CLRP CLRPSPD,即hyperheuristic方法。因此,主要贡献如下:(我)针对解决两个基本模型在复杂的物流系统,我们探索generality-oriented和新兴的启发式求解这两个主题在复杂的物流网络,即进化hyperheuristic-based迭代局部搜索。(2)metaheuristics过程的启发,几个ESs开发实现一个在线学习策略的自适应地选择有前途的序列LLHs试图实现全局搜索,也就是说,QS,和PS。其他最近和相关与选择策略(RP, TS, FRR-MAB) [5- - - - - -7)也被选为基准进行比较。(3)四个基本验收标准用于与ES和non-ES检查他们的表现,也就是说,所有动作(AM),天真的验收(NA),大洪水(GD)和模拟退火(SA)。

本研究的其余部分组织如下。部分2提供了一个简短回顾的方法问题域和hyperheuristic近几十年来。节3的3项MIP配方CLRPSPD定义。提出基于进化学的选择策略中所描述的部分4,提出了评价和讨论部分5。最后,给出了结论部分6。

2。文献综述

两种类型的评论本节有关:一个问题域(CLRP / LRPSPD)和方法(即。,hyperheuristic和HH)。前者主要集中在有效的方法解决CLRP CLRPSPD,而后者评论最近的技术发展HH和HH在现实世界中的应用。

2.1。Location-Routing问题

在复杂的物流,CLRPSPD更实用的变种CLRP通过考虑逆向物流,也就是说,商品时需要从客户车辆发货给客户。CLRP首先,我们回顾最近的一些方法,然后最近CLRPSPD是调查。

CLRP的主要组件,VRP研究了几十年。在过去的几年,一些研究人员致力于VRP的发展。蚁群算法应用于解决网络密集的汽车服务(8]。多个以人群为基础的遗传算法是用来解决列车循环计划问题(9]。混合禁忌搜索算法开发了一个真实的问题(10),打开VRP考虑燃料消耗。同时,开发了几种方法求解VRP的变种(11),即VRP随着时间窗口。然而,上述论文没有分析仓库在物流网络的影响。

在单体的变体,CLRP最近已经成为一个最解决,在裁判。12),应用于许多实际应用,如玻璃回收(13],粮食分配[14],讨厌浪费[15],救灾[16),等等。提供了几个调查CLRP。参考文献(17- - - - - -21]。上面的调查提出了分类方案方面的结构特点或解决方法并总结CLRP变异和扩展,但最好的解决方法总结CLRP没有提供。

考虑到方法解决CLRP量身定做解决方案,致力于解决CLRP几种具体方法,如branch-and-cut-and-price [22],branch-and-cut [23,24),和动态规划25),这是最有效的方法在解决CLRP。然而,没有人能够实现大规模实例证明最优合理的CPU时间。已经提出最有效的启发式解决大型实例和提到以后。

提出了一种两阶段metaheuristic方法与TS体系结构将CLRP分解为两个子问题(26]。迭代的两阶段方法应用于裁判。27]。在他们的算法,客户被聚集到supercustomers,然后利用拉格朗日松弛法在定位阶段,和细粒度的TS (GTS)约束提出了改善路线在第二阶段。提出了一种聚类分析生成路由数据,然后仓库位置是解决倒塌的路线(28]。在裁判方法。29日),结合自组织映射神经网络和TS应用于解决single-depot单体。提出了一个迭代的启发式单体在平面上的两个决策问题的迭代处理反馈信息(30.]。

最近,杂化掌握开发(31日目,进化的本地搜索过程被用来在两解空间搜索。SA启发式基于三个随机社区研究[32]。一种自适应启发式相结合的大型社区搜索层次结构和几个运营商开发(33]。提出了两阶段混合启发式通过构造两个阶段:施工阶段和提高阶段(34]。方法是使用分层结构的蚁群的结构开发的多蚁群优化算法(35]。GTS与附近一个变量搜索算法求解CLRP [36]。提出了一种独特的遗传算法对CLRP [37),使用局部搜索过程在突变阶段不改变标准遗传算法框架。除此之外,上述精确和启发式方法已经成功地应用于CLRP被许多研究人员和最需要高效的建设性的方法获取初始种群。

很少关注发展CLRPSPD已经收到。这个问题首先在裁判。38]。在他们的论文中,一个精确的算法叫做branch-and-cut SA (BC-SA)相结合的方法进行了研究。明年,同一作者开发了两种类型的公式CLRPSPD:节点——基于流的公式和39]。Multistart SA提出了Multistart爬山策略合并到SA框架(40]。Two-echelon CLRPSPD已经解决了与小于50客户解决实例(41]。然而,没有解决与超过100客户实例来证明以上四个最优性的方法。SA雇佣三个本地社区搜索机制是解决几个实例开发超过100的客户(4]。上述方法致力于CLRPSPD的发展,取得显著成功获得高的解决方案质量相当高的计算时间为代价的。我们的以前的工作2)可能比上述论文的计算时间和解决方案质量通过开发一个通用的框架hyperheuristics使用迭代局部搜索过程。

2.2。Hyperheuristic

结论源自上述方法CLRP和CLRPSPD可以吸引不同的搜索运营商参与这些方法,例如,山登山者,突变启发式和跨界车,这可能是有效的在寻找全球最佳状态。然而,对他们来说很难获得勘探(探索新的解决方案)和开发之间的权衡(利用更好的解决方案)加油,没有相应的策略建议有效的评估和管理这些运营商在正确的时间,显示有关计算时间的表现。此外,现有的基于搜索的方法通常domain-dependent,导致测试人员不需要深入了解的一个艰巨的任务域。的理想hyperheuristic被定义为“启发式选择启发式”[5,42]。后方,一个广泛的版本开发方法,分为两种类型:启发式选择和启发式生成(启发式生成启发式)[43]。本文基于single-point-search方法前,和简短的描述和评论以后提供。

选择HH,框架的两个水平而言:通过和LLH。通过操纵的空间组成的固定池LLHs直接修改空间的解决方案(44]。两个主要类别可以通过考虑:选择策略和验收标准(45]。启发式选择机制的作用是智能构建有效的启发式序列LLHs从池中,而验收准则旨在决定是否接受或拒绝新的解决方案应用后选择LLH [46]。通过分析反馈信息的来源,三个模块可以被认为是:在线,离线,没有学习。选择函数(5,47),强化学习(48],TS [2,6,49- - - - - -52],FRR-MAB [2,53- - - - - -57)的例子为在线选择策略和简单随机,随机的后裔,RP,等等,被视为不学习方法。提出了几个metaheuristic-based策略设计hyperheuristics文学:蚁群,粒子,和量子激发hyperheuristic所。的特点最进化hyperheuristics文学展示在表1,对于每个EHH范畴,应用领域,出版的来源,主要特征,出版年。验收标准而言,两种类型涉及:确定和nondeterminate方法。前确定地接受合成的结果,如所有动作,只有改善,改善,平等而NA SA, GD和蒙特卡罗举出nondeterminate方法接受新的解决方案。

随着hyperheuristic的普及,它已广泛应用于实践,如二维规则和不规则的包装问题[73年),护士名单(74年),车辆路径问题(54],建设水准问题[52,软件项目调度问题56),t方法测试套件的一代(6,75年),产品差异性测试功能模型(55)、快速机重新分配(76年),和制定时间表77年- - - - - -81年]。我们有兴趣的读者参考这些论文(43,82年,83年]hyperheuristic广泛的审查。

我们所知,到目前为止使用进化hyperheuristics尚未解决的基本模型复杂的物流网络,即。,CLRP CLRPSPD。

3所示。数学公式

CLRPSPD CLRP考虑的是一个更实际的变体的逆向物流皮卡和交付发生在同一时间为每个客户端(4]。CLRPSPD和CLRP上定义一个完整的有向图G= (V,E),V=J∪我是一组节点J和我分别代表了潜在的仓库和客户节点E= {(我,j):我,j∈V,我≠j}\ {(我,j):我,j∈J}是弧的集合。每个弧(我,j)∈E有一个负的距离c_ij。每个客户端我∈我有一个积极的交付需求吗问_我和皮卡的需求p_我(只有CLRPSPD)。一个存储容量和固定成本f_j与每一个潜在的仓库吗j∈J。用指数的车辆类型K组成的均匀的能力问。的目标是确定最优方案的仓库和线路组成的总成本最小化打开仓库,车辆,和旅行费用。

两种类型的MIP配方CLRPSPD参中定义。(38,39]:节点和流为基础配方的区别取决于额外变量的定义在图:节点或弧和相似的上述两个是建立在两个索引的概念。本文基于流的MIP配方为CLRPSPD定义3项。在描述这个配方之前,应该考虑一些假设:(我)每个路线由一个汽车服务,每个客户只提供一次。(2)每辆车必须回到出发的得宝的路线。(3)每个客户端交付货物和在相同的位置,和货物交付给每个客户端之前拿起。(iv)总车辆在任何电弧负载不得超过车辆的能力。(v)总交付和皮卡的需求客户,每个仓库不能超过仓库容量。

决策变量:

额外的变量:U_ijk:每个弧的动态负载(我,j)运营的车辆k。

基于上述假设和符号,提出的基于流程的制定(2)如下: 受

在这3项flow的MIP制定目标函数(1)代表健身价值健身组成的总成本由固定租赁仓库和车辆成本和旅行成本的边缘;约束(2)保证每个客户只提供一次;约束(3)消除仓库之间的路线;约束(4)确保进出边等于每个节点;约束(5)要求只有一个途径是分配给一个车辆和车辆只离开一个仓库;子电路在每个路线被禁止通过约束(6);约束(7)消除了一个客户的情况是由多元不同的仓库;约束(8)指定复数不同仓库必须不存在于相同的路线;约束(9)和(10)执行,客户分配给所选仓库,每个仓库开放必须提供至少一个客户端;每辆车被分配给所选择的选择仓库,每个仓库必须至少有一个车辆,由约束(保证11)和(12);约束(13)确保连续两个客户的路线是由相同的仓库,约束(14)禁止,不得超过总交付和皮卡的需求客户仓库的容量;约束(15)保证所有客户的总交货要求,每个仓库应该等于油库的总交货负载;约束(16)要求所有客户的总皮卡的要求,每个仓库应该等于仓库总皮卡负载;方程(17)表达的正确运动负荷交付和/或皮卡;约束(18)确保每个弧的车辆的总负载不得超过车辆的能力。

4所示。建议的方法

在下面几节中,我们将介绍HH通过描述采用的解决方案表示,有效的建设性的启发式,低级启发式域,九选择策略,和四个高级启发式的验收标准。

4.1。解决方案表示

中发挥着重要作用的解决方案表示CLRPSPD改善算法的性能,应该包括所有的路线和选择仓库的路线。因此,一系列的细胞是用来表示一个完整的解决方案决定了分配客户每辆车,选择仓库,客户的顺序来访问一个特定的车辆开始和结束在同一仓库。本文应用解决方案表示一个简单、高效的编码(2),这是一套完整的车辆路线,也就是说,R= {r₁,r₂、…r_K}插入所选仓库在每个线路的两端。与此同时,我们也每个路由的属性存储在每个路线的第二子室。值得注意的是,我们的染色体表示可以满足约束(2)- (18)避免恢复的可行性解决方案,允许快速评估不需要解码的健身价值。

4.2。初步解决方案

初始化方法是一种改进的贪婪启发式(启发方法的裁判。4]),命名——在这里后悔k贪婪启发式(RKGH),提出我们的以前的工作2]。实施后贪婪启发式(4),仓库的配置(米≥2)已经确定。让x_本土知识∈{1,2,…米}是一个变量,表示客户的仓库我有k^th成本最低,c(我,x_本土知识)≤c(我,x_{本土知识′})。使用这个符号,我们可以定义一个遗憾kΔ价值c^k(我)作为Δc^k(我)=c(我,x_本土知识)−c(我,x_我1)。——换句话说,遗憾k价值的区别是在客户的成本放在第一个仓库及其最佳k^th最好的仓库。RKGH选择分配客户端我最大化

乘数α取决于每个仓库的剩余容量,α代表客户= 1我是由这个仓库没有违反生产约束;否则,α设置为0。本文的价值k也设置为2,即R2GH。

4.3。Hyperlevel启发式

在本文中,我们使用不同的运营商的向量的配对和验收标准。有36个可能配对的九个运营商的向量和四个验收标准。几种策略:RP, TS, FRR-MAB, QS, PS,三个变体也发达。策略实施QS, PS,及其变体可以归类为ES。四个摘要提供验收标准:点,NA, GD和SA。在以下部分中提出了简要的描述。

4.3.1。运营商选择向量设计

运营商选择策略的文献通常概率分配给每个运营商和使用轮盘赌或tournament-like过程选择LLHs根据他们(54),命名为运营商选择向量。运营商的选择向量组成一个数组,每个都有一个概率的选择。本文选择向量是由每个LLH分配概率设计,和最初的选择向量LLHs同等概率的选择。(1)记者:在运行初始向量是没有改变,和LLHs都有平等的选择概率无论性能,也称为固定选择器(84年),随机选择一个与他人作为比较的基准。(2)TS:禁忌列表是用来禁止LLHs过早被应用的最近表现不佳。LLHs属于禁忌(即。,the selection probability is 0) are released (i.e., the selection probability is initial value) whenever other LLHs make a change in objective function, which is slightly different from the aspiration criterion [51]。(3)FRR-MAB [7]:FRR-MAB提出了自适应地选择合适的LLH近期根据其表现在滑动窗口实现FIFO存储机制。讨论了两个连续的阶段:信贷分配和选择机制。前提供测量方法对质量的影响在搜索过程中造成的应用最近LLHs,而后者与最大化选择一个LLH收到信用值产生新的解决方案。申请选择向量,每个LLH规范化的奖励价值作为选择概率。另一个版本基于FRR-MAB结合TS(视为FMT)提出的我们的以前的工作2),吸收的快速反应能力TS排除LLHs表现不佳。(4)q:启发式搜索空间ξLLHs QS被定义为 在哪里h_我=代表h_我问位和|β_我|²和|α_我|²给的概率h_我分别选择和废弃状态,保证|α_我|²+ |β_我|²= 1。基于Q-gate学习策略是利用更新选择概率|β_我|²的h_我基于实时性能。 在哪里是问位的h_我在t^th迭代和的旋转角吗问位;Δθ^t是旋转角t^th迭代;k均匀分布在 ;t_马克斯最大迭代;π^t和分别是,电流选择LLHs序列和选择LLHs获得最佳的解决方案;和的国家是h_我当前,全球的选择LLHs序列;π^t=代表当前LLHs序列;和x^t可以说明x^t=如果ξ= 7。另一个版本基于QS结合TS(命名为QS2),吸收的快速反应能力差的TS排除LLHs性能。(5):灵感来自应用蚁群优化(ACO)旅行商问题(TSP)和0/1背包问题,两个版本的开发成自适应地决定选择有利LLHs序列。第一个变体(联袂,AS2)强调了对LLHs的联合演出通过确定下LLH(一次)基于概率正比于所示每一个启发式的信息素水平对方程(24);在这个版本中,信息素铺设标准(59)修改为对信息素的达成改善之前的函数,也就是说,如果一只蚂蚁执行启发式h_x,h_y,h_z和h_y导致nonimproving和解决方案h_z提供了一个更好的解决方案,信息素将被放置在边缘x- - - - - -z也不x- - - - - -y也不y- - - - - -z,而后者(级)强调个人表现每个LLH通过查看个人LLH作为其信息素轨迹的性能信息(67年]。选择可能的序列LLHs正常化追踪信息素的选择概率。 在哪里(ξ×ξ),(ξ×ξ分别)定义的信息素轨迹和选择概率我- - - - - -j在t^th迭代;0 <ρ≤1表示信息素的蒸发率;冷杉_j是健身改进率相比以前的解决方案(7,55];和η_ij(ξ×ξ)是能见度信息说明启发式信息。上面的方程(25)是用于更新追踪信息素η_ij=T_我+T_j(T_我显示的运行时间h_我),而方程(25)可以修改的η_j=T_j通过忽略之前的h_我。(6)PS: PS被提名为通过策略来衡量他们的订单处理和选择机制的有效性。每个粒子是一个矢量ξ数字代表的选择概率LLHs得到正常化的位置(使用原始配方)粒子。应用粒子施加的顺序LLHs解决方案域。每个粒子冷杉是使用性能评价指标。

在过去七选择策略,利用概率选择LLHs LLHs,最大效用的分数/重量是放置在前面的列表。然后选择LLHs应用于序列遵循这个顺序。然而,选择LLHs序列是随机置换来修改当前RP和TS的解决方案。

4.3.2。验收标准设计

最近LLHs的应用后,取得解决方案被认为是接受作为现任解决方案到下一个迭代。如果新的解决方案是至少一样好前面的解决方案将取代,然后它会自动被认为是当前解决方案无论接受的本质机制;否则,验收标准是利用是否丢弃新解决方案(65年,84年]。提出了以下四个验收标准与上述选择策略,旨在指出这对比别人表现得更好。(1)我(5:当前的结果是被所有新结果与概率值1。(2)NA (84年:目前的结果是被no-improving结果与概率值为0.5。(3)GD [50,84年]:no-improving结果被接受,如果它比一个动态变化的阈值,取决于当前和历史的健康信息。决定接受孩子的解决方案的范围,应用阈值,减少与增加迭代。 在哪里t和t_马克斯显示当前和最大迭代步骤G_最好的(t)代表全球最佳解决方案到目前为止所发现的客观价值。(4)SA (65年]:新的解决方案被认为是当前解决方案是否满足概率准则,即改善结果接受概率值在1虽然no-improving结果被接受统一的值在[0,1]临界值。接受的概率计算在SA no-improving方案决定是否接受它(65年]: Δ在哪里f之间的区别是质量新的解决方案和当前解决方案和ΔF^t代表预期的质量变化范围,最大限度地解决方案,ΔF^t=G_最好的(t)−G_最好的(0)。

4.4。低级的启发式

LLHs的池可以被视为一个“黑盒子”,是用来扰乱现任解决方案通过强化或多样化的搜索在搜索区域,用于参考。2]。他们通常是一组简单,便宜,而且knowledge-poor LLHs [5]。本文的模块是由13 LLHsh₁,h₂、…h₁₃跨两个池的启发式:突变启发式(MH)和本地搜索/山登山者(HC),确定的角色在改善或恶化的解决方案。前六LLHs实现探索新的地区:2-opt,还是选择,转变,交换,添加,肖。其他人则利用利用更好的解决方案:搬迁,2-opt, 3-opt,搬迁,1-interchange算法,应用内部和inter-route动作。

的详细信息h₁∼h₄可以从裁判获得。54),这是简单和基本的突变启发式。的h₅启发式分散开放仓库之间通过打开一个新的和随机分配1和2/3的路线(37]。最后LLH多元化h₆(85年),这是一个方法命名为destroy-and-repair运营商提出删除相关的客户,即。、客户地理上彼此接近,插入到最佳位置。在我们的论文中,基本的贪婪启发式(86年)建议重新插入删除客户回路线。干扰的解决方案被接受,只要上述验收标准在每个弧和车辆容量和仓库容量是服从。

搬迁h₇重新选择合适的仓库确定开发路线。每个路由陷入一个集群和最小的插入成本可以作为仓库的距离计算在原来的路线。更大的仓库数量的集群优先开放。然后其他未赋值的集群(从大到小的顺序)共享相同的接近最亲密的仓库,仓库将安排,除非指定仓库的能力和成本并不满意。2-opt [87年)在线路相当于知名2-opt移动(h₈)[88年),而另一个版本的2-opt实现不同路线标识(h₉)。由于减少了CPU时间,intral-3-opt (h₁₀)[89年只考虑。搬迁启发式(90年]统治者一个客户在另一个位置在现任路线(h₁₁)或在另一个路线(h₁₂)。1-interchange [91年启发式互换每个职位的客户从一个路线与每个客户在另一条路线,如果不共享相同的仓库(h₁₃)。如果找到改进和仓库容量和车辆荷载在每个弧,上述举措实现,允许他们改善现有的解决方案。

肉类通常执行简单随机移动到扰乱现任解决方案没有保证竞争的结果。尽管实现竞争力不足的结果,他们是有用的随机化,有利于导航提供当地的最适条件。然而,高碳钢扮演着一个关键角色,迅速获得更好的解决方案在每一步。此外,它可能是可取的应用高碳钢在应用程序的任何MH和肉类如果很难申请高碳钢提供有价值的解决方案。考虑上述特性,提出九选择策略是利用自适应管理高碳钢,灵感从本地搜索启发式机制管理5,54)和自动分类方法根据性能提出了裁判。57]。概率选择任何一个MH作为指导者摆脱局部最优设置为1当且仅当没有HC可以提供一个改进之前的客观价值;否则,概率值设置为0。因此,图1摘要hyperheuristics应用框架。

此外,停止机制定义为评价限制最大数量的健身评价(α_马克斯),旨在提供公平的比较。

5。计算评价

在本文中,我们探索的表现一组hyperheuristics解决CLRP CLRPSPD。实验由四个部分组成。在第一部分中,一个整体相关的选择策略和验收提供替代品来排名36双并确定前四个优秀的性能对下列实验。然后,选择对的效率和功能进行了分析通过实现的三套CLRP基准实例。在第三部分中,我们探索的性能选择对解决CLRPSPD基准集。最后,选择对的性能测试与最近的和有效的定制方法在文献中。

5.1。实验设计

给了HH方法36双编码在Matlab 8.6和桌面计算机上运行英特尔酷睿i7 - 6700 k (TM) (4.00 GHz)和8 GB RAM, Windows下10;它是嵌入到CLOR工具,可用电子邮件给我们。

校准是,两种类型的参数有关:具体参数和常见hyperheuristic参数选择策略。前者涉及到选择的设置策略,而后者占LLHs之间常见的参数,通过总结在表2。

一些指定的参数按照违约提出的文学,和其他人进行初步实验测定各种设置针对获得相对更好的结果在合理的CPU时间。常见hyperheuristic参数,初步选择概率p设置为每个LLH 0.5符合QS的初始概率振幅;禁忌列表的大小l_t设置为7这是高碳钢的数量;single-point-based搜索hyperheuristic框架研究本文中使用的人口规模LLH和通过设置在1。相当比较每组的运行时间,健身的最大数量为每个实例评价,提供不同的方法在裁判。2(即。,the maximum iterations without improving solution), depending directly on the number of clients, depots, and vehicles:

针对获得良好的解的质量和计算时间之间的权衡,乘数一个是在所有实例值5。

5.2。基准实例

三套CLRP基准实例采用评估的效率和功能为hyperheuristic每一对。这些集合提供了参考文献。(26- - - - - -28]。一种分离方法用于生成的数据集CLRPSPD从上面CLRP基准,实例化W输入参考。92年与设置0.8)β。

第一基准实例(28)包含19例。的客户范围从12到318的数量,和仓库的数量米2和15之间的不同,以及车辆固定成本不是。在随机生成集27),客户范围从20到200的数量,仓库的数量米5,10,和车辆容量问是{70、150}= 1000。基准实例(26]也随机生成含有36例n∈{100、150、200},米∈{10 20},问= 150,= 10。和客户的需求这个基准测试的范围从1到20。上述三个基准集都是可用的http://sweet.ua.pt/sbarreto/or_http: / / prodhonc.free.fr /主页。

欧几里得距离被应用在所有的数据集。CLRPSPD王子等人基准设定,获得的距离乘以100 (CLRP围捕到下一个整数)和总成本围捕到下一个整数,它不同于参集获得的。(4,38]。车辆的工作成本为每个实例与小于100客户在第一盘增加到20,也就是说,= 20。

5.3。结果

5.3.1。36对实验

第一组实验进行比较的性能36对hyperheuristics针对确定的前四个优秀对以下实验。九CLRP实例Barreto组客户从50到318的数量是每一对的用于测试性能,实现50每个实例上运行。健康评估的最大数量设置为10000。针对所有成对比较和评分,公式(1)采用评分系统,由CHESC用于排名方法(跨域启发式搜索的挑战)在2010年之前(http://www.asap.cs.nott.ac.uk/external/chesc2011/)。前八名的方法给出了10分,8、6、5、4、3、2、1分,每题从最好到最坏的情况下,先后[65年]。其余的方法得到0分。本文10分的分数分配给对可以利用最著名的解决方案(noble),和其他的分数对类似于公式(1)评分系统。因此,90年是最大的总分一对。

实验结果如表所示3,整体成绩最好的四双,九选择策略,和四个提供验收标准。从结果可以看出,HH表演我是最好的赢家,和PS-AM QS2-SA, TS-SA也比其他对。hyperheuristic使用,FRR-MAB-TS、TS和RP选择组件执行比其他人无论接受组件,和一些有趣的结论可以从整体分数(1)TS可以促进更好的性能选择策略通过排除LLHs表现不佳,与选择策略的性能相比没有TS,达到改善平均25分;(2)使用0/1背包问题的性能优于AS2应用TSP,换句话说,相比一个铺设蚂蚁信息素轨迹路线,机制奠定蚂蚁信息素轨迹顶点(即。LLHs)有更大的机会成功指导LLHs蚂蚁选择有前途的序列;(3)PS-AM和QS2-SA总分排名第二/第三位配对,即使PS / QS2几乎没有令人满意的性能。从过去四分数接受组件无论选择组件,和SA排名,分别第一和第二得分529年和518年,而其他两个接收的473年和429年,分别。

图2显示的箱线图的9个选择策略和四个验收标准。箱线图,获得的最大和最小值(不包括异常值),上下四分位数、中位数。

从这样的分析和回答第一个实验中,我们认为我是最好的一对考虑大多数情况下和分数,和额外的PS-AM QS2-SA, TS-SA也选择进行以下实验。

5.3.2。实验CLRP

前四个优秀对测试执行50每个实例上运行,从最好的发现解决方案,差距noble,和计算时间,提供页面空间不足。三个CLRP基准实例的结果如表所示4- - - - - -6。每个表的第一列是每个实例的名称,其次是商品,和结果四对含有最好的发现结果(最好),差距(百分比)人,平均计算时间秒(CPU)。平均数和中位数的值差距和CPU显示在最后两行。

第一个三双(表4),商品的实例与小于150的客户利用平均差距TS-SA−0.04%, QS2-SA−0.07%,−0.05%给我。只有一个人无法发现的差距为0.06%,最高的最后一对平均值−0.04%。关于商品的平均价值差距,它们的值0。计算时间平均不到29岁,25岁,27岁和17岁的年代,和中间值低于6 s即使最大的实例存在。两个新的商品由四对发现,获得超过0.5%的改善perl83 - 318×4 PS-AM和perl83 - 318×0.7%以上由QS2-SA 4 - 2。

在第二个基准(表5可以找到),至少有16人四双,找到最好的50-5-2b与差异。四个新商品在这个集合中分别获得,达成改善超过0.3%的200 - 10 - 1 b TS-SA PS-AM和0.1% 200 - 10 - 2 b和200 - 10 - 3 b TS-SA。关于空白的最佳,平均值,分别对其他双TS-SA为0.06%和0.07%,最高的差距是四双的不到0.8%。所有对中间值等于0。CPU平均值和中位数的值分别是50.8和14.9年代TS-SA, 47.7和15.3年代QS2-SA,我41岁和13.1 s, PA-AM 33.6和12.6 s。

Tuzun和伯克基准(表6),TS-SA PS-AM并列第一名的新商品发现13个新的商品,和QS2-SA反面获胜者第二利用12个新商品和我同样是在过去的地方。有关解决方案的数量小于或等于noble, TS-SA, PS-AM, QS2-SA,分别排名第一,第二,第三,29日,28日和27日解决方案小于或等于商品,和我同样等级的地方26小于或等于noble的解决方案。让我们吃惊的是,新商品的数量占30%以上,除了我有27.8%的36个实例在这个基准。关于空白的最佳,平均值分别TS-SA−0.01%, 0.01% QS2-SA和PS-AM SA-AM为0.03%,所有对中间值是0。计算平均时间是77.6,74.5,59.6,和52.5 s,和中位数的值是62.6,64.4,53.8和50.3。

我们对结果进行统计分析的三组CLRP基准表4- - - - - -6通过表7基于多个成对比较95%置信水平(例如,α= 0.05),即弗里德曼测试。在弗里德曼的测试,零假设(H₀)只是拒绝如果弗里德曼统计(χ²)大于临界值,查找χ²表通过样本大小和置信水平和事后测试基于Wilcoxon Rank-Sum应进行检测样品之间的显著差异,在需要的时候;否则,零假设(H₀)是接受指示,四双之间无显著差异有关。在表7弗里德曼统计(χ²)的值为3.923 Barreto et al ., 6.750普林斯et al .,和6.201 Tuzun和伯克,分别低于10.117,18.493和23.269,表明没有明显的四双性能之间的差异。

5.3.3。实验CLRPSPD

CLRPSPD基准实例,首先在参转换。(2,38),也用于评估最好的四双的特性。然而,本文只考虑了WCLRPSPD上述类型集。主要原因是组X,Y,Z类型显示相同的特征与原套CLRP,是最难获得商品的使用实例W类型的分离方法。所有的商品都来自裁判。1]。结果三个CLRPSPD基准实例表所示8- - - - - -10。每个表的第一列是每个实例的名称,紧随其后的是最著名的解决方案(noble),数据前四最好对含有最好的结果(最好),差距(百分比)人,平均计算时间秒(CPU)。平均(AV)和中间值(MD)差距或差距和CPU显示在最后两行。

Barreto基准,计算平均时间低于35岁,30岁,29岁和18岁中间值是3.9,4,3.4,和3.1 s,分别。关于空白的最佳,平均值分别为0、0.03%、0.01%和0.03%,和中位数的值等于0。新商品例如318客户发现0.11%的改进之前由我和PS-AM募集。差距与最高noble所有实例非常低缺口为第一对低于0.08%,0.25%为第二和第三条,最后一个为0.42%。

看表9计算时间平均不到65年,60岁,50岁和40年代,分别和中间值,分别为17.6,18.3,16.2和13.8。关于空白noble,平均和中间值,分别为TS-SA−0.17%和0,QS2-SA−0.12%和0,−0.15和0第三条,−0.16和0最后一对。商品从缺口的角度来看,我们验证了方案实现裁判。2]。与此同时,我们获得了四个改进四个实例,即。,50-5-3(问年代2- - - - - -年代A), 200-10-1 (four pairs), 200-10-1b (four pairs except for QS2-SA), and 200-10-2b (PS-AM), one of them reaching an improvement of over 5.9% to previous BKSs.

如表所示10计算时间平均不到84,83,64,和56个年代,和中位数的值是66.6,68.6,58.6,和47.7 s,分别。至于差距商品而言,平均/值中位数0.1 / 0.05%,0.16 / 0.09%,0.14 / 0.08%,分别和0.21 / 0.08%。与此同时,新商品的九个实例是由我们提出的算法,获得最大的进步是P23通过QS2-SA超过1%。我比其他人获得五个新的商品,其次是TS-SA QS2-SA, PS-AM表现最糟糕的。然而,表现最好的双TS-SA平均差距募集。

统计分析进行了三组结果的表8- - - - - -10通过表11根据弗里德曼的测试。在表11弗里德曼统计(χ²)的值为3.279 Barreto et al ., 4.621普林斯et al .,和4.087 Tuzun和伯克,分别低于10.117,18.493和23.269,表明有四双的性能之间无显著差异。因此,我们可以强烈地得出结论,提出对CLRPSPD基准实例可以实现高质量的解决方案。

总的来说,四双,两种类型的讨论和结论进行:一个对问题域,一个用于hyperheuristic对。从量的角度的主题,CPU时间直接取决于客户的数量(n)、仓库(米)和车辆容量(问),运行时间和上面的因素之间的关系图3和4(不包括异常值)和图5。一些结论在运行时间达到:(1)运行时间受到客户的数量以指数方式;(2)仓库的数量有轻微的影响运行时间,这可能会导致一些仓库;(3)计算时间增加而减少车辆的多项式形式的能力;(4)上述影响因素的顺序运行时间的影响n,问,米。第一个和第三个结论也共享Ref。2]。此外,时间复杂度和解决方案可能部分取决于质量的数学模型的复杂性。图6说明了数学模型的复杂性对运行时间的影响。更具体地说,解决CLRPSPD实例的平均计算时间Barreto集,就会增加4.2 - -21.5% 30.6 - -46.8%为王子,Tuzun和伯克和5.3 -10.2%,分别比处理CLRP病例的平均运行时间。关于解决方案的质量和平均标准偏差,实例的复杂性是直接作用的因素包括客户的数量,仓库和车辆,客户和仓库的分布。此外,复杂的方法或者对选择策略和验收标准也显著影响运行时间,标准偏差和解决方案的质量。PS-AM似乎与下降最快的36岁,33岁,20%的平均运行时间与别人相比,我和QS2-SA排名第二和第三的平均运行时间。解决方案的质量,没有显著差异在这些四对弗里德曼通过上面的测试,表明PS-AM和我比其他人获得更好的折衷解决方案质量和运行时间,但所有对可以获得高的解决方案质量合理的运行时间。

5.3.4。比较和评价

来说明我们提出的方法的优点CLRP CLRPSPD,比较最近的和有效的方法在文献中在表进行12,平均差距(AG)发现的最好解决商品和平均运行时间CLRP提供建议的方法,它们分别掌握+船(31日],SALRP / SALRP + [32],ALNS / ALNS + [33,宏观35,高度34),掌握独立+ (25],GVTNS [36],近半年/近半年+ (37),CLRPSPD,方法是BC-SA [38),SA / SA(4),和RP / TS / FRR-MAB / FMT [2]。

即使时间执行的比较是不公平的,这取决于许多因素(电脑配置、编程语言、健康评估的数量,等等),这是一个显著的性能指标判断方法的优势。如表所示12似乎,我们四对hyperheuristic上述方法中最快的。此外,我们的方法方面的解决方案中最好的质量在所有CLRP CLRPSPD基准集和非常小的差距。总之,我们可以强烈认为hyperheuristics能够超越最近的和有效的方法解决质量或计算时间。

6。结论和未来的工作

在这项研究中,提出了基于进化学的hyperheuristics应对CLRP和它的一个变体,即CLRPSPD。五个进化和四个与选择策略作为高级开发选择策略与四个验收标准做出正确的决定在构建有效的序列LLHs每一步,指导该方法达到最优值。

第一个实验进行了确定四大双可以正确地反映每个LLH的性能信息和快速应对选择有前途的LLHs。结果表明,(1)我和SA验收标准执行更好的相比其他两个;(2)、FRR-MAB-TS和TS作为选择策略表现更好相比其他的选择策略;(3)我的平均表现,PS-AM, QS2-SA, TS-SA通过执行明显比其余的对。第一个四个突出的双挑出实现剩下的两个实验。PS-AM和我比别人获得良好的解的质量和计算时间之间的权衡,以及所有四对合理的运行时间内可以实现高质量的解决方案,提供一些新的商品占超过30% Tuzun和伯克CLRP集。比较分析也进行了定制的方法发表文献中,结果表明,我们提出的方法的性能优于上述方法在解的质量和计算时间。提倡Ref。93年hyperheuristic),该方法在利用能力足够好,很快,和足够便宜的解决方案。

拟议中的hyperheuristic(36条)已经实现决策支持工具,和我们感兴趣的读者参考咨询方案。接下来的研究内容将关注的自适应选择肉类和其他山登山者的选择策略,例如,选择函数(5,47),自适应追求(94年),和公平份额方法(95年]。使CLRP / CLRPSPD更贴近现实,更实际的约束也会考虑在未来的作品,如时间窗、动态要求,交付,和皮卡。

数据可用性

使用的数据来支持本研究的发现可以从相应的作者。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项工作在一定程度上支持中国的国家自然科学基金(51875524和51875524号)和国家自然科学基金委的浙江(没有。Y19F030017)。