مسئله فروشنده دوره‌گرد — بررسی تخصصی، مدل ریاضی و روش‌های حل

در این مقاله از سری مقالات مجله پی‌اِستور به بررسی تخصصی مسئله فروشنده دوره‌گرد خواهیم پرداخت و از اهمیت و کاربرد این مسئله در بهینه‌سازی تا روش‌های حل آن و ارائه روش‌های مبتنی بر الگوریتم‌های متاهیوریستیک سخن خواهیم گفت.

مسئله فروشنده دوره‌گرد چیست؟

مسئله فروشنده دوره‌گرد «Traveling Salesman Problem» یا TSP یکی از مشهورترین مسائل بهینه‌سازی ترکیبیاتی در علوم کامپیوتر و ریاضی است. در این مسئله، فروشنده‌ای فرض می‌شود که باید تعدادی شهر را بازدید کند و هدف آن است که کوتاه‌ترین مسیر ممکن را برای بازدید از همه شهرها و بازگشت به شهر اولیه پیدا کند. این مسئله به دلیل ساختار چالش‌برانگیز خود، کاربردهای گسترده‌ای در علوم کامپیوتر، حمل و نقل و مهندسی دارد.

تاریخچه پیدایش مسئله فروشنده دوره‌گرد

مسئله فروشنده دوره‌گرد مسئله‌ای مشهور است ولی ریشه پیدایش اولیه مسئله فروشنده دوره گرد واضح و مشخص نیست. از ۱۸۳۲ در کتاب های خطی، این مسئله را با عنوان تورهای نمونه در آلمان و سوئیس برای فروشندگان دوره گرد مطرح کرده‌اند و در آن‌ها از دیدگاه ریاضی به این مسئله پرداخته نشده است. اولین بار مسئله فروشنده دوره گرد به صورت یک مسئله ریاضی توسط ریاضیدان ایرلندی ویلیام همیلتون W.R. Hamilton و ریاضیدان بریتانیایی توماس کرکمن Thomas Penyngton Kirkman تدوین شد.

به نظر می‌رسد ایده اصلی طراحی مسئله فروشنده دوره گرد از بازی نمادین همیلتون icosian نشأت گرفته شده است. هدف بازی پیدا کردن یک چرخه همیلتونی در امتداد لبه‌های یک ۱۲ وجهی است به طوری که از هر راس یک بار بازدید می‌شود و نقطه پایان آن همان نقطه شروع است. شکل کامل تر مسئله TSP برای اولین بار توسط ریاضیدانان در دهه ۱۹۳۰ در دانشگاه وین و هاروارد مورد مطالعه قرار گرفته است، به ویژه توسط کارل منگر Karl Menger که طرح مسئله فروشنده دوره گرد را مشخص کرد. کارل برای حل مشکل پستچی‌ها برای توزیع نامه‌ها فکر کرد و این مسئله را به شکل ریاضی و تعداد جایگشت‌های مسئله و حل آن مطرح کرد.

در دهه ۱۹۳۰ مریل فلوید Merrill M. Flood که به دنبال حل مشکل مسیریابی اتوبوس مدرسه بود، حل مسئله فروشنده دوره گرد مورد توجه اش قرار گرفت. هسلر ویتنی Hassler Whitney در دانشگاه پرینستون علاقه‌ای به این مسئله ایجاد کرد، که او آن را مسئله ۴۸ ایالت یا 48states problem نامید. اولین نشریه‌ای که از عبارت مسئله فروشنده دوره گرد استفاده کرد گزارش RAND Corporation 1949 توسط جولیا رابینسون بود. در دهه‌های ۱۹۵۰ و ۱۹۶۰، این مسئله پس از آن‌که شرکت RAND در سانتا مونیکا برای مراحل حل مسئله جوایزی را اهدا کرد، در محافل علمی اروپا و ایالات متحده رواج بیشتری یافت.

