附录B 外文原文

Production, Manufacturing and Logistics

An improved ant colony optimization for vehicle routing problem

Abstract

The vehicle routing problem (VRP), a well-known combinatorial optimization problem, holds a central place in logistics management. This paper proposes an improved ant colony optimization (IACO), which possesses a new strategy to update the increased pheromone, called ant-weight strategy, and a mutation operation, to solve VRP. The computational results for fourteen benchmark problems are reported and compared to those of other metaheuristic approaches.

Keywords: Vehicle routing problem ；Improved ant colony optimization ；Ant-weight strategy； Mutation operation

1. Introduction

Finding efficient vehicle routes is a representative logistics problem which has been studied for the last 40 years. A typical vehicle routing problem (VRP) aims to find a set of tours for several vehicles from a depot to a lot of customers and return to the depot without exceeding the capacity constraints of each vehicle at minimum cost. Since the customer combination is not restricted to the selection of vehicle routes, VRP is considered as a combinatorial optimization problem where the number of feasible solutions for the problem increases exponentially with the number of customers increasing (Bell and McMullen, 2004). Heuristic algorithms such as simulated annealing (SA) (Chiang and Russell, 1996; Koulamas et al., 1994; Osman, 1993; Tavakkoli-Moghaddam et al., 2006), genetic algorithms (GAs) (Baker and Ayechew, 2003; Osman et al., 2005; Thangiah et al., 1994; Prins, 2004), tabu search (TS) (Gendreau et al., 1999; Semet and Taillard, 1993; Renaud et al., 1996; Brandao and Mercer, 1997; Osman, 1993) and ant colony optimization (Doerner et al., 2002; Reimann et al., 2002; Peng et al., 2005; Mazzeo and Loiseau, 2004; Bullnheimer et al., 1999; Doerner et al., 2004) are widely used for solving the VRP. Among these heuristic algorithms, ant colony optimizations (ACO) are new optimization methods proposed by Italian researchers Dorigo et al. (1996), which simulate the food-seeking behaviors of ant colonies in nature. It has been successfully applied as a solution to some classic compounding optimization problems, e.g. traveling salesman (Dorigo et al., 1996) quadratic assignment (Gambardella et al., 1997), job-shop scheduling (Colorni et al., 1994), telecommunication routing (Schoonderwoerd et al., 1997), etc. If taking the central depot as the nest and customers as the food, the VRP is very similar to food-seeking behaviors of ant colonies in nature. This makes the coding of an ant colony optimization for the VRP is simple. Among the earliest studies was that of Bullnheimer et al. (1997) who presented a hybrid ant system algorithm with the 2-opt and the saving algorithm for the VRP. Other researches of the ACOs to the VRP included the work by Bullnheimer et al. (1999), Bell and McMullen (2004), Chen and Ting (2006). In the ACOs, the 2-opt exchange was used as an improvement heuristic within the routes found by individual vehicles and the pheromone updating rules mainly considered the global feature of the solution. This paper proposes an improved ant colony optimization with a new pheromone updating rule that can integrate the global feature and the local feature, a mutation operation and the 2-opt exchange for the VRP. The remainder of the paper is organized as follows. Section 2 presents the mathematical model for VRP. In Section 3, we present the IACO with ant-weight strategy and the mutation operation. Some computational results are discussed in Section 4 and lastly, the conclusions are provided in Section 5

1. Vehicle routing problem

The VRP is described as a weighted graph G = (C,L) where the nodes are represented by C = {c0, c1,..., cN} and the arcs are represented by L = {(ci, cj): i – j}. In this graph model, c0 is the central depot and the other nodes are the N customers to be served. Each node is associated with a fixed quantity qi of goods to be delivered (a quantity q0 = 0 is associated to the depot c0). To each arc (ci, cj) is associated a value di,j representing the distance between ci and cj.

Each tour starts from and terminates at the depot c0, each node ci must be visited exactly once, and the quantity of goods to be delivered on a route should never exceed the vehicle capacity Q

1. Improved ACO for VRP
   1. Generation of solutions

Using ACO whose colony scale is P, an individual ant simulates a vehicle, and its route is constructed by incrementally selecting customers until all customers have been visited. The customers, who were already visited by an ant or violated its capacity constraints, are stored in the infeasible customer list (tabu). The decision making about combining customers is based on a probabilistic rule taking into account both the visibility and the pheromone information. Thus, to select the next customer j for the kth ant at the ith node, the ant uses the following probabilistic formula.

