ارائة مدل مکانی هوشمند به‌منظور یافتن مسیرهای بهینه در شبکة حمل‌ونقل شهری

نوع مقاله : علمی - پژوهشی

نویسندگان

1 استاد مرکز مطالعات سنجش از دور و GIS، دانشکدة علوم زمین، دانشگاه شهید بهشتی

2 دانشجوی دکتری GIS، دانشکدة نقشه‌برداری، دانشگاه صنعتی خواجه نصیرالدین طوسی

3 دانشجوی دکتری GIS، مرکز مطالعات سنجش از دور و GIS، دانشگاه شهید بهشتی

چکیده

یکی از تحلیل‌های پرکاربرد سیستم‌های اطلاعات جغرافیایی (GIS) یافتن مسیرهای بهینة بین دو نقطه در شبکة حمل‌ونقل شهری است. به‌دلیل تنوع بالای مسیرهای ممکن بین دو نقطه در شبکة حمل‌ونقل شهری، یافتن مسیرهای بهینه کار پیچیده‌ای است. از سویی، درنظرگرفتن هم‌زمان تمامی پارامترهای مؤثر در انتخاب مسیر از جمله طول مسیر، ترافیک، سختی عبور از تقاطع‌ها، کیفیت معابر و ...، پیچیدگی فرایند کشف مسیر بهینه را دوچندان می‌کند. همچنین در پاره‌ای از موارد، وجود دو یا چند پارامتر مؤثر ناسازگار، مانند طول مسیر و ترافیک، بر پیچیدگی مسئله می‌افزاید. الگوریتم‌های بهینه‌سازی، به‌ویژه الگوریتم‌هایی مانند الگوریتم ژنتیک چندهدفه NSGA-II، که توانایی درنظرگرفتن هم‌زمان چندین پارامتر ناسازگار در یک مسئله را دارند، می‌توانند GIS را در حل این‌گونه مسائل یاری کنند. هدف از این پژوهش عرضة مدلی برمبنای الگوریتم NSGA-II در بستر GIS، به‌منظور کشف مسیرهای بهینه در شبکة حمل‌ونقل شهری است. بدین‌منظور، الگوریتم NSGA-II به‌گونه‌ای مدل شد تا ساختار توپولوژیک مسیرهای بهینه (پیوستگی و نبودِ حلقه در مسیر) حفظ شود؛ بنابراین، هم در تولید مسیرهای اولیه و هم در عملگرهای ژنتیکی مورد استفاده، حفظ ساختار توپولوژیک مسیرهای خروجی مدنظر قرار گرفت. در این راستا به‌منظور رسیدن به اهداف یادشده، دو عملگر ژنتیکی ابتکاری، متناسب با مسئلة بهینه‌سازی مسیر در شبکة حمل‌ونقل شهری، توسعه داده شد. همچنین با هدف بالابردن کارآیی مدل در ارائة مسیرهای بهینه، افزون‌بر درنظرگرفتن طول مسیر، ترافیک و کیفیت مسیر به‌منزلة توابع هدف، دشواری عبور از تقاطع‌ها نیز به‌مثابة یکی دیگر از توابع هدف مدل شد. به‌منظور آزمودن قابلیت‌های مدل، یک شبکة حمل‌ونقل شهری فرضی با محدودیت‌های لازم طراحی شد و مدل، با بهره‌گیری از آن، مورد ارزیابی قرار گرفت. نتایج به‌دست‌آمده نشان‌دهندة صحت کارکرد مدل و توانایی بالای آن در یافتن مسیرهای بهینه با چندین هدف متضاد است.

کلیدواژه‌ها

عنوان مقاله [English]

A Smart Location Model, Based on Multi-Objective Genetic Algorithms to Find Optimal Routes in the Road Network

نویسندگان [English]

  • A Matkan 1
  • B Mirbagheri 2
  • K Akbari 3
1 Professor in Remote Sensing & GIS Research Center, Shahid Beheshti University
2 Ph.D. Student of GIS, Faculty of Geodesy and Geomatics Engineering, K.N. Toosi University of Technology
3 Ph.D. Student of GIS, Remote Sensing And GIS, Remote Sensing & GIS Research Center, Shahid Beheshti University
چکیده [English]

