مسيريابي چند ساختي‌ چند هدفه با استفاده از الگوريتم‌هاي ژنتيك چند هدفه با مرتب‌سازي غير مغلوب نسخه‌ي 2 و تاپسيس

Multimodal multi-objective route planning using non-dominated sorting genetic algorithm-II and TOPSIS method

در يك مساله‌ي مسيريابي چند ساختي‌ چند هدفه، هدف پيدا كردن مسيري بهينه، متشكل از چند ساخت حمل و نقلي، با در نظر گرفتن چند تابع هدف بين نقاط مبدا و مقصد مي‌باشد. اكثر مسايل بهينه‌سازي چند هدفه با اختصاص دادن يك وزن به هر تابع هدف و استفاده از مجموع وزن‌دار توابع به عنوان يك تابع هدف جدا حل مي‌شوند. اين روش‌ حل مسايل بهينه‌سازي چند هدفه داراي نقاط ضعفي مي‌باشد كه از جمله‌ي آنها مي‌توان به عدم توانايي در جست‌ و جوي فضاي مساله و نياز به نرمال‌ سازي توابع هدف اشاره نمود. بنابراين، در اين تحقيق از الگوريتم ژنتيك چند هدفه‌ با مرتب سازي غير مغلوب نسخه 2 (NSGA-II) براي حل مساله‌ي بهينه‌سازي بهينه‌ي چند ساختي‌ چند هدفه استفاده شده است. اين الگوريتم به جاي يك مسير، مجموعه‌اي از مسيرها را پيشنهاد مي‌دهد كه اين مسيرها هيچ برتري مطلقي بر هم ندارند. در نهايت مسير بهينه از بين اين مجموعه از مسيرها با استفاده از روش تاپسيس تعيين مي‌گردد. توابع هدف در نظر گرفته شده در اين تحقيق شامل كمترين تعداد تغيير ساخت‌هاي حمل و نقلي، كرايه‌ي مسير و زمان طي شدن مسير مي‌باشند. همچنين در اين تحقيق، ساختهاي حمل و نقلي اتوبوس، اتوبوس‌هاي تندرو، تاكسي، مترو و پياده روي براي جابجايي در سطح شبكه‌ي حمل و نقلي در نظر گرفته شده‌اند. نتايج نشان‌ داد مسير پيشنهادي الگوريتم NSGA-II به ترتيب در 89 و 87 درصد مسيريابي‌هاي صورت گرفته برتر از مسيرهاي پيشنهادي الگوريتم هاي ژنتيك و شبيه سازي تبريد بوده ‌است.

In a multi-modal multi-objective route planning problem, the main purpose is finding an optimal route between the origin and destination, which is a combination of multi-transportation modes, pairs by considering multi-fitness function. Most of multi-objective problems are solved by assigning a weight to each objective function and using a linear averaging of the objectives as a distinct objective function. These methods have some weaknesses such as inability in searching the problem space and a need to normalize the objective functions. Therefore, in this paper, a non-dominated sorting genetic algorithm (NSGA-II) has been used to solve the multi-modal multi-objective routing problem. This algorithm proposes a set of non-dominated routes that has no absolute superiority to each other. Finally, the optimal route was determined using TOPSIS method from this set. The intended objective functions in this research are the lowest number of changes in transportation means, fare and time during the path. Moreover, five transportation modes including subway, taxi, bus, BRT, and walking transportation modes have been considered as means of transportation inside the mentioned network. This algorithm was implemented in a part of Tehran transportation network and results showed that the proposed NSGA-II algorithm proposed a better route in 89% and 87% of the routing cases than those of the genetic and the simulated annealing algorithms respectively.