Hybrid genetic algorithm for the open capacitated arc routing problem
Hybrid genetic algorithm for the open capacitated arc routing problem
复制标题
DOI：
10.1016/j.cor.2017.09.020
复制
发表时间：
2018-02-01
影响因子：
4.6
通讯作者：
Usberti, Fabio Luiz
中科院分区：
文献类型：
--
作者：
Arakaki, Rafael Kendy;Usberti, Fabio Luiz
开放式容量约束弧路由问题（Open Capacitated Arc Routing Problem，OCARP）是一个NP-难的弧路由问题，在给定的无向图中，目标是找到满足所有正需求边（需求边）的最小成本路由集。路线受到与边缘需求相关的容量约束。OCARP与容量限制弧形路径问题（CARP）不同，因为OCARP不考虑站点，并且路径不受形成循环的约束。提出了一种可行化和局部搜索相结合的混合遗传算法。一组基准实例上进行的计算实验表明，所提出的混合遗传算法实现了几乎所有的情况下的最佳上界。(C)2017爱思唯尔有限公司版权所有
The Open Capacitated Arc Routing Problem (OCARP) is an NP-hard arc routing problem where, given an undirected graph, the objective is to find the least cost set of routes that services all edges with positive demand (required edges). The routes are subjected to capacity constraints in relation to edge demands. The OCARP differs from the Capacitated Arc Routing Problem (CARP) since OCARP does not consider a depot and routes are not constrained to form cycles. A hybrid genetic algorithm with feasibilization and local search procedures is proposed for the OCARP. Computational experiments conducted on a set of benchmark instances reveal that the proposed hybrid genetic algorithm achieved the best upper bounds for almost all instances. (C) 2017 Elsevier Ltd. All rights reserved.