基于粒子群算法与人工蜂群算法的多目标车辆路径优化

基于粒子群算法与人工蜂群算法的多目标车辆路径优化

吴天红，王玮，姜英姿

江苏省徐州工程学院，江苏，徐州， 221000

摘要：车辆路线问题是配送计划的基本问题，它试图考虑客户的数量，他们的约束以及可用车辆的数量和容量的情况下，以最小的位移成本找到最佳的行进路线。在这项研究中，我们首先描述了旅行商问题和车辆路线模型，然后提出了考虑顾客之间优先约束的多目标车辆路线模型。有不同的元启发式算法可以解决此类NP难题。本研究提出了一种基于粒子群算法和人工蜂群算法相结合的求解算法。此外，通过分析一个操作样本，使用区域内客户的数据，考虑问题及其功能的不同约束，并使用惩罚方法和附加的分段约束方法，可以获得最佳的车辆路线。以及对每种算法的结果结合其混合算法进行了演示。

关键词：车辆路线问题；元启发式算法；粒子群优化；人工蜂群；混合算法；优先约束

一 、介绍

车辆路径问题^[1]是配电系统的重要组成部分之一，引起了该领域许多专家的关注。这些问题具有旅行推销员问题的逻辑，试图找到覆盖客户，满足他们的需求，降低成本并提高收益的最佳方法，从而使他们可以从一个角度出发，然后遍及所有地区，回到第一个起点。

考虑优先约束，将旅行商问题^[2]定义为：一个仓库和多个客户为输入数据，客户与仓库之间以及客户之间的所有距离都是确定的。我们正在寻求解决这个问题，以便以最小的成本，并考虑到客户之间的优先距离和约束，找到最佳的路线。

通过考虑通常源自现实的确定方法，元启发式算法^[3]从一个角度开始解决问题。然后，在重复算法之后，他们寻求找到最佳响应。在该领域已经提出了不同的算法，一种是粒子群优化算法。通过考虑不同的约束条件并研究概率模型，该算法已用于车辆路径问题。此外，人工蜂群通过考虑不同的约束条件，例如交货时间、需求限制、装载量、最大订货量，该算法同样也已用于该问题。该模型已在存在此类限制的情况下进行了求解，其结果已用于获得最佳响应。基于此，一种新的方法是在元启发式算法领域中使用混合算法，以更快更好地实现最佳响应。在该领域中已经提出了几种混合算法。例如，PSO算法与其他种算法的结合已经弥补了PSO算法在随机选择初始人群、寻找最佳个人和群体经验以及更新速度矢量方面的弱点，因此可以更快地获得响应。PSO和ABC算法的结合，混合了两个相似的连续算法，并在更广泛的搜索域中找到原始数据，从而更快地获得了响应。

二、问题陈述

首先，我们假设仓库中有车辆，并且必须拜访一些客户。具有优先约束的车辆路径问题包括找到一条路径，该路径从一个点开始并以确定的距离通过不同的节点。此方法与以前的路径方法不同，不需要从某个点开始再返回到该点，但是必须遵守优先约束。这种新方法称为开放式车辆路线选择方法。

例如，图1中给出了一个考虑优先约束的样本图。其中，首先访问节点2，然后访问节点4。为了访问该节点，在其等效节点之中，必须分别进行最小访问成本，这在算法中进行了说明。

图
1. 具有优先约束的示例关系图

2.1 问题变量和参数

x_ijk：是值为0或1的变量，如果为1，则表示车辆k从客户i到客户j的移动。

y_ik：是值为0或1的变量，如果为1，则表示车辆k已为客户i提供服务。

2.2 目标功能

适用于此问题的目标包括最小化四个目标功能:

（1）

总成本最小化功能（ ）定义如下：

（2）

在此公式中，Cij是从节点i到节点j的路径成本，即车辆的固定成本。此公式可以计算客户之间通过所有路线的总成本。

减少旅行时间（f₂）定义如下：

（3）

在此公式中，t_ij是从客户i到客户j的旅行时间。此公式可以获得客户之间的总访问时间，并将其最小化。

