毕设附件外文文献翻译原文及译文.doc

毕设附件外文文献翻译原文及译文译文基于遗传算法的车辆路径规划研究克鲁尼•贝克1引言基木的车辆路径问题(VRP)由客户的数量、每一个指定重量的货物交付所组 成每一个从仓库中派遣的车辆，都必须按要求交货要求车辆运送路线必须开 始和完成都是在仓库中，以便所有客户需求都得到满足以及毎辆车服务一•个客 户车辆的运输能力时限定的，每辆车都有其自身的最大行驶距离在后—•种情 况下，运输距离限制可能与每个客户有关，因为车辆是按照客户的特定要求來安 排的因此 对一辆车来说，为许多客户服务，将会导致其在总的行驶距离上无 法满足可行的方案就是找出一组运送路线以满足客户的这些需求，并使得运输 成本最低，通常的做法是总行驶距离最小化，或尽量减少使用汽车的数量，然后 使这批车辆的行驶距离最小化例如，拉波特给出了各种解决车辆路径问题的数 学公式使用启发法来解决问题是比较现实的在这方面的课题研究上，有很多的研 究文献，包括拉波特和奥斯曼所给出的各种扩展性问题塔亚尔和罗查特运用禁忌搜索法，获得了基准车辆路径问题的最佳结果不 同的研究者使用禁忌搜索模拟退火法也获得了类似的结果然而，雷诺观察到， 使用启发法需要大量的计算吋间和许多的参数设置。

最近，有一个新的算法可以用来这一组合优化难题，那就是蚁群优化法，这方面 有很多成功的报道，包括在车辆路径问题中也得到了使用两个最优启发法的改 善了路线优化问题，这种方法也给了仅略次于禁忌搜索法的结果当今，作为现代共通启发式演算法乙一，现代遗传算法(GAs)已经被广泛使用 现代遗传算法(GAs)的应用也被用于解决多种车辆路径组合优化以及校车路径规 划问题中混合动力车辆路径规划使用遗传算法(GAs)的报道也很多然而，现代 遗传算法(GAs) R前为止，在车辆路径问题VRP上表现出很大的影响木研究的 H的是提出一个概念上的，关于车辆路径问题的遗传算法，在计算吋间和质量上, 它可与其他现代启发式方法相竞争我们也考虑将邻域搜索法整合到遗传算法中 的混合启发法给出了基准的问题的计算结果，除了一•些使用禁忌搜索和模拟退 火法得出的知名的结果，我们也给出了混合启发法得出的计算结果2遗传算法的基础遗传算法的原则是众所周知的H前还是维持着原有的人口解决方案，繁殖 过程允许父母从种群中选择解决方案后代繁殖解决方案，都展示出了每个父母 的一些特点每种解决方案都与ri标函数值联系在一•起在这种情况下，总行驶 距离和任何违反约朿的程度。

类似于牛物过程，有较好的健康水平的后代更有可 能牛存和繁殖，这样整个人口的健康水平才会得到提高和发展李维斯给出了更 多细节任何遗传算法的起点都是体现在每个解决方案上通常，这将是一个字符串 或染色体的形式在个人的立场來看，每个染色体被称为基因尽管二进制字符 串已被许多遗传算法研究人员所青睐,不过，一些成功的案例使用非二进制表示 例如，楚和比斯利在他们的分配问题解决方法中，普遍使用非二进制表来表示， 以最低总成本分配好工作在他们的研究中，每个染色体由一串十进制数字，以 索引的顺序，指定好代理和每个工作的分配数量所组成车辆路径问题和遗传算法之间的结构相似性已经被指出吗，并且在过去成功 地得到应用例如：费舍尔和加库玛；贝克和莎士比车辆路径问题VRP类似 于楚和比斯利的遗传算法所表示和指定的差距，为每一个客户分配好车辆数量 因此，给予n个客户m辆车，个体解决方案染色休的一个长度为n的字符申的 形式，每个基因值的范围(1米)不像一些表示已经使用了 VRP所表示的每个车 辆应遵循的确切的路线然而，随着分配给客户的车辆，隐式地指定个别航线， 包括总行驶距离和任何违反约束的行为对于(TSP)问题，车辆分配的解决方案, 需要从-个隐式的解决方案过渡到一个明确的解决方案，使适应性价值与每个成 员联系在一起。