where pij（k） is the probability of choosing to combine customers i and j on the route, tau;ij the pheromone density of edge (i,j), eta;ij the visibility of edge (i,j), alpha;and beta; the relative influence of the pheromone trails and the visibility values, respectively and tabuk is the set of the infeasible nodes for the kth ant.

• 1. Mutation operation

Mutation operation referring to genetic algorithm (Yu and Yang, 2007; Yu et al., 2007) alters each child at a predefined probability.The operators can help the IACO to reach further solutions in the search space. The idea of the mutation operation is to randomly mutate the tour and hence produce a new solution that is not very f

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

附录A 译文

生产、制造和物流车辆路径问题的一种改进蚁群优化算法

车辆路径问题（VRP）是一个著名的组合优化问题，在物流管理中占有核心地位。本文提出了一种改进的蚁群优化算法（IACO），该算法采用了一种新的策略来更新增加的信息素，称为蚂蚁权重策略，并采用变异操作来解决VRP问题。报告了十四个基准问题的计算结果，并与其他元启发式方法进行了比较。

关键词： 车辆路径问题；改进的蚁群算法；蚂蚁权重策略；突变手术

1. 简介

寻找有效的车辆路径是过去40年来研究的一个具有代表性的物流问题。一个典型的车辆路径问题（VRP）的目标是为多辆车从一个车辆段找到一组路线，到达许多客户，然后返回车辆段，而不超过每辆车的容量限制，成本最低。由于客户组合不限于车辆路线的选择，VRP被视为一个组合优化问题，其中问题的可行解决方案随着客户数量的增加呈指数增长（Bell和McMullen，2004）。

寻找有效的车辆路径是过去40年来研究的一个具有代表性的物流问题。一个典型的车辆路径问题（VRP）的目标是为多辆车从一个车辆段找到一组路线，到达许多客户，然后返回车辆段，而不超过每辆车的容量限制，成本最低。由于客户组合不限于车辆路线的选择，VRP被视为一个组合优化问题，其中问题的可行解决方案随着客户数量的增加呈指数增长（Bell和McMullen，2004）。

启发式算法，例如模拟退⽕ (SA) (Chiang and Russell, 1996; Koulamas et al., 1994; Osman, 1993; Tavakk oli-Moghaddam et al., 2006)、遗传算法 (GAs) (Baker and Ayechew, 2003; Osman 等⼈，2005 年；Thangiah 等⼈，1994 年；Prins，2004 年），禁忌搜索（TS） （Gendreau 等⼈，1999 年；Semet 和 Taillard，1993 年；Renaud 等⼈，1996 年；Brandao 和 Mercer，1997 年） ; Osman, 1993)和蚁群优化(Doerner et al., 2002; Reimann et al., 2002; Peng et al., 2005; Mazzeo and Loiseau, 2004; Bullnhei mer et al., 1999; Doerner et al., 2004）被⼴泛⽤于解决VRP。在这些启发式算 法中，蚁群优化（ACO）是意⼤利研究⼈员Dorigo 等⼈提出的一种新的优化⽅法。 （1996），它模拟了自然界中蚁群的觅⾷行为。它已成功应⽤于解决一些经典的复合优化 问题，例如旅行商(Dorigo et al., 1996)⼆次分配(Gambardella et al., 1997),⻋间调度，1994)，电信路由（Schoonderwoard等人，1997）等。如果以中央仓库为巢穴，以顾客为食物，VRP在本质上与蚁群的觅食行为非常相似。这使得用于VRP的蚁群优化的编码变得简单。最早的研究包括Bullnheimer等人的研究（1997年），他们提出了一种混合蚂蚁系统算法，该算法是具有2-opt和VRP的保存算法。对VRP的ACO的其他研究包括Bullnheimer等人（1999）、Bell和McMullen（2004）、Chen和Ting（2006）的工作。在蚁群优化算法中，2-opt交换被用作单个车辆找到的路径内的改进启发式算法，信息素更新规则主要考虑解决方案的全局特征。本文提出了一种改进的蚁群优化算法，该算法采用了一种新的信息素更新规则，将全局特征和局部特征结合起来，并对VRP进行了变异操作和VRP的2-opt交换。论文的其余部分组织如下。

