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

The Heterogeneous Fixed Fleet Capacitated Arc Routing Problem

作　　者：刘天堂[1] 江志斌[1] 耿娜[1] 刘冉[1] 刘树军[1] 

机构地区：[1]上海交通大学机械与动力工程学院,上海200240

出　　处：《上海交通大学学报》2012年第11期1759-1763,共5页Journal of Shanghai Jiaotong University

基　　金：国家自然科学基金资助项目(70872077);国家自然科学基金国际(地区)合作交流项目(70831160527)

摘　　要：研究了带有异质固定车队的能力约束弧路径问题(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.

关 键 词：能力约束弧路径问题 异质固定车队 启发式算法 加强的局域搜索 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]