减少车辆总数（f₃）定义如下：

（4）

在此公式中，h_k表示返回仓库之前要服务的最后一个节点（驾驶员的家），并且M是足够大的常数。此公式可以最小化根据来源计算的车辆总数。

缩短客户拜访的时间间隔（f₄）定义如下：

（5）

在此公式中，L_max是所有客户在最近和最早时间之间的最大差异，应将其最小化。

2.3 约束条件

（6）

（7）

根据优先约束图得到每个客户确定的条件，按比例获得问题关注的优先约束。对于某些客户，它们是根据限制条件指定的，在访问另一个客户之前必须明确执行。

三、优化算法

现已经开发出解决多目标问题^[5]的不同方法。其中之一是目标函数应首先假定为局限性，并通过一个目标函数解决问题。通过以下步骤，本研究中使用的方法是一种附加的细分约束方法：

3.1 粒子群算法

PSO算法^[7]是元启发式算法之一，它于1995年由Kennedy提出，针对车辆路径问题而开发。它是用于解决连续问题的首批算法之一，并且与进化策略有关，该策略受鸟类或鱼类的群体行为来寻找食物的启发。因此，一群鸟在随机的空间中寻找食物，而有一块食物，没有一只鸟知道它的位置，只知道它们到食物的距离。最好的策略之一是跟随靠近食物的鸟。在观察鸟类运动时，可以看到所有鸟类都以不同的偏差跟随领先的鸟类。

该算法的功能如下：每个粒子都趋向于朝一个目标运动，而这一运动的因素是速度。因此，每个粒子的新位置将等于先前位置加上新速度。

(8)

根据该算法，影响速度的因素是旧速度，与最佳个人经验的距离以及与最佳总体经验的距离。

为了更好地理解这三个概念，我们研究以下示例。假设我们在重复项10处,并且有两个解。

（1）第一个解决方案的个人经验：84

（2）第二种解决方案的个人经验：29

（3）第一个解决方案的最佳个人经验：80

（4）第二种解决方案中的最佳个人体验：25

（5）团体最佳总经验：25

3.2 人工蜂群算法

人工蜂群算法^[8]由Karaboga于2005年首次提出，并针对车辆路径问题而开发。与PSO算法类似，它受鱼类或鸟类的群体运动的启发，而人工蜂群算法则受蜜蜂运动启发。它是根据蜜蜂的觅食而形成，在现实世界中，蜜蜂被分为三类：工作蜂、旁观蜂、侦察蜂。

该算法基于对所用蜜蜂的搜索而开始，这是完全随机的。每只蜜蜂随机选择一个相邻的蜜蜂并向其移动。该运动的公式如下：

(9)

其中V_ij是新位置，X_ij是以前的位置, 是[-1，1]内的随机数，j是运动维度，k是相邻蜜蜂，i是当前蜜蜂。如果新的位置更好（与目标函数兼容），则蜜蜂将停留在新的位置。否则，它将返回到其先前的位置，并且会将一个单位添加到该蜜蜂的试验索引中。

3.3 粒子群与人工蜂群的混合算法（PSO-ABC）

本文提出了一种结合粒子群算法和人工蜂群链的算法。该算法首先为粒子/蜜蜂建立随机的初始个人最佳位置。然后在主循环中，它使用粒子群优化阶段和人工蜂群优化阶段方法改进个人最佳状态。当主循环结束时，算法扫描最新的个人最佳位置，并将其中的最佳位置作为全局最佳位置返回。粒子群优化阶段方法获取粒子的最佳位置列表，用更好的位置更新它们，然后返回。与个人最佳值相比，为每个粒子指定一个新的随机当前位置。PSO阶段输出修改后的个人最佳值集，而PSO算法返回单个全局最佳位置。

表2. 考虑主要随机数据和优先约束获得可能的路线