در سال ۱۹۵۹، جیلیان بردوود، J.H. هالتون و جان هامرسلی مقاله‌ای تحت عنوان “کوتاه‌ترین مسیر از طریق بسیاری از نقاط” در مجله انجمن فلسفی کمبریج منتشر کردند. در دهه‌های بعد، این مسئله توسط بسیاری از محققان ریاضی، علوم کامپیوتر، شیمی، فیزیک و سایر علوم مورد مطالعه قرار گرفت. با این حال، در دهه ۱۹۶۰، رویکرد جدیدی ایجاد شد، که به جای جستجوی راه حل‌های بهینه، راه حلی را تولید می‌کرد که طول آن به طور اثبات شده با مضرب طول مطلوب محدود می‌شد و با این کار مرزهای پایین‌تری برای مسئله ایجاد می‌کرد. سپس از این محدوده‌های پایینی با رویکردهای شاخه و حد استفاده می‌شد.

در سال ۱۹۷۶، کریستوفیدس و سردیوکوف مستقل از یکدیگر پیشرفت بزرگی در این راستا انجام دادند. الگوریتم کریستوفیدس-سردیوکوف راه حلی را ارائه می‌داد که در بدترین حالت حداکثر ۱.۵ برابر طولانی‌تر از راه حل بهینه است. از آن‌جا که این الگوریتم ساده و سریع بود، بسیاری امیدوار بودند که جای خود را به روش حل تقریباً مطلوب بدهد. با این حال، این امید به بهبود، فوراً محقق نشد و کریستوفیدس-سردیوکوف تا سال ۲۰۱۱، زمانی که الگوریتم تقریبی (بسیار) کمی بهبود یافته بود، بهترین روش برای بدترین سناریو بود.

اهمیت مسئله در بهینه‌سازی و کاربردهای آن

حل بهینه این مسئله می‌تواند کاربردهای بسیاری در صنایع مختلف داشته باشد، از جمله:

• برنامه‌ریزی مسیرهای حمل و نقل: در لجستیک و حمل و نقل شهری، برای بهینه‌سازی مسیرهای تحویل کالا
• طراحی مدارهای الکترونیکی: برای بهینه‌سازی مسیرهای مدار در صنعت الکترونیک
• بیوانفورماتیک: در مطالعات ژنتیکی و بررسی توالی‌های ژنوم

با وجود کاربردهای وسیع، مسئله فروشنده دوره‌گرد یکی از مسائل NP-کامل است که حل دقیق آن به دلیل رشد نمایی پیچیدگی، برای تعداد زیاد شهرها غیرممکن یا بسیار دشوار می‌شود. از این رو، تلاش‌های زیادی برای یافتن راه‌حل‌های تقریبی و فراابتکاری برای این مسئله صورت گرفته است.

پاورپوینت مسئله فروشنده دوره گرد — Traveling Salesman Problem

کلیک کنید

تشریح مسئله فروشنده دوره گرد به عنوان مسئله گراف

مسئله TSP را می‌توان به عنوان یک گراف وزن دار بدون جهت مدل کرد، به طوری که شهرها رأس‌های گراف هستند و مسیرها لبه‌های آن هستند و فاصله یک مسیر وزن لبه است. در این گراف مسئله، به حداقل رساندن شروع و پایان در یک رأس مشخص پس از بازدید دقیق از یک رأس است. اغلب مدل، یک گراف کامل است (یعنی هر جفت رأس با یک لبه یا یال به هم متصل می‌شوند). در واقع هدف از حل مسئله فروشنده دوره گرد از دیدگاه یک مسئله گراف می‌خواهیم در یک گراف وزن دار یک سیکل بهینه یا تور همیلتونی را بیابیم به شرطی که جمع وزن یال‌ها یا لبه‌ها مینیمم باشد.

همانطور که در شکل بالا مشاهده می‌شود در سمت چپ گراف کامل وزن دار داریم یعنی از تمامی گره‌ها به گره‌های دیگر یال وجود دارد اگر بخواهیم یک تور بهینه همیلتونی بدست بیاوریم یعنی مجموع وزن یال‌ها مینیمم شود به صورت گراف سمت راست می‌توان یال‌هایی را انتخاب کرد که مجموع وزن کم‌تری داشته باشد یا به عبارت دیگر با تعمیم به مسئله فروشنده دوره گرد مسافت طی شده کم‌تری را داشته باشد. اکنون اگر از هر شهر در این گراف شروع به حرکت کنید این مسیر مسیر بهینه خواهد بود.

