کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
474927 699171 2006 29 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Savings based ant colony optimization for the capacitated minimum spanning tree problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Savings based ant colony optimization for the capacitated minimum spanning tree problem
چکیده انگلیسی

The problem of connecting a set of client nodes with known demands to a root node through a minimum cost tree network, subject to capacity constraints on all links is known as the capacitated minimum spanning tree (CMST) problem. As the problem is NP-hard, we propose a hybrid ant colony optimization (ACO) algorithm to tackle it heuristically. The algorithm exploits two important problem characteristics: (i) the CMST problem is closely related to the capacitated vehicle routing problem (CVRP), and (ii) given a clustering of client nodes that satisfies capacity constraints, the solution is to find a MST for each cluster, which can be done exactly in polynomial time. Our ACO exploits these two characteristics of the CMST by a solution construction originally developed for the CVRP. Given the CVRP solution, we then apply an implementation of Prim's algorithm to each cluster to obtain a feasible CMST solution. Results from a comprehensive computational study indicate the efficiency and effectiveness of the proposed approach.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 33, Issue 6, June 2006, Pages 1794–1822
نویسندگان
, ,