ارایه روشی ابتکاری برای حل مسیله مسیریابی «فروشنده دوره‌گرد»

مسیریابی یکی از مسایل بسیار پرکاربرد gis است که هدف اصلی آن یافتن بهترین مسیر گذرنده از یک سری موقعیت‌های از پیش تعیین شده است. این فرایند می‌تواند تاثیر بسزایی در تصمیم‌گیری‌های حساس مکانی داشته باشد. به همین دلیل از دیرباز تحقیقات بسیاری در مورد بهینه‌سازی این مسیله با استفاده از الگوریتم‌های مختلف صورت گرفته است. مسیله فروشنده دوره‌گرد یکی از مسایل بسیار کهن در علوم کاربردی است که پیش از پیدایش gis نیز مطرح بوده است. این مسیله با ظهور فناوری‌های جدید مانند gis کاربردهای بسیاری یافته و روش‌های جدیدی نیز برای حل آن پیشنهاد شده است. الگوریتم‌های تکاملی (ژنتیک) یکی از روش‌هایی هستند که برای حل مسایل بهینه‌سازی مختلف به کار گرفته می‌شوند. تحقیقات نشان داده است که تلفیق روش‌های جست‌وجوی محلی (local search) با عملگرهای ژنتیک می‌تواند منجر به نتایج بهتری در حل مسیله فروشنده دوره‌گرد شود. در نوشتار حاضر، روشی تازه و ابتکاری برای حل مسیله مسیریابی ارایه و پیاده‌سازی شده است. در این روش با بهره‌گیری از مفهوم مرکز هندسی به برازش چندضلعی‌ها با ریوس شهرها، به گونه‌ای پرداخته شده است که مسیر نهایی محدب‌ترین چندضلعی باشد. این الگوریتم با رویکردی پوششی با جهت بیرونی ـ درونی بزرگ‌ترین دایره محیطی شهرها را به کوچک‌ترین چندضلعی محدب ممکن تبدیل می‌کند. همچنین با استفاده از جست‌وجوی محلی مبتنی بر الگوریتم ژنتیک و روش نزدیک‌ترین همسایه (nn)، به حل مسیله مسیریابی فروشنده دوره‌گرد پرداخته شده است. ارزیابی نتایج حاصل از روش پیشنهادی با نتایج حاصل از روش‌های ژنتیکی، جست‌وجوی محلی و نزدیک‌ترین همسایه حاکی از این بود که روش‌ پیشنهادی، سرعت و دقت بالایی را در تولید مسیرهای نهایی ارایه می‌کند. بررسی نتایج نهایی ژنتیک با روش ابتکاری نشان دادکه این الگوریتم همواره نمی‌تواند به جواب‌های بهتری برسد. مثلاً در تعداد 25 بار اجرای جداگانه جست‌وجوی ژنتیک، 3/69 درصد از جواب‌ها از جواب روش پیشنهادی، بهتر نبودند. از طرف دیگر روش پیشنهادی می‌تواند چندین هزار برابر سریع‌تر از الگوریتم قدرتمند ژنتیک جواب‌های نهایی را تولید کند. کلید‌واژه‌ها: gis، مسیریابی، الگوریتم ژنتیک، جست‌وجوی محلی، نزدیک‌ترین همسایه (nn).