کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
476091 699414 2008 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Computing all efficient solutions of the biobjective minimum spanning tree problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Computing all efficient solutions of the biobjective minimum spanning tree problem
چکیده انگلیسی

A common way of computing all efficient (Pareto optimal) solutions for a biobjective combinatorial optimisation problem is to compute first the extreme efficient solutions and then the remaining, non-extreme solutions. The second phase, the computation of non-extreme solutions, can be based on a “k-best” algorithm for the single-objective version of the problem or on the branch-and-bound method. A k-best algorithm computes the k-best solutions in order of their objective values. We compare the performance of these two approaches applied to the biobjective minimum spanning tree problem. Our extensive computational experiments indicate the overwhelming superiority of the k-best approach. We propose heuristic enhancements to this approach which further improve its performance.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 35, Issue 1, January 2008, Pages 198–211
نویسندگان
, ,