遗传算法求解动态车辆调度外文翻译资料

英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料

遗传算法求解动态车辆调度

Franklin T. Hanshar·Beatrice M. Ombuki-Berman

摘要 很多复杂的组合优化问题都以静态问题为模型，然而在实际中，许多问题都是动态变化的，在所有设计数据出现之前必须做出一些决定。例如在动态车辆路径问题（DVRP）中，随着时间的推移会出现新的客户订单，我们必须在执行当前方案时重新配置新路线。 Montemanni等人[1]认为DVRP是标准车辆路径问题（VRP）的一个拓展，它可以分解为一系列静态VRP，然后用蚁群算法（ACS）解决。

本文所提的遗传算法（GA）为[1]中DVRP模型提供解决方案，通过文献中基准来评估GA的有效性。与这里实现的禁忌搜索和上述的ACS比较，拟议的GA在最低运输成本方面表现更好。

关键词 动态车辆路径 遗传算法 禁忌算法

1介绍

众所周知车辆路径问题（VRP）是经常在配送物流和运输系统中出现的NP难题——在物流分配运输中系统中。大多数VRP规划都假设所有与客户需求，运输成本等相关的数据在设计数据时已知。然而在大多数实际情况中，VRP是动态的，是随着时间变化的。最近几年，动态VRP中利息增长有两个主要诱因，。近年来，效益增长不断集中于动态或随机的VRP版本。对此有两个主要刺激因素。首先，更复杂的信息科技的进步和通信系统允许一同实时处理对车队的控制和客户订单的管理。这种进步有利于对运输系统规划的迅速更新，即使在车辆部署完毕之后。甚至可以在车辆之后。其次，顾客在电子商务中对于满足他们运输要求的期望变得更加快速和灵活（Fleischmann[2]，比安奇[3]等）。

因为DVRP是个在实际生活中广泛应用的NP难题并且，所以优化方法是否可以在有限时间内得出高质量解决方案的能力，即启发式算法是尤为重要的。许多文章所提及到的DVRP在实际中的应用像dial-a-ride服务包括小范围的门对门服务。包括对有打包配送需求的老年人和残疾人，还有大量未知客户订单的出租车服务。第二个应用是repair and courier服务，包括有时间约束的单一路径插入。第三个应用是邮件传送，包含一天当中在不同地区的物品打包配送（如UPS，联邦快递）。

在DVRP中，虽然客户需求或者订单可能在设计方案之前就已知晓，但随着时间的推移其中一些会逐渐增加。通常，对已知数据执行优化，直到诸如新客户之类的事件为止

请求，发生[6]。然后将路线规划重新配置，尽可能的满足新客户的需求。本文默认在设计方案时一些客户已知，而随时间推移会不断出现新客户。我们所研究的具体DVRP模型由Kilby[7]等人首次提出，并由Montemanni[1]等人进一步凝练。在[1]中作者介绍了DVRP的一些实例基准并发表了关于动态幅度如何影响最终运输成本的研究。Montemanni等人通过把DVRP分解为一系列静态VRP ，认为其可以是标准VRP的延伸拓展，并且可以用蚁群算法（ACS）解决。[1] 通过进一步定义[7]所给出的基准问题扩展了[7]的工作。我们在本文中讨论的DVRP模型类似于Montemanni [1]等人所研究的并使用相同的基准。据我们所知，除[1，7]外，仅Gendreau[8]等人和Ichoua[9]等人对类似问题进行了研究。然而 Gendreau [8]等人使用禁忌搜索研究类似的DVRP，他们不考虑载重量和[1]中所述的时隙的概念。Ichoua [9]等人将车辆改道机制融入Gendreau[8]等人的算法中。

文献中存在各种其他关于DVRP的研究。Bent 等人[6]提出了一个考虑多场景下的大邻域搜索策略，它产生大量与过去决策相一致的方案。Ichoua等人[10]研究了类似[6]中的问题，并通过对关于未来事件信息的发掘来提高决策水平。Zhu等人[11]将开放约束规划应用于实时DVRP，把客户和动态车辆调度的动态运输时间相融合。Coslovich等人[12]针对问题提出了一种两阶段嵌入算法。 Gendreau等人[5]也针对拨号问题提出了一些邻里搜索的启发式方法。

Caramia等人[13]探索了一个大都市多重运输系统并提出了一种基于启发式方法的动态编程。Krumke等人[14]研究了汽车服务单位的实时调度并提供了基于列生成和集合划分的解决方案，Salvelbergh和Sol[15]为运输公司提供计划组件。Larsen[16]针对带时间窗的TSP问题开发了实时解决方案。Guntsch和Middendorf [17]为TSP设计了一种蚁群启发式算法。对不同类型DVRP所获得的结果的调研同样可以在Psaraftis [18，19]，Gendreau和Potvin[4]，以及Bianchi [3]中找到。

