آنالیز شبکه‌ی حمل و نقل

شبکهٔ حمل و نقل، یک شبکه یا گراف در فضای جغرافیایی است که زیرساختی را توصیف می‌کند، به گونه‌ای که حرکت یا جریان را مجاز و محدود می‌کند.^[۱] به عنوان مثال می‌توان به شبکه‌های جاده‌ای، ترابری ریلی، مسیرهای هوایی، خطوط لوله، قنات‌ها، خطوط برق و … اشاره کرد. نمایش دیجیتالی این شبکه‌ها، و روش‌های تجزیه و تحلیل آنها، بخشی اصلی از آنالیز فضایی، سامانه‌های اطلاعات جغرافیایی، سازمان‌های عمومی و مهندسی حمل و نقل است. آنالیز شبکه، کاربردی از نظریه‌ها و الگوریتم‌های گراف تئوری، و شکلی از آنالیز مجاورت است.

تاریخ[ویرایش]

کاربرد نظریهٔ گراف در پدیده‌های جغرافیایی در اوایل کار شناخته شد. در حقیقت، بسیاری از مشکلات و نظریه‌های اولیه‌ای که نظریه پردازان گراف اراده به حل آن‌ها کردند، از موقعیت‌های جغرافیایی الهام گرفته‌اند، مانند مسئله هفت پل کونیگسبرگ، که یکی از پایه‌های اصلی نظریهٔ گراف بود که توسط لئونارد اویلر در سال ۱۷۳۶ حل شد.^[۲]

در دههٔ ۱۹۷۰، این ارتباط توسط توسعه دهندگان اولیه سیستم‌های اطلاعات جغرافیایی، که آن را در ساختار داده‌های توپولوژیک چند ضلعی‌ها (که در اینجا موضوعیت چندانی ندارد) و آنالیز شبکه‌های حمل و نقل، برقرار شد. کارهای اولیه، مانند تینکلر (۱۹۷۷)، بیشتر روی شبکه‌های شماتیک ساده متمرکز بودند، احتمالاً به دلیل کمبود حجم قابل توجهی از داده‌های خطی و پیچیدگی محاسباتی بسیاری از الگوریتم‌ها. اجرای کامل الگوریتم‌های تجزیه و تحلیل شبکه در نرم‌افزار GIS تا دههٔ ۱۹۹۰ ظاهر نشده‌است،^[۳]^[۴] اما امروزه ابزارهای پیشرفته‌ای معمولاً در دسترس هستند.

دادهٔ شبکه[ویرایش]

تجزیه و تحلیل شبکه نیاز به داده‌های دقیق دارد که عناصر شبکه و خصوصیات آن را نشان دهد.^[۵] هستهٔ اصلی یک مجموعه دادهٔ شبکه، یک لایه بُرداری از چندخطی‌ها است که مسیرهای سفر را نشان می‌دهد، چه مسیرهای جغرافیایی دقیق یا چه نمودارهای شماتیک، معروف به یال‌ها. به علاوه، اطلاعاتی دربارهٔ توپولوژی شبکه نیاز است، که رابطهٔ بین خطوط را نشان می‌دهد، و بنابراین امکان حمل و نقل از یک خط به خط دیگر را فراهم می‌کند. به‌طور معمول، این نقاط اتصال یا گره‌ها، در مجموعهٔ دادهٔ اضافی، شامل می‌شوند.^[۶]

یال‌ها و گره‌ها، به ویژگی‌های مربوط به حرکت یا جریان نسبت داده می‌شوند:

ظرفیت، اندازه‌گیری هرگونه محدودیت در حجم جریان مجاز، مانند تعداد باندها در جاده، پهنای باند مخابراتی یا قطر لوله.
مقاومت، اندازه‌گیری مقاومت در برابر جریان یا سرعت جریان مانند محدودیت سرعت یا ممنوع بودن دور برگردان در تقاطع خیابان.
هزینه‌ی جمع شده از طریق سفر مجردی در امتداد یال یا در گره، زمان سپری شدهٔ عمومی که مطابق با اصل اصطکاک فاصله است. به عنوان مثال، گره‌ای در یک شبکهٔ خیابانی، ممکن است به زمان‌های متفاوتی برای پیچیدن به چپ یا راست در یک تقاطع مشخص، نیاز داشته باشد. چنین هزینه‌هایی می‌تواند در طول زمان متغیر باشد، مانند الگوی زمان طی یک خیابان شهری، بسته به چرخه‌های روزانهٔ حجم ترافیک.
حجم جریان، اندازه‌گیری خود حرکتِ در حال انجام است. که ممکن است اندازه‌گیری‌های خاص رمزگذاری شده با زمان باشد که با استفاده از شبکه‌های حسگر مانند شمارنده‌های ترافیک یا روندهای کلی در طی یک دوره زمانی مانند میانگین سالانه ترافیک روزانه (AADT) جمع‌آوری شده‌است.

