نوع مقاله : مقاله پژوهشی
نویسندگان
1 گروه مهندسی نقشه برداری، دانشکده مهندسی عمران، دانشگاه تربیت دبیر شهید رجائی، تهران، ایران
2 گروه مهندسی ژئوتکنیک و آب، دانشکده مهندسی عمران، دانشگاه تربیت دبیر شهید رجائی، تهران، ایران
چکیده
پیشینه و اهداف: امروزه، مدیریت شهری به عنوان یکی از مهم‌ترین مسائل تصمیم‌گیران و مدیران در حوزههای شهری است. مسئله‌ی یافتن کوتاهترین مسیر، به عنوان یکی از مسائل مهم در حوزه‌ی مدیریت شهری به منظور کاهش زمان سفر بین دو نقطه‌ی حیاتی، همواره مورد توجه بسیاری از حوزههای تحقیقاتی از قبیل مدیریت شهری، حمل و نقل، ارتباطات و غیره بوده است. در طول دهه‌های گذشته، الگوریتم ژنتیک در حل مسائل پیچیده‌ی بهینه‌سازی چند هدفه، به خوبی عمل کرده است، اما بسیاری از الگوریتمهای ژنتیک، تنها برای یافتن مسیر بهینه در شبکههای محلی، مناسب هستند. در این شبکهها، در صورتی که تعداد نقاط افزایش یابد، الگوریتمهای ارائه شده کارآیی خود را نخواهند داشت. هدف از این تحقیق، یافتن مسیری در شبکه‌ی خیابانهای شهر تهران میباشد که کمترین زمان، مسافت و هزینه را داشته باشد. بنابراین، یک روش جدید برای حل مسئله‌ی مسیریابی بر مبنای الگوریتم ژنتیک، با این فرض که تمام خطوط موجود در شبکه دارای وزنهای مثبت میباشند، پیشنهاد میگردد.
روش‌ها: ویژگی الگوریتم پیشنهادی، متغیر بودن عملگرهای الگوریتم ژنتیک میباشد که متناسب با ساختار شبکه، تعریف میگردد. بر همین اساس، عملگر جهش در الگوریتم ژنتیک بر اساس فضای مورد مطالعه و فاصله‌ی بین نقاط شروع و پایان، تعریف میگردد. برای حل مسئله، از کدگذاری اعداد صحیح استفاده میشود و لذا، نقاط موجود در این گراف با استفاده از اعداد صحیح، نام‌گذاری شده و هر فرد در جمعیت به عنوان یک جواب برای حل مسئله، در نظر گرفته میشود. اندازه‌ی جمعیت، بسته به تعداد گرههای موجود در گراف و طول هرکروموزوم دارد. طول رشتههای انتخاب شده، حداکثر برابر با تعداد گرههای موجود در شبکه، در نظر گرفته میشود، زیرا این احتمال وجود دارد که بهترین مسیر، مسیری باشد که از تمام گرهها عبور میکند. در پایان، این الگوریتم بر روی شبکه‌ی مورد مطالعه که یک گراف مسطح میباشد، پیادهسازی میشود. دقت روش پیشنهادی نسبت به روش متداول، در سه جفت نقطه، مورد ارزیابی قرار گرفته است.
یافته‌ها: با توجه به این‌که هدف از حل مسئله، یافتن مسیری بود که کمترین وزن را داشته باشد، در الگوریتم پیشنهادی یک عملگر ترکیب و سه عملگر جهش، ارائه گردید. این، در حالی است که در الگوریتمهای ژنتیک رایج، تنها از یک عملگر جهش و ترکیب، استفاده شده است. در این الگوریتم، نحوه‌ی استفاده از عملگرهای جهش، به ساختار شبکه و فاصله‌ی بین نقطه‌ی شروع و پایان، بستگی دارد. استفاده از الگوریتم ژنتیک پیشنهادی، نسبت به الگوریتم ژنتیک رایج، با 16% بهبود عملکرد همراه بوده است که نشان میدهد الگوریتم ژنتیک پیشنهادی، سریع‌تر به جواب مسئله میرسد. همان‌طور که در شکل 4 نشان داده شده است بهترین مسیر، مسیری است که مقدار تابع برازندگی آن به یک، نزدیکتر باشد. نتایج حاصل از مقایسه‌ی روش پیشنهادی با روش‌های متداول، 16 درصد سرعت بالاتر را نشان میدهد.
نتیجه‌گیری: با توجه به این‌که فرض اولیه‌ی این تحقیق، مثبت بودن وزن تمام خطوط موجود در شبکه بوده است، عملگر جهش در الگوریتم ژنتیک، بر اساس فضای مورد مطالعه و فاصله‌ی بین نقاط شروع و پایان، تعریف شد. نتایج نشان داد که در صورت وجود فضای جستجوی کوچک، نقاط کمتری مورد نیاز است و به منظور تولید جمعیت اولیه، گرههایی که در کنار هم قرار دارند و به هم نزدیکتر هستند، باید انتخاب شوند. بدین ترتیب، مقدار تابع برازندگی افراد موجود در جمعیت اولیه، افزایش یافته و جوابها به واقعیت، نزدیکتر میشود. برای تحقیقات آتی، پیشنهاد میگردد که به منظور تولید جمعیت اولیه، نقاط بین نقطه‌ی شروع و پایان انتخاب گردد و همچنین، نقاط انتخاب شده در نزدیکی خط واصل بین نقطه‌ی شروع و پایان باشد، زیرا هنگامی که وزن یالهای شبکه، فاصله‌ی بین نقاط باشد، بهترین مسیر در فضای بین نقطه‌ی شروع و پایان قرار دارد. همچنین، پیشنهاد میشود که عملکرد شبکه با چندین عملگر ترکیب نیز، مورد ارزیابی قرار گیرد.
کلیدواژه‌ها
موضوعات
عنوان مقاله [English]
A New Approach to Solve the Shortest Route in Urban Networks Based on Evolutionary Algorithms
نویسندگان [English]
- S. Behzadi 1
- M. Adresi 2
- M. Shirazian 1
1 Department of Surveying Engineering, Faculty of Civil Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran
2 Department of Geotechnical and Water Engineering, Faculty of Civil Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran
چکیده [English]
Background and Objectives: Today, urban management is one of the most important issues for decision makers and managers in urban areas. The problem of finding the shortest route, as one of the important issues in the field of urban management in order to reduce the travel time between two critical points, has always been the focus of many research fields such as urban management, transportation, communication, etc. During the past decades, the genetic algorithm has worked well in solving complex multi-objective optimization problems, but many genetic algorithms are only suitable for finding the optimal route in local networks. In these networks, if the number of points increases, algorithms will not be effective. The purpose of this research is to find a route in the street network of Tehran that has the least time, distance and cost. Therefore, a new method is proposed to solve the routing problem based on genetic algorithm, with the assumption that all lines in the network have positive weights.
Methods: The charactristics of the proposed algorithm is the variability of genetic algorithm operators, which is defined according to the network structure. Accordingly, the mutation operator in the genetic algorithm is defined based on the studied space and the distance between the start and end points. Integer coding is used to solve the problem, and therefore the points in this graph are named using integers and each person in the population is considered as an answer to solve the problem. The population size depends on the number of nodes in the graph and the length of each chromosome. The length of the selected strings is considered equal to the maximum number of nodes in the network, because there is a possibility that the best route is the route that passes through all the nodes. At the end, the proposed algorithm is implemented on the study area, which is a planar graph. The accuracy of the proposed method compared to the conventional genetic algorithm has been evaluated in three pairs of points.
Findings: Considering that the goal of solving the problem was to find the route that has the least weight, one combination operator and three mutation operators were presented in the proposed algorithm. This is despite the fact that in traditional genetic algorithms, only one mutation and combination operator is used. In this algorithm, the way to use mutation operators depends on the structure of the network and the distance between the start and end points. The use of the proposed genetic algorithm compared to the traditional genetic algorithm has been associated with a 16% improvement in performance, which shows that the proposed genetic algorithm reaches the solution of the problem faster. As shown in Figure 4, the best route is the route whose fitness function value is closer to one. The results of comparing the proposed method with conventional methods show 16% higher speed.
Conclusion: Considering that the initial assumption of this research was the positive weight of all the lines in the network, the mutation operator in the genetic algorithm was defined based on the studied space and the distance between the start and end points. The results showed that if there is a small search space, fewer points are needed and in order to generate the initial population, the nodes that are next to each other and closer to each other should be selected. In this way, the value of the fitness function of the people in the initial population increases and the answers become closer to reality. For future research, it is suggested that in order to generate the initial population, the points between the start and end points should be selected, and also the selected points should be near the connecting line between the start and end points, because when the weight of the edges of the network is the distance between the points, the best route is in the space between the starting point and the end point. It is also suggested to evaluate the performance of the network with several combination operators.
کلیدواژه‌ها [English]
- Combination operators
- Genetic Algorithm
- Graph theory
- Jump operators
- Optimal route
COPYRIGHTS
© 2023 The Author(s). This is an open-access article distributed under the terms and conditions of the Creative Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) (https://creativecommons.org/licenses/by-nc/4.0/)
)