A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem with Time Windows
A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem with Time Windows
复制标题
DOI：
10.1007/s10589-005-3070-3
复制
发表时间：
2003-11
影响因子：
2.2
通讯作者：
K. Tan;Yoong Han Chew;L. Lee
中科院分区：
文献类型：
--
作者：
K. Tan;Yoong Han Chew;L. Lee
带时间窗的车辆路径问题（Vehicle Routing Problem with Time Window，VRPTW）是将一组容量有限的车辆从一个中心仓库运送到一组地理上分散的具有已知需求和预定义时间窗的客户。该问题通过优化车辆路线来解决，以满足所有给定的约束条件并最小化行驶距离和车辆数量的目标。本文提出了一种混合多目标进化算法（HMOEA），它结合了各种算法的局部开发的进化搜索和Pareto的最优性的概念，解决多目标优化VRPTW。建议HMOEA具有专门的遗传算子和可变长度的染色体表示，以适应VRPTW中面向序列的优化。与现有的VRPTW方法通常将多个准则和约束聚合到一个折衷函数中不同，HMOEA同时优化了所有的布线约束和目标，从而在许多方面改进了布线解决方案，例如更低的布线成本，更宽的散射区域和更好的收敛跟踪。HMOEA应用于解决基准测试所罗门的56个VRPTW 100客户实例，产生了20个路由解决方案，比文献中发布的最佳解决方案更好或具有竞争力。
Vehicle routing problem with time windows (VRPTW) involves the routing of a set of vehicles with limited capacity from a central depot to a set of geographically dispersed customers with known demands and predefined time windows. The problem is solved by optimizing routes for the vehicles so as to meet all given constraints as well as to minimize the objectives of traveling distance and number of vehicles. This paper proposes a hybrid multiobjective evolutionary algorithm (HMOEA) that incorporates various heuristics for local exploitation in the evolutionary search and the concept of Pareto's optimality for solving multiobjective optimization in VRPTW. The proposed HMOEA is featured with specialized genetic operators and variable-length chromosome representation to accommodate the sequence-oriented optimization in VRPTW. Unlike existing VRPTW approaches that often aggregate multiple criteria and constraints into a compromise function, the proposed HMOEA optimizes all routing constraints and objectives simultaneously, which improves the routing solutions in many aspects, such as lower routing cost, wider scattering area and better convergence trace. The HMOEA is applied to solve the benchmark Solomon's 56 VRPTW 100-customer instances, which yields 20 routing solutions better than or competitive as compared to the best solutions published in literature.