عنوان پایان‌نامه
مسیر یابی بهینه چند حالته بر اساس تصمیمات چند معیاره کاربر
- رشته تحصیلی
- مهندسی عمران-سیستمهای اطلاعات جغرافیایی(GIS)
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی پردیس 2 فنی شماره ثبت: 3206;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 73520
- تاریخ دفاع
- ۲۹ بهمن ۱۳۹۴
- دانشجو
- فاضل قادری
- استاد راهنما
- پرهام پهلوانی
- چکیده
- هدف از انجام این پایان‌نامه، طراحی یک سیستم اطلاعات مکانی تحت وب به منظور انجام مسیریابی بهینه‌ی چند حالته بین یک زوج مبدا- مقصد، با در نظر گرفتن مقادیر اهمیت معیارهای مختلف، بر اساس نظر کاربر می‌باشد. جهت نیل به این هدف، در این تحقیق با در نظر گرفتن چهار معیار طول مسیر، زمان طی شدن مسیر، کرایه‌ی مسیر و میزان سختی کاربر؛ به طراحی، پیاده‌سازی و ارزیابی روش‌هایی به منظور (الف) مدل‌سازی ترجیحات کاربر در انتخاب مسیر چند حالته‌ی چند معیاره، (ب) مسیریابی بهینه‌ی چند حالته‌ی چند معیاره و (ج) مسیریابی بهینه‌ی چند حالته‌ی چند معیاره شخصی سازی شده بر اساس مدل ترجیحات کاربر در انتخاب مسیر پرداخته شده است که در ادامه هر یک از این موارد تشریح شده‌است. در این تحقیق به منظور مدل‌سازی ترجیحات کاربر در انتخاب مسیر چند حالته‌ی چند معیاره، از ترکیب روش وزن دهی fuzzy AHP و ترکیب کمیت‌سنج‌های مفهومی با عملگرهای OWA برای وزندهی معیارها و محاسبه‌ی میزان سازگاری مسیرها استفاده شده است. ویژگی مهم این روش، در نظر گرفتن عدم قطعیت کاربر در وزندهی معیارها و قابلیت پشتیبانی از استراتژی‌های تصمیم‌گیری مختلف می‌باشد. در این روش، ابتدا کاربر با استفاده از روش fuzzy AHP به وزندهی معیارها می‌پردازد. سپس با در نظر گرفتن استراتژی تصمیم‌گیری اتخاذ شده توسط کاربر، به محاسبه میزان سازگاری هر یال پرداخته می‌شود. در این تحقیق، به منظور جست‌وجوی مسیر بهینه‌ی چند حالته‌ی چند معیاره در شبکه‌ی جهت‌دار حمل و نقلی، از الگوریتم پیشنهادی Yen، الگوریتم‌های تکاملی ژنتیک، شبیه‌سازی تبرید تدریجی و الگوریتم ژنتیک رتبه‌بندی شده‌ی غیر مغلوب (NSGA-II) استفاده شده‌است. به منظور مقایسه‌ی نتایج خروجی‌های این الگوریتم‌ها، به تعداد مسیرهایی که در جبهه‌ی اول پارِتوی الگوریتم NSGA-II قرار می‌گیرند، مسیرهای برتر بدست آمده از سه الگوریتم دیگر تعیین شده و سپس برترین مسیر از هر کدام از این دسته‌ها با استفاده از روش تاپسیس تعیین شده است. سپس این مسیرهای پیشنهادی، با استفاده از روش Lp-norm با یکدیگر مقایسه شدند. نتایج نشان دهنده‌ی سازگاری بالاتر مسیرهای خروجی ترکیب الگوریتم پیشنهادی Yen و روش تاپسیس بودند. اما، به دلیل پیچیدگی زمانی بالای این الگوریتم، از به‌کارگیری آن برای طراحی یک سیستم اطلاعات مکانی تحت وب برای مسیریابی چند حالته‌ی چند معیاره‌ی شخصی سازی شده صرف نظر شده و به جای آن از ترکیب الگوریتم‌های NSGA-II و تاپسیس – که بیشترین میزان کارایی را نسبت به دو الگوریتم دیگر داشت- به منظور استفاده برای جست‌وجوی مسیر بهینه‌ی چند حالته‌ی چند معیاره در سیستم مسیریاب استفاده شد. در نهایت یک سیستم اطلاعات مکانی برای مسیریابی بهینه‌ی چند حالته‌ی چند معیاره‌ی شخصی سازی شده با استفاده از ترکیب روش‌های AHP fuzz، ترکیب کمیت‌سنج‌های مفهومی با عملگرهای OWA، الگوریتم NSGA-II و روش تاپسیس طراحی شد. سیستم مسیریاب پیشنهادی، بر روی بخشی از شبکه‌ی حمل و نقل عمومی مرکز شهر تهران پیاده گشت و نتایج حاکی از آن بود که به طور میانگین، 23/80 % کاربران با استراتژی‌های تصمیم‌گیری مختلف، مسیر پیشنهادی را بهترین مسیر بین مبدا و مقصد دانسته‌اند.
- Abstract
- The main purpose of this thesis is to design a web based geospatial information system for optimal multimodal routing between a pair origin-destination by considering different criteria’s importance based on the user preferences. To achieve this objective, in this thesis, by considering four criteria including the route length, the route crossing time, the route fare, and the user’s bother; the design, implementation, and evaluation of some methods have been done for (a) the user’s preferences modeling to select multimodal multi-criteria route, (b) multimodal multi-criteria routing, and (c) personalized optimal multimodal multi-criteria routing based on the user’s preferences model in route selecting. Each method has been explained in follows. In this research, for modeling a user’s preferences in selecting multimodal multi-criteria route, the combination of fuzzy AHP weighting method, as well as integrating of OWA operators with linguistic quantifiers have been used for criteria weighting and calculating routes fitness. An important aspect of this method is considering a user’s uncertainty in criteria weighting and supporting different decision strategies. In this method, at first, the user tries weighting the criteria using fuzzy AHP weighting method. Then, by considering a decision strategy by the user, the fitness value of each route will be calculated. In this research, the Yen’s algorithm, a genetic algorithm, a simulated annealing algorithm, and non-dominated sorting genetic algorithm-II (NSGA-II) have been used for searching optimal multimodal multi-criteria route in a directed transportation network. To compare these algorithms results, the amount of routes, i.e., n, in the first Pareto front of the proposed NSGA-II algorithm was calculated at first. Then, the best n routes proposed by the other three proposed algorithms were determined subsequently and for each algorithm, the optimal route would be determined using TOPSIS algorithm. Then, these four optimal routes were compared using Lp-norm method. Results showed the higher values of the routes proposed by integrating Yen’s algorithm and TOPSIS method. But, because of high time complexity of this algorithm, using of this algorithm for designing a personalized web-based geospatial information system for multimodal multi-criteria routing was neglected and the combination of NSGA-II algorithm and TOPSIS method –that had higher fitness compared to the other two algorithms- used for searching optimal multimodal multi-criteria route in routing system. Finally, a geospatial information system using the integrated fuzzy AHP method, the integrated OWA operator and linguistic quantifiers, the NSGA-II algorithm, and the TOPSIS method was designed for personalized multimodal multi-criteria routing. The proposed system was implemented in an area of the transportation network of center of Tehran and results showed on average 80.23% of the users with different decision strategies, selected the system proposed route as the best route between the origin and destination points. Keywords: optimal multimodal multi-criteria routing, fuzzy AHP weighting method, OWA operators, fuzzy linguistic quantifiers, NSGA-II algorithm, genetic algorithm, simulated annealing algorithm, k-shortest path algorithm, TOPSIS method
