[صفحه اصلی ]   [Archive]  
:: صفحه اصلي :: درباره نشريه :: آخرين شماره :: تمام شماره‌ها :: جستجو :: ثبت نام :: ارسال مقاله :: تماس با ما ::
:: جلد 6، شماره 1 - ( 12-1393 ) ::
جلد 6 شماره 1 صفحات 65-78 برگشت به فهرست نسخه ها
A Metaheuristic Algorithm for the Minimum Routing Cost Spanning Tree Problem
آقای ستار ستاری، دیده ور
دانشگاه صنعتی امیرکبیر ، s.sattari@aut.ac.ir
چکیده:   (5222 مشاهده)

The routing cost of a spanning tree in a weighted and connected graph is defined as the total length of paths between all pairs of vertices. The objective of the minimum routing cost spanning tree problem is to find a spanning tree such that its routing cost is minimum. This is an NP-Hard problem that we present a GRASP with path-relinking metaheuristic algorithm for it. GRASP is a multi-start algorithm that in each iteration constructs a randomized greedy solution and applies local search to it. Path-relinking stores elite solutions and to find better solutions explores the paths between different solutions. Experimental results show the performance of our algorithm on many benchmark problems compared to the other algorithms.

متن کامل [PDF 488 kb]   (3170 دریافت)    
نوع مطالعه: پژوهشی | موضوع مقاله: Discrete Optimization
دریافت: 1396/1/7 | پذیرش: 1396/1/7 | انتشار: 1396/1/7
ارسال پیام به نویسنده مسئول

ارسال نظر درباره این مقاله
نام کاربری یا پست الکترونیک شما:

CAPTCHA


XML   English Abstract   Print



جلد 6، شماره 1 - ( 12-1393 ) برگشت به فهرست نسخه ها
مجله انجمن ایرانی تحقیق در عملیات Iranian Journal of Operations Research
Persian site map - English site map - Created in 0.05 seconds with 30 queries by YEKTAWEB 4241