改进的冠状病毒群体免疫优化算法解决车辆路径问题

沙特国王大学学报一种改进的冠状病毒群体免疫优化算法求解有容量限制的车辆路径问题放大图片作者：Lamees Mohammad Dalbaha，Mohammed Azmi Al-Betara，b，Mohammed A.Awadallahc，d，Raed Abu Zitarea阿拉伯联合酋长国阿治曼大学工程与信息技术学院人工智能研究中心（AIRC）b信息技术系，Al-Huson大学学院，Al-Balqa应用大学，P.O. Box 50，Al-Huson，伊尔比德，约旦c阿克萨大学计算机科学系，P.O. Box 4051，加沙，巴勒斯坦d阿拉伯联合酋长国阿拉伯联合酋长国阿布扎比，索邦大学，索邦人工智能中心阿提奇莱因福奥文章历史记录：2021年1月13日收到2021年6月16日修订2021年6月17日接受2021年6月24日在线提供保留字：优化冠状病毒群免疫优化器（CHIO）车辆路径问题COVID-19元分析学A B S T R A C T容量约束车辆路径问题是一个NP难调度问题，其主要问题是在一定的车辆容量约束下，为多个分散的客户服务，寻找最优的车辆路径。由于容量限制的车辆路径问题的复杂性，元启发式优化算法被广泛用于解决这类挑战。冠状病毒群体免疫优化器（CHIO）是一种最新的基于人群的元启发式算法，它模仿了COVID-19群体免疫治疗策略。本文对CHIO算法进行了改进，并将其应用于有能力约束的车辆路径问题。对CHIO的修改是通过修改其算子来实现的，以保持这种类型的车辆路径问题的解决方案的可行性为了评估修改后的CHIO，使用两组数据集：第一组数据集有10个合成CVRP模型，而第二组是ABEFMP数据集，其中有27个不同模型的实例。此外，通过修改CHIO实现的结果与其他13个备受好评的算法的结果进行了比较对于第一个数据集，修改后的对于第二个和更复杂的数据集，修改后的CHIO能够实现非常有竞争力的结果，并在27个实例中排名第一。总之，修改后的CHIO能够有效地解决容量限制的车辆路径问题，并可以用于其他路径问题，如多旅行商问题在未来版权所有©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍在20世纪50年代后期，车辆路径问题（VRP）被定义为对现实世界的路径和调度问题的模仿（Zhou等人，2016年）。它的目标是观察最佳路线的车辆数量，其中车辆负责*通讯作者：阿拉伯联合酋长国阿治曼大学工程与信息技术学院人工智能研究中心（AIRC）电 子 邮 件 地 址 ： 202011795@ajmanuni.ac.ae （ L.M.Dalbah ） ， m.ac.aewww.example.comAl-Betar ） ， ma. alaqsa.edu.ps （ M.A.Awadallah ） ，raed.sorbonne.ae（R.A. Zitar）。沙特国王大学负责同行审查用于将产品交付给多个客户。1959年，Dantzig和Ramser在基本的VRP优化问题中加入了车辆容量约束，称之为有容量约束的车辆路径问题（CVRP）。车辆容量限制是指确保车辆在其容量范围内运送货物。在优化术语中，VRP被称为NP难问题，因为它是多个旅行商问题（mTSP）的集成（Archetti等人，2011年），其中，很难找到解决方案，通常只能得到“足够好”的解决方案。此外，CVRP可以被认为是其他类型问题的基础问题，例如Boyer等人（2018）所示的机组调度问题（CSP）。传统上认为，NP难问题很难用精确算法来解决。因此，使用了启发式和Meta启发式算法（Sharma和Saini，2020）。启发式算法被用作逐步求解技术，直到完成整个图片部分（例如，CVRP路线）。因此，只能对低维问题实施逻辑学，并且由于现实生活中的问题很多，https://doi.org/10.1016/j.jksuci.2021.06.0131319-1578/©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comL.M. Dalbah，文学硕士Al-Betar，M.A.Awadallah等人沙特国王大学学报47831/4fgΣ Σ ΣΣ元分析因其复杂的高维性而受到优化研究界的关注。这是因为他们能够在可接受的时间内为复杂问题提出可接受的解决方案。元启发式算法是自然或生物启发的算法。最流行的元启发式算法是遗传算法（Koza和Koza ， 1992 ） 、 粒 子 群 优 化 （ PSO ） （ Eberhart 和 Kennedy ，1995 ） 、人 工 蜂 群（ ABC ） （Karaboga ， 2005 ） 、花 授 粉 算法（ Alyasseri 等 人 ， 2018 ） 、 蚁 群 优 化 （ ACO ） （ Dorigo 等 人 ，2006）、哈里斯霍克优化（HHO）（Heidari等人，2019;Al-Betar等人，2021）、Krill Herd算法（Bolaji等人，2016），b-爬山优化器（ Al-Betar ， 2017; Al-Betar 等 人 ， 2019 ） ， 以 及 Dokeroglu 等 人（2019）报道的许多其他研究。此外，元启发式用于优化深度学习方法，例如神经网络（De Rosaet al.， 2018年）。元启发式算法被广泛应用于车辆路径问题以及与车辆路径问题相关的各种问题。在Wei等人（2018）中，使用具有二维装载约束的模拟退火算法来解决车辆路径问题（CVRP）的容量限制版本。此外，Ng等人的作者。（2017）使用多种群人工蜂群算法解决了时间相关交通拥堵下的CVRP。其他研究人员考虑切换离散VRP和准连续VRP的解决方案，如Li等人（2019）。提出了改进蝙蝠仿生元启发式算法的切换准则。此外，Fathollahi-Fard等人（2020）中的Red Deer元启发式（RDA）和众所周知的遗传算法（GA）（Baker和Ayechew，2003）被用于解决VRP。在另一项研究中，遗传算法与禁忌搜索算法相结合来求解VRP，他们称之为GTS（Prins，2004）。在GTS中，禁忌搜索算法取代变异算子，以增强局部搜索能力。实验结果表明，GTS算法的解质量优于GA算法. Zhou等人（2016年）将蝙蝠算法与路径重链接相结合，用于求解CVRP，作者称之为HBA-PR。在HBA-PR算法中引入了路径重连，与其他方法相比，HBA-PR算法取得了令人满意的结果。类似地，Feld等人将量子退火算法与2-Phase-Heuristic相结合来求解CVRP。（2019年）。该算法采用启发式算法将CVRP分为分簇和路由两个阶段。在聚类阶段，CVRP映射到背包问题，以包装客户到车辆。在路径选择阶段，将CVRP问题映射为旅行商问题，以寻找最小路径。仿真结果表明，与其他算法相比，该算法在计算时间和解的质量方面是有效的。Elshaer和Awad（2020）和Zhang（2021）报道了其他提出来解决VRP的元启发式算法。状病毒群豁免优化器（CHIO）是最近的一Al-Betaret al.（2020）提出的基于群体的元启发式算法。群体免疫机制是CHIO的核心部分，用于在COVID-19大流行期间治愈人群。CHIO通过13个单/多模态测试函数和几个工程优化问题证明了它的效率。CHIO在参数要求和数学计算方面可以被认为是一个简单的算法，因为它需要很少的参数初始化和简单的数学case函数实现。与其他基于种群的算法一样，CHIO首先初始化一个随机种群，其中种群中的每个个体代表一个问题解决方案。人群个体分为易感病例、免疫病例和感染病例。为每种情况类型形成适应度函数。 反复地，人口将通过进化步骤得到增强，直到满足停止条件。最近，CHIO已经成功地应用于Tra- vailing Salesman Problems（Dalbah等人， 2021），以及车轮电机设计问题（Mary等人，2021年）。COVID-19也是一些机器学习作品的灵感来源（Zivkovic et al.， 2021年）。由于CVRP的复杂性，在本文中，以下贡献可以总结如下：1. CHIO步骤已被修改，以兼容并有效地用于CVRP搜索空间。2. 通过在改进的CHIO优化循环中使用修复过程，保持CVRP的可行性。使用两组数据集来评估改进后的CHIO的性能：包含10个模型的简单数据集和包含27个模型的复杂数据集。CVRP所使用的基准在复杂性和问题维度方面各不相同。评估结果以适应度函数值（即，最好的，最坏的，平均成本）。作为评价步骤，改进的CHIO方法的性能也与其他13个元启发式算法进行了比较。有趣的是，对于第一个数据集，所提出的CHIO能够在十个实例中的两个实例中获得与其他比较方法相同的最佳结果，并且对于其余实例获得可接受的结果。对于第二个和更复杂的数据集，所提出的CHIO能够实现非常有竞争力的结果，并排名第一27起案件中有8起本文的其余部分组织如下：CVRP的定义和讨论在第2节。在第3节中介绍了用于CVRP时CHIO优化器的修改步骤的使用。VRP数据集描述和CHIO与其他比较方法的结果讨论见第4节。第五部分总结了本文的研究结果，并指出了未来的工作方向.2. 问题描述在解决优化问题时，主要关注的是在不违反问题约束的情况下实现要求。在此基础上，定义了VRP的成本函数，以有效地评价VRP的完成结果。VRP模型使用成本函数来确定总服务距离，并相应地增强或选择解决方案。车辆容量是一个额外的约束条件，使车辆路径问题更加现实。这种约束确保车辆在其能力范围内提供需求。能力约束车辆路径问题是车辆路径问题的一种扩展，它保证了车辆的能力约束在车辆路径问题的求解中得到考虑2.1. 数学模型CVRP模型的数学符号见表1。CVRP模型由j个客户（C1;C2;... . ;cjg），其中的每一个请求需求的数量（r1/2r1;r2;. . ;rj]）。车辆段配备有i 辆 车（V¼fv 1;v 2;. . ;vig） ，每 个 都具有 恒 定 容量（VAva1;va2;... ;va i）。仓库和客户有X和y坐标这指到他们的位置X¼x0;x1;x2;. ;xj=0;y1;y2;. ;y j =0。 注意x0和y0是仓库坐标。其目标是发现车辆路线，以最小的总距离服务于客户的需求，并确保约束满足。作为初始步骤，每个客户和仓库之间的距离使用等式计算。（一）.此外，每个客户和所有其他客户之间的距离arw使用Eq. （2）、L.M. Dalbah，文学硕士Al-Betar，M.A.Awadallah等人沙特国王大学学报4784XXXK J[1/2]表1容量限制车辆路径问题符号和说明。符号描述i车辆数量（v）j客户数量（C）为了继续下去，使用方程（1）验证飞行器容量约束需求。（三）、此后，如果满足，则路由成本VC将使用Eq. （四）、最后，所有的车辆成本是总结了使用方程。（五）、该结果将代表解决方案的有效性。n子集中的nr客户需求va车辆容量车辆路线车辆成本vvirkk¼16vai;n2j3n车辆容量有效性xy客户坐标x0y0仓库坐标vcidc1胡志明市dk¼1;n2j其中k和j是客户索引。作为一个假设，我们假设距离是对称的，使得ck和cj之间的距离等于cj和ck之间的距离。同样的假设也适用于仓库和客户之间的距离。我最小值（V）1/13. 车辆路径问题（VRP）的冠状Dc ¼qx0-xj2y0-y j2dc;c <$qxk-xj2yk-yj2ð1Þð2Þ自2019年12月以来，世界正面临一场名为被世界卫生组织列为冠状病毒疾病（COVID-19）（组织，2020; Singhal，2020）。该病毒是一种攻击活宿主器官细胞的因此，客户将被划分为子集，其中包含n个客户，将为每辆车建立一条路线，仓库;c1;c2;. 仓库确保起点和终点都在仓库为了2015年）。它通常攻击呼吸系统。用于将个体诊断为感染病例的常用方法是使用血液样品（DPI测试）或通过鼻交换（聚合酶链反应PCR测试）（Ibarrondo等人， 2020年）。的起源Fig. 1. 提出的改进的CHIO算法的流程图。JL.M. Dalbah，文学硕士Al-Betar，M.A.Awadallah等人沙特国王大学学报4785ðÞ¼ðÞCOVID-19疾病被认为是蝙蝠，但病毒如何传播给人类仍未得到证实（Singhal，2020）。截至二零二零年十二月底，COVID-19的传播导致超过77百万例确诊病例及约707，000人死亡，涉及220个国家1以便表2CHIO参数。变量描述类类型PopSize人口规模正整数参数为了降低死亡率，必须通过自然感染病原体或接种疫苗来提高人群免疫率（Randolph和Barreiro，2020）。抗体的间接作用机制建立的免疫系统被称为群体免疫（Randolph和Barreiro，2020）。lb和ub下部和上部顾客c最大迭代次数正/负整数正整数在这种疾病的情况下，人口个体被分为感染个体（确诊病例）、免疫个体n问题维数正整数BRr基本扩散率阳性双对照参数（那些拥有“豁免护照”的人）Ibarrondo等人，2020）和易感个体（有感染风险的人）（Randolph和Barreiro，2020）。社会距离是一种保护个人的方法，最大年龄感染病例阈值年龄C0初始感染病例数，初始等于1正整数隔离确诊病例以及与之有直接接触的人他们从社区的其他人，从而保护可疑的个人。群体免疫方法和社会距离-每种方法都可以单独使用来处理流行病，或者可以互换使用，直到达到有效的治疗3.1. CHIO程序步骤COVID-19传播和群体免疫现象是CHIO算法的灵感来源（Al-Betaret al.， 2020年）。CHIO的优化过程是真实流行病的演示，其中个体代表优化解决方案。根据社会距离和群体免疫的实施，最终将个体转化为免疫案例，同样也会优化CHIO算法的解 图 1说明了所提出的算法的程序步骤。CHIO适用于有能力限制的车辆路径问题（VRP）。CHIO由六个程序步骤组成。随后的小节包含每个步骤的详细说明3.1.1. 步骤1：初始化CHIO和问题参数CHIO参数分为算法参数和控制参数。CHIO算法参数是用作群体建立参数的定量参数，例如：群体大小、最大迭代次数、个体的上下界和问题维度。另一方面，管理CHIO姿态的参数是控制参数。CHIO控制参数是传播率（或繁殖率（BRr））、感染病例阈值年龄（Maxa ge）和确诊病例的初始数量（通常等于1）。参数描述、类别和类型见表2。关于CVRP，其参数通常从CVRP基准模型上传所需的参数是客户和车辆的数量、每个客户的需求、每个车辆的容量以及客户和仓库的位置。3.1.2. 步骤2：人口生成CHIO的种群应填充CVRP溶液，并且这些溶液必须可行。总体被构造为具有PopSize大小的路由实例的结构矩阵。每个路由案例代表CVRP的一个解决方案，包括位置、费用、年龄、状态和解决方案，如图所示。 二、每个变量的描述见表3。请注意，状态为1的路由事例数等于C0的值。1https://www.worldometers.info/coronavirus。CVRP解决方案表示CVRP解决方案，如图所示。 3，表示为结构矩阵R r 1; r 2;. ;rPopSize，其中ri是总体中的结构化解决方案，包括关于每个车辆将遵循的路线和行驶距离，每个车辆处理的货物，以及IsFeasible变量，用于检查可行性状态。注意IsFeasible变量的值将为0或1，该值完全取决于车辆的货物验证能力（vv），使用公式（3）在第2节中讨论。例如，如果所有车辆满足容量约束，则IsFeasible将为1。否则，它将为0（如果一个或更多车辆违反容量限制）。表4显示了矩阵变量的结构。在建立车辆路径时，将顾客在车辆之间进行分配，并对容量有效性提出要求，以满足容量约束。分配客户的标准可以概括为以下六个步骤：步骤1初始化第2步对“Positions”进行排序，并将索引存储在“Indices”数组中。步骤3创建“车辆”矢量= 1.. . 其值将按顺序排列的车辆数量。第4步根据“指数”中的顺序将客户平均分配到车辆中步骤5将剩余的客户按照vehi- cle数组进行分配，每次对“Vehicle”数组进行右循环移位第6步计算每辆车处理的总需求量，如下所示：情况1如果总需求6车辆容量，则设置vv= 1壳体2如果总需求>车辆容量，则删除一个客户并将其添加到下一辆车的末尾请注意，下一辆车是根据“车辆”数组选择的每次使用“交通工具”数组时循环使用此后，将对当前车辆重复步骤修理程序如果车辆处理的需求大于车辆容量，则将对车辆中的客户进行维修。 在这种情况下，修复过程将被调用，而preparing初始种群在解决方案的进化循环。修复程序旨在调整客户分布，而不是重新初始化解决方案。为了管理此问题，一位客户将L.M. Dalbah，文学硕士Al-Betar，M.A.Awadallah等人沙特国王大学学报4786图二. 人口结构数组。表3人口变量的描述。变量描述定位由CHIO算法参数的lb和ub范围内的实值随机初始化的i个成本值vRv车辆路线的总长度，表示为vc年龄初始化为零，随着病例持续感染而状态由0或1初始化，0表示易感病例，1表示确诊病例解决方案布线案例换到另一辆车，以实现所需的可行性。为此，将计数器变量try num附加到每个车辆，指示调用修复策略的次数此外，此变量将用于确定要删除的客户。如算法1中所示执行修理程序，该算法还确保所有车辆被分配为服务至少一个客户，其中车辆向量是1/21;2;3;4;. . ;i]代表-表4解决方案变量。变量描述可行性0或1表示车辆容量和货物分配状态车辆路线的VRVC1xI车辆阵列行驶距离成本VV0或1表示车辆负载验证发送车辆编号，其中1表示车辆1，2表示车辆2，依此类推。numcust是一个变量，存储车辆服务的客户数量。try num是一个客户索引变量，以及存储解决方案修复路径的数量的变量。removec变量保存将被移除的客户，并且该客户将被分配给剩余车辆之一。将服务于removec客户的期望车辆编号存储在下一车辆变量中。要构建解决方案，首先，解决方案车辆try num变量将被设置为零。 然后，对于每辆车，将使用numel函数计算num cust，该函数提供向量中元素的数量。接下来，将检查try num和num cust变量，以便try num此检查步骤是为了保持维修和客户删除图三. 解决方案结构数组。L.M. Dalbah，文学硕士Al-Betar，M.A.Awadallah等人沙特国王大学学报4787J3JJJJJJ2JJPf cKJJðþ Þð ð Þ ððþ ÞÞ ð ð Þ人口规JþJJJJJJ¼Jj j jjj j jjjj jj我黑腹小在车辆服务的客户数量内进行处理。接下来的步骤是客户删除步骤。它首先指定remove c客户。将从车辆中删除的客户的索引将为“end-（try_num）"。 以来修复过程是一个重复的过程，每次try num都加1。将更改选择删除的客户。被选中的客户将被转移到下一个车辆，其中下一辆车是车辆向量中的第一辆车。保持记住，新客户将被放置在下一个车辆变量的末尾。最后一步是将循环移位应用于Vehi- cle向量，以便在每个时间。下一辆车是相应的现代-固定（例如，循环移位前的车辆= [1，2，，5，6]，车辆后表5CHIO种群进化（Al-Betar等人， 2020年）。感染函数Initial casec条件r1×BRr<新病例类型感染病例功能cit1cit方程Ccitcitr×cit-ck敏感函数Initial casec条件r2×BRr<...新病例类型3易感病例循环移位= [6，1，2，.. . ，5]）。客户交换是另一个步骤，仅当超载车辆的num cust等于1时才执行。交换过程是添加到客户移除步骤的辅助步骤，其中剩余客户和以前一样被移到下一辆车上。然而，在实施这一移除之前，下 一辆 车 的 最后一 位 客户将被转移到超载的车辆，然后将进行removec这将确保所有车辆至少为一名客户提供将从下一车辆转移到超载车辆的客户被存储到removec2变量。 修复过程是伪编码的，算法1.算法1. 维修程序1：{-第一步：计算车内客户数-}2：num_cust = numel（v（i）.vr）3：{-第二步：检查试验编号-}函数cit1Ncit方程Ncitcitr×cit-cm免疫函数Initial casec条件rBRr<新病例类型函数cit1Rcit方程RCitcitr×cit-cv未应用Initial casec条件rPBRr新案例类型功能方程式Rc分别为0和0。如果构造的解决方案的可行性被破坏，则调用前面讨论的修复过程。4：if（（num_cust6 try_num）OR num_cust== 1）5：v（i）.try_num = 06：如果7：{-Step 3：Remove customer-} 8：remove_c = v（i）.vr（end-（try_num））9：v（i）.vr（end-（try_num））=● 受感染病例：如果r<3×BRr，则cjtth被感染，并且受感染的函数将用于生成cit1（使用k t）这是任何状态为1/4的感染病例。● 易感情况：如果r<3×BRr，则使用易感函数Ncit1生成cit1，其中mt1是任何易感的10：next_vehicle=Vehicle1/2（]1）11：{-第四步：客户交换-}12：如果num_cust == 113：remove_c2 = v（next_vehicle）.vr（end）14：v（i）.vr（1）=remove_c215：v（next_vehicle）.vr（end）=16：如果17：{-第五步：将客户移到下一辆车的尾部-}18：v（next_vehicle）.vr（end）=remove_c19：{---第六步：将右循环移位应用于车辆阵列---}20：Vehicle = circshift（Vehicle，1）3.1.3. 步骤3：人口演变在此步骤中使用CHIO演进功能来增强初始种群达到最优解。在下面的讨论中，将表5作为参考。根据CHIO的原始论文（Al-Betar等人，2020），表5是CHIO进化步骤的总结。请注意，cit表示客户j在当前t次迭代的路线i中的当前位置，而JJ J状态为0的情况● 免疫的情况：如果r