修改后的和声搜索算法求解动态时间窗车辆路径问题

文摘

车辆路径问题(VRP)是一个经典的组合优化问题。它通常是静态的方式模仿;然而,在实践中,新客户请求到达后最初的工作日计划正在进行中。在这种情况下,线路必须动态地重新计划。探讨动态时间窗车辆路径问题(DVRPTW),客户的请求可以在工作日的开始或随着时间的推移发生动态。我们提出一个混合启发式算法相结合的和谐的搜索算法(HS)和变量附近下降(盾)算法。它使用HS提供全球探索能力和使用盾的局部搜索能力。为了防止过早收敛的解决方案,我们评估人口多样性利用熵。Lackner基准问题的计算结果表明,该算法具有竞争力从文学与现有最好的算法。

1。介绍

车辆路径问题(VRP)在1959年首次引入[1]。自那时以来,它已成为一个中心研究问题领域的行动研究,也是一个重要的应用领域的运输、分销和物流。问题涉及到一个仓库,一些客户,一些货物。货物必须从中央仓库交付客户使用一些车辆在不同的位置。这是一个组合优化问题的目标是找到最优的解决方案,满足服务需求,路由限制和车辆约束。

DVRPs已经持续3年的重要研究领域。由于最近的信息和通信技术的进步,汽车舰队现在可以实时管理。在这种背景下,动态车辆路径问题(DVRPs)正变得越来越重要2- - - - - -4]。各种各样的方面是通过许多方法来解决。早期的研究可以找到DVRP Psaraftis的工作(5]。他们提出了一个动态规划的方法。Bertsimas和Van Ryzin [6)视为DVRP模型与一个单一的汽车和没有容量限制,请求随机出现。他们描述这个问题通过一个通用的数学模型,认为等待时间为目标函数。关于DVRPTW,陈和徐7)提出了一个动态列生成算法根据DVRPTWs决定时代的概念规划周期,标明在一天的最好的时间来执行以过程。de Oliveira et al。8)解决出现的问题与客户的需求发生在实时DVRPTW和生产的舰队。他们的解决方案是通过metaheuristic方法使用一个蚁群系统。香港(9还考虑时间窗口和一些请求可能会迫切的事实。这项工作采用连续以方法和使用一个大型社区搜索算法。当一个新的请求到来时,它立即被认为是包含在当前的解决方案;因此,它运行的大型社区搜索再次获得一个新的解决方案。阿马斯和Melian-Batista10)解决DVRPTW与几个现实的约束。类似于香港的工作,他们也采取了连续以方法,但计算解决方案使用一个变量社区搜索算法。在一些最近的调查,Pillac et al。11)分类路由问题从信息质量和演化的角度。他们介绍的活力程度的概念和目前的应用程序和解决方案的综合评估方法对动态车辆路径问题。Bekta et al。12)提供另一项调查在这个领域;他们提供了一个更深入、更详细的分析。最后但并非最不重要,Psaraftis et al。13)将进一步揭示在这个领域工作超过3年发展DVRP论文根据11的分类标准。

正如我们所知,对于大型DVRPTW,很难开发精确的方法来解决这种类型的问题。大多数现有的研究处理metaheuristics和智能优化算法。和谐的搜索算法(HS)是一个metaheuristic算法,开发的(14]。该算法模仿音乐即兴创作的行为过程。音乐家调整合成音调与其他乐队,依靠自己的音乐创作中的内存,最后音调达到一个美好的和谐状态。同样,它已经成功地采用许多研究者解决各种复杂的问题,如大学课程安排(15,16),护士名单(17)、水网络设计(18),数独谜题(19]。由于其优化能力,HS算法也被用作解决蚁群搜索框架。解决绿色VRP(经典VRP的扩展),Kawtummachai和Shohdohji20.)提出了一个基于HS算法的混合算法中HS是由当地的杂化改进过程。他们测试了该算法与零售公司的实际情况,和结果表明,该方法可以有效地应用于案例研究。此外,Pichpibul和Kawtummachai [21)提出了一个修正HS算法生产配送VRP和概率Clarke-Wright储蓄算法结合到和谐记忆机制来实现更好的初步解决方案。然后,采用轮盘赌选择过程与和谐即兴创作机制来改善其选择策略。结果表明,修正HS算法与现有最好的算法具有竞争力。最近,亚森et al。22)提出了一个meta-HS算法(meta-HAS)解决VRPTW。比较的结果证实,meta-HS产生竞争与其他方法的结果。

