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

本科毕业设计（论文） 中英文对照翻译 (此文档为word格式,下载后您可任意修改编辑!) 译文 基于遗传算法的车辆路径规划研究 克鲁尼·贝克 1 引言 基本的车辆路径问题(VRP)由客户的数量、每一个指定重量的货物交付所组成。每一个从仓库中派遣的车辆，都必须按要求交货。要求车辆运送路线必须开始和完成都是在仓库中，以便所有客户需求都得到满足以及每辆车服务一个客户。车辆的运输能力时限定的，每辆车都有其自身的最大行驶距离。在后一种情况下，运输距离限制可能与每个客户有关，因为车辆是按照客户的特定要求来安排的。因此，对一辆车来说，为许多客户服务，将会导致其在总的行驶距离上无法满足。可行的方案就是找出一组运送路线以满足客户的这些需求，并使得运输成本最低，通常的做法是总行驶距离最小化，或尽量减少使用汽车的数量，然后使这批车辆的行驶距???最小化。例如，拉波特给出了各种解决车辆路径问题的数学公式。 使用启发法来解决问题是比较现实的。在这方面的课题研究上，有很多的研究文献，包括拉波特和奥斯曼所给出的各种扩展性问题。 塔亚尔和罗查特运用禁忌搜索法，获得了基准车辆路径问题的最佳结果。不同的研究者使用禁忌搜索模拟退火法也获得了类似的结果。然而，雷诺观察到，使用启发法需要大量的计算时间和许多的参数设置。 最近，有一个新的算法可以用来这一组合优化难题，那就是蚁群优化法，这方面有很多成功的报道，包括在车辆路径问题中也得到了使用。两个最优启发法的改善了路线优化问题，这种方法也给了仅略次于禁忌搜索法的结果。 当今，作为现代 共通启发式演算法之一，现代遗传算法(GAs)已经被广泛使用。 现代遗传算法(GAs)的应用也被用于解决多种车辆路径组合优化以及校车路径规划问题中。混合动力车辆路径规划使用遗传算法(GAs)的报道也很多。然而,现代遗传算法(GAs)目前为止，在车辆路径问题VRP上表现出很大的影响。本研究的目的是提出一个概念上的，关于车辆路径问题的遗传算法，在计算时间和质量上，它可与其他现代启发式方法相竞争。我们也考虑将邻域搜索法整合到遗传算法中的混合启发法。给出了基准的问题的计算结果，除了一些使用禁忌搜索和模拟退火法得出的知名的结果，我们也给出了混合启发法得出的计算结果。 2 遗传算法的基础 遗传算法的原则是众所周知的。目前还是维持着原有的人口解决方案，繁殖过程允许父母从种群中选择解决方案。后代繁殖解决方案，都展示出了每个父母的一些特点。每种解决方案都与目标函数值联系在一起。在这种情况下，总行驶距离和任何违反约束的程度。类似于生物过程，有较好的健康水平的后代更有可能生存和繁殖，这样整个人口的健康水平才会得到提高和发展。李维斯给出了更多细节。 任何遗传算法的起点都是体现在每个解决方案上。通常，这将是一个字符串或染色体的形式。在个人的立场来看，每个染色体被称为基因。尽管二进制字符串已被许多遗传算法研究人员所青睐,不过，一些成功的案例使用非二进制表示。 例如，楚和比斯利在他们的分配问题解决方法中，普遍使用非二进制表来表示，以最低总成本分配好工作。在他们的研究中，每个染色体由一串十进制数字,以索引的顺序，指定好代理和每个工作的分配数量所组成。 车辆路径问题和遗传算法之间的结构相似性已经被指出吗，并且在过去成功地得到应用。例如：费舍尔和加库玛；贝克和莎士比。车辆路径问题VRP类似于楚和比斯利的遗传算法所表示和指定的差距，为每一个客户分配好车辆数量。 因此，给予n个客户m辆车，个体解决方案染色体的一个长度为n的字符串的形式，每个基因值的范围(1米)。不像一些表示已经使用了VRP所表示的每个车辆应遵循的确切的路线。然而，随着分配给客户的车辆，隐式地指定个别航线，包括总行驶距离和任何违反约束的行为。对于(TSP)问题，车辆分配的解决方案，需要从一个隐式的解决方案过渡到一个明确的解决方案，使适应性价值与每个成员联系在一起。 可采取两个步骤来保持尽可能多的结构。首先，客户被分为几类，并被连续编号，以便由相同的车辆为多个客户提供服务。问题在于，客户是随机分布的，他们是根据递增的顺序来排序。当顾客位于集群而不是随机的，他们是根据近邻分类法来解决TSP问题，在仓库访问所有客户。其次，我们试图对车辆进行编号，以便在同一地区，任何车辆都可以最大化地服务好客户。然后，我们将遗传算法应用到繁殖过程中，从而产生新的解决方案，可以与主线分享某些航线结构。 这些方面将在以下部分中进行更详细的描述。 3生成初始种群 对随机生成的初始种群、结构化的解决方案的初始种群，以及包含随机的和结构化的解决方案的混合种群进行实验。预期是，合理的结构性解决方案的初始种群将发展为高质量的解决方案，将得到一个相对较小数量的一代又一代的遗传算法。然而，一个可能的缺点是，与那些使用禁忌搜索法相比，这样的算法