مدل‌سازی مساله پوشش یال‌ها و حل آن توسط الگوریتم ژنتیک

مساله پوشش یکی از پرکاربردترین مسائل در زمینه مکان‌یابی تسهیلات می‌باشد. بیشترین تحقیقات انجام گرفته تاکنون در زمینه پوشش، نقاط تقاضا را برروی گره‌های شبکه در‌نظر‌ گرفته‌اند. در این مقاله مسئله پوشش در‌حالتی‌‌که نقاط عرضه بروی گره‌ها و نقاط تقاضا یال‌های گراف باشند مورد مطالعه قرار گرفته است. در مرحله اول با در‌نظر‌گرفتن محدودیت ظرفیت نقاط عرضه، هدف یافتن کمترین نقاط عرضه است به‌نحوی‌که تمام یال‌ها به‌صورت‌کامل پوشش داده شوند. در مرحله بعد نقاط عرضه‌ی به‌دست آمده ثابت نگه‌داشته می‌شوند و هدف تخصیص یال‌ها به تسهیلات است به‌گونه‌ای که میزان مسافتی که توسط تسهیلات پوشش داده می‌شود تا‌حد‌امکان متعادل باشد. با مطالعه ادبیات موضوع مشخص شده است که مسئله پوشش یال‌ها با در‌نظر‌گرفتن این فرض که یک یال می‌تواند توسط بیش از یک گره پوشش داده شود، مورد بررسی قرار نگرفته است. همچنین ایده بخش دوم مسئله نیز کاملاً نو می‌باشد و مورد مشابهی در ادبیات یافت نشده است. با توجه به مطالب فوق و کاربرد بسیار زیاد مسئله در موضوع مکان‌یابی و لجستیک مطالعه برروی آن ضروری به‌نظر می‌رسد. در اینجا فرض می‌شود که بخشی از یک یال می‌تواند توسط یک گره و بخش دیگر آن توسط گره دیگر پوشش داده شود.