如上所述,HS算法已经成功地应用于解决标准vrp但尚未应用于解决动态蚁群。解决动态蚁群通常是更复杂的比解决相应的标准蚁群,我们应该解决多个VRP当我们处理动态请求。众所周知,减少旅行的距离标准vrp是np难在一般情况下,所以解决动态蚁群具有相同目标函数也是一个艰难的计算任务。在本文中,我们提出一个修改的和谐解决DVRPTW搜索(肉类)算法。静态VRPTW有关,因为它可以被描述为一个路由的问题,信息的问题可以改变在工作日。它是一个离散时间动态问题,可以看作是一系列的静态VRPTW问题。因此,肉类我们提出算法包括两个部分:一个是静态优化问题;我们把基本HS算法与变量附近下降(盾)算法,目标是实现这两种方法来提高搜索的好处。结合HSVND算法区分本身在三个方面:首先,和谐记忆的编码的特点改进了基于蚁群路由。第二,这个增广盾HS杂化了一个增强的方法来协调搜索多样化和有效地强化。 In this scheme, four neighbourhood structures were proposed. Third, in order to prevent premature convergence of the solution, we evaluate the population diversity by using entropy. The other is the dynamic customer check and insertion. Four rules were employed within the DVRPTW that address the insertion of dynamic requests into the DVRPTW. Furthermore, the MHS is verified for practical implementation by using a comparison study with other recently proposed approaches. The results show that our algorithm performs better than the compared algorithms; its average refusal rate was smallest among the three compared algorithms. Moreover, travel distances computed by our algorithm were also best in 29 out of 30 instances.

本文的其余部分的结构如下。下一节提供了一个正式的DVRP的数学模型。简要的概述了符号部分2。部分3描述了主要框架和细节HSVND DVRP算法的发展。中给出的实验设置和结果部分4。最后,部分5总结了本文的主要结论和建议一些可能为未来的研究方向。

2。问题定义

DVRPTW可以由一个无向图数学模型 ,在那里 是顶点的集合包括仓库()和客户 ,也称为请求、命令或要求 是每一对顶点之间的边的集合。每个顶点有几个与之关联的非负权重,即一个请求的时间吗 ,一个位置坐标 ,需求 ,服务时间 ,和一个最早的和最新 ,可能的开始时间为服务,定义一个时间窗口 ,而 是服务时间范围。同时,每条边 有关旅游的时间吗和旅行的距离 。

一个总数客户是固定大小的舰队相同的汽车,每辆车与非负相关能力吗 。每个客户都有到达时间并开始服务时间 。特别是车辆只允许启动该服务不早于最早的服务时间 , 。换句话说,如果车辆提前到达 ,它必须等到 。客户可以分为两类,静态客户()和动态客户(),根据客户的时间要求。客户在的位置和要求在规划周期的开始(即。,time 0), are also called priority customers because they must be serviced within the current day. The locations and demands of customers who belong to set将已知的只有当时的订单请求。随着时间的推移这些客户在要求现场服务。

目标是接受尽可能多的请求,而找到一个可行的路线总旅行距离最小。目标我们认为这是一个分层的方法,这是类似于[定义的目标10]。目标函数是在词典顺序如下。(我)拒绝客户的数量。(2)总行驶距离。(3)总数的路线。

