Abstract
This study considers the application of a genetic algorithm (GA) to the basic vehicle routing problem (VRP), in which customers of known demand are supplied from a single depot. Vehicles are subject to a weight limit and, in some cases, to a limit on the distance travelled. Only one vehicle is allowed to supply each customer.
The best known results for benchmark VRPs have been obtained using tabu search or simulated annealing. GAs have seen widespread application to various combinatorial optimization problems, including certain types of vehicle routing problem, especially where time windows are included. However, they do not appear to have made a great impact so far on the VRP as described here. In this paper, computational results are given for the pure GA which is put forward. Further results are given using a hybrid of this GA with neighborhood search methods, showing that this approach is competitive with tabu search and simulated annealing in terms of solution time and quality.
Scope and purpose
The basic vehicle routing problem (VRP) consists of a number of customers, each requiring a specified weight of goods to be delivered. Vehicles dispatched from a single depot must deliver the goods required, then return to the depot. Each vehicle can carry a limited weight and may also be restricted in the total distance it can travel. Only one vehicle is allowed to visit each customer. The problem is to find a set of delivery routes satisfying these requirements and giving minimal total cost. In practice, this is often taken to be equivalent to minimizing the total distance travelled, or to minimizing the number of vehicles used and then minimizing total distance for this number of vehicles.
Most published research for the VRP has focused on the development of heuristics. Although the development of modern heuristics has led to considerable progress, the quest for improved performance continues. Genetic algorithms (GAs) have been used to tackle many combinatorial problems, including certain types of vehicle routing problem. However, it appears that GAs have not yet made a great impact on the VRP as described here. This paper describes a GA that we have developed for the VRP, showing that this approach can be competitive with other modern heuristic techniques in terms of solution time and quality.
Keywords：Routing; Heuristics; Genetic algorithms
1. Introduction
The basic vehicle routing problem (VRP) 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. Vehicle 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 many 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 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 extensive 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 been 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 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 modern metaheuristics, and several applications to VRPs incorporating time 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 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 GA 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 algorithm
The principles of GAs are well known. A population of solutions is maintained and a reproductive process 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 constraint violation. Analogous to biological processes, offspring with relatively good fitness levels are more likely to survive and reproduce, with the ex
剩余内容已隐藏，支付完成后下载完整资料
摘要
本研究考虑将遗传算法(GA)，应用到基本的车辆路径问题(VRP)中,已知的客户需求，通过一个专门的仓库来供应。汽车受到重量的限制，在某些情况下，还受到限制行驶距离的限制。一般来说，一种车辆只能被允许用来为某一个客户服务。
最著名的车辆路径问题优化基准就是使用禁忌搜索或模拟退火算法。遗传算法(GA)已经被广泛的应用到各种组合优化问题中，包括某些类型的车辆路径规划问题，特别是在限时派送中。不过，似乎在目前为止，它们还没有像这里所描述的那样，对车辆路径问题（VRP）有很大的影响。在本文中，提出了纯遗传算法(GA)给出的计算结果，并且进一步给出了混合使用遗传算法GA与邻域搜索方法得出的结果，研究表明这种方法与禁忌搜索和模拟退火算法相比，特别是在时间和质量的解决方案问题上，更加具有竞争力。
研究范围和目的
基本的车辆路径问题(VRP)由客户的数量、每一个指定重量的货物交付所组成。每一个从仓库中派遣的车辆，都必须按要求交货，然后返回到仓库中。每辆车都受到所携带重量的限制，也可能会受到它的行驶距离的限制。因此，只能一个车辆服务一个单独的客户。我们所要解决的问题是，要找到一组运送路线以满足客户的这些需求，并使得运输成本最低。在具体的实践中，通常的做法是总行驶距离最小化，或尽量减少使用汽车的数量，然后使这批车辆的行驶距离最小化。 大多数已经发表出来的关于车辆路径问题的研究都集中在启发法的发展上。虽然现代启发法的发展带来了相当大的进步，但是寻求改进绩效的努力仍在继续。遗传算法(GAs)已经被用来解决许多组合优化问题，包括某些类型的车辆路径问题。然而，它们还没有像这里所描述的那样，对车辆路径问题（VRP）有很大的影响。本文描述了一种遗传算法, 我们用来解决车辆路径问题，研究表明这种方法与禁忌搜索和模拟退火算法相比，特别是在时间和质量的解决方案问题上，更加具有竞争力。
关键词：路径;启发法；遗传算法
1 引言
基本的车辆路径问题(VRP)由客户的数量、每一个指定重量的货物交付所组成。每一个从仓库中派遣的车辆，都必须按要求交货。要求车辆运送路线必须开始和完成都是在仓库中，以便所有客户需求都得到满足以及每辆车服务一个客户。车辆的运输能力时限定的，每辆车都有其自身的最大行驶距离。在后一种情况下，运输距离限制可能与每个客户有关，因为车辆是按照客户的特定要求来安排的。因此，对一辆车来说，为许多客户服务，将会导致其在总的行驶距离上无法满足。可行的方案就是找出一组运送路线以满足客户的这些需求，并使得运输成本最低，通常的做法是总行驶距离最小化，或尽量减少使用汽车的数量，然后使这批车辆的行驶距离最小化。例如，拉波特给出了各种解决车辆路径问题的数学公式。
使用启发法来解决问题是比较现实的。在这方面的课题研究上，有很多的研究文献，包括拉波特和奥斯曼所给出的各种扩展性问题。
塔亚尔和罗查特运用禁忌搜索法，获得了基准车辆路径问题的最佳结果。不同的研究者使用禁忌搜索模拟退火法也获得了类似的结果。然而，雷诺观察到，使用启发法需要大量的计算时间和许多的参数设置。
最近，有一个新的算法可以用来这一组合优化难题，那就是蚁群优化法，这方面有很多成功的报道，包括在车辆路径问题中也得到了使用。两个最优启发法的改善了路线优化问题，这种方法也给了仅略次于禁忌搜索法的结果。当今，作为现代 共通启发式演算法之一，现代遗传算法(GAs)已经被广泛使用。现代遗传算法(GAs)的应用也被用于解决多种车辆路径组合优化以及校车路径规划问题中。混合动力车辆路径规划使用遗传算法(GAs)的报道也很多。然而,现代遗传算法(GAs)目前为止，在车辆路径问题VRP上表现出很大的影响。本研究的目的是提出一个概念上的，关于车辆路径问题的遗传算法，在计算时间和质量上，它可与其他现代启发式方法相竞争。我们也考虑将邻域搜索法整合到遗传算法中的混合启发法。给出了基准的问题的计算结果，除了一些使用禁忌搜索和模拟退火法得出的知名的结果，我们也给出了混合启发法得出的计算结果。
2 遗传算法的基础
遗传算法的原则是众所周知的。目前还是维持着原有的人口解决方案，繁殖过程允许父母从种群中选择解决方案。后代繁殖解决方案，都展示出了每个父母的一些特点。每种解决方案都与目标函数值联系在一起。在这种情况下，总行驶距离和任何违反约束的程度。类似于生物过程，有较好的健康水平的后代更有可能生存和繁殖，这样整个人口的健康水平才会得到提高和发展。李维斯给出了更多细节。
任何遗传算法的起点都是体现在每个解决方案上。通常，这将是一个字符串或染色体的形式。在个人的立场来看，每个染色体被称为基因。尽管二进制字符串已被许多遗传算法研究人员所青睐,不过，一些成功的案例使用非二进制表示。例如，楚和比斯利在他们的分配问题解决方法中，普遍使用非二进制表来表示，以最低总成本分配好工作。在他们的研究中，每个染色体由一串十进制数字,以索引的顺序，指定好代理和每个工作的分配数量所组成。
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[27945]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
