مسئله فروشنده دوره گرد (TSP) یکی از مشهورترین مسائل در علم ریاضیات کاربردی و بهینهسازی است. در این مسئله، یک فروشنده شهرها را طی میکند و باید به صورت بهینه کوتاهترین مسیر ممکن را بین شهرها طی کند. این مسئله به عنوان یک مسئله برنامهریزی ریاضی معروف است.
در مسئله TSP، شهرها به عنوان نقاط در صفحه فضایی مدل میشوند و فاصله بین هر دو شهر نیز مشخص است. هدف فروشنده دوره گرد، پیدا کردن کوتاهترین مسیری است که هر شهر را دقیقاً یک بار بازدید کند و در نهایت به شهری که از آن شروع کرده برگردد.
این مسئله به دلایل مختلفی اهمیت دارد، از جمله کاربردهای در زمینه مسائل حمل و نقل، مسائل توزیع، مسائل مسیریابی، مسائل برنامهریزی تولید و مسائل مسیریابی در شبکهها. همچنین، از لحاظ ریاضی، مسئله TSP یک مسئله NP-hard است، به این معنی که نیاز به الگوریتمهای پیچیدهتری برای حل آن داریم.
در طول سالها، محققان برای حل مسئله TSP الگوریتمهای مختلفی را توسعه دادهاند و تکنیکهای پیشرفتهتری برای بهبود عملکرد آنها بکار بردهاند. با این حال، مسئله TSP همچنان یک مسئله پیچیده است و برای مسائل بزرگ، بهینهسازی دقیق آن زمانبر خواهد بود و ممکن است به دلیل پیچیدگی محاسباتی باشد.
مجموعهها و پارامترهای مسئله به صورت زیر تعریف میشود:
: مجموعه تمامی نقاط.
: مجموعه نقاط برای بازدید و .
: مجموعه نقطه شروع ابتدایی (منزل شخص یا دیپات).
: میزان مسافت از گره به گره .
متغیرهای تصمیم مسئله به صورت زیر میباشند:
: متغیر باینری یا صفر و یک که نشان میدهد که گره به گره متصل شده است.
: متغیر کمکی صفر و یک برای نوشتن محدودیتهای حذف زیرتور.
مدل ریاضی مسئله فروشنده دوره گرد:
رابطه بالا، تابع هدف مسئله را نشان میدهد که به دنبال کمینه کردن مسافت طی شده است.
هنوز بررسیای ثبت نشده است.