请注意,(10]包括7目标函数:总不可能实行(客户的时间之和超过时间窗)、延期服务,额外的小时数(小时和车辆的工作变化超过),额外的小时数(小时之和,车辆的工作转变是超过),总旅行距离,路线,总数和时间平衡(最长的和最短路线时间由一个汽车关于时间)。他们认为与软时间窗约束;因此,他们需要考虑这些额外的目标函数。相比之下,因为我们认为时间窗口是硬约束,时间窗口相关的目标函数可以被删除。

可以模仿DVRPTW以下公式。首先,我们介绍三个二元决策变量 , ,和 ,定义如下: = 1如果边缘 是乘坐交通工具和0。 = 1,如果车辆使用和0。 如果动态客户= 1被接受。

的主要目标可以被描述为下面的公式: 在哪里客户的车辆到达时间吗和的实际开始时间吗 ,所以 (9)表示。此外,对于每一个客户 ,让表示相反的到达时间,定义为(10)。

目标函数(1拒绝客户的数量降至最低,2)旨在减少旅行的距离,(3)最小化的总数路线。情商。4)是一个流守恒约束:每个客户必须有它的入度等于出度,这是最多的一个。情商。5确保每个客户 必须由一个访问。情商。6)确保每条线路开始和结束中央仓库。情商。7)指定每辆车的能力。情商。8)- (11)定义的时间窗口。最后,(12)强加限制决策变量。

问题的程度的活力(国防部)[23)定义代表多少动态请求发生在一个问题。让和分别是静态和动态请求的数量。然后,国防部描述如下: 国防部在0和1之间变化。当国防部= 0,所有的请求都是提前知道(静态问题),而当它等于1时,所有的请求是动态的。

3所示。解决方案方法

在本节中,我们提出一个解决DVRPTW metaheuristic算法。首先,我们引入了启发式算法的框架来展示如何解决DVRPTWs交互。然后,我们讨论的细节提出了和声搜索算法,包括它的初始化,它临时凑成新的解决方案,其VND-based本地搜索方法。最后,我们提出一些策略用于适应动态请求。

3.1。框架的一般算法

一般的算法来解决DVRPTW交互式地总结了算法1。首先,路线和交付HSVND静态客户解决,这是我们建议的和声搜索算法中描述的部分3.2。HSVND将返回找到最好的解决方案,所有的静态客户已经插入了路线。因此,舰队可以开始发货的客户根据路线发现在这个解决方案中。然后,动态客户提交请求。当一个新的动态客户请求发生时,该算法将立即检查维修请求算法的可行性3(讨论部分3.3)。如果请求被接受,然后再次调用HSVND重新排列所有已知的客户请求,到目前为止尚未提供服务。否则,请求将被拒绝。这个动态过程重复进行,直到没有新的请求。然后,整个解决方案,包括为所有静态和动态服务客户的请求将返回的通用算法。

下面的内容将讨论HSVND算法和方法插入动态详细客户请求。

3.2。HSVND框架

在本节中,我们描述的核心肉类包含两个方法:和谐的搜索算法(HS)和变量附近血统(盾)算法。该混合算法,称为HSVND,得益于HS和盾的优势;越南盾商品具有较高的全局搜索能力,而擅长本地搜索。

HS算法由Geem et al。14)基于音乐家即兴创作新和声在内存中。海关是一个基于进化算法的解决方案所代表的和声和所代表的人口和谐的记忆。HS是一个迭代的过程,始于一组初始存储在内存(HM)和谐的解决方案。每个迭代生成一个新的解决方案,然后目标函数是用来评估新的解决方案的质量。HS方法将取代最糟糕的解决方案与新解决方案如果新的解决方案是更好的质量比HM最糟糕的解决方案。重复这个过程,直到满足预定的终止准则。HSVND给出算法的伪代码2。

HSVND算法由以下六个步骤:初始化、评价、即兴创作一个新的解决方案的嗯,本地搜索盾,更新HM,终止和检查标准。初始化后,混合算法迭代直到满足终止准则改进解决方案。下列部分详细解释HSVND算法的每一步。

3.2.1之上。初始化

