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

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

تاریخ

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

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

دادهٔ شبکه

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

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

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

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

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

مسیریابی بهینه

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

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

آنالیز مکان

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

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

مناطق خدماتی

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

تحلیل خطا

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

مهندسی حمل و نقل

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

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

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

شکل ۱: نفوذ شبکه‌های ترافیکی در یک روز معمول در پکن. A دسته‌های با سرعت بالا را نشان می‌دهد. در B می‌توان دسته‌ها را در آستانهٔ بحرانی، مشاهده کرد. C حالت کم سرعت را نشان می‌دهد که در آن می‌توان به کل شهر رسید. در D، می‌توان رفتار نفوذ بزرگترین (سبز) و دومین اجزای بزرگ (نارنجی) را به عنوان تابعی از سرعت نسبی مشاهده کرد. E آستانهٔ حساس (${\displaystyle q_{c}}$) را در طول روزهای کاری و آخر هفته، نشان می‌دهد. ${\displaystyle q_{c}}$ بالا، به معنی ترافیک جهانی خوب در حالی که ${\displaystyle q_{c}}$ کم، ترافیک بدی است - در ساعت شلوغی.

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

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