英语原文共 5 页

2019年 2 月 20 日

具有模糊需求的有容量限制的车辆路径问题的混合遗传蚁群优化算法 - 以垃圾收集系统为例

摘要：物流配送问题，通常是表示为有容量约束的车辆路径问题（CVRP），是物流中非常重要的问题。因此，本文考虑具有模糊需求的CVRP（CVRPFD）。作为一个NP难题，CVRP的许多研究都应用了元启发式方法而不是确切的方法。在此次研究中，本文提出了一种混合遗传算法（GA）和蚁群优化（ACO）。它结合了GA，ACO和两种局部搜索方法，即Prim算法和2-opt。为了测试提出的方法的性能，我们在CVRP中的八个基准数据集上进行测试。结果表明所提出的GACO算法与用于解决CVRP的其他现有算法相比是具有竞争力的。而且，本文提出的方法也适用于解决垃圾收集系统（作为CVRPFD问题）。结果也是非常有希望的。

1. 引言

近年来，物流配送已成为物流管理中一个关键工作。高效的分配策略不仅提高了客户服务满意度水平，也降低了运输成本。因此，在该领域有很多研究工作，以找到最佳的物流配送路径规划。有容量限制的车辆路径问题（CVRP）是一种适用于物流配送的模型[1]。在基本问题中，信息，如客户需求和送达时间，都被明确为具体的数值。但是，在很多实际问题中，信息通常存在数据不确定的情况。有两种方法可以适用于不确定的CVRP，即随机CVRP和模糊CVRP。如果问题有不确定的数据可供分析，能用概率假设预测，那么随机CVRP是一种可以使用的方法[2]。相反，如果问题有不确定因素，主观，模棱两可，模糊或不精确，模糊变量方法更适合解决该问题[3]-[6]。最近几年，一些研究应用了不同的模糊方法来处理不确定因素[7]-[9]。

本文研究的是印度尼西亚的垃圾收集系统。该系统旨在最大限度地降低从几个临时转储区中收集垃圾的运输成本。它是清楚地知道垃圾量是不确定和不精确的。因此，我们考虑用具有模糊需求的CVRP（CVRPFD）来表示这个问题。在此，使用郑和刘提出的模糊可信度测量理论来处理不确定的需求。

经典的CVRP明确定义为NP-hard组合问题。由于它的复杂性，很多这方面的研究更偏向于用启发式或元启发式算法而不是精确的方法来解决这个问题，比如遗传算法（GA）。 GA已成功应用于CVRP [10]。模糊CVRP中的GA应用可以在郑和刘 [11]以及Goncalves等人 [9]的文献中找到，这些人应用了遗传算法求解具有模糊需求的CVRP。此外，程和Gen [11]也应用GA进行求解具有模糊交货时间的CVRP。

在求解CVRP方面，已经设计出了几种元启发式算法，如蚁群优化（ACO），粒子群优化（PSO），模拟退火（SA），禁忌搜索等。本文设计了一种新的混合元启发式方法来解决CVRPFD。它采用ACO和GA作为基础算法，因为它们都已成功应用于CVRP或CVRPFD [10]- [14]。本研究中提出的混合GA和ACO（GACO）算法将蚂蚁的路径规划与交叉和突变操作结合起来，以完成本地搜索和全局搜索。此外，嵌入了局部搜索算法以改进此算法的性能。

本文的其余部分安排如下。第二节给出了应用于本文的带模糊需求的CVRP数学模型。第三节讨论本文提出的GACO算法。第四节展示如何验证所提出的算法，第五节展示案例研究。最后，第六节给出了结论。

1. 带模糊需求的CVRP数学模型

CVRP被定义为这样一个问题：在满足若干限制的条件下，找到一条能访问到每个客户且满足客户的需求的最优路径。CVRP一般包括以下几个内容：一个完整的图， 是顶点集，E是边集。顶点 对应于每个客户。顶点0对应于仓库，n是客户数量。每个客户i都有必须交付给仓库的非负需求。车辆集，每辆车的容量都为C，每辆车在仓库中都可使用，且在完成配送任务之后必须回到仓库。对于所有来说，非负代价与边有关，且表示顶点i到j的距离。决策变量在（1）和（2）中定义。