在初始化过程中,商品的参数初始化。这些参数是(我)和谐内存大小(HMS),这决定了HM的许多初步的解决方案;(2)和谐记忆考虑率(HMCR),这决定了HM的速率值选择的解决方案;(3)音高调整率(PAR),这决定了当地的改善;及(iv)即兴的数量(倪),对应的最大迭代数允许改善解决方案。接下来,初始解人口将随机生成并存储在英国。这些解决方案是按升序排序对他们的目标函数值。

人口也是初始化。嗯是三维空间的表示为一个矩阵。行包含一组解决方案,和列包含车辆(路线)为每个解决方案 。每辆车的路线可以被认为是一个序列的客户 ,在哪里和代表了仓库。在经典商品,每个和谐HM的尺寸必须相同(14]。在我们的研究中,一个和谐代表一组包含车辆(路线)。因此,每个和谐HM的维度可以是不同的,所示 在哪里在溶液中车辆的总数吗 。

DVRP,决定等待或移动车辆时应完成服务客户。在本文中,我们引入一个预期等策略。假设实际的时间 。车辆完成服务客户并准备下一个客户服务 。我们允许的车辆等位置,直到 。因此,车辆将在当前位置,等待时间

解决方案的人口是由迭代生成车辆路线。算法按顺序打开路线,让他们与客户,直到没有更多的顾客可以插入,同时仍然保持路线可行。更准确地说,这个过程选择一个unrouted客户,并试图将其插入到当前路线生成可行的路线,包括客户。这一步会重复,只要客户可以插入到路线在不违反任何约束。当这不再是可能的,路线是封闭和添加到解决方案继续下一个车辆路线和过程,直到所有的客户都插入到解决方案。

3.2.2。评估种群熵

和谐的多样性将根据种群熵,定义如下: HMS和谐内存大小,的目标函数值吗th和谐,熵是规范化的人口。在每一代,嗯更新之后,人口熵计算。如果人口熵增加或者保持不变,它肯定发生了过早收敛。然后,将保留最好的和谐。对其他人来说,它在HM计数频率,消除了和声的最高频率,然后生成新的和声。

3.2.3。即兴创作一个新的解决方案

一个新的解决方案 即兴创作是基于三个规则:(i)随机选择,(ii)内存的考虑,和(3)调整音高。随机选择规则允许车辆选择一个随机路线从整个搜索范围。除了随机选择,车辆可以从以前的路线为同一车辆存储在HM这样吗 。后一个新的球场(路线)是来自记忆,它进一步认为确定一个音高调整是必需的。具体来说,生成新的解决方案如下:首先,创建一个空的解决方案 ;接下来,生成一个随机数范围内 。如果小于HMCR,选择一条路线从HM并将它添加到吗 。否则,生成随机并将它附加到的新路线 。具体来说,新球(路线)生成如下。

选择当一个新的路线的嗯,它调整的概率由本地搜索,在哪里 。我们产生一个随机数在0和1之间。如果小于票面价值,那么当前的路线将通过一个随机选择的邻国修改策略。即兴创作过程结束时,汽车的数量在新的解决方案存储在HM等于最小的一个。DVRP,不同的社区结构被用于改善当地的路线。因此,我们使用三个小区搜索方法如下。

转变。这个操作随机选择一个用户,并将其从当前位置移动到一个新的随机位置在同一路线。例如,在图1 (b)后,客户选择2和6日客户。

交换。这个操作随机选择两个客户和交流他们的位置在同一路线。在图1 (c),客户2和6的位置也被替换。

反。这个操作随机选择两个客户并颠倒子序列之间相同的路线。在图1 (d)边(1、2)和(6、7)被删除和边(1,6)和(7)是相互联系的;因此,子序列从2到6是反向的。

请注意任何局部变化导致不可行路线将被丢弃;只接受可行的路线。每个社区结构是由一个特定的控制标准范围如下:

