مسیریابی بهینه در شبکه ی حمل و نقل درون شهری با ادغام الگوریتم های فرا ابتکاری ژنتیک (Ga) و جستجوی ممنوع (Ts)

با توجه به گسترش شهرها و پیچیده تر شدن شبکه ی راه های درون شهری به ویژه در شهرهای بزرگ، مسئله ی مسیریابی و در واقع یافتن کوتاه ترین مسیر تبدیل به یکی از دغدغه های افراد در هنگام تصمیم گیری برای انتخاب مسیر در جابجایی از مبدا حرکت به یک مقصد مشخص، شده است. روشی که در این پژوهش برای حل مسئله ی کوتاه ترین مسیر پیشنهاد می شود، استفاده از ترکیب الگوریتم های فراابتکاری ژنتیک (ga) و جستجوی ممنوع (ts) می باشد. بدین منظور پس از اعمال یک سری پیش پردازش هندسی بر روی شبکه ی مورد نظر برای سرعت بخشیدن به روند جستجوی الگوریتم از یک محدوده ی جستجو حول نود مبدا و مقصد استفاده می شود. در الگوریتم پیشنهادی، تابع هزینه به صورت یک عدد مختلط تعریف می شود که قسمت حقیقی آن نشان دهنده ی مجموع وزن یال های واقعی و قسمت موهومی آن نشان دهنده ی تعداد یال های مجازی و در واقع تعداد عدم اتصالات بین نود ها در کروموزوم های الگوریتم ژنتیک می باشد. همچنین در بحث اعمال جهش بر روی کروموزوم های الگوریتم ژنتیک، از الگوریتم جستجوی ممنوع استفاده می گردد. علت پیشنهاد این روش، جدید بودن و نیز زمان بر بودن روش های قطعی مثل الگوریتم دایجسترا و نیز جواب نامناسب الگوریتم ژنتیک خالص(غیر ترکیبی) از لحاظ وزن نهایی مسیر در حل مسئله ی مسیریابی در شبکه های واقعی بخصوص شبکه های بزرگ می باشد. به منظور ارزیابی کارایی الگوریتم پیشنهادی، الگوریتم بر روی یک شبکه ی واقعی جهت دار شامل 739 نود و 1160 یال که بخشی از شبکه ی راه های شهر تهران می باشد، پیاده سازی شد. نتایج نشان می دهد که در الگوریتم پیشنهادی، طول مسیر تا حد ممکن به جواب حاصل از الگوریتم قطعی دایجسترا نزدیک است. این الگوریتم طول نهایی مسیر را 5 درصد بیشتر پیش بینی می کند. اما از لحاظ سرعت اجرا به طور متوسط 5.12 برابر نسبت به الگوریتم دایجسترا سریع تر است. در مقایسه با الگوریتم ژنتیک خالص نیز الگوریتم پیشنهادی از نظر طول مسیر به طور متوسط 9 درصد کوتاه تر می باشد و از نظر زمان اجرا سرعت الگوریتم پیشنهادی با الگوریتم ژنتیک خالص تقریبا برابر است. همچنین به لحاظ قابلیت تکرارپذیری نیز الگوریتم پیشنهادی 25.36 درصد، تکرارپذیری را نشان می دهد.

Optimum Routing in the Urban Transportation Network by Integrating Genetic Meta-heuristic (GA) and Tabu Search (Ts) Algorithms

Urban transportation is one of the most important issues of urban life especially in big cities. Urban development, and subsequently the increase of routes and communications, make the role of transportation science more pronounced. The shortest path problem in a network is one of the most basic network analysis issues. In fact, finding answers to this question is necessity for higher level analysis. In general, shortest path solution methods using optimization algorithms are divided into two categories: exact and approximate algorithms. In exact algorithms, achieving the optimal solution requires time, and consequently more cost. On the opposite side, there are some approximate algorithms that work in a short period of time. Metaheuristic algorithms are among approximate algorithms that are capable of finding optimal or nearoptimal solutions in a reasonable period of time. The method used in this study is to solve the shortest path problem with the combination of Genetic metaheuristic (GA) and Tabu Search (TS) algorithms. GA is inspired by genetic science and Darwinchr('39')s theory of evolution; it is based on survival of the highest or natural selection. A common use of genetic algorithms is to be used as an optimization function. In GA, the genetic evolution of living things of life is simulated. Inspired by the evolutionary process of nature, these algorithms solve problems. GA forms a set of population (solutions), then it achieves an optimal set by acting some possess on the correct set. To solve a problem by genetic algorithms, it is necessary the problem is converted to the specific form required by GA. On the other hand, TS algorithm is not populationbased. It obtains an answer, then it tries to direct the answer to the optimal solution by applying a series of operators. This algorithm is highly similar to the Simulated Annealing algorithm. In this paper, for solving the shortest path problem, a series of geometric preprocessing on the network is done to generate a search area around the source and destination nodes. In the proposed algorithm, the cost function is defined as a complex number, which the real part shows the sum of the weight of the real edges, and the imaginary part denotes the number of virtual edges. The innovation of this research is about applying Tabu Search algorithm in mutations process of genetic algorithm. The proposed method overcomes the inappropriate response of the pure genetic algorithm in terms of the final weight of the path especially the large networks. In order to evaluate the efficiency of the proposed algorithm, the algorithm was implemented on a real directional network which is part of Tehran city road networks including 739 nodes and 1160 edges. The results show that in the proposed algorithm, the length of the path is as close as possible to the solution obtained from the definitive Dijkstra rsquo;s algorithm. This algorithm predicts approximately the final path length of 5% more than Dijkstra rsquo;s algorithm. But in terms of running speed, it is 5.12 times faster than the Dijkstra rsquo;s algorithm. In comparison with the pure genetic algorithm, the proposed algorithm is 9% shorter in average in terms of path length. And about the running time, the speed of the proposed algorithm is approximately equal to the pure genetic algorithm. Regarding to repeatability, the proposed algorithm also shows 25.36% of repeatability.