مدل‌سازي رياضي و ارائۀ روش حل براي مسئلۀ هاب سلسله‌مراتبي با درنظرگرفتن مسيريابي در پايين‌ترين سطح

Mathematical Modeling of a Hierarchical Hub Routing Problem and Using the Benders Decomposition and Artificial Bee Colony Algorithms to Solve it

در مسئلۀ هاب سلسله‌مراتبي-مسيريابي مورد مطالعه، شبكه‌اي شامل سه سطح (مشتريان، هاب غيرمركزي و هاب مركزي) با هدف يافتن مكان بهينۀ استقرار هاب‌هاي مركزي و غيرمركزي، تخصيص مشتريان به هاب‌هاي غيرمركزي و همچنين پيداكردن مسير بهينه بين مشتريان و هاب غيرمركزي، درنظر گرفته شده است. از جمله كاربردهاي اين مدل مي‌توان به سيستم ارسال مراسلات پست، بانك‌ها، شبكه‌هاي دريافت و ارسال و... اشاره كرد. در اين مطالعه، يك مدل رياضي عدد صحيح مختلط ارائه شده و براي حل آن در اندازۀ متوسط، از الگوريتم تجزيۀ بندرز استفاده شده است. با توجه به NP-hard بودن مسئله، براي حل در اندازۀ بزرگ، از الگوريتم زنبورعسل مصنوعي استفاده شد. الگوريتم مصنوعي زنبورعسل، در مسائل پيوسته كاربرد دارد، اما در اين پژوهش، با انجام­دادن تغييراتي در الگوريتم، براي حل مدل گسستۀ پيشنهادي به­ كار گرفته شد. نتايج بيانگر عملكرد مناسب الگوريتم‌هاي تجزيۀ بندرز و زنبورعسل مصنوعي، به­ ترتيب براي حل مدل در اندازۀ متوسط (25 نقطه) و اندازۀ بزرگ (80 نقطه) است.

The hierarchical hub routing network consists of 3 levels (customer, the non-central and The hierarchical hub routing network consists of 3 levels (customer, the non-central and central hubs), which aims to find the optimum location of the central and non-central hubs, allocation of customers to established hubs to find the optimal path between customers and non-central hubs. Among the functions of this model are for post, banks, and sending and receiving services. In this study, a MIP mathematical model is proposed. The hierarchical hub routing is based on the traveling salesman problem. So it is an NP-hard problem too, and to solve this model in the medium and large sizes, Benders’ decomposition and artificial bee colony algorithms are proposed respectively. The proposed artificial bee colony algorithms has some changes while it has been developed for continuous type problems. Results showed good performance of Benders decomposition and artificial bee colony in order to solve the model in medium and large sizes. Also the numerical examples and sensitivity analysis confirms validity of the proposed mathematical model.