如图1所示,新的解决方案可能是不可行的,因为有些客户可能错过或重复。因此,在即兴创作过程中产生新的解决方案后,我们必须检查它的可行性。修复技术是利用变换一个不可行解到一个可行的解决方案使用以下两个步骤:首先,我们确定客户既没有计划,也没有复制在新的解决方案。然后,我们删除任何重复客户从旧路线,最后,要么错过的客户分配给任何可以接受他们的路线或生成一个新的路线。

3.2.4。盾的方法

即兴创作一个新的解决方案后,我们使用盾方法进一步优化解决方案。让越南盾DVRPTW方法可用,有必要为DVRPTW定义适当的社区结构的解决方案。我们提出如下四个不同的社区结构。

交换。选择一个客户从路线和另一个客户从另一条路,然后交换(见图2(一个))。

2-Opt 。选择两个路由和交换的最后部分选择路线后选择两个点,分别来自路线(见图2 (b))。

String-Exchange。选择一个客户从一个路线,另一个子序列的子序列的客户交易两个子序列(从另一个途径代表子序列的最大长度(见图)2 (c))。

搬迁。删除一个客户从一个路线,将它插入另一个路线(见图2 (d))。

越南盾提出方法算法所示3,从第一个结构 。在每个迭代中,该算法找到一个解决方案在当前的社区结构的最小目标函数值(线)。在评价步骤,如果 ,那么解决方案成为下一个现任的解决方案(线继续使用)和算法(行);否则,它探讨了未来社区结构(线)。当最后的结构, ,已经应用和进一步的改进是可行的,越南盾的方法终止并返回最后一个局部最优解。

3.2.5。更新嗯

新的解决方案是替换和添加到嗯如果它比英国最严重的和谐解决方案的目标函数值。否则,新创建的解决方案被拒绝。然后,HM再次排序的目标函数值。

3.2.6。检查终止条件

海关的程序继续,直到满足终止条件。我们使用三个终止条件:达到最大数量的临时措施(倪),没有改进后发生一定数量的临时措施(立方寸)最好的解决方案在HM达到一定值(CBS)。它会停止是否满足终止条件之一。

3.3。插入动态请求

需要动态请求如客户位置信息和时间窗口获得当请求到来。此外,在给定的时间点,车辆可能是服务客户,等待客户,或走向下一个客户。我们DVRPTW算法应该首先确定请求到达这个时间点是否可以接受,如果是这样,哪个车,哪个时间点能服务。的算法应该拒绝请求没有车辆可以将服务他们。决定接受或拒绝一个请求,我们将讨论一些插入规则。

规则1(时间窗约束)。假设客户请求服务时间 ,和车辆来访的客户还是去拜访,客户根据计划路线r。为新请求插入解决方案,它必须至少满足一个车或者安排一个新的车辆可以到达在年底前客户的时间窗口。表达的规则如下: 或

规则2(容量约束)。一个客户可以插入路线(假定它是由车辆如果它不违反车辆)约束的能力。规则检查这种情况表示如下:

规则3(直接插入)。一个新客户客户之间可以插入吗和在路线如果允许车辆到达结束前的时间窗口和服务开始后的时间窗口。表达的规则如下:

规则4(插入)。这条规则管理客户时的条件不能插入到任何位置的路线 ;然而,如果路线分为两种途径(和)和客户可以插入的这两个新航线(使用规则吗3和4),然后客户可以接受。一个路由 可以分为 和 如果

算法4描述了动态请求可以插入一个路线。

4所示。实验结果

本节显示了密集的计算结果使用提出HSVND实验。我们实现了HSVND使用c#编程语言编译的。净框架4.5和执行所有的实验与Intel®Pentium®CPU电脑G645处理器时钟在2.90 GHz处理器、2 GB内存运行Windows 7操作系统。

Lackner基准上的实验研究,起源于所罗门标准的基准。100年这个基准测试,客户分布在欧氏平面上超过100×100平方的地区,在那里顾客之间的旅行时间等于相应的距离。基准分为六组,名为R1, R2, C1, C2, RC1,分别和RC2。每组包含8到12实例,因此总共有56个实例。为了适应测试的动态部分,每个实例相关联的五种不同程度的活力,10%,30%,50%,70%,和90%,分别。在接下来的实验中,我们使用符号标签每个实例“Group-Index-Dod。”在哪里集团是实例所属的组名,指数是群体中其索引(使用两个阿拉伯数字),然后呢国防部是它的动态程度值。例如,标签“R1 - 05 - 70”表示在R1组第五实例,实例包含70客户动态。