مدل ریاضی مسئله فروشنده دوره‌گرد

در ادامه بررسی مسئله فروشنده دوره‌گرد به معرفی مدل ریاضی می‌پردازیم.

معرفی متغیرها و پارامترها

برای فرموله‌سازی ریاضی مسئله فروشنده دوره‌گرد، از مدل زیر استفاده می‌شود:

• \(n\): تعداد شهرها
• \({d_{ij}}\): فاصله بین شهرهای \(i\) و \(j\)
• ​\({x_{ij}}\): متغیری دودویی که اگر فروشنده از شهر \(i\) به شهر \(j\) سفر کند برابر با ۱ و در غیر این صورت برابر با ۰ است.

فرموله‌سازی ریاضی TSP

تابع هدف مسئله به صورت زیر تعریف می‌شود:

$$min\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{d_{ij}}.{x_{ij}}} } $$

به طوری که:

۱- هر شهر تنها یک‌بار بازدید می‌شود:

$$\sum\limits_{j = 1}^n {{x_{ij}} = 1,\forall i} $$
2- از هر شهر یک‌بار خروج صورت می‌گیرد و یک‌بار ورود:

$$\sum\limits_{i = 1}^n {{x_{ij}} = 1,\forall i} $$
3- شرط زیرمجموعه‌های بدون حلقه (Subtour Elimination Constraints): برای جلوگیری از ایجاد حلقه‌های کوچکتر از مسیر اصلی.

پیچیدگی محاسباتی و NP-کامل بودن

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

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

همان‌طور که اشاره شد مسئله فروشنده دوره‌گرد جزو مسائل NP-Hard می‌باشد و با توجه به تعداد شهرها و مسیرها می‌توان از روش‌های مختلفی برای حل این مسئله استفاده کرد. به‌طور کلی سه روش برای حل مسئله فروشنده وجود دارد که در ادامه به بررسی هر کدام خواهیم پرداخت.

۱- روش‌های دقیق (Exact Methods)

روش‌های دقیق هدفشان پیدا کردن جواب بهینه مطلق برای مسئله TSP است. برخی از مهم‌ترین روش‌ها عبارت‌اند از:

• روش شاخه و کران (Branch and Bound): این روش یک درخت جستجو می‌سازد و شاخه‌هایی که نمی‌توانند جواب بهینه بدهند را هرس می‌کند.
• برنامه‌ریزی پویا (Dynamic Programming): این روش توسط بلمن معرفی شد و به‌ویژه برای تعداد شهرهای کم کارآمد است.
• پیمایش کامل (Exhaustive Search): در این روش، تمام مسیرهای ممکن بررسی می‌شوند؛ با این حال، این روش برای تعداد شهرهای زیاد به دلیل تعداد ترکیب‌های ممکن، غیرعملی است.

۲- روش‌های تقریبی (Approximation Methods)

روش‌های تقریبی برای حل مسئله‌های بزرگ‌تر و در زمانی کوتاه‌تر کاربرد دارند، اما نمی‌توانند جواب بهینه دقیق را تضمین کنند:

• روش‌های حریصانه (Greedy Algorithms): مانند الگوریتم نزدیک‌ترین همسایه (Nearest Neighbor)، که فروشنده را به نزدیک‌ترین شهر هدایت می‌کند.
• روش‌های تصادفی چند جمله‌ای (Randomized Polynomial Algorithms): این الگوریتم‌ها از جستجوی تصادفی و قواعد ساده برای کاهش پیچیدگی استفاده می‌کنند.

۳- روش‌های فراابتکاری (Metaheuristic Methods)

برای حل مسئله فروشنده دوره گرد بوسیله الگوریتم‌های هوشمند و بویژه الگوریتم‌های فرا اکتشافی می‌بایستی راه حل‌های آن کد شوند به طور کلی ۳ روش کد کردن مسئله TSP وجود دارد:

• نمایش جواب به صورت رشته گسسته جایگشتی

در این نوع راه حل با توجه به ویژگی الگوریتم حل کننده در گسسته بودن، یک جایگشت از اعداد تولید می‌شود و در هر تکرار جای این اعداد به نوعی باهم عوض می‌شود تا در نهایت بهترین جایگشت به عنوان بهترین راه حل ارائه می‌شود. این روش نسبت به دو روش دیگر بهتر عمل می‎کند از مهم‌ترین الگوریتم‌ها در این دسته می‌توان به موارد زیر اشاره کرد:

• • الگوریتم ژنتیک یا Genetic Algorithms
  • شبیه‌سازی تبرید یا Simulated Annealing 
  • جستجوی ممنوعه یا Tabu Search
  • جستجوی همسایگی متغیر یا Variable Neighborhood Search
  • بهینه‌سازی کلونی مورچگان یا Ant Colony Optimization 
  • جستجوی هارمونی یا Harmony Search 

• نمایش جواب به صورت کلیدهای تصادفی یا Random Key

در این نوع راه حل که با الگوریتم های پیوسته انجام می‌شود جایگشت را مستقیماً نمی‌توان تولید کرد به همین دلیل از مرتب سازی تعداد مقادیر موجود در جواب الگوریتم یک جایگشت ایجاد می‌شود و به عنوان جواب مسئله فروشنده دوره گرد در هر تکرار مورد مقایسه قرار می‌گیرد. از مهم‌ترین الگوریتم‌ها در این دسته می‌توان به موارد زیر اشاره کرد:

• • بهینه‌سازی ازدحام ذرات یا Particle Swarm Optimization
  • الگوریتم رقابت استعماری یا Imperialist Competitive Algorithm
  • تکامل تفاضلی یا Differential Evolution
  • بهینه‌سازی مبتنی بر جغرافیای زیستی یا Bio-geography Based Optimization
  • استراتژی‌های تکاملی یا Evolution Strategies
  • برنامه‌ریزی تکاملی یا Evolutionary Programming

برای مقایسه انواع الگوریتم‌ها با یکدیگر برای حل مسئله فروشنده دوره گرد می‌توانید مقایسه الگوریتم های حل مسئله TSP را مشاهده کنید.

• نمایش جواب به شکل ماتریس‌های فرومون

نمایش جواب به شکل ماتریس‌های شبیه فرومون که توسط تمامی الگوریتم‌های اشاره شده در قسمت قبل قابل استفاده می‌باشد.

الگوریتم جستجوی ممنوعه یا Tabu Search، از قوی‌ترین الگوریتم‌ها در زمینه حل مسائل بهینه‌سازی، به خصوص مسائل بهینه‌سازی مبتنی بر گراف و مسائل بهینه‌سازی ترکیباتی است. این الگوریتم در اواخر دهه ۱۹۸۰ و توسط گلووِر (Glover) و همکارانش ارائه گردید. غالباً یکی از مسائلی که برای حل آن‌ها از الگوریتم TS استفاده می‌شود، مسئله فروشنده دوره گرد یا TSP است. این الگوریتم پاسخ‌های بسیار مناسبی را برای انواع مسائل گسسته به خصوص مسئله TSP ارائه می‌کند.

نتیجه‌گیری و جمع‌بندی

مسئله فروشنده دوره‌گرد نمونه‌ای چالش‌برانگیز از مسائل بهینه‌سازی ترکیبیاتی است که با پیچیدگی بالایی روبرو است. با استفاده از الگوریتم‌های فراابتکاری می‌توان راه‌حل‌هایی تقریباً بهینه برای آن یافت و کاربردهای عملی آن در زمینه‌های مختلف، اهمیت بالای این مسئله را نشان می‌دهد. بهینه‌سازی در حل مسائل ترکیبیاتی می‌تواند در آینده به کمک پیشرفت‌های محاسباتی و الگوریتمی به دقت و سرعت بیشتری دست یابد.