ارائه یک الگوریتم حل دقیق برای مسأله جایابیp هاب میانه با تخصیصی r-تایی

نوع مقاله: مقاله پژوهشی

نویسندگان

دانشگاه کردستان

چکیده

مسائل جایابی هاب نقش مهمی در شبکه‌های حمل‌ونقل و سیستم‌های مخابراتی دارند. این مسائل در دهه‌های اخیر، بسیار مورد توجه بوده‌اند. در مسأله جایابی هاب میانه باید p گره در شبکه به‌عنوان تسهیلات هاب انتخاب شده و سایر گره‌ها به نحوی به نقاط انتخابی اختصاص داده شوند که هزینه‌های مسیریابی در شبکه کمینه شود. در تحقیق حاضر مسأله جایابی هاب میانه با تخصیص r-تایی مورد مطالعه قرار گرفته است. در این مسأله هر گره غیر هاب می‌تواند حداکثر به r عدد از  pهاب جایابی شده اختصاص یابد. هدف تحقیق کنونی مطالعه و طراحی یک الگوریتم حل دقیق بر مبنای رویکرد تجزیه بندرز برای مسأله ذکر شده است و بر اساس ساختار مسأله مورد مطالعه، راهکارهایی برای بهبود الگوریتم تجزیه بندرز کلاسیک ارائه شده است. نتایج محاسباتی الگوریتم دقیق ارائه شده با استفاده از مجموعه داده شبکه ترکیه و USA423 انجام شده است. آزمایشات محاسباتی کارایی الگوریتم پیشنهادی را تأیید می­کند.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

An Exact Solution Approach for the r-allocation p-Hub median problem

نویسندگان [English]

  • Alireza Eydi
  • Khaled Barzegar
University of Kurdistan
چکیده [English]

Hub location problems have important role in transportation networks and telecommunication systems. These problems have received much attention in the recent decades. In p-hub median problem, hub facilities are located in a network and non-hub nodes are allocated to hub nodes such that the total routing cost is minimized. In this paper, the r-Allocation p-Hub median problem has been studied. In this problem, each node can be allocated to at most r hubs. The purpose of this paper is to study and design of an exact solution approach based on benders decomposition to tackle the proposed problem. Based on problem structure, we proposed some strategies to accelerate the convergence of benders decomposition algorithm. The computational results of the proposed exact algorithm are presented using the Turkish network and USA423 data sets. Computational experiments confirm the effectiveness of the proposed method

کلیدواژه‌ها [English]

  • Hub median location
  • Multiple allocation
  • Exact solution algorithm
  • Benders decomposition