Two memetic algorithms for heterogeneous fleet vehicle routing problems
Two memetic algorithms for heterogeneous fleet vehicle routing problems
复制标题
DOI：
10.1016/j.engappai.2008.10.006
复制
发表时间：
2009-09
期刊：
影响因子：
--
通讯作者：
C. Prins
中科院分区：
文献类型：
--
作者：
C. Prins
车辆路径问题（VRP）是供应链配送环节中的一个重要问题。从具有相同的有限容量的车辆的仓库，它包括确定一组最小总长度的车辆行程，以满足一组客户的需求。一般来说，使用的车辆数量是一个决策变量。异构车队VRP（HFVRP或HVRP）是具有若干车辆类型的自然概括，每种类型由容量、固定成本、每距离单位成本和可用车辆的数量来定义。车队混合问题（VFMP）是一个变种，每种类型的车辆数量不受限制。本文提出了两种模因算法（遗传算法与局部搜索杂交）能够解决VFMP和HVRP。他们是基于染色体编码为巨大的图尔斯，没有行程分隔符，并在一个最佳的评价程序，这些图尔斯分裂成可行的行程，并分配车辆给他们。第二种算法使用解空间中的距离度量来分散搜索。对标准VFMP和HFVRP算例的数值试验表明，这两种方法，特别是距离测度方法，与已发表的元分析方法相比，改进了几种著名的解决方案。
The vehicle routing problem (VRP) plays an important role in the distribution step of supply chains. From a depot with identical vehicles of limited capacity, it consists in determining a set of vehicle trips of minimum total length, to satisfy the demands of a set of customers. In general, the number of vehicles used is a decision variable. The heterogeneous fleet VRP (HFVRP or HVRP) is a natural generalization with several vehicle types, each type being defined by a capacity, a fixed cost, a cost per distance unit and a number of vehicles available. The vehicle fleet mix problem (VFMP) is a variant with an unlimited number of vehicles per type. This paper presents two memetic algorithms (genetic algorithms hybridized with a local search) able to solve both the VFMP and the HVRP. They are based on chromosomes encoded as giant tours, without trip delimiters, and on an optimal evaluation procedure which splits these tours into feasible trips and assigns vehicles to them. The second algorithm uses a distance measure in solution space to diversify the search. Numerical tests on standard VFMP and HFVRP instances show that the two methods, especially the one with distance measure, compete with published metaheuristics and improve several best-known solutions.