A simple and effective evolutionary algorithm for the vehicle routing problem
A simple and effective evolutionary algorithm for the vehicle routing problem
复制标题
DOI：
10.1016/s0305-0548(03)00158-8
复制
发表时间：
2004-10-01
影响因子：
4.6
通讯作者：
Prins, C
中科院分区：
文献类型：
--
作者：
Prins, C
车辆路径问题（VRP）是配送网络优化的核心问题。由于一些经典的75个节点的实例抵制最佳的精确解方法，大多数研究人员集中在元算法来解决现实生活中的问题。与带时间窗的车辆路径问题相比，没有一种遗传算法能够与为车辆路径问题设计的强大的禁忌搜索（TS）方法相媲美。本文提出了一种相对简单但有效的混合遗传算法来弥补这一差距。在平均求解成本方面，该算法在14个经典Christofides实例上的性能优于大多数已发表的TS算法，并成为Golden等人生成的20个大规模实例的最佳求解方法。令人惊讶的是，在文献中没有有效的遗传算法（GA）的车辆路径问题（VRP，主要的能力限制节点路由问题），相反的时间窗口或弧路由问题的节点路由问题。早期的尝试是基于染色体与行程定界符，并需要一个修复程序，以获得可行的儿童后，每次交叉。众所周知，这种程序会削弱父母向子女传递信息的遗传能力。本文提出了一种遗传算法没有行程定界符，杂交与局部搜索过程。在任何时候，染色体都可以转换为最佳的VRP解决方案（取决于染色体序列），这要归功于特殊的分裂过程。这种设计选择避免了维修程序，并允许使用经典的交叉，如OX。由此产生的算法是灵活的，相对简单，并且非常有效的应用时，从50到483客户的两套标准的基准测试实例。(C)2003爱思唯尔有限公司。保留所有权利。
The vehicle routing problem (VRP) plays a central role in the optimization of distribution networks. Since some classical instances with 75 nodes resist the best exact solution methods, most researchers concentrate on metaheuristics for solving real-life problems. Contrary to the VRP with time windows, no genetic algorithm (GA) can compete with the powerful tabu search (TS) methods designed for the VRP. This paper bridges the gap by presenting a relatively simple but effective hybrid GA. In terms of average solution cost, this algorithm outperforms most published TS heuristics on the 14 classical Christofides instances and becomes the best solution method for the 20 large-scale instances generated by Golden et al.Scope and purpose.The framework of this research is the development of effective metaheuristics for hard combinatorial optimization problems met in vehicle routing. It is surprising to notice in the literature the absence of effective genetic algorithms (GA) for the vehicle routing problem (VRP, the main capacitated node routing problem), contrary to node routing problems with time windows or arc routing problems. Earlier attempts were based on chromosomes with trip delimiters and needed a repair procedure to get feasible children after each crossover. Such procedures are known to weaken the genetic transmission of information from parents to children. This paper proposes a GA without trip delimiters, hybridized with a local search procedure. At any time, a chromosome can be converted into an optimal VRP solution (subject to chromosome sequence), thanks to a special splitting procedure. This design choice avoids repair procedures and enables the use of classical crossovers like OX. The resulting algorithm is flexible, relatively simple, and very effective when applied to two sets of standard benchmark instances ranging from 50 to 483 customers. (C) 2003 Elsevier Ltd. All rights reserved.