基于遗传算法的车辆路径规划外文文献翻译

1、毕设附件外文文献翻译原文及译文译文基于遗传算法的车辆路径规划研究克鲁尼贝克1引言基本的车辆路径问题(VRP)由客户的数量、每一个指定重量的货物交付所组 成。每一个从仓库中派遣的车辆，都必须按要求交货。要求车辆运送路线必须开 始和完成都是在仓库中，以便所有客户需求都得到满足以及每辆车服务一个客 户。车辆的运输能力时限定的，每辆车都有其自身的最大行驶距离。在后一种情 况下，运输距离限制可能与每个客户有关，因为车辆是按照客户的特定要求来安 排的。因此，对一辆车来说，为许多客户服务，将会导致其在总的行驶距离上无 法满足。可行的方案就是找出一组运送路线以满足客户的这些需求，并使得运输 成本最低，通常的做

2、法是总行驶距离最小化，或尽量减少使用汽车的数量，然后 使这批车辆的行驶距离最小化。例如，拉波特给出了各种解决车辆路径问题的数 学公式。使用启发法来解决问题是比较现实的。在这方面的课题研究上，有很多的研 究文献，包括拉波特和奥斯曼所给出的各种扩展性问题。塔亚尔和罗查特运用禁忌搜索法，获得了基准车辆路径问题的最佳结果。不 同的研究者使用禁忌搜索模拟退火法也获得了类似的结果。然而，雷诺观察到， 使用启发法需要大量的计算时间和许多的参数设置。最近，有一个新的算法可以用来这一组合优化难题，那就是蚁群优化法，这方面 有很多成功的报道，包括在车辆路径问题中也得到了使用。两个最优启发法的改 善了路线优化问题，

3、这种方法也给了仅略次于禁忌搜索法的结果。当今，作为现代共通启发式演算法之一，现代遗传算法(GAs)已经被广泛使用。 现代遗传算法(GAs)的应用也被用于解决多种车辆路径组合优化以及校车路径规 划问题中。混合动力车辆路径规划使用遗传算法(GAs)的报道也很多。然而，现代 遗传算法(GAs)目前为止，在车辆路径问题VRP上表现出很大的影响。本研究的 目的是提出一个概念上的，关于车辆路径问题的遗传算法，在计算时间和质量上, 它可与其他现代启发式方法相竞争。我们也考虑将邻域搜索法整合到遗传算法中 的混合启发法。给出了基准的问题的计算结果，除了一些使用禁忌搜索和模拟退 火法得出的知名的结果，我们也给出了

4、混合启发法得出的计算结果。2遗传算法的基础遗传算法的原则是众所周知的。目前还是维持着原有的人口解决方案，繁殖 过程允许父母从种群中选择解决方案。后代繁殖解决方案，都展示出了每个父母 的一些特点。每种解决方案都与目标函数值联系在一起。在这种情况下，总行驶 距离和任何违反约束的程度。类似于生物过程，有较好的健康水平的后代更有可 能生存和繁殖，这样整个人口的健康水平才会得到提高和发展。李维斯给出了更 多细节。任何遗传算法的起点都是体现在每个解决方案上。通常，这将是一个字符串 或染色体的形式。在个人的立场来看，每个染色体被称为基因。尽管二进制字符 串已被许多遗传算法研究人员所青睐,不过，一些成功的案例

5、使用非二进制表示。 例如，楚和比斯利在他们的分配问题解决方法中，普遍使用非二进制表来表示， 以最低总成本分配好工作。在他们的研究中，每个染色体由一串十进制数字，以 索引的顺序，指定好代理和每个工作的分配数量所组成。车辆路径问题和遗传算法之间的结构相似性已经被指出吗，并且在过去成功 地得到应用。例如：费舍尔和加库玛；贝克和莎士比。车辆路径问题VRP类似 于楚和比斯利的遗传算法所表示和指定的差距，为每一个客户分配好车辆数量。 因此，给予n个客户m辆车，个体解决方案染色体的一个长度为n的字符串的 形式，每个基因值的范围(1米)。不像一些表示已经使用了 VRP所表示的每个车 辆应遵循的确切的路线。然而

6、，随着分配给客户的车辆，隐式地指定个别航线， 包括总行驶距离和任何违反约束的行为。对于(TSP)问题，车辆分配的解决方案, 需要从一个隐式的解决方案过渡到一个明确的解决方案，使适应性价值与每个成 员联系在一起。可采取两个步骤来保持尽可能多的结构。首先，客户被分为几类，并被连续 编号，以便由相同的车辆为多个客户提供服务。问题在于，客户是随机分布的， 他们是根据递增的顺序来排序。当顾客位于集群而不是随机的，他们是根据近邻 分类法来解决TSP问题，在仓库访问所有客户。其次，我们试图对车辆进行编 号，以便在同一地区，任何车辆都可以最大化地服务好客户。然后，我们将遗传 算法应用到繁殖过程中，从而产生新的

