Sayohatchi sotuvchi muammosini tushunish

milni etkazib berishda xarajatlarni minimallashtirish, asosan, avtomobilni yo'naltirish muammosidir (VRP). VRP TSP ning umumlashtirilgan versiyasi bo'lib, matematik optimallashtirishda eng ko'p o'rganiladigan muammolardan biridir. U etkazib berish xarajatlarini kamaytirish uchun marshrutlar yoki yo'llar to'plamini topish bilan shug'ullanadi. Muammoli domen bir qator omborlar, yuzlab etkazib berish joylari va bir nechta transport vositalarini o'z ichiga olishi mumkin. TSPda bo'lgani kabi, VRP ning eng yaxshi yechimini aniqlash NP-qiyin, shuning uchun kombinativ optimallashtirish yoki matematik dasturlash yordamida optimal tarzda echilishi mumkin bo'lgan muammolar soni cheklangan bo'lishi mumkin. Shunday qilib, tijorat hal qiluvchilar odatda evristikadan foydalanadilar - bu bizning miyamiz uchun yorliqlar kabi, tez va oson hal qilish uchun ko'plab matematika yoki hisob-kitoblarni yo'q qiladi - ular hal qilishlari kerak bo'lgan real dunyo VRPlarining chastotasi va hajmi tufayli. 

Haqiqiy TSP va VRP yechimlari

TSP va akademik echimlar esa VRP ta'minlash niyatidamiz bu NP-qattiq muammolarga optimal yechim real dunyo muammolarni hal bo'lsa, ularning ko'pchiligi so'nggi mil logistik vazifalarni hal etish uchun keladi, ayniqsa, amaliy emas.

Buning sababi, akademik hal qiluvchilar mukammallikka intilishadi va shuning uchun optimal echimlarni hisoblash uchun uzoq vaqt talab etiladi - soatlar, kunlar va ba'zan yillar. Agar etkazib berish biznesi kunlik marshrutlarni rejalashtirishi kerak bo'lsa, ularga bir necha daqiqa ichida marshrut yechimi kerak bo'ladi. Ularning biznesi etkazib berish marshrutini rejalashtirish yechimlariga bog'liq bo'lib, ular o'z haydovchilari va tovarlarini imkon qadar tezroq eshikdan olib chiqishlari mumkin.

Haqiqiy TSP va VRP yechimlari marshrutni optimallashtirish algoritmlaridan foydalanadi, ular qisqa vaqt ichida deyarli optimal echimlarni topadi, bu esa etkazib berish korxonalariga marshrutlarni tez va samarali rejalashtirish imkoniyatini beradi.

Muammo

Sayohatchi sotuvchi muammosi barcha davrlarning eng mashhur kompyuter fanlaridan biridir. Aslida, muammo kompyuter olimlari va matematiklar tomonidan shunchalik intensiv o'rganilganki, hatto TSP-dan ilhomlangan o'yinlar va TSP jahon rekordlari mavjud .

Ularni endi ko‘p ko‘rmayapmiz, biroq sotuvchilar bir paytlar uyma-uy yurib, changyutgichlardan tortib to ensiklopediyalargacha har xil tovarlarni sotishardi. Samarali bo'lish uchun sotuvchilar uydan uyga yoki shaharga eng qisqa yo'lni topishlari kerak edi. Ammo eng qisqa yo'lni topish oson emas - aslida bu kompyuter olimlari buni NP-qiyin muammo deb atashadi . Sayohatchi sotuvchi muammosini hal qilish sotuvchi tashrif buyurishi kerak bo'lgan uylar yoki shaharlar soni ko'p bo'ladi.

Bir necha uylar yoki shaharlar bo'lsa, sotuvchi (yoki boshqa birov) buni tushunishi mumkin. Ammo kattaroq muammolar uchun optimallashtirish usullari va algoritmlari oqilona izlash va optimalga yaqin echimlarni topish uchun kerak bo'ladi.

Yechimlar

Qalam va qog'ozdan tashqari TSP muammosini hal qilishning bir necha yo'li mavjud. Mapbox optimallashtirish API’sini 12 tagacha yo‘nalish nuqtasini taklif qiladi , Google Maps yo‘nalishlari API’si esa 23 tagacha yo‘nalish nuqtalarini vaqt oynalarisiz, aylanma