روش‌های آنالیز[ویرایش]

طیف گسترده‌ای از روش‌ها، الگوریتم‌ها و تکنیک‌ها برای حل مشکلات و مسائل مربوط به جریان شبکه به وجود آمده‌است. برخی از این موارد بین انواع شبکه‌های حمل و نقل مشترک هستند، در حالی که برخی دیگر، مخصوص دامنه‌های اپلیکیشن خاص هستند.^[۷] بسیاری از این الگوریتم‌ها در نرم‌افزارهای تجاری و منبع باز (open-source) GIS، پیاده‌سازی شده‌اند مانند GRASS GIS و اکستنشن Network Analyst به Esri ArcGIS.

مسیریابی بهینه[ویرایش]

یکی از ساده‌ترین و متداول‌ترین کارها در یک شبکه، یافتن مسیر بهینهٔ اتصال دو نقطه در طول شبکه است. منظور از بهینه، به حداقل رساندن بخشی از هزینه‌ها است مانند مسافت، انرژی یا زمان.^[۸] یک مثال متداول، یافتن مسیر در شبکهٔ خیابانی است، که تقریباً ویژگی همهٔ برنامهٔ نقشهٔ وب مانند گوگل مپس (google maps) است. محبوب‌ترین راه حل، که در بیشتر نرم‌افزارهای GIS و نقشه‌برداری استفاده می‌شود، الگوریتم دایکسترا است.^[۹]

علاوه بر مسیریابی نقطه به نقطهٔ پایه‌ای، مشکلات مسیریابی مرکب نیز رایج هستند. مسئلهٔ فروشندهٔ دوره‌گرد، بهینهٔ (حداقل مسافت/هزینه) ترتیب و مسیر برای رسیدن به تعدادی مقصد مشخص را می‌خواهد. این یک مشکل NP سخت است، اما حل آن در فضای شبکه تا حدودی آسان‌تر از فضای نامحدود است به دلیل مجموعه جواب کوچکتر.^[۱۰] مسئلهٔ مسیریابی وسیله نقلیه، یک کلی گویی در این مورد است که اجازه می‌دهد چندین مسیر همزمان برای رسیدن به مقصد وجود داشته باشد. مسئلهٔ بازرسی مسیر یا «پستچی چینی» مسیر بهینه (کمترین مسافت/هزینه) را که از هر یال عبور می‌کند، می‌خواهد. یک برنامه متداول، مسیریابی ماشین‌های جمع‌آوری زباله است که به نظر می‌رسد این مسئله با الگوریتم‌هایی که دارای پیچیدگی زمانی چند جمله‌ای هستند، راحت‌تر قابل حل باشد.

آنالیز مکان[ویرایش]

هدف این دسته از مشکلات، یافتن مکان بهینه برای یک یا چند مکان در امتداد شبکه است. منظور از بهینه، به حداقل رساندن هزینهٔ سفر برای رفت یا برگشت بین مجموعه‌ای از نقاط در شبکه. یک مثال متداول تعیین محل انبار برای به حداقل رساندن هزینه‌های حمل و نقل به خرده فروشی‌ها برای به حداقل رساندن زمان سفر از محل سکونت مشتریان آن است. در فضای نامحدود (مختصات دکارتی)، این یک مسئلهٔ NP سخت است که نیاز به راه حل‌های ابتکاری مانند الگوریتم لوید دارد، اما در یک فضای شبکه می‌توان آن را به‌طور قطعی حل کرد.^[۱۱]

اپلیکیشن‌های خاص معمولاً محدودیت‌های بیشتری به مسئله اضافه می‌کنند، مانند مکان تأسیساتی که از قبل وجود داشتند یا رقابتی هستند، ظرفیت تأسیسات یا حداکثر هزینه.

مناطق خدماتی[ویرایش]

یک منطقهٔ سرویس شبکه، مشابه بافر در فضای نامحدود است، تصویری از منطقه‌ای است که می‌تواند از یک نقطه (به‌طور معمول یک مرکز خدمات) در کمتر از یک فاصلهٔ مشخص یا سایر هزینه‌ها به آن برسد.^[۱۲] به عنوان مثال، منطقه خدمات بهینه برای یک ایستگاه آتش‌نشانی، جاهایی است که بتوان به بخش‌های خیابان، در مدت زمان کوتاه‌تر برسد. هنگامی که چندین تسهیلات وجود دارد، هر یال به نزدیک‌ترین مرکز اختصاص داده می‌شود و نتیجه‌ای مشابه نمودار ورنوی تولید می‌کند.^[۱۳]