（1）

（2）

公式（3）-（10）提及CVRP数学模型。

最小化 （3）

满足以下条件：

公式(3)是CVRP的目标函数。它最大限度地减少总配送距离。第一个约束条件公式（4）保证从仓库出发的车辆数量与到达仓库的车辆数量相同。接下来两个约束条件等式(5)和(6)确保每个客户都被访问一次。公式(7)中提到了可用车辆数量的限制。公式(8)和(9)表示两个决策变量之间的关系。最后，公式(10)中的约束条件保证不超过车辆容量。

CVRP 最早由Dantzig and Ramser [1]介绍。假设基本 CVRP 中的所有变量都是确定了的。然而，在实际问题中，很多配送问题都要处理不确定的数据。最近，改进的CVRP 使用模糊变量来处理不确定数据。

Zadeh 提出了模糊集理论，它作为一个非清晰的边界，其元素具有隶属度 [15]。关于模糊变量在具有不确定数据的 CVRP 上的应用，有人已经提出了一些模糊事件测量理论，例如可能性和必要性理论 [16] 和可信度理论 [17]。模糊事件的可信度被定义为其可能性和必要性的平均值，如果其可信度为 1，模糊事件必须成立，如果其可信度为 0，则不成立[18]。在 2006 年，郑和刘应用这些理论开发了具有模糊运输时间的 CVRP[7]。

在CVRPFD中，客户需求表示为三维模糊数值，，d1和d3分别表示需求量的最小值和最大值。d2对应于1的成员等级。假设客户i的需求量表示为。那么车辆k服务的总需求量为。因为是个模糊数值，那么也是个模糊数值，即，公式11展示了可信度。

配送员偏好指数表示配送员对风险的态度[8,18]，且的值在[0,1]范围内主观确定。如果，则满足容量约束条件。参数的值较低，表示配送员尽可能多地使用车辆容量。而更大的值表示配送员正规避风险的。最后，公式（12）表示了CVRPFD的容量约束条件。它保证，在满足车辆容量限制的条件下，所有客户都被访问，且置信水平为。

1. 研究方法

本文提出的 GACO 算法结合了遗传算法、蚁群算法和两种局部搜索算法。GACO 算法尝试提高基本蚁群算法的性能。第一次改进是改进 ACO 中的初始化步骤。通常，ACO 中的初始解是基于初始信息素生成的，初始信息素被设置为随机数或者常量。然而，信息素给出的信息应该代表每条路径的长度。通过传统的初始化步骤，这些重要信息无法传递给初始的蚂蚁。因此，初始蚂蚁被困在恶劣路线中的概率较高。在这项研究中，我们假设如果初始信息素能够提供关于每个路径长度的良好信息，初始蚂蚁将有更高的概率来规划更好的路径。如此一来可以帮助 ACO更快地找到最佳解决方案。提出的 GACO 算法在初始解的基础上提供了初始信息素。初始解是局部最优解，通过根据客户的距离对它们进行分组并使用 Prim 算法为每个组规划子路径来获得。

此外，为了进行局部搜索和全局搜索，GACO通过将ACO和GA相结合来生成新的解决方案。本文采用蚁群算法的路径构造过程，并将其嵌入遗传算法中常用的交叉和变异操作中。这种策略是为了平衡倾向于由ACO完成的局部探索和通过交叉和突变操作进行的全局探索。最后一个改进是对构建的解决方案进行微调。最后，提出了求解CVRPFD的GACO算法，具体如下：

(1) 设置参数。

(2) 通过根据客户的距离分组并使用Prim算法为每个组构建子路径来构建初始解决方案。

(3) 基于初始解设置初始信息素。在初始解决方案中通过的路径应该具有更高浓度的信息素。把i=1设为计数器。

(4) 为每只蚂蚁执行以下操作：

a. 构建解决方案和更新局部信息素。