7、解决方案，可以与主线分享某些航线结构。 这些方面将在以下部分中进行更详细的描述。3生成初始种群对随机生成的初始种群、结构化的解决方案的初始种群，以及包含随机的和 结构化的解决方案的混合种群进行实验。预期是，合理的结构性解决方案的初始 种群将发展为高质量的解决方案，将得到一个相对较小数量的一代又一代的遗传 算法。然而，一个可能的缺点是，与那些使用禁忌搜索法相比，这样的算法解决 方案可能会缺乏种群的多样性。有两种方法可以被用来生成一个种群结构的解决方案。第一种方法是基于吉 勒特和米勒的扫描方法。在仓库周围的客户是随机分布的，正如之前已经描述的 那样，他们是根据极角递增的顺序排序。然后，生成每个群体

8、成员，随机选择一 个客户开始扫描程序，选择一个合适的运输车辆。按照他们被排好的的顺序，给 客户分配当前的汽车，直到达到约束条件为止。最后客户可能会或可能不会从车 辆继续扫描下一个汽车，根据下面的规则。对于仅有的车辆装载能力方面限制的问题，车辆的剩余载货容量在添加最后 一个客户的派送任务时，会将该客户的装载需求显示出来，并通过Rc来表示。 而对于装载能力和行驶距离限制方面的问题，车辆可以额外行驶的距离，在添加 最后一个客户的运输要求之前，会以Rd来表示。因此，Rc或Rd的值接近1的 时候，表示有轻微的违反限制约束，而如果值更小的话，Rc或Rd则表明已经较 严重的违反了限制约束。用于确定是否要满足

9、最后一个客户的装载需求的决策规 则，取决与路线是否紧张；最后，显示出是否要装载的在最终决定。对于路线不 紧张时，会尽量安排最后一个客户的装载需求，反之，将会根据具体情况来安排。当顾客是集群分布而不是随机分布的时候，要根据最近的客户分布来排序， 以最利于派件人方便派件的方案。扫描过程如上所述，运用过程同上，不需要对 流程做进一步地改变。这已被证明是一个更有效的方法，用来获得初始种群，以 合理的解决方案，解决集群客户的运输需求。第二种生成结构化的解决方案的方法是建立在费舍尔和加库玛提出的需求 分配方案基础之上的。这些学者提出了一种可按每个客户群体的位置自动生成车 辆安排方案方法。使用一个近似的总的

10、车辆行驶距离，来为这些客户群体分配好 车辆。解决车辆分配问题，并且保证车辆不违反负荷约束。然而，对遗传算法 GA而言，我们生成的一个初始种群运输的解决方案，其路线结构可能是相当粗 糙的，并不是很精确，以及可能会发生违反运输约束限制的情况。因此，我们稍 微精简了一下这个方法，我们使用随机分配法给每个客户安排两个最好的车辆运 输方案选择。原文The research of vehicle routing planning based on genetic algorithmClooney beck1. IntroductionThe basic vehicle routing problem (V

11、RP) consists of a large number of customers, each with a known demand level, which must be supplied from a single depot. Delivery routes for vehicles are required, starting and finishing at the depot, so that all customer demands are satisfied and each customer is visited by just one vehicle. Vehicl

12、e capacities are given and, frequently, there is a maximum distance that each vehicle can travel. In the latter case, a drop allowance may be associated with each customer, which is added to the total distance travelled by the vehicle to which the customer is assigned. Thus, a vehicle which visits m

13、any customers will not be able to travel as far as a vehicle that visits relatively few customers. Possible objectives may be to find a set of routes which minimizes the total distance travelled, or which minimises the number of vehicles required and the total distance travelled with this number of

14、vehicles. Various mathematical formulations of the VRP are given by, for example, Laporte .Problems of realistic size are tackled using heuristics. There have been many contributions to the subject, including various extensions to the basic problem described above. Laporte gives a survey, and an ext

15、ensive bibliography has been compiled by Laporte and Osman.The tabu search implementations of Taillard and Rochat and Taillard have obtained the best known results to benchmark VRPs. Various authors have reported similar results, obtained using tabu search, or simulated annealing. However, it has be

16、en observed by Renaud et al. that such heuristics require substantial computing times and several parameter settings.Ant colony optimization is another recent approach to difficult combinatorial problems with a number of successful applications reported, including the VRP. With a 2-optimal heuristic

17、 incorporated to improve individual routes produced by artificial ants, this approach also has given results which are only slightly inferior to those from tabu search.Genetic algorithms (GAs) have seen widespread use amongst modem metaheuristics, and several applications to VRPs incorporating time

18、windows have been reported. Applications of GAs have also been reported for the VRP with backhauls, for a multi-depot routing problem, and a school bus routing problem. A hybrid approach to vehicle routing using neural networks and GAs has also been reported. However, GAs do not appear to have made