تحلیل خطا[ویرایش]

یک کاربرد متداول در شبکه‌های خدمت‌های عمومی، شناسایی مکان‌های احتمالی خرابی یا گسیختگی در شبکه است (که غالباً پنهان می‌شود یا مشاهدهٔ آن به‌طور مستقیم دشوار است)، از گزارش‌هایی که به راحتی قابل شناسایی است، مانند شکایت‌های مشتری، استنباط می‌شود.

مهندسی حمل و نقل[ویرایش]

ترافیک با استفاده از روش‌های فیزیک آماری به‌طور گسترده مورد مطالعه قرار گرفته‌است.^[۱۴]^[۱۵]^[۱۶]اخیراً یک شبکهٔ حمل و نقل واقعی در پکن با استفاده از یک رویکرد شبکه و تئوری نفوذ، مورد مطالعه قرار گرفته‌است. این تحقیق نشان داد که می‌توان کیفیت ترافیک جهانی در یک شهر را در هر زمان از روز، با استفاده از آستانه نفوذ توصیف کرد (شکل ۱). در مقاله‌های اخیر، تئوری نفوذ، برای مطالعهٔ تراکم ترافیک در یک شهر استفاده شده‌است. کیفیت ترافیک جهانی در یک شهر در یک زمان مشخص، با پارامتر آستانهٔ بحرانی نفوذ، اندازه‌گیری می‌شود. آستانه بحرانی نشان دهندهٔ سرعتی است که می‌توان در بخش بزرگی از شبکهٔ شهر حرکت کرد. این روش قادر به شناسایی گلوگاه‌های تکراری ترافیک است.^[۱۷] نمایندگان واجب که توصیف کنندهٔ توزیع میزان پراکندگی ترافیک هستند، مشابه تئوری نفوذ می‌باشند.^[۱۸] همچنین مشخص شده‌است که در ساعت‌های شلوغی، شبکهٔ ترافیک می‌تواند چندین حالت قابل متغیر در اندازه‌های مختلف شبکه و رد و بدل بین این حالت‌ها داشته باشد.^[۱۹]

اخیراً یک مطالعه تجربی دربارهٔ توزیع اندازه ترافیک توسط Zhang و همکاران انجام شده‌است.^[۲۰] آنها یک قانون تقریبی جهانی قدرت برای توزیع حجم ترافیک پیدا کردند.

روشی برای شناسایی بخش‌های فعال از خیابان‌های مکانی-زمانی که نشان دهندهٔ جریان روان ترافیک در یک شهر است، توسط سِرُک و همکاران ایجاد شده‌است.^[۲۱] G. Li و همکاران روشی را برای طراحی یک شبکهٔ حمل و نقل بهینهٔ دو لایه، در یک شهر توسعه داد.^[۲۲]

الگوهای جریان ترافیک[ویرایش]

الگوهای جریان ترافیکیِ رودخانه مانند، در مناطق شهری در شهرهای بزرگ در ساعات شلوغی و غیر شلوغی توسط Yohei Shida و همکاران بررسی شده‌است.^[۲۳]

منابع[ویرایش]

