A heuristic procedure for the Capacitated m-RingStar Problem
- سال انتشار: 1388
- محل انتشار: سومین کنفرانس بین المللی انجمن تحقیق در عملیات ایران
- کد COI اختصاصی: ICIORS03_390
- زبان مقاله: انگلیسی
- تعداد مشاهده: 354
نویسندگان
Majid SalariPaolo Toth University of Bologna
چکیده
In this paper we propose a heuristic method to solve the Capacitated m-Ring-Star Problem which has many practical applications in communication networks. The problem consists of finding in rings (simple cycles) visiting a central depot, a subset of customers and a subset of potential (Steiner) nodes, while customers not belonging to any ring must be allocated to a visited (customer or Steiner) node. Moreover, the rings must be node-disjoint and the number of customers allocated or visited in a ring cannot be greater than the capacity Q given as an input parameter. The objective is to minimize the total visiting and allocation costs. The problem is a generalization of the Traveling Salesman Problem, hence it is NP-hard. In the proposed heuristic, after the construction phase, a series of different local search procedures are applied iteratively. This method incorporates some random aspects by perturbing the current solution through a shaking procedure which is applied whenever the algorithm remains in a local optimum for a given number of iterations. Computational experiments on the benchmark instances of the literature show that the proposed heuristic is able to obtain, most of the optimalsolutions and can improve some of the best known results.کلیدواژه ها
Capacitated m-Ring-Star problem, Heuristic Algorithms, Networksمقالات مرتبط جدید
اطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.