4.1。参数设置

本节探讨HSVND参数HMS HMCR,和标准,以及收敛速度。我们随机抽取15这些实验的实例。他们是“C1-01-50”、“c1 - 05 - 90”,“C2-01-30”,“C2-07-10”,“R1-03-30”,“r1 - 09 - 70”“R1-03-10”,“R2-03-50”,“R2-06-10”,“r2 - 09 - 70”“RC1-04-50”,“rc1 - 06 - 90”,“rc2 - 02 - 70,”“rc2 - 03 - 90”和“RC2-08-30。“为每个实例,10独立运行。因为我们把DVRP分割成一系列的静态vrp在解决过程中,我们只有用户静态客户规划周期的开始( )在所有的实验中,我们将算法的终止条件设置为只考虑临时措施(NI = 1000)的最大数量。表1- - - - - -3显示的结果的优化目标函数对HMS使用不同的设置,HMCR,不相上下。

结果在表1证明HSVND的性能取决于HM的大小:HMS越大,意味着结果越好。因此,使用HMS的较大值可以达到更好的目标函数值较低的解决方案。这可能发生,因为在HM更多的解决方案提供了更好的转变模式,更有可能结合成良好的新的解决方案。因此,HMS = 30所有基准选择实例。

列在表2时,该算法的性能会降低增加随机选择的数量当HMCR值都在0.8以下。然而,扰动有必要给英国带来多样性,避免局部最小值。因此,我们建议值为0.8的HMCR基于实验结果。

表3表明小PAR值减少HSVND的收敛速度。根据实验结果,我们建议使用PAR值大于0.6。

我们也评估HSVND的收敛速度。在这个实验中,我们设置HMS = 30, HMCR = 0.8, = 0.6如上所述不相上下。以同样的方式与前面的实验中,我们为每个实例运行HSVND 10倍和终止后最多倪= 1000次迭代。连续未被利用的迭代的最大和平均数量(立方寸)和计数的最佳解决方案(CBS)报道在表4,立方寸显示所需的迭代次数找到下一个局部最优解从当前局部最优解。在此期间之间当前最佳解决方案,下一个,哥伦比亚广播公司(CBS)被定义为解决方案的数量发现有相同的客观价值作为当前最佳解决方案。

从表4可以看出,平均HSVND至少需要13个迭代找到一个新的局部最优解,同时,最多需要150次迭代。至少在搜索,找到一个解决方案,最多,发现7相同的客观价值的解决方案。因此,我们设置了其他终止条件如下:立方寸= 200和CBS = 10。

4.2。与现有算法的比较

评估HSVND提出算法的性能,我们跑Lackner基准上的算法实例,并与现有的两个方法:ILNS [9]和GVNS [10]。比较了有关这些算法基于拒绝服务的比率,所需的车辆数量,总路程。收集实验数据,10为每个实例并为每个单独的运行进行一定的活力Lackner基准。我们记录的最佳执行10分,计算每组的平均价值。物品在这些表显示粗体文本匹配与当前知名的解决方案。我们设置HS参数如下:HMS = 30, HMCR = 0.8, = 0.6,倪= 1000,立方寸= 200,哥伦比亚广播公司(CBS) = 10。表5列出了比较结果,第一列表示的实例(),第二列显示了程度的活力(),另一个列显示车辆的平均数量,平均总距离、平均插入时间、分别和拒绝比。此表列出的最后两行总体平均结果的不同方法和特点的计算机算法被处决。

