1、 外文翻译 原文 An algorithm for the capacitated vehicle routing problem with route balancing Material Source:Springer Link Author: Istvn Borgulya Abstract: In this paper, we present a multi-objective evolutionary algorithm for the capacitated vehicle routing problem with route balancing. The algorithm is
2、based on a formerly developed multi-objective algorithm using an explicit collective memory method, namely the extended virtual loser (EVL).We adapted and improved the algorithm and the EVL method for this problem. We achieved good results with this simple technique. In case of this problem the qual
3、ity of the results of the algorithm is similar to that of other evolutionary algorithms. Keywords: Evolutionary algorithm; Multi-objective optimization; Explicit collective memory; Combinatorial optimization; CVRP 1 Introduction The vehicle routing problem (VRP) is a well-known and frequently analyz
4、ed model and often used in real life applications, like transportation, logistics, and scheduling. One of the simplest versions of the VRP is the Capacitated Vehicle Routing Problem (CVRP). The CVRP is a graph problem that can be described as follows: the quantity qi should be delivered to customer
5、i (i = 1, . . . , n) from a single depot using a fleet of vehicles with capacity C. A solution of the CVRP is a collection of tours where each customer is visited only once and the total tour demand is at most C, with the objective of minimizing the total distance traveled by all the vehicles. The V
6、RP has been proved to be NP-hard (Laporte 1992) and the solution methods applied a range from exact methods to specific heuristics and meta-heuristics. The branch and bound or branch and cut methods provide optimal solutions (Hadjiconstantinou and Christofides 1995) however, some problems with 75 no
7、des are not solved yet (Prins 2004). Therefore, heuristic algorithms are highly welcome to solve large problems. In the realm of heuristics we can mention specific heuristics like the neural network and meta-heuristics like simulated annealing, tabu search, evolutionary algorithms (EA), ant colony o
8、ptimization, particle swarm optimization (e.g. Sun et al. 2005; Van Breedam 2001; Berger and Barkaoui 2003; Cordeau and Laporte 2002; Mazzeo and Loiseau 2004; Chen et al. 2006; El-Sherbeny 2001; Tavares et al. 2003). In real life applications there are many versions of CVRP. For example, we can ment
9、ion VRP with time window constraints, dynamic vehicle routing, or some multiobjective versions of the VRP. In the multi-objective versions the additional objectives can be, e.g. the minimum number of the vehicles, the balance of the routes, or in dynamic cases, the minimum total mean transit time an
10、d the minimum total variance in transit time, and even more objectives can be included. In this paper, we consider the capacitated vehicle routing problem with route balancing (CVRPRB). The following two objectives are considered: f1: Minimization of the distance traveled by the vehicles. f2:Minimiz
11、ation of the difference between the longest route length and the shortest route length. References (Jozefowiez et al. 2002, 2006; Pasia et al. 2007a,b) already contain solutions for this problem. In Jozefowiez et al. (2002, 2006), there are two different solutions with EAs: an island model with tabu
12、 search, and an island model with the NSGA II method (Deb et al. 2002). Pasia et al. (2007a,b) describe a method with population-based local search, and another one with ant colony optimization. In this paper, we present a new EA for the multi-objective problem. 1.1 Motivation for a new EA In an ear
13、lier work (Borgulya 2006) we presented a new method for the bi-objective quadratic assignment problem (bQAP), using a new extended version of an explicit collective memory method, called virtual loser. In the extended virtual loser (EVL) we enabled the virtual loser to handle several discrete values
14、 instead of binary values, and the values of variables for example can be the values of permutations, too. (We can use this extended virtual loser technique in case of combinatorial models without the problem discrete making through binary or Gray coding.) For the bQAP, we had modified our earlier m
15、ulti-objective EA using the EVL technique, and we presented fine results with the new algorithm (named MOSCA2b). UsingMOSCA2b we want to indicate that this algorithm framework can be applied successfully for solving further types of multi-objective combinatorial problems, too. Let us note that MOSCA
16、2b was applied first time in Borgulya (2007) to solve multiobjective TSP. Now we are going to use MOSCA2b to solve CVRPRB. For the CVRPRB we modified the MOSCA2b (Borgulya 2006): we adapted the EVL for the CVRPRB. we used the EVL technique with a restart strategy. we used a special version of the tr
17、uncation selection. we used two special stochastic 2-opt local search algorithms to improve the solutions. The published evolutionary algorithms solve the CVRPRB problems by using sophisticated selection, recombination and mutation operators. We will show that our approach is a simpler one. The pape
18、r is organized in the following way: Sect. 2 shows the structure of the MOSCA2b algorithm, and Sect. 3 describes the details of the algorithm: the operations for the CVRPRB, the extended virtual loser and the mutation operator, and the details of the implementation. Section 4 shows our computational
19、 experience with the new EA and compares our results to that of other heuristics. Section 5 gives the conclusions. 2 The structure of MOSCA2b The principles of the general MOSCA2 version are as follows (Borgulya 2005): the population is separated into t subpopulations, each subpopulation approximate
20、 other part of the Pareto front. Each subpopulation is storing only non-dominated individuals of the possible members of the subpopulation (at a limited amount). The dominance of a new descendant getting into the subpopulation is determined by comparing it to a designated non-dominated individual, t
21、he prototype. If it finds a non-dominated descendant superior to the previous prototype, it deletes the former members of the subpopulation, and replaces the prototype by the new descendant. During the evolution process the new potential Pareto optimal solutions are periodically stored in a separate
22、 archive, and we have the result in this archive. If this separate archive (SARC) is full, the algorithm deletes a given percentage (10%) of its elements. We select first the most dominated individuals for deletion, after that continuously one of the individuals close to each other. The MOSCA2 uses
23、a 2-stage algorithm structure where both stages are a steadystate EA. The first stage is a quick “preparatory” one whose task is to improve the quality of the initial population. The second stage is an evolutionary strategy with some special operators (more detail in Borgulya 2005). Version MOSCA2b
24、is modified for combinatorial problems and uses some special operators. The selection is a special truncation one, and mutation is based on EVL. The algorithm uses a local search procedure with a weighted objective (Deb 2001), and it does not use any recombination operator. As additional operation,
25、the algorithm updates the ECM matrix, the memory of the EVL method. 3 Experimental results The result of the CVRPRB is a similar Pareto front by every test problem as we can see in Fig. 1. Usually we describe these results by two points of the Pareto front: with the minimum value of the distance tra
26、veled by the vehicles and the minimum value of the difference between the longest route length and the shortest route length.We show the results of the test problems in Table 1. Every test problem was run five times, and the table shows the best results (similar way as in the other papers). In the t
27、able we give the problem name (name), the number of the customers (n), the best length found (mindist) with its associated balance (bal), the best balance found (minbal) with its associated length (dist), the average number of the solutions in the approximations(eff ). Finally we give the maximum nu
28、mber of generations in thousands (gen) and the average running time in CPU seconds (CPU). To compare the results of our algorithm we chose two meta-heuristics. The first is a parallel hybrid EA that uses tabu search as local search (Jozefowiez et al. 2002) (notation: Ptabu). The second one is also a
29、 parallel EA (Jozefowiez et al. 2006) that is based on the standard multi-objective EA, the NSGA II (notation: PNSGA) (Deb et al. 2002). Both methods solved only the benchmark problems of Christofides, they did not try to solve benchmark problems from the Vehicle Routing Data Sets. We could not choo
30、se the methods (Pasia et al. 2007a,b) for comparison, because they did not publish the necessary dates. One of the main problems of this comparison is that the optimal Pareto frontiers are not known. We can compare the value obtained for the total length criterion to the best-known solutions of the
31、CVRP (objective f1) only. We find similar comparisons in Jozefowiez et al. (2002) and Jozefowiez et al. (2006) as well. We enrich the comparison applying a single-objective method that solves the CVRP problems in both test sets. The name of this method is the CLOVES, published in Ganesh and Narendra
32、n (2007). Table 2 presents the results of the comparison. The table exhibits the problem name (name), the best known solution of the CVRP ( BKS), and the error of the best found length from BKS (Error %). The Error % are based on the results of MOSCA2b, Ptabu, PNSGA, and CLOVES. Due to this comparis
33、on we can choose results with one processor except those of Ptabu, where we know the results only with more processors. Notwithstanding, our dates are very incomplete, so we try to compare the quality of the different results. Because of the problems of Vehicle Routing Data Sets, we can compare the
34、results of MOSCA2b and CLOVES only. Due to these problems MOSCA2b has better results, in general. However, using the benchmark problems of Christofides, we can compare all methods, but CLOVES results are the best. It is easy to see that the average performance of PNSGA is the best. However, MOSCA2b
35、has similar results. The performance of MOSCA2b in case of C1 and C12 are the same, while in case of C2, C3 and C11 the results are weaker, while in case of C4, C5, the performance of MOSCA2b is better. Using the second objective we have obtained very good results (see Table 1). The best balance is
36、very close to 0, one can assume that very well-balanced solutions are obtained. Comparing to PNSGA, we can conclude that the best balance values are less than 1, while in case of MOSCA2b and PNSGA the balance values are between 0.06 and 2.18 (Jozefowiez et al. 2006). The comparison of the running ti
37、mes is difficult as, using several processors, only the PNSGAs and the population-based local search methods running times are published (Jozefowiez et al. 2006; Pasia et al. 2007a). (The PNSGA program ran on IBM RS6000/SP with Power4 1.1 GHz processors, and the local search method ran on a PC with
38、a 3.3GHz processor). For comparison, we could use only the benchmark problems of Christofides. Based on the outcomes we can say that PNSGA has 4, 6 or 10 times shorter running times (Table 3 shows the running times of MOSCA2b and PNSGA in case of one and four processors). But the programs use variou
39、s programming languages, operating systems and computers. Moreover, IBM RS6000 with Power4 processors is faster than our PC. Another problem is the different number of processors. Generally, the parallel program with 4, 8 or 16 processors is 24 times faster than using only one processor. So, we may
40、not compare the two methods adequately. The comparison is easier with the population-based local search: its running times are between 600 and 30,000 CPU seconds. Although our computer is two times slower, we obtain our results during shorter running times. 译文 带有路线平衡的生产线路问题的一种计算方法 资料来源 : SpringerLin
41、k 作者： Istvn Borgulya 摘要 ： 在这里 ， 我们提出一种使路线平衡的车辆运输路线的多目标的优化算法 。 该算法是基于多目标采用了一个原本开发的明确的集体记忆方法 ， 即扩展虚拟的遗忘者（ EVL)。 我们采用和改进了 EVL 算法来解决这一问题 。 如果这种算法使问题的结果的质量与其他演化算法相似 ， 那么采用这种技术我们将取得不错的效果 。 关键词 ： 优化算法 ； 多目标的最优化 ； 明确的集体记忆 ； 优化组合 1 简介 车辆路径问题（ VRP)是一个著名的 、 经常分析的模型并且在现实生活中经常碰到的问题 ， 例如运输 、 物流 、 调度 。 最简单的一种车辆路径问
42、题是生产车辆路径问题 (CVRP)。 生产车辆路径问题是一种如下所述的图形问题 ： 将一定数量 iq 的物品用容量为 C 的车队从单一的车场送到客户 i（ i=1， .， n） 手里 。CVRP 的解决方案是将一批由各个散户提供但总量接近 C 的货物用所有车辆以总旅程最少的方式送抵目的地 。 车辆路径问题已经被证实为一个 NP 困 难问题（拉波特 1992） ，其解决方式的应用从精确的方式到具体的启发式算法和元启发式算法。分支定界法和分支切割法提供了最优解（ Hadjiconstantinouand 和Christofides 1992）。然而 ， 还有一些含有 75 节点的问题至今仍未解决
43、。 因此 ，启发式算法被推崇于去解决大问题 。 在启发式领域中 ， 我们谈及的特定的启发法例如神经网络和元启发法例如模拟退火算法 、 禁忌搜索法 、 演化式演算法 、蚁群演算法 、 粒子群算法 。 在现实生活中有很多生产车辆路径问题的应用 。 例如 ， 有时间窗约束的车辆路径问题 ， 动态车辆路径 ， 多目 标版本的生产车辆路径问题 。 在多目标版本以外的目标 ， 例如 ， 少量的车辆 、 线路的平衡 ， 或在动态情况下 ， 最低总平均穿流时间和最小总差异的转运时间 ， 甚至更多的目标等等 。 在这篇文章中 ， 我们考虑生产车辆路径的路线平衡问题 (CVRPRB)。 我们考虑一下两个方面 ：
44、1.车辆运输距离的最小化 。 2.最长的线路长度和最短路线的长度的差异最小化 。 在参考文献（ Jozefowiez et al. 2002, 2006; Pasia et al. 2007a,b）中已包含了这些问题的解决方案 。 在 Jozefowiez et al. (2002, 2006)中 ， 有两种用进化算法的不同的解决方案 ： 一个关于禁忌搜索的岛上模型和一个关于 NSGA 方式的岛上模型（ Deb et al. 2002) 。 Pasia et al.(2007 ab)描述了一种以人群为基础的搜索方式和另一种蚁群优化的方式 。 在这里 ， 我们提出了一种新的关于多目标问题的进化算
45、法 。 1.1 新进化算法的目的 在更早的研究中（ Borgulya 2006）提出了一种关于双目标的二次分配问题（ bQAP)的新方法 ， 它使用一种新扩展版本名叫 “ 虚拟遗忘者 ” 的明确的集体记忆方法 。 在扩展的版本（ EVL)中 ， 我们使虚拟遗忘者来处理一些离散值来替代二项值 ， 和变量值例如也可以是变量值 。 （我们可以用这个扩展的虚拟遗忘者技术假设通过二进制或格雷码制造的组合模式没有离散问题 。 ）为了解决双目标的二次分配问题 ， 我们改良了先前的使用了 EVL 方式的多目标进化算法 ， 并提出了有很好结果的新算法（名叫 MOSCA2b）。 通过 MOSCA2b 算法，我们想
46、要指出，该算法的框架也可以成功应用于解决更进一步的多目标组合问题。我们看到 MOSCA2b 算法首次应用于 Borgulya（ 2007）来解决多目标的旅行商问题（ Traveling Salesman Problem)，现在我们用 MOSCA2b 算法来解决车辆途径问题。 为了解决车辆途径问题 (CVRPRB)， 我们改良了 MOSCA2b 算法（ Borgulya 2006）。 我们试 EVL 试用于 CVRPRB. 我们将 EVL 技术应用于重新启动战略。 我们使用一种特殊的截断选择的版本 。 我们用两个特殊的随机二选择局部搜索算法来改进解决方案。 公布的进化算法解决 CVRPRB 问题
47、 ， 运用复杂的选择 、 重组 、 变异算子 。我们将证明这是种更为简单的方法。 本文将分为一下方式 ： 第 2 节讲述 MOSCA2b 算法的结构 ， 第 3 节讲述算法的细节部分 ： CVRPRB 的运算 ， 扩展的虚拟遗忘者和变异算子 ， 及其具体实施方式 。 第 4 节讲述我们对新进化算法与其他启示法的计算结果的比较 。 第 5节给出结论 。 2 MOSCA2b 算法的结构 MOSCA2b 版的一般原则如下（ Borgulya 2005） ： 一个群体被分成 t 个次级群体 。 每个次级群体接近于其他的 Pareto 前沿部分。每个次级群体只供应该群体内非支配个体的成员（在限定范围）。
48、一个带有优势的新后代进入次级群体决定于与指定的非支配个体的模型的比较。如果发现一个不 占主导地位的后代优于原先的模型 ， 先前的群体的成员将被删除 ， 原先的模型也将被新后代所代替 。 在进化过程的基础上 ， 新的 帕累托 最优解解决方案会定期的储存在独立的档案中 ， 而且我们在这些档案里已得到了结果 。 如果这些独立的数据（ SARC)被充满了 ， 启示法将删除那些数据已获得部分的 10%.我们选择首先删除最受控的个体 ， 然后其他的个体将连续不断的靠近彼此 。 MOSCA2 算法使用 2 段的算法结构，它的每个阶段都是一种稳定的进化算法。第一阶段是为了提高初始群体的工作质量的快速的 “ 准
49、备 ” 阶段。第二阶段是具有某些特殊操作的进化策略（ 更多详见 Borgulya 2005）。 MOSCA2b 的修改版本是一个运用了特别操作的组合问题。这个修改是一个截断的选择，这些修改是基于 EVL 方法。该算法使用了带有一个加权目标的局部搜索过程（ DEL 2001)，而且它不使用任何复合算子，作为额外的操作，该算法更新了误差修正模型（ ECM）和 EVL 的记忆方法。 3 实验结果 车辆路径问题的路线平衡问题的结果是一个类似与帕累托前沿的每个测试的结果都可以再图 1 中看到 。 通常我们是通过帕累托前沿的两点来描述这些问题 ： 车辆运行线路的最小值和最长的线路距离和最短的线路距离 的最小值 。 我们将实验问题的结果标注在表 1。 每个检测问题运行 5 次 ， 然后最优的结果在表中显示（同样的方法运用于其他的问题） 。 表格中给出问题的名字（ name） ，客户的数量（ n） ， 最好的距离（ mindist）及它的平衡（ bal） ， 最好的平衡（ bal）及它最好的距离（ mindist） ， 解决问题的平均值的近视值（ eff） 。 最后我们将给出成千上万里产生的最大值（