本文的主要贡献在于展示通过有效设计遗传算法来为DVRP生成良好解决方案。我们提出了一个新的有效的染色体表示方案，并提供有效的DVRP交叉机制。 据我们所知，这是这种特定DVRP研究方向的第一个GA实现。通过使用[1]和[7]中所介绍的数据集进行测试，并与其他知名启发式算法相比较。GA的表现在DVRP的求解质量上要优于Montemanni等[1]的ACS。此文还展示了应用其他普及的，像简单高效的禁忌搜索等DVRP启发式算法的潜在可能。

本文的其余部分安排如下。在第二部分，我们定义了在此处理的DVRP模型。在第三部分，我们探讨了自己的实验方法，然后在第4部分中提供了实验结果。又在第5部分通过讨论结果的含义得出结论并且提供了对未来工作的建议。

2问题定义

DVRP通常可以通过多种方式制定这取决于现实生活中的潜在问题。这项研究采用了Montemanni等人[1]提出的DVRP模型。我们的DVRP模型由经典VRP [20，21]的常规描述来引出，在静态VRP中优化开始之前就已知所有的线路信息，因此，在优化期间不会有新的相关路线信息。另一方面，在动态VRP中，优化开始之前设计者已知晓一些信息，但通常来说，在优化期间信息也是可以更改或添加的。

2.1 静态车辆调度问题

一般的VRP可以如下定义：设计从配送中心到一系列分布点（顾客、商店、学校、城市、仓库等）的车辆最低成本线路，同时满足各种需求。每一个服务对象一次只能使用一辆容量固定的车。服务时间指的是每一位客户所要求服务他的时间。

VRP可以用一个无向图G=(V，E)数学建模，顶点集V={，，hellip;}，边集E={()|，isin;V，ilt;j}，集合m代表从同一车场出发载重量为Q的同类型车辆，并且必须服务所有客户{，...，}。对于E，我们在客户到之间定义一个成本或距离矩阵C=（），每个客户都有需要被唯一车辆服务的非负需求。设，...，为覆盖所有客户V的路线m的分区，行驶给定路线= {，，...，}的成本或距离，其中isin;V，供应中心 = 由下式给出：

， （1）

对所有路线求和，形成解S的累积成本：

（S）= （2）

因此，静态VRP包括遵循以下约束的车辆m的（S）最小化：（i）每一条从配送中心开始和结束的路线；（ii）每个客户只被访问一次；（iii）所有路线总需求量不超过Q。

2.2动态车辆路径问题

我们研究了由Montemanni等人[1]提出的DVRP模型，它被认为是标准VRP的扩展，通过将DVRP分解为一系列静态VRP，然后用蚁群算法解决它们。在大量车辆被委派后新订单还会随时间推移不断增加。这些新订单需要纳入现有的车辆行驶路线或为它们新创路线。因此在任何时刻，，可能存在已经接受服务的客户和需要服务的新客户。如果一个工作日被细分为多个离散时间段，那么DVRP可以被表示为一系列含静态VRP（如第2.1节所述）的有向图。这意味着DVRP也是NP难题[22]，因为每个离散时间段都须解决一个静态VRP。图1给出了一个DVRP的场景示例。如图所示，一些客户订单是事先已知的，并且为了服务这些客户产生了初始路径。随着时间的推移新的客户订单到达，并且这些新增订单需要重新安排一个或多个路线。

3.基于遗传算法的DVRP

自从由Holland提出，遗传算法在组合优化问题中。如果希望在特定问题中应用遗传算法，必须将问题转化为通过遗传算子修改的基因组或染色体，（交叉或变异），遗传算法中，染色体用来定义候选解决方法，为了模拟自然选择，候选群数量（染色体）在交配池中相互竞争，交配池是产生后代的解集，。每一个染色体都有明确的适应度，适应度是衡量提供优良解决方案能力的。DVRP遗传算法的详细说明。DVRPGA主要有两部分组成：事件调度器和遗传优化算法，如图二所示。

事件调度器负责解决委托阶段，分配新车辆部署或发信号让他们返回。一旦顾客路线确定将不能更改。事件调度器还负责接收新订单和构造类似静态VRP实体

遗传优化阶段用遗传算法求静态VRP实体。必须通过事件调度器并且在有效时间内运行。换言之，优化阶段在计划表的离散的时间片段上反复运行。