如表所示5平均,HSVND优于其他方法。首先,HSVND获得最小的平均拒绝比例,0.46%,而ILNS拒绝0.50%,GVNS拒绝0.61%。HSVND和GVNS能够服务所有请求组R2, C2, RC2;因此,他们获得同样的拒绝比率(即。,0.00%)。HSVND执行比GVNS组R1和RC1拒绝比率而GVNS C1组表现最好。平均而言,GVNS ILNS达到一个更好的拒绝比。算法所需的车辆的平均数量低于GVNS但略大于ILNS。车辆的平均数量是8.58,8.50,和8.88 HSVND, ILNS和GVNS分别。然而,在寻找短距离HSVND显示良好的性能;它的平均距离是1030.28,平均距离ILNS和GVNS是1100.62和1098.40,分别。 Note that HSVND was the best at optimizing travel distances among the three algorithms for all groups. Overall average insertion time also indicates that our proposed algorithm improves on the others; however, note that the computational environments under which the algorithms were executed are different.

类似于评估执行GVNS,我们也计算10处决为每个客户的平均性能与GVNS相比较,如表所示6。HSVND改进GVNS的平均总距离在所有情况下。有7个类型和HSVND优于GVNS完全拒绝比,平均数量的车辆,而平均总距离。拒绝比率保持不变时,有10个类型比GVNS HSVND可以找到一个更好的解决方案。

总的来说,我们的结果表明,商品取得了良好的结果与现有的方法相比,我们的算法有能力之间取得良好的平衡DVRPTWs多样化和强化。

5。结论

在本文中,我们提出一个修改和谐搜索DVRPTW,叫做肉类,它是基于HS算法。首先,和谐记忆的编码改进了基于路由在vrp的特点。其次,为了提供一个有效的平衡全球多样化和当地的强化,增强基本变量附近下降(盾)纳入迭代海关。第三,即兴创作一个新的和谐也得到了改进。在这个过程中,为了防止过早收敛的解决方案中,我们利用熵评价种群多样性。最后,动态请求到达时,五个规则中使用的DVRPTW地址DVRPTW动态请求插入。为了验证我们的方法的有效性,我们进行了一些数值试验用标准的基准。结果分析了集中与最近提议通过比较算法。比较结果表明,该肉类算法比其他现有的算法可以获得更好的解决方案。有几个有趣的研究对象,探索未来。 One of them can be adapting the MHS heuristic for solving other dynamic vehicle problems. Another prospective research may focus on extending the DVRPTW by introducing some realistic aspects and constraints.

的利益冲突

作者宣称没有利益冲突。

确认

这项研究部分由中国国家自然科学基金(没有。61402070,没有。61672122,没有。61602077),中国辽宁省自然科学基金(没有。2015020023),中国辽宁省教育委员会(没有。L2015060),中央大学(没有基础研究基金。3132016348,没有。3132017125)。这种支持。

引用