第2节介绍了VRP的数学模型。在第3节中，我们介绍了带有蚂蚁权重策略的IACO和变异操作。第4节讨论了一些计算结果，第5节给出了结论。

1. 车辆路径问题

VRP被描述为加权图G=（C，L），其中节点由C={c0，c1，hellip;，cN}表示，弧由L={（ci，cj）：ine;j}表示。在这个图模型中，c0是中央仓库，其他节点是要服务的N个客户。每个节点与待交付货物的固定数量qi关联（数量q0=0与仓库c0关联）。每个弧（ci，cj）都有一个值di，j，表示ci和cj之间的距离。

每次行程从站点c0开始，并在站点c0结束，每个节点ci必须精确访问一次，且一条路线上交付的货物数量不得超过车辆容量Q。

1. 改进的VRP蚁群算法
   1. 生成解决方案

使用蚁群规模为P的蚁群算法，单个蚂蚁模拟一辆车，通过逐步选择客户来构建其路线，直到所有客户都被访问。已经被蚂蚁访问或违反其容量限制的客户存储在不可行客户列表（禁忌）中。

组合客户的决策基于概率规则，同时考虑了可见性和信息素信息。因此，为了在第i个节点为第k个蚂蚁选择下一个客户j，蚂蚁使用以下概率公式。

其中，p_ij（k）是选择在路线上组合客户i和j的概率，tau;_ij是边缘的信息素密度（i，j），eta;_ij是边缘的可见性（i，j），alpha;和beta;分别是信息素路径和可见性值的相对影响，tabu_k是第k蚂蚁的不可行节点集。

• 1. 变异操作

参考遗传算法的变异操作（Yu和Yang，2007；Yu等人，2007）以预定义的概率改变每个孩子。运营商可以帮助IACO在搜索空间中找到进一步的解决方案。变异操作的想法是随机变异巡更，从而产生一个新的解决方案，与原来的解决方案相差不远。在本文中，变异算子被设计成以随机方式进行客户交换。图2显示了图1中的父解决方案的表示。变异操作的步骤如下：

第一步，从所选父解决方案中选择两个回路，并从每个突变回路中选择突变点。图3a显示选择了第三次旅行中的第九位客户和第四次旅行中的第十二位客户。

图1 VRP的一个例子

图2 父解决方案的示例

第二步，交换不同旅行团中的客户同时生成子解决方案（参见图3b）。

第三步，确保子解局部最优。应用2-opt改进了子解中的变异旅行。最后，变异子解的表示和遍历如图所示。3c和4。

然而，变异操作可能违反车辆容量限制。处理这种情况有两种方法。第一种方法是为这些候选解决方案分配非常高的成本，从而降低它们在即将到来的搜索中被选中的概率。第二种方法是尝试通过调整交付量来修复由此产生的容量冲突。与第一种方法相比，第二种方法的优势在于，它更适合于更可能导致车辆通行能力违规的问题，并使IACO能够调查搜索空间中的进一步点。因此，采用第二种方法来处理车辆通行能力违规情况。

解决方案的每一条路径都以一定的概率发生变异。通常，在运行开始时，解决方案的多样性很大，并且随着时间的推移而减少。我们在运行过程中调整突变率，以促进第一代快速收敛到好的解，并在后期引入更多多样性以逃避局部最优。t代的突变概率为

其中，p_m^min和p_m^max分别是起始和结束时的较低和较高突变率，T和t分别是给定的最大世代数和迭代的当前世代数。

根据初步测试，我们建议将较低的突变率设置为p_m^min=1/n_c，其中n_c是客户数量，将较高的突变率设置为p_m^max=1/n_v，其中n_v是溶液中的路线数量。

图3a 突变程序（步骤1）。

图3b 突变程序（步骤2）

图 3c。突变过程（步骤 3）

图4 参观变异儿童解决方案

• 1. 本地搜索

在2-opt交换中，对单个车辆访问的客户位置的所有可能的成对交换进行测试，以查看是否可以实现目标函数的整体改进。该方法已用于VRP的几个ACO（Bullnheimer等人，1997年、1999年；Bell和McMullen，2004年；Chen和Ting，2006年）。

