عنوان پایان‌نامه
بهینه سازی برنامه مشا هداتی شبکه های تعیین مو قعییت ماهواره ای به روش الگوریتم مور چگان
- رشته تحصیلی
- مهندسی عمران - نقشه برداری- ژئودزی
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی پردیس 2 فنی شماره ثبت: 2331;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 57882
- تاریخ دفاع
- ۰۴ مهر ۱۳۹۱
- دانشجو
- سحر ابوالحسنی
- استاد راهنما
- محمدعلی شریفی
- چکیده
- در این تحقیق به بخش خاصی از شبکه‌های سیستم تعیین موقعیت جهانی پرداخته شده است و آن ترتیب‌دهی و سازمان‌دهی کارهای زمینی است که جزئی از طراحی مرتبه اول به شمار می‌آید. هدف، تعیین بهترین تعداد گیرنده و بهترین ترتیب برای جابه‌جایی گیرنده‌ها بین نقاط شبکه است. در مورد اول، زمان انجام مشاهدات و در مورد دوم هزینه مالی شبکه به عنوان معیار بهینه‌سازی استفاده شده است. اهمیت این مسئله با افزایش ابعاد شبکه، افزایش می‌یابد. مسئله تعیین بهترین ترتیب برای جابه‌جایی گیرنده‌ها به نوع پیچیده‌ای از مسئله فروشنده دوره‌گرد که یک مسئله کلاسیک در"پژوهش عملیاتی " است، تبدیل می‌شود. این مسئله، یک مسئله بهینه‌سازی ترکیبی از نوع چندجمله‌ای غیرقطعی سخت است. ابعاد بزرگ این‌گونه مسائل، در یک زمان محدود قابل حل نیستند. بنابراین به سراغ روش‌های ابتکاری می‌رویم که جواب‌های نزدیک به بهینه را در زمان نسبتاً کوتاهی می‌یابند. روش ابتکاری که در این‌جا استفاده شده الگوریتم لانه مورچگان نام دارد که از رفتار واقعی مورچه‌های در جستجوی غذا الهام گرفته شده است. مسئله تعیین بهترین تعداد گیرنده با تغییر تعداد گیرنده‌ها بین 2 تا 7 و تعیین برنامه‌های زمانی بهینه مربوطه صورت می‌گیرد. بدین نحو که هزینه مالی لازم برای اجرای هر یک از 6 برنامه بهینه، محاسبه شده و در نهایت آن تعداد گیرنده که مستلزم صرف کمترین هزینه است، به عنوان بهترین تعداد گیرنده بهینه معرفی می‌شود. برای ارزیابی عملکرد روش ارائه شده از یک شبکه در شهر تهران که دارای 26 ایستگاه است، استفاده شده است. الگوریتم مورچگان توانست برنامه زمانی طراحی شده توسط نقشه‌بردار را با فرض داشتن 2، 3، 4، 5، 6، 7 گیرنده، به ترتیب 19.32%، 24.83%، 24.71%، 30.61%، 21.2% و 24.14% بهبود بخشد. به علت ترافیک موجود در شهر تهران، ماتریس هزینه که در بردارنده زمان لازم برای جابه جایی بین جلسه‌هاست، برای هر ساعت کاری، جداگانه محاسبه و در روند محاسبات، مرتباً به روزرسانی گردید. برای این کار از اطلاعات موجود در شرکت جامع حمل و نقل و ترافیک تهران استفاده شد. به منظور تعیین بهترین تعداد گیرنده‌ها، هزینه لازم برای هر یک از این برنامه‌ها مورد ارزیابی قرار گرفت که به ترتیب عبارت بود: از 85400000 ریال، 73200000 ریال ، 85400000 ریال، 91500000 ریال ، 54900000 ریال و 64050000 ریال. با توجه به این ارقام، 6 گیرنده به عنوان مناسب‌ترین تعداد گیرنده مشخص شد.
- Abstract
- The problem addressed in this thesis is to determine the best order for the observational sessions and also the optimum number of receivers in Global Positioning System networks. These two would lead to the least costs in the network. For the first optimization problem time and for the second optimization problem monetary cost were considered as the optimization criteria. Importance of these two optimization problems increases as the size of the network increases. The problem of determining the best order for moving receivers was transformed to a complicated form of traveling salesman problem which is a well-known operational research. This is a combinatorial optimization problem and is a hard nondeterministic polynomial problem. Exact methods can only solve small problems of this type. For large ones they need impractical running times. Heuristic methods are the best option to solve these problems. The heuristic method used in this thesis is Ant Colony System which is inspired by the foraging behavior of real ants. The problem of determining the optimum number of receivers was solved by changing the number of receivers between 2 and 7 and also specifying the related observational schedules. In fact, monetary costs for each of the six schedules were estimated and the one which was associated with the least cost was considered as the best schedule. To validate the proposed method, we used a network in Tehran consisting twenty-six stations. The ant colony algorithm could improve the first schedules, designed by the surveyor, for 2, 3, 4, 5, 6 and 7 receiver respectively up to 19.32%, 24.83%, 24.71%, 30.61%, 21.2% and 24.14%. Since the traffic in Tehran is considerable, the cost matrix which includes the necessary time for moving between sessions was calculated for each working hour separately and was optimized during the optimization process. For this, we used the information provided by Tehran Comprehensive Transportation and Traffic Studies Company. Monetary costs of each schedule were calculated in order to determine the optimum number of receivers. The costs for 2, 3, 4, 5, 6 and 7 receivers were respectively: 86400000 Rials, 73200000 Rials, 85400000 Rials, 91500000 Rials, 54900000 Rials and 64050000 Rials.
