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

Document Type : علمی - پژوهشی

Authors

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

Abstract

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.

Keywords

References

  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.
Iranian Journal of Remote Sensing & GIS
Volume 9, Issue 3 - Serial Number 3
February 2018
Pages 111-126

Files

Share

How to cite

Statistics