دیتاست: مسئله فروشنده دوره گرد عمومی (GTSP):

تعریف مسئله فروشنده دوره گرد عمومی (GTSP):

منظور از مسئله فروشنده دوره گرد عمومی یا Generalized Traveling Salesman Problem تغییر یافته مسئله فروشنده دوره گرد متقارن است که در آن گره ها به خوشه هایی تقسیم می شوند و هر گره از خوشه دقیقاً یکبار در هر چرخه ملاقات می شود. کاربردهای متعدد آن عبارت است از : مسیریابی هواپیما، مرتب سازی فایل های کامپیوتر و تحویل پست. در واقع مسئله فروشنده دوره گرد عمومی یک نوع دیگری از مسئله فروشنده دوره گرد معروف می باشد که در آن همانند TSP، گراف شامل n گره می باشد که هزینه بین دو گره هم مشخص می باشد. همچنین مانند مسئله TSP ، مسئله فروشنده دوره گرد عمومی نیز یک مسئله NP-hard می باشد. تفاوت آن با TSPدر این است که ، بر خلاف TSP که به دنبال حداقل هزینه مسیر در گراف است به طوری که از هر گره دقیقاً یکبار عبور کند، مجموعه گره هایی که به m خوشه تقسیم شده اند راه حل بهینه برای بدست آوردن حداقل هزینه یک چرخه ای است که دقیقاً یک گره از هر خوشه را ملاقات کند. در شکل 1 نمونه ای از GTSP با سه خوشه آورده شده است که در آن برای بدست آوردن حداقل هزینه از هر خوشه دقیقاً یک گره انتخاب شده است. این نوع از GTSP مرسوم به مسئله فروشنده دوره گرد عمومی تساوی (E-GTSP) می باشد.  

شکل 1: مسئله فروشنده دوره گرد عمومی با سه خوشه

در شکل 2 یک مثال دیگر از مسئله فروشنده دوره گرد عمومی با سه خوشه با جزئیات بیشتر آورده شده است.

شکل 2: مسئله فروشنده دوره گرد عمومی با سه خوشه

نوع های دیگری از مسئله فروشنده دوره گرد عمومی وجود دارد که به جای انتخاب دقیقاً یک گره از حداقل یک گره در هر خوشه استفاده می کنند.

دیتاست های مسئله فروشنده دوره گرد عمومی:

در سال 1997 فیشیتی، سالازار گونزالس و توس یک فرآیند خوشه سازی ساده که می تواند برای ایجاد نمونه های GTSP استفاده شود معرفی کردند.

یکی از سایت هایی که در آن دیتاست های مسئله فروشنده دوره گرد عمومی وجود دارد http://www.cs.nott.ac.uk/~pszdk/gtsp.html می باشد که توسط دانیل کاراپتیان ایجاد و نگهداری می شود. برای نمونه دیتاست 3Burma14 در شکل 3 نشان داده شده است که در آن یک مسئله فروشنده دوره گرد عمومی با چهارده گره و سه خوشه می باشد و یک ماتریس 14*14 نشان دهنده فاصله گره ها از یکدیگر می باشد.

شکل 3: دیتاست 3Burma14

همچنین در فایل های جداگانه بهترین جواب هایی که تاکنون بدست آمده اند، گنجانده شده است. که در آن علاوه بر بهترین جواب مسیر راه حلی که به بهترین جواب منجر می شود نیز ذکر شده است. آخرین بروزرسانی این سایت در سال 2012 انجام شده است.

 [1]. John Silberholz ,Bruce L. Golden, “The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach”, Proceedings of the 10th INFORMS Computing Society Conference: 165-181.,2007.

 [2]. http://www.cs.nott.ac.uk/~pszdk/gtsp.html.