• 1. 更新信息素信息

信息素路径的更新是蚁群算法自适应学习技术和未来解决方案改进的关键因素。首先，信息素更新是通过减少所有链路上的信息素数量来进行的，以模拟信息素的自然蒸发，并确保没有一条路径变得过于主导。这是通过以下信息素更新方程完成的，

其中tau;_ij^new是更新后链路（i，j）上的信息素，tau;_ij^old是更新前链路（i，j）上的信息素，rho;是控制蒸发速度的常数，kappa;是路由数，k是解决方案中的路由数，kgt;0和Delta;tau;_ij^k是蚂蚁发现的路由k的链路（i，j）上增加的信息素。

信息素增量更新规则使用Yang等人（2007）提出的蚂蚁权重策略。具体而言，该战略的内容如下：

如果链接eth;i；jTHORN;在kth路线上，否则

其中Q是常数，L是解决方案中所有路线的总长度，即L=Sigma;_kD^k，D^k是解决方案中第k条路线的长度，d_ij是边的长度（i，j），m^k是第k条路线中的客户数量，m^kgt;0。

蚂蚁权重策略根据解的质量和每个环节对解的贡献来更新增加的信息素，它由两部分组成：全局信息素增量和局部信息素增量。在蚁权策略中，每条路径的全局信息素增量Q/（Ktimes;L）的数量与解的总长度有关，而每条链路的局部信息素增量（D^k-d_ij）/（m^ktimes;D^k）的数量基于链路（i，j）对解的贡献。由于更新增加的信息素的策略同时考虑了解决方案的全局特征和局部特征，因此可以确保分配的增加的信息素与路由质量成正比。链路/路由越有利，分配给它的信息素增量越多，为以后的搜索提供的指示信息也越准确。同时，通过自动调整当前最优路径链接的信息素分配方法，该算法可以在下一个循环中在更有利的区域进行更精细的搜索，这有助于扩大以往搜索的学习能力。用于更新图1中的解决方案中边缘上增加的信息素的参数如图5所示计算。

此外，为了防止局部优化并提高获得更高质量解的概率，更新方程的上限和下限[tau;_min，tau;_max]是固定的。

i其中d0i是从中央仓库到第i个客户的距离。

图5 更新增加的信息素的参数

• 1. 整体程序

我们的VRP IACO流程图如图6所示。

1. 数值分析

前几节中描述的启发式方法适用于14个车辆路径问题，这些问题可以从OR库下载（见Beasley，1990），并被广泛用作基准，以比较其找到VRP解决方案的能力。14个问题的信息显示在表1的第2-4列中，其中包括问题大小n、车辆容量Q和众所周知的公布结果（Taillard，1993；Rochat和Taillard，1995）。用于VRP实例的IACO参数为Q=1000、alpha;=2、beta;=1和rho;=0.8。然后，在Visual C 中对IACO进行编码。Net 2003，并在配备512 MB RAM和1000 MHz奔腾处理器的PC上执行。第5-8列显示了IACO的结果，包括最佳解决方案、最差解决方案、平均解决方案和平均运行时间（秒）。粗体数字是最著名的解决方案的结果。

为了评估蚂蚁权重策略和变异操作，构造了两种不同策略的蚁群优化。第一种是带有蚂蚁权重策略的标准蚁群优化（用ACO-W表示），另一种是带有变异操作的标准蚁群优化（用ACO-M表示）。计算结果如表2所示。粗体数字是三种算法中最好的解决方案。可以观察到，ACO-M可以在测试问题1、2、3、6、7、11、12和14中获得与IACO相同的解，而ACO-W只能在测试问题1、2、6、7和14中获得最优解。与ACO-W相比，ACO-M通常能为这14个问题提供更好的解决方案。这可能是因为引入变异操作可以使蚁群多样化，探索新的可能解空间，防止算法陷入局部最优。然而，虽然变异操作改进了解，但也增加了计算时间。我们可以看到：

表1 使用IACO的计算结果和著名的公开结果

图6 IACO的流程图

表2 使用IACO、ACO-W和ACO-M的计算结果

ACO-M比ACO-W更多。这可能是因为在ACO-W中，蚂蚁权重策略用于更新增加的信息素。它可以根据溶液的质量

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

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