↑ Barthelemy, Marc (2010). "Spatial Networks". Physics Reports. 499 (1–3): 1–101. arXiv:1010.0302. Bibcode:2011PhR...499....1B. doi:10.1016/j.physrep.2010.11.002. S2CID 4627021.
↑ Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40.
↑ Ahuja R K, Magnanti T L, Orlin J B (1993) Network flows: Theory, algorithms and applications. Prentice Hall, Englewood Cliffs, NJ, USA
↑ Daskin M S (1995) Network and discrete location — models, algorithms and applications. Wiley, NJ, USA
↑ "What is a network dataset?". ArcGIS Pro Documentation. Esri.
↑ "Network elements". ArcGIS Pro Documentation. Esri. Retrieved 17 March 2021.
↑ deSmith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). "7.2.1 Overview - network and locational analysis". Geospatial Analysis: A Comprehensive Guide to Principles, Techniques, and Software Tools (6th revised ed.).
↑ Worboys, Michael; Duckham, Matt (2004). "5.7 Network Representation and Algorithms". GIS: A Computing Perspective (2nd ed.). CRC Press. pp. 211–218.
↑ Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390. S2CID 123284777.
↑ "v.net.salesman command". GRASS GIS manual. OSGEO. Retrieved 17 March 2021.
↑ deSmith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). "7.4.2 Larger p-median and p-center problems". Geospatial Analysis: A Comprehensive Guide to Principles, Techniques, and Software Tools (6th revised ed.).
↑ deSmith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). "7.4.3 Service areas". Geospatial Analysis: A Comprehensive Guide to Principles, Techniques, and Software Tools (6th revised ed.).
↑ "v.net.alloc command". GRASS GIS documentation. OSGEO. Retrieved 17 March 2021.
↑ Helbing, D (2001). "Traffic and related self-driven many-particle systems". Reviews of Modern Physics. 73 (4): 1067–1141. arXiv:cond-mat/0012229. Bibcode:2001RvMP...73.1067H. doi:10.1103/RevModPhys.73.1067. S2CID 119330488.
↑ S., Kerner, Boris (2004). The Physics of Traffic: Empirical Freeway Pattern Features, Engineering Applications, and Theory. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-540-40986-1. OCLC 840291446.
↑ Wolf, D E; Schreckenberg, M; Bachem, A (June 1996). Traffic and Granular Flow. Traffic and Granular Flow (به انگلیسی). WORLD SCIENTIFIC. pp. 1–394. doi:10.1142/9789814531276. ISBN 9789810226350.
↑ Li, Daqing; Fu, Bowen; Wang, Yunpeng; Lu, Guangquan; Berezin, Yehiel; Stanley, H. Eugene; Havlin, Shlomo (2015-01-20). "Percolation transition in dynamical traffic network with evolving critical bottlenecks". Proceedings of the National Academy of Sciences (به انگلیسی). 112 (3): 669–672. Bibcode:2015PNAS..112..669L. doi:10.1073/pnas.1419185112. ISSN 0027-8424. PMC 4311803. PMID 25552558.
↑ Switch between critical percolation modes in city traffic dynamics, G Zeng, D Li, S Guo, L Gao, Z Gao, HE Stanley, S Havlin, Proceedings of the National Academy of Sciences 116 (1), 23-28 (2019)
↑ G. Zeng, J. Gao, L. Shekhtman, S. Guo, W. Lv, J. Wu, H. Liu, O. Levy, D. Li, ... (2020). "Multiple metastable network states in urban traffic". Proceedings of the National Academy of Sciences. 117 (30): 17528–17534. doi:10.1073/pnas.1907493117. PMC 7395445. PMID 32661171.{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)
↑ Scale-free resilience of real traffic jams, Limiao Zhang, Guanwen Zeng, Daqing Li, Hai-Jun Huang, H Eugene Stanley, Shlomo Havlin, Proceedings of the National Academy of Sciences 116(18), 8673-8678 (2019)
↑ Nimrod Serok, Orr Levy, Shlomo Havlin, Efrat Blumenfeld-Lieberthal (2019). "Unveiling the inter-relations between the urban streets network and its dynamic traffic flows: Planning implication". SAGE Publications. 46 (7): 1362.{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)
↑ G. Li, S.D.S. Reis, A.A. Moreira, S. Havlin, H.E. Stanley, J.S. Andrade Jr. (2010). "Towards Design Principles for Optimal Transport Networks". Phys. Rev. Lett. 104 (1): 018701. arXiv:0908.3869. Bibcode:2010PhRvL.104a8701L. doi:10.1103/PhysRevLett.104.018701. PMID 20366398. S2CID 119177807.{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)
↑ Y. Shida, H. Takayasu, S. Havlin, M. Takayasu (2020). "Universal scaling laws of collective human flow patterns in urban regions". Scientific Reports. 10 (1): 21405. doi:10.1038/s41598-020-77163-2. PMC 7722863. PMID 33293581.{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)

[Bart-1] Barthelemy, Marc (2010). "Spatial Networks". Physics Reports. 499 (1–3): 1–101. arXiv:1010.0302. Bibcode:2011PhR...499....1B. doi:10.1016/j.physrep.2010.11.002. S2CID 4627021.

[2] Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40.

[3] Ahuja R K, Magnanti T L, Orlin J B (1993) Network flows: Theory, algorithms and applications. Prentice Hall, Englewood Cliffs, NJ, USA

[4] Daskin M S (1995) Network and discrete location — models, algorithms and applications. Wiley, NJ, USA

[5] "What is a network dataset?". ArcGIS Pro Documentation. Esri.

