Sayohatchi sotuvchi muammosini tushunish

Eng yaqin qo'shni usuli

Bu, ehtimol, eng oddiy TSP evristikasi. Ushbu usulning kaliti har doim eng yaqin manzilga tashrif buyurish va keyin barcha boshqa shaharlarga tashrif buyurilganda birinchi shaharga qaytishdir. Ushbu usul yordamida TSPni hal qilish uchun tasodifiy shaharni tanlang va keyin eng yaqin tashrif buyurilmagan shaharni qidiring va u erga boring. Barcha shaharlarga tashrif buyurganingizdan so'ng, siz birinchi shaharga qaytishingiz kerak.  

Sayohatchi sotuvchi muammosini hal qilish uchun marshrutni optimallashtirish algoritmlari qanday ishlaydi. Batafsil ma'lumot.

TSP uchun akademik yechimlar

Akademiklar ko'p yillar davomida sayohatchi sotuvchi muammosiga eng yaxshi yechim topishga harakat qilishdi, so'nggi yillarda quyidagi echimlar nashr etildi:

• 
  Nolinchi qo'shimcha usuli : Hindiston tadqiqotchilari tomonidan ishlab chiqilgan bu usul klassik simmetrik TSPni hal qiladi. 
  
• 
  Biogeografiyaga asoslangan optimallashtirish algoritmi : Bu usul optimallashtirish muammosini hal qilish uchun hayvonlarning migratsiya strategiyasi asosida ishlab chiqilgan. 
  
• 
  Meta-evristik ko'p qayta ishga tushirilgan takrorlangan mahalliy qidiruv (MRSILS): Ushbu tadqiqot tarafdorlari klasterlardan foydalanilganda meta-evristik MRSILS genetik algoritmlarga qaraganda samaraliroq ekanligini ta'kidladilar. 
  
• 
  Ko'p maqsadli evolyutsiya algoritmi : Bu usul NSGA-II asosida bir nechta TSP ni hal qilish uchun mo'ljallangan. 
  
• 
  Ko'p agentli tizim : Ushbu tizim N ta shaharning TSPni qat'iy manba bilan hal qilish uchun mo'ljallangan. 
  

Haqiqiy TSP ilovalari

Sayohatchi sotuvchi muammosini hal qilishning murakkabligiga qaramay, u hali ham barcha vertikallarda ilovalarni topadi. 

Masalan, TSP orqali topilgan samarali echimlar oxirgi milni yetkazib berishda qo'llaniladi. Oxirgi milga yetkazib berish deganda yuk tashish markazidan, masalan, ombor yoki ombordan yakuniy mijozning yetkazib berishni tanlashigacha olib o‘tish tushuniladi. Oxirgi milga yetkazib berish ta'minot zanjiridagi etakchi xarajat omilidir. Kompaniyalar odatda bozorda yaxshiroq raqobatlashish uchun xarajatlarning bir qismini o'z zimmalariga oladilar. Darhaqiqat, oxirgi milni yetkazib berish kompaniyaga o'rtacha 10,1 dollarga tushadi, ammo mijoz o'rtacha 8,08 dollar to'laydi. Aynan shuning uchun korxonalar oxirgi milni yetkazib berish narxini minimallashtirishga intilishadi. 

Oxirgi