الگوریتم بهینه سازی جمعیت مورچگان برای گسترش مساله فروشنده دوره گرد

مساله فروشنده دوره گرد، TSP، مساله ای است که در آن فروشنده ای از یک گره دلخواه شروع به حرکت کرده و بعد از ملاقات کردن بقیه گره ها، در نهایت به آن گره باز می گردد. هدف در این مساله یافتن توری با هزینه مینیمم بین همه گره ها است. در این مساله هرکدام از گره ها، به غیر از گره اول که یکبار در شروع حرکت و یکبار بعد از ملاقات شدن تمامی گره های دیگر مورد ملاقات قرار می گیرد، دقیقا یک بار توسط فروشنده دوره گرد ملاقات می شود. این مساله علاوه بر اینکه کاربردهای عملی بسیار مهمی در مسایل دیگر مانند زمانبندی و مسیریابی دارد، از نوع مسایلNP- تام بوده و الگوریتم های بهینه سازی دقیق برای حل این مساله با ابعاد بزرگ ناکارآمد هستند.
در این مقاله در ابتدا گسترشی از این مساله، به نام مساله فروشنده دوره گرد باز، ارایه می شود که در آن فرض شده است گره شروع با گره پایانی یکسان نباشد. به عبارت دیگر فروشنده در این مساله تمامی گره ها را فقط یکبار مورد ملاقات قرار می دهد. سپس یک مدل برنامه ریزی ریاضی برای آن پیشنهاد و در نهایت روش الگوریتم مورچگان برای حل آن بکار گرفته می شود.