19、a great impact so far on the basic VRP. The aim of this study is to put forward a conceptually straightforward GA for the basic VRP, which is competitive with other modern heuristics in terms of computing time and solution quality. A hybrid heuristic which incorporates neighborhood search into our G

20、A is also considered. Computational results are given for benchmark problems, alongside some of the well-known results obtained using tabu search and simulated annealing.2. Basis for a genetic algorithmThe principles of GAs are well known. A population of solutions is maintained and a reproductive p

21、rocess allows parent solutions to be selected from the population. Offspring solutions are produced which exhibit some of the characteristics of each parent. The fitness of each solution can be related to the objective function value, in this case the total distance travelled, and the level of any c

22、onstraint violation. Analogous to biological processes, offspring with relatively good fitness levels are more likely to survive and reproduce, with the expectation that fitness levels throughout the population will improve as it evolves. More details are given by Reeves, for example.The starting po

23、int for any GA is in the representation of each solution or population member. Typically, this will be in the form of a string or chromosome. Individual positions within each chromosome are referred to as genes. Although binary strings have been favored by many GA researchers, some successful implem

24、entations use non-binary representations. For example, Chu and Beasley use a non-binary representation in their approach to the generalized assignment problem (GAP), which requires jobs to be assigned to agents at minimum total cost, subject to resource limitations for each agent. In their represent

25、ation, each chromosome consists of a string of decimal numbers, in index order of the jobs, specifying the agent number to which each job is assigned.Structural similarities between the VRP and the GAP have been noted and successfully exploited in the past; for example, by Fisher and Jaikumar , and

26、by Baker and Sheasby. Our VRP representation is similar to Chu and Beasleys GAP representation and specifies, for each customer, the vehicle number to which it is assigned. Thus, given n customers and m vehicles, the chromosome for an individual solution has the form of a string of length n, with ea

27、ch gene value in the range l,m. Unlike some representations which have been used for the VRP, this does not specify explicitly the exact route which each vehicle should follow. However, with the assignment of customers to vehicles known, individual routes are implicitly specified, including the tota

28、l distance travelled and the levels of any constraint violations. The solution of a travelling salesman problem (TSP) is required for each vehicle in order to make the transition from an implicit to an explicit solution, enabling a fitness value to be associated with each population member.Two steps

29、 are taken to maintain as much structure as possible. Firstly, the customers are sorted and numbered so that consecutive customers are likely to be served by the same vehicle. For problems where the customers are randomly distributed around the depot, they are sorted according to increasing order of

30、 polar angle. When customers are located in clusters rather than randomly, they are sorted according to a nearest neighbor solution to the TSP, starting from the depot and visiting all customers. Secondly, we attempt to number the vehicles so that any vehicle, i, operates in approximately the same r

31、egion for all population members. Then, we apply the usual reproductive processes for GAs to the population, generating new solutions that share certain route structures with their parents. These aspects are described in more detail in the following sections. Since a similar approach has proved succ

32、essful with the GAP, we could reasonably expect such a GA to produce good solutions to the VRP.3. Generating the initial populationExperiments were carried out with the initial population generated randomly, with an initial population of structured solutions, and with a mixed population containing b

33、oth random and structured solutions. The expectation is that an initial population of reasonably structured solutions will evolve to high-quality solutions in a relatively small number of generations of the GA. However, a possible drawback is that such a population will lack the diversity needed to

34、obtain near-optimal solutions, comparable in quality to those obtained using tabu search.Two methods were used to generate a population of structured solutions. The first method is based on the sweep approach of Gillett and Miller. For problems where the customers are randomly distributed around the

35、 depot, they are sorted according to increasing order of polar angle, as already described. Then, to generate each population member, a customer is chosen at random to begin the sweep process for one of the vehicles. Customers are allocated to the current vehicle in the order in which they have been

36、 sorted, until a constraint violation occurs. The last customer may or may not be removed from the vehicle before continuing the sweep with the next vehicle, according to the following rules.For problems with only capacity constraints, the remaining capacity of the vehicle before adding the last cus

37、tomer is expressed as a proportion of the demand of this customer, and is represented by 7?c. For problems with both capacity and distance constraints, the additional distance which the vehicle could have travelled before adding the last customer is expressed as a proportion of the additional distan

38、ce required to include the last customer (including any drop allowance) and is represented by R&. Thus, a value of Rc or Rd close to 1 indicates a minor violation of the constraint, and a smaller value of Rc or indicates a more significant violation. The decision rule used to determine whether the l

39、ast customer is removed from the route takes into account the problem tightness, defined here as the total demand of the customers divided by the total capacity of the vehicles. The decision rule is then as shown in. For problems which are not tight, the last assignment is maintained only if the constraint violation is minor; for tight problems, a more significant constraint violati