基于概率矩阵粒子群优化的生产配送车辆路径问题外文翻译资料

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

基于概率矩阵粒子群优化的生产配送车辆路径问题

Byung-In Kim · So-Jung Son

摘要：粒子群算法（PSO）是一个相对较新的、最近备受各种优化领域研究人员关注的元启发式方法。然而, PSO应用于有容量约束的车辆路径问题(CVRP)是非常有限的。本文提出了一个简单的算法方法求解CVRP。提出的PSO算法方法使用一个概率矩阵粒子作为编码和解码的主要设备。然而现有研究，PSO专为客户分配路线和使用其他算法为客户路线排序，本文提出的PSO方法适用于同时解决两种问题。计算结果表明了相比于以前的方法该算法的有效性。

关键词：粒子群算法·有容量约束配送车辆路径问题·元启发式·优化

介绍：

有容量约束的车辆路径问题(CVRP) 是去寻找在满足客户特定需求的情况和相同的容量下，最好的车辆路线。(Dantzig and Ramser 1959; Toth and Vigo 2002)。每个客户只应该被一辆车访问，并且每辆车都应该从配送中心出发并最终回到配送中心。除了容量约束，CVRP 也可能限制最大路径长度。CVRP是一个非常基本的车辆路径问题，有很多变量和其他的考虑因素，比如说时间窗，不同的运输车辆，多天数，提货和运输的关联(Toth and Vigo 2002)。CVRP 是著名的NP完全问题，所以各种启发式包括禁忌搜索算法 (Gendreau et al. 1994, 1999），遗传算法(Berger and Barkaoui 2003; Wang and Lu 2009)，和蚁群优化算法 (Bullnheimer et al. 1999)已经为这个问题而开发出来。

粒子群算法(PSO)是一个相对新的启发式算法(Kennedy and Eberthart 1995; Eberhart and Kennedy 1995)，最近吸引不同优化应用领域研究人员的注意。 然而，粒子群算法在CVRP问题中的应用非常有限。据作者最佳的了解，Chen et al. (2006) and Ai and Kachitvichyanukul (2007, 2009)是唯一相关的的工作。他们仅用（PSO）来解决客户路径分配，其他算法为顾客进行路线排序。

本文算法除了适用于客户路径分配，同时也为顾客进行路线排序。基准问题实例计算测试表明了粒子群算法的有效性，相比于以前的方法。其余的部分本文组织结构如下。一个简短的粒子群算法文献回顾及其CVRP对应部分的应用在“文献回顾”的章节提供。我们提出的基础粒子群算法在“基于粒子群算法解决有容量约束的车辆路径问题。”一节中被描述。计算结果和结论出现在随后的章节。

文献回顾

粒子群算法最开始是模拟鱼教育和鸟成群结队的社会行为进行 (Kennedy and Eberthart1995; Eberhart and Kennedy 1995)。

图1

它是一个基于搜索方法的种群迭代。PSO表示一个解决问题方案是一个粒子编码的多维度定位及种群动态高速移动在搜寻区域寻找一个更优解。在每一次迭代中，粒子的位置和速度是基于粒子的个体经验和种群的共享社会信息。Shi and Eberhart (1999)提出以下模型来表示粒子位置的更新。

式中，t代表迭代次数，粒子i的位置被表示为xi = (xi1, xi2,..., xi D)，粒子i的速度为vi = (vi1, vi2,...,vi D)，粒子i最新的最优解（或位置）为pi = (pi1, pi2,..., pi D)，全局的最新最优解为pg = (pg1, pg2,..., pgD)。W是惯性因子，c1和c2是加速权重因子，rand(0,1)为[0,1]之间的随机数。

图1形象地显示了（1）和（2）的更新机理，惯性因子w在等式1中平衡粒子局部和全局搜索。Shi and Eberhart (1999)发表，开始时，惯性权重接近于1，在算法后期设置线性减少的惯性权重以进行局部搜索。Kennedy and Eberthart (1995)设置学习因子c1和c2为2。

自从1995年粒子群算法被提出，它的应用领域逐渐扩展。它被应用到连续非线性优化问题(Kennedy and Eberthart，1995)，训练人工神经网络(Eberhart and Shi 2001)，作业车间调度问题(Zhang et al . 2009年)，钢热轧进程调度 (Chen et al. 2008)，旅行商问题 (Pang et al. 2004)，供应链网络设计问题 (Banks et al. 2008)，部分测序数控机床和操作排序优化 (Kumar et al. 2009)，视力检查印刷电路板(Wu et al. 2009)，和其他等等。更加多样化的应用领域进行了Eberhart and Shi (2001), 和Banks et al. (2007, 2008)。下面的一些与本文研究工作相关的。 本文进行简要回顾。

Chen et al.(2006)应用离散形式的粒子群算法在模拟退火(SA)有容量约束的车辆路径问题上。他们用一个编码方法将值设置为两个客户和车辆，1表示如果顾客认为是分配给车辆，否则0。该算法被用来分配客户车辆和SA用于序列的路线。

Ai and Kachitvichyanukul(2007,2009)为有容量约束的车辆路径问提出了两个编码方法命名SR-1和SR-2。SR-1下，一个CVR有n个客户和m辆车被编码为 (n 2 m)维粒子，每个粒子的维度可以得到一个实数。第一个n维的粒子显示客户的优先顺序和剩下的2m维度代表车辆的参考位置。基于客户的优先顺序，每个客户分配给有足够的剩余能力的最近车辆。每当客户分配给一个车，车辆的路线是由构造启发式和生成由2-opt改进的改进算法。

SR-2编码一个CVRP用三个维度用于车辆的（3m）维粒子：两个维度参考点和一维的车辆覆盖半径。基于车辆的位置和半径，他们尽可能被分配多个的客户，在他们的范围内和没有被分配到其他汽车，车辆的路线用构造启发式建立。客户分配后,，生成的路线由2-opt改善，一对一的交流，1 - 0交换过程。他们的计算结果显示SR-2超过SR-1Chen et al. (2006)。

Pang et al.(2004)使用一个基于矩阵的编码方法，将算法应用于旅行商问题(TSP)。他们代表粒子位置和TSP与n个客户，它的速度为(ntimes;n)方阵。每个元素位置矩阵有一个值在0和1之间，每一行的总和是1。速度矩阵的每个元素都有一个任意值而每一行的总和等于0。从这个粒子位置矩阵,可以生成一个解决方案如下。矩阵的每一行对应一个客户。每一行的元素不选择在前面行，选择具有最高价值。这样的选择意味着客户对应的行会被立即访问在选择客户所在列之前。我们使用类似的编码方法在这篇论文里。

提出粒子群算法解决有容量约束的车辆路径问题

如前一节所述，现有的粒子群算法解决有容量约束的车辆路径问题仅分配客户路线，而用其他启发式来客户路线排序。本节描述了我们将粒子群算法用于客户分配路线以及同步排序测序客户路线。

解决方案的编码

我们使用一个基于矩阵的粒子表示相似于Pang et al. (2004)。CVRP 中有n个客户，有一个 [(n 1)times;(n 1)]位置矩阵。每个元素的位置矩阵赋一个值在0和1之间，每一行的总和是1。行和列1到n对应着客户，第一行和第一列(坐标为0)对应于仓库。我们不使用速度矩阵。元素 ei j的元素位置矩阵显示关联节点i和节点j的概率。(一个节点意味着一个客户或一个仓库)。

图2中的解决方案可以编码如图2 b我们的编码方案。因为客户3、4、6、7是相关的节点，从仓库（0）到客户连接的概率设置为0.25。因为客户1 连接到2和7，从1到2和7的概率设置为0.5。注意，我们假设节点之间的距离是对称的，方向不影响总距离。距离不对称的CVRP 可能需要一个不同的编码方案。

解决方案解码

从一个粒子编码可以生成的一个解决方案如下。一条路线从仓库开始。基于仓库和客户之间的概率，一位客户被选择。 例如，考虑到编码矩阵在图3，客户 1、2、3、4、6、7可能被选择的概率分别为0.，,0.1，0.2，0.2，0.2和0.2。如果客户1 被选中时，下一个客户将从第一行中选择，所以，假设客户可以添加到当前路线在不违反车辆容量约束的情况下，选择客户2、3、7的概率分别是0.3，0.3和0.2。由于概率之和小于1，他们是规范化的总和。让我们假设客户3被选择。

在这个阶段,只能视客户4为下一个节点，因为所有其他的客户(1和2) 正概率已经路由。如果当前路线可以包含客户4而没有违反车辆容量、 客户将被包括在内。现在，从客户4起不在线路上的客户概率为正的将被考虑。在这个示例案例中，客户5是唯一的一个。然而，如果当前线路不能带客户5因为车辆容量约束，则当前的路线将被关闭，一个新的路线将由相同的程序。如果客户7 被选中作为一个启动客户，客户5和6是候选人作为下一个节点。如果客户选择6，客户5将被选择，最后如图3b所示。

因为我们的解码方法构造一个解决方案使用概率，编码的粒子可以生成不同的解决方案。例如,客户3，而不是客户2可以被选择在客户1之后，如图3所示。 然后客户可以在序列中选择客户4和5。当没有客户为正的概率，路线容量又没有达到时，不在线路上的客户可以被选择因为其到基础节点的距离。例如，如果在序列中客户6和7被选择为第二路线，如图3b所示，没有客户被认为是下一个客户，因为所有正概率的客户已经在线路中。在这种情况下，不在线路上的客户2被认为是下一个，如果当前路线可以在不违反的容量能力约束。

粒子更新

随着算法的总体框架(Kennedy and Eberthart 1995)，更新粒子的位置迭代。然而，我们使用一个稍微不同的更新机制，如等式(3)所示。正如之前提到的，我们不使用速度的概念，因为我们想保持位置矩阵的元素值介于[0,1]，就像概率那样来选择客户。当使用速度，调整位置矩阵的值需要保持值范围。事实上，我们尝试使用原始的更新机制方程式(1)和(2)所示，但我们的初步研究表明，修改没有速度更好，所以我们更新机制决定使用它。

式中，wt1 wt2 wt3 = 1，t代表迭代数, 粒子i的位置被表示为Ai矩阵，粒子i最新的最佳解决方案(或位置)为Pi矩阵，最新的全球最佳解决方案为G 矩阵。wt1是一个惯性因素，wt2和wt3是权重因素。wt1 可以由客户提供的初始和最终值决定。wt2来自随机数(0,1)lowast;(1minus;wt1)和wt3是通过1minus;wt1minus;wt2计算得来。

图4显示了一个示例的粒子更新步骤，假设wt1 = 0.5，wt2 = 0.2，wt3 = 0.3。简而言之，更新规则使用加权总和（或凸组合）以前的粒子矩阵，个体最好粒子矩阵, 和全局最佳粒子的矩阵。

粒子的适应度值计算的基础为路线的数量以及其相应的总距离，对应的解决方案。当粒子的适应度值相比较，前者和后者被认为是标准。换句话说，一个路径数量较少的解决方案被认为是比一个距离更短但路径数量多的解决方案更好。当一个粒子发现一个更好的解决方案比其最新的最佳解决方案，其个体最佳解决方案矩阵将被改变。全局最佳粒子也更新矩阵及其解决方案 每当一个新找到最佳解决方案。

初步解决方案建设

因为PSO是一个基于种群元启发式方法，它需要生成多个数量的初步解决方案。我们最初的解决方案是一种已知的变量排除算法(Gillett and Miller 1974)如下。

步骤0：计算每一站和仓库之间的极角。

客户极角递增的顺序排序(逆时针方向)：s1，s2，s3，hellip;hellip;，sn。

设置k =用户提供数量(或一个随机数)在1到n之间。

插入命令sk，sk 1，sk 2，hellip;hellip;sn，s1，s2，hellip;hellip;hellip;，skminus;1。

步骤1。开始一个新的路线。

从列表中指定第一个没有分配路线客户的路线。

步骤2。从目前的路线选择最近的客户。

继续这样分配最近的客户去构造路线，保证客户的需求总和不超过容量约束。

步骤3。如果有一个未分配线路的客户存在，重复步骤1。此外，去步骤4。

步骤4。改进局部程序运行的子部分：“局部改善程序”。

该算法首先以最小的极角在剩下的客户中分配客户路线，然后找到最近的客户分配路线。重复这个过程直到没有更多的顾客可以分配路线满足容量约束。所构造的路线在下一小节进行程序改进。

局部改善程序

无论什么时候一个解决方案提出最初的路线构建方法或粒子群算法中粒子更新迭代算法方法，一些流行局部搜索程序应用于改进域间路径和域内路径。域间路径的改进程序是将1:1交换为1 - 0。1:1交换程序选择两条路径，交换一条路径的一位客户和另一条路径的另一位客户。当这会带来改善，这次交换将被接受。1 - 0交换程序选择两种途径，移动一个客户从一条路径到另一条路径。

域内路径改进程序是将2-opt和Or-opt交换。2-opt交换程序尝试改善旅游路线距离，通过交换两个连续的客户，i、ehellip;hellip;链接或边沿。它找到最好的一对连续的客户提高了旅行距离和接受交换。这个过程是重复进行，直到没有改善。还

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

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