b. 将通过蚂蚁构建的解决方案转化为染色体。

(5) 执行全局信息素更新。

(6) 对于每个染色体，执行:：

a. 与优良的解决方案进行交叉操作。

b. 通过交换染色体中 30% 的数来进行突变。

(7) 找到最佳解决方案。

(8) 对步骤 (7) 中获得的最佳解决方案应用 2-opt 算法。

(9) 更新优良的解决方案。

(10) 如果i=T，则停止操作。否则，返回步骤4继续执行操作。

以下小节将清楚地讨论这些步骤。为了解决 CVRPFD问题，GACO 算法应该能够处理模糊计算。本文利用模糊可信度测量理论对不确定需求进行处理。因此，在 GACO 中需要进行等式 (11) 中提到的两次计算。该方程用于识别是否违反容量约束条件。

A．初始化

初始化步骤的目的是提供一种初始解，通过初始信息素可以将其转化为更有前景的信息。GACO 算法中的初始化步骤分两步进行。第一步，所有的城市都被分成几个小组。然后，为每个组构造一个子路径或最小生成树。

由于并行路径方法比顺序路径方法 [19] 表现更好，所以进行了这种分组。它从找到任何距离仓库最远的任意城市开始。然后，将靠近该城市的其他城市插入同一集群。用 Prim 算法求最小生成树。初始化的算法如下所示。

1. 给出城市集。这些城市被分成K个集群，，那么且。城市的模糊需求表示为。
2. 一辆车服务一个集群，服务集群的车辆的装载量是。
3. 初始化作为计数器，且设置。
4. 任意找一个离仓库最远的城市。
5. 将插入，且。
6. 更新，如果，则停止。否则，返回步骤7继续执行。
7. 找到下一个要被访问的离最近的点。
8. 更新。
9. 应用公式（11）计算。
10. 如果，就把插入，并返回步骤6继续执行。否则，更新，设置，且返回步骤4继续操作。

B．局部和全局信息素更新

信息素更新是为更新信息素给出的信息而执行的操作。本文提出的GACO执行局部信息素更新（13）和全局信息素更新（14）（在文献[29]中被应用）。

（13）

是一个参数，且。执行以下公式(14)以更新全局信息素。

（14）

是一个全局信息素衰变参数，，且

（15）

是曾获得最短的距离。

C.染色体表示

CACO算法使用离散染色体代表由蚂蚁构建的路线。每一位表示的数字代表城市的指数，而位索引对应于其序列（图1）。

图1.染色体表示

在应用交叉和变异操作之后，每条染色体代表一条完整的路径。因此，考虑到公式（4）-（10）和（12）所提到的约束条件，仓库索引点需插入现有的染色体中。以下为操作步骤：

1. 给出染色体，其中，表示染色体X的第i位。
2. 仓库表示为。
3. T是X的完整路径，将插入T。
4. 设定计数器，初始车辆装载量为。
5. 计算当前车辆装载量，是指中的城市的需求量。
6. 使用等式（11）计算。
7. 如果，就将位的城市插入T中。否则，在插入T之前将插入T，更新。
8. 增加计数器。
9. 如果，就将插入T，然后停止操作。否则，返回步骤5继续操作。

D．交叉和变异

交叉是为了加速全局搜索而进行的。在GACO算法中，在不考虑交叉率的情况下，对所有染色体进行交叉操作。精英解被定义为获得的最优解。

为了避免局部最优，GACO算法进行了变异。它是通过交换两个比特位来进行的。由于该方法中使用的染色体是代表序列的离散染色体，因此仅交换两个比特位不足以避免局部最优，特别是对于大规模CVRP。因此，为了确保该操作能够有效地帮助GACO算法避免陷入局部最优，对30%的比特数进行了变异操作。

E．局部搜索

GACO算法的最后一个改进是2-opt算法。该局部搜索用于改进前面步骤构建的解决方案。为了找到更好的序列，该方法被应用于在一个子路径中系统地交换两个城市。一条完整的路线由几个子路径组成。对每个子路径执行2-opt算法，以

资料编号：[4730]