Edge Assembly Crossover for the Capacitated Vehicle Routing Problem
Edge Assembly Crossover for the Capacitated Vehicle Routing Problem
复制标题
DOI：
10.1007/978-3-540-71615-0_13
复制
发表时间：
2007-04
期刊：
影响因子：
--
通讯作者：
Y. Nagata
中科院分区：
文献类型：
--
作者：
Y. Nagata
摘要提出了一种求解有能力约束的车辆路径问题的进化算法。EA使用边缘组装交叉（EAX），最初是为旅行商问题（TSP）设计的。如果不考虑车辆容量的约束，EAX可以直接扩展到CVRP。为了解决约束违反问题，将2-optandInterchangeneighborhoods的罚函数方法引入到进化算法中.此外，局部搜索也被纳入EA。实验结果表明，该算法能有效地找到Christofidesbenchmark上的最优解.此外，我们的EA在合理的计算时间内找到了10个新的最佳解决方案。
AbstractWe propose an evolutionary algorithm (EA) that applies to the capacitated vehicle routing problem (CVRP). The EA uses edge assembly crossover (EAX) which was originally designed for the traveling salesman problem (TSP). EAX can be straightforwardly extended to the CVRP if the constraint of the vehicle capacity is not considered. To address the constraint violation, the penalty function method with2-optandInterchangeneighborhoods is incorporated into the EA. Moreover, a local search is also incorporated into the EA. The experimental results demonstrate that the proposed EA can effectively find the best-known solutions onChristofidesbenchmark. Moreover, our EA found ten new best solutions forGoldeninstances in a reasonable computation time.