[6] "Network elements". ArcGIS Pro Documentation. Esri. Retrieved 17 March 2021.

[7] Smith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). "7.2.1 Overview - network and locational analysis". Geospatial Analysis: A Comprehensive Guide to Principles, Techniques, and Software Tools (6th revised ed.).

[Worboys-8] Worboys, Michael; Duckham, Matt (2004). "5.7 Network Representation and Algorithms". GIS: A Computing Perspective (2nd ed.). CRC Press. pp. 211–218.

[Dijkstra1959-9] Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390. S2CID 123284777.

[10] "v.net.salesman command". GRASS GIS manual. OSGEO. Retrieved 17 March 2021.

[11] Smith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). "7.4.2 Larger p-median and p-center problems". Geospatial Analysis: A Comprehensive Guide to Principles, Techniques, and Software Tools (6th revised ed.).

[12] Smith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). "7.4.3 Service areas". Geospatial Analysis: A Comprehensive Guide to Principles, Techniques, and Software Tools (6th revised ed.).

[13] "v.net.alloc command". GRASS GIS documentation. OSGEO. Retrieved 17 March 2021.

[14] Helbing, D (2001). "Traffic and related self-driven many-particle systems". Reviews of Modern Physics. 73 (4): 1067–1141. arXiv:cond-mat/0012229. Bibcode:2001RvMP...73.1067H. doi:10.1103/RevModPhys.73.1067. S2CID 119330488.

[15] S., Kerner, Boris (2004). The Physics of Traffic: Empirical Freeway Pattern Features, Engineering Applications, and Theory. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-540-40986-1. OCLC 840291446.

[16] Wolf, D E; Schreckenberg, M; Bachem, A (June 1996). Traffic and Granular Flow. Traffic and Granular Flow (به انگلیسی). WORLD SCIENTIFIC. pp. 1–394. doi:10.1142/9789814531276. ISBN 9789810226350.

[17] Li, Daqing; Fu, Bowen; Wang, Yunpeng; Lu, Guangquan; Berezin, Yehiel; Stanley, H. Eugene; Havlin, Shlomo (2015-01-20). "Percolation transition in dynamical traffic network with evolving critical bottlenecks". Proceedings of the National Academy of Sciences (به انگلیسی). 112 (3): 669–672. Bibcode:2015PNAS..112..669L. doi:10.1073/pnas.1419185112. ISSN 0027-8424. PMC 4311803. PMID 25552558.

[18] Switch between critical percolation modes in city traffic dynamics, G Zeng, D Li, S Guo, L Gao, Z Gao, HE Stanley, S Havlin, Proceedings of the National Academy of Sciences 116 (1), 23-28 (2019)

[19] G. Zeng, J. Gao, L. Shekhtman, S. Guo, W. Lv, J. Wu, H. Liu, O. Levy, D. Li, ... (2020). "Multiple metastable network states in urban traffic". Proceedings of the National Academy of Sciences. 117 (30): 17528–17534. doi:10.1073/pnas.1907493117. PMC 7395445. PMID 32661171.{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)

[20] Scale-free resilience of real traffic jams, Limiao Zhang, Guanwen Zeng, Daqing Li, Hai-Jun Huang, H Eugene Stanley, Shlomo Havlin, Proceedings of the National Academy of Sciences 116(18), 8673-8678 (2019)

[21] Nimrod Serok, Orr Levy, Shlomo Havlin, Efrat Blumenfeld-Lieberthal (2019). "Unveiling the inter-relations between the urban streets network and its dynamic traffic flows: Planning implication". SAGE Publications. 46 (7): 1362.{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)

[22] G. Li, S.D.S. Reis, A.A. Moreira, S. Havlin, H.E. Stanley, J.S. Andrade Jr. (2010). "Towards Design Principles for Optimal Transport Networks". Phys. Rev. Lett. 104 (1): 018701. arXiv:0908.3869. Bibcode:2010PhRvL.104a8701L. doi:10.1103/PhysRevLett.104.018701. PMID 20366398. S2CID 119177807.{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)

[23] Y. Shida, H. Takayasu, S. Havlin, M. Takayasu (2020). "Universal scaling laws of collective human flow patterns in urban regions". Scientific Reports. 10 (1): 21405. doi:10.1038/s41598-020-77163-2. PMC 7722863. PMID 33293581.{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

[۱۰]

[۱۱]

[۱۲]

[۱۳]

[۱۴]

[۱۵]

[۱۶]

[۱۷]

[۱۸]

[۱۹]

[۲۰]

[۲۱]

[۲۲]

[۲۳]