مدل‌بندي و حل مساله ماكزيمم پوشش p -هاب تك تخصيصي با پوشش تدريجي

Modeling and Solving Single-Allocation p-Hub Maximal Covering Location Problem with Gradual Coverage

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

P-hub maximal covering location problem is one of the most commonly used location- allocation problems. In this problem, the goal is to determine the best location for the hubs such that the covered demand is maximized by considering the predefined coverage radius. In classical hub problems, if the distance between the origin and destination is less than this radius, coverage is possible; otherwise the demand between the two points will not be covered. In this paper, the problem of p-hub maximal covering is investigated with gradual coverage. First, the concept of gradual coverage and its developed functions is examined and then, a new mathematical model is presented for the problem. Also, in order to calculate the appropriate upper bound for the problem, the Lagrangian relaxation method is used and a heuristic method and a genetic algorithm are used to solve it. Finally, the results of using these methods are compared with the results of GAMS software. This comparison shows that the new model presented for gradual coverage and the new covering parameter have more suitable results in comparison with the coverage model and function in the literature of the subject. Also, applying Lagrangian relaxation will provide a suitable upper bound for the problem. The heuristic method yields better computational results in less time, and the genetic algorithm provides more coverage with less computational time compared to solving examples with the GAMS software, especially for larger test instances.