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

در این مقاله مساله فروشنده دوره گرد تعمیم‌یافته (GTSP) به عنوان تعمیمی از مساله فروشنده دوره گرد (TSP) تشریح می‌گردد. این مساله نخستین بار در اواخر دهه شصت میلادی توسط Heny-LaborderEe، Saksema و Srivastava معرفی شد. در GTSP فروشنده دوره گرد بایستی ضمن عبور از یک تعداد از زیر مجموعه‌های از پیش تعریف شده از مشتریها، حداقل یک مشتری در هر زیر مجموعه را بازدید کند به طوری که مجموع هزینه سفر کمینه گردد. بنابراین، لازم است علاوه بر اتخاذ استراتژی که در آن زیر مجموعه‌ها باید بازید شده باشند، فروشنده بایستی مشتری یا مشتری‌هایی را انتخاب کند که در هر زیرمجموعه بازید شده باشند. در واقع در GTSP راسها درون دسته‌هایی قرار داده می‌شوند. این دسته‌ها که خوشه نامیده می‌شوند، می‌توانند با یکدگیر اشتراک نیز داشته باشند. لذا می‌توان گفت که هدف از حل یک GTSP یافتن مسیر بسته‌ای با حداقل هزینه است که از هر خوشه حداقل یکبار دیدار کند.