Finding optimal Paths between two points on the Road network is one of the most spatial analysis in GIS. The high diversity of possible Paths between two points and difficult in apply all parameters simultaneously select the optimal Path (length of Path, easily track, traffic, road quality…) make finding optimal Paths problem to a difficult problem. Also, in some cases, two or more incompatible effective parameters such as length of the route and traffic adds to the complexity of the problem. Optimization algorithms, such as multi-objective genetic algorithm NSGA-II, that have ability simultaneous. Apply multiple incompatible parameters, can help GIS to solving these problems. Present a NSGA-II model on GIS based for finding optimal paths between origin and destination in the road network is the main Target of this paper. Also two GA innovative operator developed for enhance the ability of the model to find the optimal paths. Output of the model might be introduced optimal paths that they are shorter, quality of roads, transit of intersections and traffic. A hypothetical road network with the necessary restrictions, designed and utilizes for test the capabilities of the innovative model. Evaluation results show that the model is able to finding optimal Paths with multiple incompatible parameters.

کلیدواژه‌ها [English]

  • Multi-objective optimization Paths
  • Road Network
  • NSGA-II Algorithm
  • innovative Operators
  • GIS

مراجع

  1. تناسان، م.، 1391، طراحی مدل بهینه‌سازی کاربری اراضی، مبتنی‌بر الگوریتم ژنتیک چندهدفه با رویکرد آمایش سرزمین (حوزة مورد مطالعه: رودبار جنوب – استان کرمان)، پایان‌نامة کارشناسی ارشد، دانشگاه شهید بهشتی، گروه سنجش از دور و GIS.
  2. حسنی رخ، س.، 1379، یافتن محل استقرار و مسیریابی پویا با استفاده از تکنیک‌های ژنتیک، پایان‌نامة کارشناسی ارشد، دانشگاه تربیت مدرس.
  3. خاکساری، ع.، نیازخانی، س.، قربانپور، ز.، 1391، بهینه‌یابی مسیر حمل‌ونقل کالا بین مراکز استان ایران، با استفاده از الگوریتم ژنتیک (GA)، مهندسی حمل‌ونقل، سال سوم، شمارة 3، صص. 292-281.
  4. خشایی‌پور، م.، نقدی‌زاده، م.، پارسافرد، م.، ۱۳۹۱، مسیریابی خودروهای حامل مواد خطرناک در شبکة معابر شهری (مطالعة موردی: شهر تهران)، دوازدهمین کنفرانس مهندسی حمل‌ونقل و ترافیک ایران، تهران، سازمان حمل‌ونقل و ترافیک تهران، معاونت حمل‌ونقل و ترافیک شهرداری تهران.
  5. رجبی، م.، منصوریان، ع.، علیمحمدی، ع.، طالعی، م.، 1389، بهینه‌سازی مکانی فرایند طراحی و برنامه‌ریزی شهری به‌کمک عملگرهای ابتکاری توسعه‌داده‌شده در قالب الگوریتم تکاملی چندهدفةNSGA-II ، سنجش از دور و GIS ایران، سال دوم، شمارة 3، صص. 42-21.
  6. مطیعیان، ح.، مسگری، م.س.، نعیمی، ا.، 1391، بهینه‌سازی مسیر تردد سرویس‌های حمل‌ونقل یک شرکت، با استفاده از خوشه‌بندی و الگوریتم ژنتیک، مهندسی حمل‌ونقل، سال سوم، شمارة 4، صص. 378-365.
  7. معصومی، ز.، صادقی نیارکی، ا.، مسگری، م.س.، 1390، به‌کارگیری الگوریتم کلونی مورچة چندمعیاره در سیستم‌های حمل‌ونقل هوشمند و کاربرمبنا، پژوهشنامة حمل‌ونقل، سال هشتم، شمارة اول، صص. 62-47.
  8. معصومی، ز.، منصوریان، ع.، مسگری، م.س.، 1389، کاربرد الگوریتم ژنتیک چندهدفه در مطالعات مکان‌یابی کاربری‌های صنعتی، سنجش از دور و GIS ایران، سال دوم، شمارة 4، صص. 22-1.
  9. میرزایی قمی، م.م.، آزاده‌دل، ی.، بهادر، م.، ۱۳۹۴، ارائة مدل جامع جهت تعیین مسیر بهینة دوچرخه در شبکة معابر شهری با تلفیق فرایند سلسله‌مراتبی و سیستم اطلاعات جغرافیایی GIS (محدودة مورد مطالعه: منطقة چهار شهر تهران)، چهاردهمین کنفرانس بین‌المللی مهندسی حمل‌ونقل و ترافیک، تهران، معاونت و سازمان حمل‌ونقل ترافیک.
  10. Ahmed, F. & Deb, K., 2013, Multi-Objective Optimal Path Planning Using Elitist Non-Dominated Sorting Genetic Algorithms, Soft Computing, Vol. 17, No. 7, PP. 1283–1299.
  11. Ahn, C.W. & Ramakrishna, R.S., 2002, A Genetic Algorithm for Shortest Path Routing Problem and the Sizing of Populations, IEEE Transaction on Evolutionary Computation, Vol. 6, No. 6, PP. 566–579.
  12. Bae, S.T., Hwang, H., Cho, G.S. & Goan, M.-J., 2007, Integrated GA-VRP Solver for Multi-Depot SYSTEM, Computers and Industrial Engineering, 53, PP. 233–240.
  13. Coello Coello, C.A., Lamont, G.B & Van Veldhuizen, D.A., 2007, Evolutionary Algorithms for Solving Multi-Objective Problems, Springer Science+Business Media, LLC.
  14. Datta, D., Deb, K. & Fonseca, C.M., 2007, Multi-Objective Evolutionary Algorithm for Land-Use Management Problem., International Journal of Computational Intelligence Research, 3(4), PP. 371–384.
  15. Deb, K., Pratap, A., Agarwal, S. & Meyarivan, T., 2002, A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II., IEEE Transaction on Evolutionary Computation, 6(2), PP. 182–197.
  16. Deb, K., 2001, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, LTD.
  17. Descrochers, M., Desrosiers, J. & Solomon, M., 1992, A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows, Operations Research, PP. 342–352.
  18. Dias, A.H.F. & Vasconcelos, J.A., 2002, Multiobjective Genetic Algorithms Applied to Solve Optimization Problems, IEEE, Transactions on Magnetics.
  19. Duque, D., Lozano, L., Medaglia, A.L., 2015, An Exact Method for the Objective Shortest Path Problem for Large-Scale Road Networks, European Journal of Operational Research, 243(3), PP. 788–797.
  20. Descrochers, M., Desrosiers, J. & Solomon, M., 1992, A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows, Operations Research, PP. 342–352.
  21. Geoffrion, A.M., Dyer, J.S. & Feinberg, A., 1972, An Interactive Approach for Multicriterion Optimization with an Application to the Operation of an Academic Department, Management Science, 19(4), PP. 335–368.
  22. Goldberg, D.E., 2007, Evolutionary Algorithms for Solving Multi-Objective Problems, Second Edition, Springer Science+Business Media, LLC, P. 810.
  23. Horn, J., Nafpliotis, N. & Goldberg, D.E., 1999, A Niched Pareto Genetic Algorithm for Multiobjective Optimization, In Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Computation, 1, PP. 82–87.
  24. Jiang, B., Xu, X., Yang, C., Li., R. & Terano., T., 2013, Solving Road-Network Congestion Problems by a Multi-objective Optimization Algorithm with Brownian Agent Model, Springer V(365) ,Computer and Information Science, PP. 36–48.
  25. Li, Y. & Guo, L., 2016, Multi-Objective Optimal Path Finding in Stochastic Time-Dependent Transportation Networks Considering Timeliness Reliability and Travel Expense, In Prognostics and System Health Management Conference (PHM-Chengdu), PP. 1–6.
  26. Li, Q., Zengc, Z., Zhanga, T., Li, J. & Zhongheng, Wu., 2011, Path-Finding through Flexible Hierarchical Road Networks: An Experiential Approach Using Taxi Trajectory Data, ELSEVIER, International Journal of Applied Earth Observation and Geoinformation, 13(1), PP. 110–119.
نشریه سنجش از دور و GIS ایران
دوره 9، شماره 3 - شماره پیاپی 3
اردیبهشت 1396
صفحه 111-126

فایل ها

هم رسانی

ارجاع به این مقاله

آمار