Arc-Guided Evolutionary Algorithm for the Vehicle Routing Problem With Time Windows
Arc-Guided Evolutionary Algorithm for the Vehicle Routing Problem With Time Windows
复制标题
DOI：
10.1109/tevc.2008.2011740
复制
发表时间：
2009-06
影响因子：
14.3
通讯作者：
Panagiotis P. Repoussis;C. Tarantilis;G. Ioannou
中科院分区：
文献类型：
--
作者：
Panagiotis P. Repoussis;C. Tarantilis;G. Ioannou
本文提出了一种弧引导的进化算法来求解带时间窗的车辆路径问题，这是一个著名的组合优化问题，解决了一组客户的服务，在固定的时间间隔内使用同质车队的能力有限的车辆。其目标是尽量减少车队规模以下的最短距离的路线。所提出的方法发展的基础上的（mu + lambda）的进化策略的人口的mu个人，在每一代，一个新的中间人口的lambda个人的生成，使用离散弧为基础的表示相结合的二进制向量的战略参数。每个后代都是通过从亲本个体中提取的弧的突变产生的。弧的选择由策略参数决定，并且基于它们的出现频率和种群的多样性。多亲重组算子使策略参数自适应，而每个后代通过新的基于记忆的轨迹局部搜索算法进一步改善。对于幸存者的选择，遵循确定性方案。著名的大规模基准数据集的文献上的实验结果表明，所提出的方法的竞争力。
This paper presents an arc-guided evolutionary algorithm for solving the vehicle routing problem with time windows, which is a well-known combinatorial optimization problem that addresses the service of a set of customers using a homogeneous fleet of capacitated vehicles within fixed time intervals. The objective is to minimize the fleet size following routes of minimum distance. The proposed method evolves a population of mu individuals on the basis of an (mu + lambda) evolution strategy; at each generation, a new intermediate population of lambda individuals is generated, using a discrete arc-based representation combined with a binary vector of strategy parameters. Each offspring is produced via mutation out of arcs extracted from parent individuals. The selection of arcs is dictated by the strategy parameters and is based on their frequency of appearance and the diversity of the population. A multiparent recombination operator enables the self-adaptation of the strategy parameters, while each offspring is further improved via novel memory-based trajectory local search algorithms. For the selection of survivors, a deterministic scheme is followed. Experimental results on well-known large-scale benchmark datasets of the literature demonstrate the competitiveness of the proposed method.