دانلود مقاله ترجمه شده جستجوی محلی مبتنی بر برنامه نویسی عدد صحیح برای مسئله پوشش دهی فروشنده

چکیده

یک نسخه تعمیم ­یافته از مساله فروشنده دوره ­گرد به نام مساله پوشش ­دهی فروشنده را در نظر گرفتیم. در این مساله، مجموعه ­ای از رئوس را داریم که هر راس i می ­تواند مجموعه­ ای از رئوس را در فاصله از قبل تعیین شده خود ri پوشش دهد. هدف ایجاد یک دور هامیلتونی حداقل طول بر مجموعه ­ای از رئوس است که در آن رئوسی که در تور قرار نگرفته ­اند باید در فاصله پوشش ­دهی حداقل یک راس که در تور قرار دارد باشند. مقاله یک روش ابتکاری مبتنی بر برنامه ­ریزی خطی صحیح را به کار می ­گیرد که مزایای تکنیک­ های برنامه ­ریزی خطی صحیح و جست و جوی اکتشافی را برای بهبود کیفیت راه ­حل­ ها به کار می ­گیرد. تست­ های محاسباتی گسترده بر روی موارد معیار استاندارد و بر روی مجموعه جدیدی از مجموعه­ های داده ­ای بزرگ کارایی رویکرد مورد استفاده را نشان می­ دهد.

1-مقدمه

مسئله پوشش فروشنده(CSP)  یک تعمیم از مسئله فروشنده دوره ­گرد(TSP)  است که در آن فرض مشاهده تمام رئوس توسط تور معتبر نمی ­باشد. در اینجا، ما مجموعه ­ای از رئوس داریم در حالی که هر راس i می­ تواند یک زیر مجموعه از رئوس را در فاصله پوشش از پیش تعیین شده خود، پوشش دهد. هدف از اینCSP  ساخت یک دور هامیلتونی حداقل طول در یک زیر مجموعه از رئوس که در آن رئوسی که توسط تور مشاهده نشده ­اند باید در فاصله پوشش حداقل یک راس مشاهده شده قرار گیرند...