A filter-and-fan algorithm for the capacitated minimum spanning tree problem

作者：Rego Cesar^*; Mathew Frank

来源：Computers & Industrial Engineering, 2011, 60(2): 187-194.

DOI：10.1016/j.cie.2010.10.003

• Capacitated minimum spanning tree
• Compound neighborhoods
• Strategic oscillation
• Variable-depth neighborhood search
• Filter-and-fan

The capacitated minimum spanning tree (CMST) is a notoriously difficult problem in combinatorial optimization. Extensive investigation has been devoted to developing efficient algorithms to find optimal or near-optimal solutions. This paper proposes a new CMST heuristic algorithm that effectively combines the classical node-based and tree-based neighborhoods embodied in a filter-and-fan (F&F) approach, a local search procedure that generates compound moves in a tree search fashion. The overall algorithm is guided by a multi-level oscillation strategy used to trigger each type of neighborhood while allowing the search to cross feasibility boundaries. Computational results carried out on a standard set of 135 benchmark problems show that a simple F&F design competes effectively with prior CMST metaheuristics, rivaling the best methods, which are significantly more complex.

• 出版日期2011-3