如果我们将一个工作日分成个时间切片，每段时间等长为，T为工作日时长，并且我们假设新订单在时间切片最后到达，我们可以在离散时间段上行之有效地优化新到来的订单，此方法由Kilby第一个提出，并且适用于Mentemanni的蚁群算法。每一个时间切片代表一部分静态VRP，车辆必须服务于所有已知顾客，不用返回中心。离散时间切片的概念使静态问题，因此可以提供更有序的服务新客户的方式。时间截点，也被认为由Montemanni提出，指用户将晚到订单延迟到下一个工作日，也就是说订单接收到允许的特定时间，然后这之后的所有订单被推迟。提前承诺时间，允许司机在处理订单本身之前对新订单做出反应。

3.1 事件调度器

事件调度器处理顾客订单，创建静态问题，然后把订单交给特定车辆，它充当一个在新订单到达和程序优化之间的接口，为第一个时间段建立的第一个静态问题包含之前工作日所遗留的所有订单，参数控制新订单可能到达的时间所以因此可能会存在未被涉及的客户，这些客户被转入到下一个工作日。在被翻译成之前没有被服务到的客户之后所有订单接收，也就是说优化从昨日可能因为时间截点而错过服务的客户开始。

下一个静态问题由之前时间段接收到的订单组成，在这些问题中，车辆在合适的运输时间从任何访问过的委托客户开始，并配以适合的载重量变化。在每一个时间段后选择最好的解决方法然后在下一个 处理时间开始之前，把订单委派给他们所重视的车辆。当任何一辆车充分利用自身的载重，再送回至配送中心。

3.2 遗传优化

遗传算法是为每一个以上所提及的静态VRP所执行的，在基因库里每一个染色体代表了一个静态VRP的可行解。然后每一个染色经历迭代进化直到符合最终条件。进化部分在 普通的遗传算法进行染色体的选择交叉和变异时执行。

3.2.1 染色体的表示以及初始种群的设定

染色体表示方法的选择是给定GA实现是否成功的关键因素之一。 在我们的方法中，我们使用长度可变的染色体来表示包括一些之前访问过的客户的信息。 因为任何给定染色体可以在任何时间步长代表大量的局部路线，所以存在在当天计划中新增但没被委派给任何车辆的待定客户，但此时委托客户已经由指定车辆访问。

因此，我们的染色体表示由两种节点类型组成：代表单一客户（目前未指派配送车辆）的节点（用正整数表示）和代表客户群体（已经决定好配送车辆）的节点（用负整数表示）。因此，染色体由整数组成，新客户直接用与正指数相匹配的染色体来代表并且每个委托的客户都间接通过一个由给定部署车辆表示的群组（由负整数表示）代表。当染色体被解码时，那些预先存在的车辆（组）如果仍然有能力容纳新的客户订单，那么它可以添加新的客户。图3显示了从第二个时间段开始的染色体。在第一个时间段，还没有委派车辆，因此它相当于通过有效客户订单（如果有）解决静态VRP。下面给出染色体解码和路线选择。

初代DVRP染色体种群通过产生随机排列的每一个大小为n的染色体来获得，n表示参数T定义的之前工作日剩余的客户数量。

3.2.2解决方案构建和路径

染色体编码给出了客户将被访问的顺序。但是，它没有明确地揭示出在不使用分隔符表示路径结束时如何划分客户他们各自的m路径或车辆。路线方案需要映射基因型信息（染色体）到显性适应度或表现型，在这种情况下是一组路线，就像如上所述的DVRP染色体编码代表现有路线和新的客户要求。

委托客户在之前时间步长已构建的现存路线中被分组放置，并且每个组都指定一个负数补位。当路径算法遇到负整数时，它在被指派车辆的名单中查找此整数，将负整数映射到委派车辆。

以在表3中我们使用的染色体为例，这个染色体有由正整数表示的9个新订单和3个已经访问过多个以负整数表示客户的车辆。因为染色体的第一个元素是正整数，所以解码从创建新车辆，因此创建了代表的新车辆。假设订单要求没有违反车辆载重量限制，该车辆将5号订单和6号订单添加到其计划表中，之后我们遇到一个负整数，这意味着我们不能再继续添加，并且如果可能的话，由负整数表示的将添加订单到计划表中。假设图3中由-1表示的具有足够的载重量，则将4号和2号订单添加到其计划中，但是9号订单因为违反了的载重量限制不能添加。之后我们创建一个新的车辆，并把9号订单作为其唯一订单，当遇到另一个负整数-2，将其设为并假设具有足够的载重量以允许添加3号、1号、8号和7号订单 。最后当遇到负整数-3，对应地将第五个即最后的车辆标记为，没有新订单。

随着优化过程的进行和新的静态VRP被解决，染色体大小也随之改变。它的大小随新增客户的增加而增长，随委托客户被指派到各自分组而减小。

3.2.3 适应性评估

在将每条染色体直接

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[20946]，资料为PDF文档或Word文档，PDF文档可免费转换为Word