可采取两个步骤来保持尽可能多的结构首先，客户被分为几类，并被连续 编号，以便由相同的车辆为多个客户提供服务问题在于，客户是随机分布的， 他们是根据递增的顺序来排序当顾客位于集群而不是随机的，他们是根据近邻 分类法来解决TSP问题，在仓库访问所有客户其次，我们试图对车辆进行编 号，以便在同一地区，任何车辆都可以最大化地服务好客户然后，我们将遗传 算法应用到繁殖过程中，从而产牛新的解决方案，可以与主线分亨某些航线结构 这些方面将在以下部分中进行更详细的描述3生成初始种群对随机牛成的初始种群、结构化的解决方案的初始种群，以及包含随机的和 结构化的解决方案的混合种群进行实验预期是，合理的结构性解决方案的初始 种群将发展为高质量的解决方案，将得到一个相对较小数量的-•代乂-•代的遗传 算法然而，一个可能的缺点是，与那些使用禁忌搜索法相比，这样的算法解决 方案可能会缺乏种群的多样性有两种方法可以被用来牛成一个种群结构的解决方案第一种方法是基于吉 勒特和米勒的扫描方法在仓库周囤的客户是随机分如的，正如之前已经描述的 那样，他们是根据极角递增的顺序排序然后，牛成每个群体成员，随机选择一 个客户开始扫描程序，选择一•个合适的运输车辆。

按照他们被排好的的顺序，给 客户分配出前的汽车，直到达到约束条件为止最后客户可能会或可能不会从车 辆继续扫描下一个汽车，根据下而的规则对于仅有的车辆装载能力方面限制的问题，车辆的剩余载货容量在添加最后 一个客户的派送任务吋，会将该客户的装载需求显示出来，并通过Rc来表示 而对于装载能力和行驶距离限制方面的问题，车辆可以额外行驶的距离，在添加 最后一个客户的运输要求之前，会以Rd来表示因此，Rc或Rd的值接近1的 时候，表示有轻微的违反限制约束，而如果值更小的话，Rc或Rd则表明已经较 严重的违反了限制约束用于确定是否要满足最后一个客户的装载需求的决策规 则，取决与路线是否紧张；最后，显示出是否要装载的在最终决定对于路线不 紧张吋，会尽量安排最后一个客户的装载需求，反之，将会根据具体情况来安排当顾客是集群分布而不是随机分布的时候，要根据最近的客户分布来排序, 以最利于派件人方便派件的方案扫描过程如丄所述，运用过程同丄，不需要对 流程做进一步地改变这已被证明是一个更有效的方法，用來获得初始种群，以 合理的解决方案，解决集群客户的运输需求第二种牛成结构化的解决方案的方法是建立在费舍尔和加库玛提出的需求 分配方案基础Z上的。

这些学者提出了一种可按每个客户群体的位置动牛成车 辆安排方案方法使用一个近似的总的车辆行驶距离，來为这些客户群体分配好 车辆解决车辆分配问题，并且保证车辆不违反负荷约束然而，对遗传算法 GA而言，我们牛成的一个初始种群运输的解决方案，其路线结构可能是相当粗 糙的，并不是很精确，以及可能会发牛违反运输约朿限制的情况因此，我们稍 微精简了一下这个方法，我们使用随机分配法给每个客户安排两个最好的车辆运 输方案选择原文The research of vehicle routing planning based on genetic algorithmClooney beck1. IntroductionThe 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 Tai Hard 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 in。