ارايه يك الگوريتم حل دقيق براي مساله جايابيp هاب ميانه با تخصيصي r-تايي

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

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

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.