1. g . b . Dantzig和j . h .公羊”卡车调度问题。”管理科学》第六卷,没有。1,第91 - 80页,1959。视图:出版商的网站|谷歌学术搜索|MathSciNet
2. a·高尔和诉Gruhn“解决动态真实的车辆路径问题,”运筹学学报》运筹学学报》,页367 - 372,施普林格,2006年柏林,海德堡。视图:谷歌学术搜索
3. a . Larsen o·b·马德森,m·m·所罗门“动态车辆路由系统,分类”动态车队管理计算机科学、运筹学/接口系列、pp, 19-40 Springer,波士顿,MA,美国,2007。视图:谷歌学术搜索
4. 诉Pillac、c . Gueret和a . Medaglia动态车辆路径问题:国家的艺术和前景5 - 6,安第斯大学,波哥大,哥伦比亚,2010。
5. h . n . Psaraftis“动态规划解决单一车辆多对多直接请求dial-a-ride问题,“交通科学,14卷,不。2、130 - 154年,1980页。视图:出版商的网站|谷歌学术搜索
6. d . j . Bertsimas和g . Van Ryzin“随机和动态车辆路径问题在欧氏平面上,“运筹学39卷,第615 - 601页,1991年。视图:谷歌学术搜索
7. Z.-L。陈和h .徐“动态列生成动态时间窗车辆路径,”交通科学,40卷,不。1,第88 - 74页,2006。视图:出版商的网站|谷歌学术搜索
8. s . m . de Oliveira s . r . de Souza和m·A·l·席尔瓦”解决方案的动态时间窗车辆路径问题通过蚁群系统metaheuristic,”学报第十届巴西神经网络研讨会上,SBRN 08年2008年10月,页,第21到26巴西,。视图:出版商的网站|谷歌学术搜索
9. l .香港”,一种改进的LNS实时时间窗车辆路径问题的算法,”电脑与行动研究,39卷,不。2、151 - 163年,2012页。视图:出版商的网站|谷歌学术搜索
10. j·阿马斯和b . Melian-Batista变量附近寻找一个动态的富裕时间窗车辆路径问题,“计算机与工业工程卷,85年,第131 - 120页,2015年。视图:出版商的网站|谷歌学术搜索
11. 诉Pillac, m . Gendreau、c . Gueret和A . l . Medaglia“回顾动态车辆路径问题,”欧洲运筹学杂志》上,卷225,不。1、1 - 11,2013页。视图:出版商的网站|谷歌学术搜索|MathSciNet
12. t . Bekta p p . Repoussis和c d . Tarantilis动态车辆路径问题,2014年。
13. h . n . Psaraftis m .温,c . a . Kontovas”动态车辆路径问题:三十年和计算,”网络,卷67,不。1,3-31,2016页。视图:出版商的网站|谷歌学术搜索
14. z . w . Geem、j·h·金和g . v . Loganathan”一种新的启发式优化算法:搜索、和谐”模拟,卷76,不。2,60 - 68、2001页。视图:出版商的网站|谷歌学术搜索
15. m·A . Al-Betar和A . t .埃塞俄比亚“大学课程制定时间表,和声搜索算法”《运筹学卷。194年,3-31,2012页。视图:出版商的网站|谷歌学术搜索|MathSciNet
16. m·a·Al-Betar a t埃塞俄比亚和m·扎曼,“大学课程使用混合和谐搜索metaheuristic算法制定时间表,”IEEE系统,人,控制论,C部分:应用程序和评论,42卷,不。5,664 - 681年,2012页。视图:出版商的网站|谷歌学术搜索
17. m . Hadwan m . Ayob n . r .任妻子和瞿r .,”护士名单的和声搜索算法问题,”信息科学卷,233年,第140 - 126页,2013年。视图:出版商的网站|谷歌学术搜索|MathSciNet
18. z . w . Geem“粒子群和谐寻找水网络设计,”工程优化第41卷。。4、297 - 311年,2009页。视图:出版商的网站|谷歌学术搜索
19. z Geem”和声搜索算法来解决数独”基于知识的智能信息和工程系统b . Apolloni, r . j . Howlett和l . Jain, Eds。,卷。4692,pp. 371–378, Springer, Berlin, Germany, 2007.视图:出版商的网站|谷歌学术搜索
20. r . Kawtummachai和t . Shohdohji混合和声搜索算法(HHS)绿色车辆路径问题(GVRP)”第四届国际会议上工程优化学报》上CRC出版社,页573 - 578年,里斯本,葡萄牙,2000。视图:谷歌学术搜索
21. t . Pichpibul和r . Kawtummachai修改和声搜索算法的生产配送车辆路径问题,”学报的国际MultiConference工程师和计算机科学家,IMECS 13,页1094 - 1099,香港,中国,2013。视图:谷歌学术搜索
22. e·t·亚森m . Ayob m z . a . Nazri和n . r .任“Meta-harmony搜索算法对时间窗的车辆路径问题,“信息科学卷,325年,第158 - 140页,2015年。视图:谷歌学术搜索
23. k·隆德,o·马德森,j . Rygaard”不同程度的动态车辆路径问题,“技术。代表,IMM研究所的数学模型。丹麦技术大学,丹麦,1996年。视图:谷歌学术搜索

版权

版权©2017三陈等。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。