We consider a generalized version of the well known Traveling Salesman Problem calledCovering Salesman problem. In this problem, we are given a set of vertices while each vertex i can cover a subset of vertices within its predetermined covering distance ri. The goal is to construct a minimum length Hamiltonian cycle over a subset of vertices in which those vertices not visited on the tour has to be within the covering distance of at least one vertex visited on the tour. The paper proposes an Integer Linear Programming based heuristic method which takes advantage of Integer Linear Programming techniques and heuristic search to improve the quality of the solutions. Extensive computational tests on the standard benchmark instances and on a new set of large sized datasets show the effectiveness of the proposed approach

چکیده

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

1-مقدمه

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