带有异质固定车队的能力约束弧路径问题

The Heterogeneous Fixed Fleet Capacitated Arc Routing Problem

研究了带有异质固定车队的能力约束弧路径问题(CARP).为了在可接受时间里求得较理想的解,提出了基于Route-First,Cluster-Second思想的两阶段启发式算法,并使用局域搜索(LS)和加强的局域搜索(ELS)进行改善.基于标准CARP算例生成了HFFCARP测试数据,算法结果表明了LS和ELS的有效性,且ELS具有更好的效果.

The heterogeneous fixed fleet capaeitated arc routing problem （HFFCARP） is a generalization of the CARP, which is with several vehicle types, each type being defined by a capacity, a fixed cost and a cost per distance unit. In order to solve this new NP-hard problem in acceptable time, two-stage heuristics based on route-first, cluster-second were proposed and local search （I.S） and enhanced local search （ELS） were proposed to improve the results. The HFFCARP data generated from the CARP benchmark instances were tested and the results show that the heuristics improved by LS and EI.S are effective to solve the HFFCARP, and ELS improves the results much more significantly.