提出的混合算法（PSO-ABC）搜索针对VRP-PC问题的最佳响应。首先，需要一个随机值来启动算法，该值等于节点数（从1到n）。这些节点可以是客户或地区的数量。例如，对于包括6个客户的图1，随机生成以下数据以启动算法：{4 1 3 6 5 2}。

在操作样本中，结果和算法输出部分介绍了某公司有关的信息。通过在计算机软件中实现该程序，可以给出其结果以及不同方法与算法输出的比较。

五、算法的结果与输出

提出以下操作样本，以总结和研究用于解决具有优先约束的车辆路径问题PSO-ABC算法的输出。在此示例中，提取了分销公司中的35个客户的信息。表4列出了提取出的客户的坐标。

表4. 分销公司的35个客户信息

针对每个客户和旅行服务的优先级和延迟约束可以表示为以下优先约束。

（1）交通限制（由于道路为单向，因此必须在下一个客户之后拜访）。

（2）拜访时间限制（某些特殊客户（例如购物中心）确定了与区域交通限制兼容的特殊拜访时间）。

（3）订单数量限制（订单数量高是访问优先级，因为它在快速分发操作中有效）。

（4）特殊商品限制（主要针对医疗商品建立，这被称为战略商品，可以提供给特殊客户，也可能非常昂贵。）

表5. 从粒子群和蜂群的混合算法获得的最佳响应结果

表6. 拜访客户的最终路线以及每辆车的容量和覆盖距离

在图2中，表示出了该算法的响应收敛图。可以看出，与其他算法相比，PSO-ABC更快地达到了响应，并具有更好的收敛性。关于该图值得一提的是，平均响应以不同的重复显示。

图
2. 算法收敛图

关于获得响应的时间，混合算法中算法开始非常快地朝响应移动，并且逐渐降低了速度。但是，另外两个算法以均匀的速率移动。根据此表，混合算法在不到1分钟的时间内找到了90％的最佳解决方案，而PSO则找到了69.23％的最佳解决方案，而ABC则找到了81.87％的最佳解决方案。同样，随着迭代次数和群体（粒子或蜜蜂）数量的增加，PSO-ABC算法比其他算法更快。

六、结论

这项研究包括两个主要部分：第一部分涉及考虑优先约束车辆路径问题的建模和公式化描述，将问题陈述为多目标函数，以及使用优先约束和惩罚方法解决多目标问题的描述。第二部分包括描述元启发式算法以及使用粒子群和人工蜂群解决问题的混合算法。如本研究所示，可以很容易地手动解决小问题。但是，对于较大的区域，需要重复并比较所有路线，以获得最佳响应。该研究中提出的混合算法（PSO-ABC）比相关文献中的其他可用算法能够更快地找到最佳路径。这个问题的最后一点是，所有这些算法都可以用于通过更改模型和约束以及应用软件来获得最佳响应。

参考文献：

[1]刘云忠, 宣慧玉. 车辆路径问题的模型及算法研究综述[J]. 管理工程学报, 2005, 19(1):124-130.

[2]高海昌, 冯博琴, 朱利b. 智能优化算法求解TSP问题[J]. 控制与决策, 2006(03):3-9+14.

[3]刘青松, 孔云峰, 党兰学, et al. 元启发式算法在校车路径规划中的应用[J]. 地理空间信息, 2013, 11(5):171-174.

[4]孔阳, 李世伟, 孔晓丹. VRP问题的建模及算法研究[J]. 科技经济市场, 2015(7):170-171.

[5]肖晓伟, 肖迪, 林锦国, et al. 多目标优化问题的研究概述[J]. 计算机应用研究, 2011(03):11-14+33.

[6]王小燕, 谢邦昌, 马双鸽, et al. 高维数据下群组变量选择的惩罚方法综述[J]. 数理统计与管理, 2015, 34(6):978-988.

[7]张利彪, 周春光, 马铭, et al. 基于粒子群算法求解多目标优化问题[J]. 计算机研究与发展, 2004(07):249-254.

[8]杨丹. 人工蜂群算法的改进及应用研究[D]. 安徽大学, 2014.

大学生创新创业训练计划项目(xcx2019033)