الگوریتم های ژئو محاسباتی کارآمد برای ساخت منشورهای فضا-زمان در شبکه های جاده ای

خلاصه

منشور فضا-زمان (STP) یک مفهوم کلیدی در جغرافیای زمانی برای تجزیه و تحلیل رفتار فعالیت-سفر انسان تحت محدودیت های مختلف فضا-زمان است. اکثر مطالعات جغرافیایی زمانی موجود از یک الگوریتم ساده برای ساخت STP ها در شبکه های جاده ای با استفاده از دو جستجوی کوتاه ترین مسیر یک به همه استفاده می کنند. با این حال، این الگوریتم ساده می تواند سربار محاسباتی قابل توجهی را معرفی کند، با توجه به این واقعیت که پیوندهای قابل دسترسی در یک STP عموماً بخش کوچکی از کل شبکه هستند. برای پرداختن به این موضوع، یک الگوریتم زمین محاسباتی کارآمد به نام NTP-A* پیشنهاد شده است. الگوریتم NTP-A* پیشنهادی از تکنیک‌های A* و شاخه و کران برای دور انداختن پیوندهای غیرقابل دسترس در طول دو جستجوی کوتاه‌ترین مسیر استفاده می‌کند و در نتیجه عملکرد ساخت STP را بهبود می‌بخشد. آزمایش‌های محاسباتی جامع برای نشان دادن مزیت محاسباتی الگوریتم پیشنهادی انجام می‌شود. چندین تکنیک پیاده‌سازی، از جمله تکنیک تصحیح برچسب و تکنیک برچسب‌گذاری پیوند گره ترکیبی، مورد بحث و تجزیه و تحلیل قرار می‌گیرند. نتایج تجربی نشان می‌دهد که الگوریتم NTP-A* پیشنهادی می‌تواند به طور قابل‌توجهی عملکرد ساخت و ساز STP را در شبکه‌های جاده‌ای در مقیاس بزرگ با ضریب ۱۰۰ در مقایسه با الگوریتم‌های موجود بهبود بخشد.

کلید واژه ها:

منشور فضا-زمان (STP) ؛ شبکه های جاده ای ؛ الگوریتم جغرافیایی محاسباتی ; جغرافیای زمانی ; تجزیه و تحلیل داده های بزرگ

1. معرفی

جغرافیای زمانی برای تجزیه و تحلیل حرکات و فعالیت های انسان در فضا و زمان قدرتمند است [ 1 ]. به‌جای پیش‌بینی مستقیم رفتار سفر-فعالیت، جغرافیای زمان عمدتاً بر امکان‌پذیری یک فرد برای شرکت در فعالیت‌ها تحت محدودیت‌های فضا-زمان مختلف تمرکز دارد [ 2 ]. در هسته جغرافیای زمانی، مدل منشور فضا-زمان (STP) قرار دارد که گستره های فضا-زمانی را به تصویر می کشد که می تواند به صورت فیزیکی توسط فرد از مکان های مشخص شده در یک بودجه زمانی مشخص به آن دست یابد. این مدل STP به طور گسترده برای کاربردهای مختلف، مانند اندازه گیری دسترسی فردی به خدمات شهری استفاده شده است [ 3 ، 4 ، 5 ، 6 ، 7]، و فرمول‌بندی مدل‌های مبتنی بر فعالیت تقاضای سفر [ 8 ، 9 ، 10 ، 11 ].

جغرافیای زمانی برای اولین بار توسط Torsten Hägerstrand در دهه 1970 معرفی شد [ 1 ]. در دهه‌های پس از معرفی، جغرافیای زمانی تا حدودی در پس‌زمینه محو شد [ 12 ]، عمدتاً به دلیل فقدان الگوریتم‌های محاسباتی جغرافیایی و داده‌های حرکت در سطح فردی. با پیشرفت فناوری اطلاعات جغرافیایی (GIS) در دهه 1990، دو دهه اخیر شاهد تجدید حیات جغرافیای زمانی در ادبیات بوده است. تلاش‌های تحقیقاتی قابل توجهی برای بهبود مدل‌های STP برای نشان دادن گستره‌های فضا-زمان قابل دسترس افراد در مناطق پیچیده شهری انجام شده است. میلر با درک اینکه حرکات انسان در مناطق شهری معمولاً توسط شبکه های جاده ای محدود می شود [ 13]] یک مدل STP مبتنی بر شبکه (یا به نام منشور زمان شبکه، NTP) را پیشنهاد کرد. محققان دیگر این مدل NTP را با در نظر گرفتن پیچیدگی‌های محیط سفر، از جمله محدودیت‌های نوبتی [ 14 ] ، شرایط ترافیکی پویا و ناهمگن [ 15 ، 16 ] و عدم قطعیت‌های زمان سفر [ 17،18 ] بهبود دادند . چن و همکاران [ 19 ] مدل NTP را به شبکه های حمل و نقل عمومی گسترش دهید. یک الگوریتم جغرافیایی محاسباتی برای ساخت موثر STPها در شبکه های حمل و نقل عمومی با استفاده از تکنیک های A* و شاخه و کران توسعه داده شد. چندین ابزار مفید نیز برای تجزیه و تحلیل بصری NTPها در شبکه های جاده ای واقعی توسعه یافته اند [ 20 , 21 , 22].

در سال‌های اخیر، به دلیل داده‌های بزرگ فضایی-زمانی در حال ظهور، جمع‌آوری‌شده توسط انواع فن‌آوری‌های مکانی، از جمله مسیرهای انسان و وسیله نقلیه جمع‌آوری‌شده توسط دستگاه‌های GPS (سیستم موقعیت‌یابی جهانی)، سوابق تلفن همراه، تجدید حیات گسترده‌تری از مطالعات جغرافیایی زمانی صورت گرفته است. داده‌های کارت هوشمند، ورود به شبکه‌های اجتماعی، و غیره. این داده‌های بزرگ مکانی-زمانی فرصت بی‌سابقه‌ای را برای مطالعات جغرافیایی زمانی فراهم می‌کند تا الگوهای تحرک مردم و تعاملات آن‌ها با محیط شهری را آشکار کند [ 23 ، 24 ، 25 ، 26 ، 27 ، 28 ، 29 ، 30]. برای حمایت از چنین مطالعات زمانی-جغرافیایی در عصر داده‌های بزرگ مکانی-زمانی، الگوریتم‌های ژئومحاسباتی کارآمد برای ساخت NTP در شبکه‌های جاده‌ای در مقیاس بزرگ به شدت مورد نیاز است.

در بیشتر مطالعات قبلی جغرافیایی زمانی، NTP ها توسط یک الگوریتم ساده ساخته می شوند [ 31]، که از دو جستجوی کوتاه ترین مسیر یک به همه، بر اساس الگوریتم Dijkstra استفاده می کند. این الگوریتم ساده از این پس برای سهولت به عنوان الگوریتم NTP-Dij شناخته می شود. در الگوریتم NTP-Dij، ابتدا جستجوی کوتاه‌ترین مسیر رو به جلو از مبدا انجام می‌شود تا زودترین زمان رسیدن در هر گره مشخص شود. سپس، جستجوی کوتاهترین مسیر به عقب از مقصد انجام می شود تا آخرین زمان حرکت در هر گره به دست آید. در نهایت، گره های قابل دسترسی (و پیوندها) را می توان با بررسی اینکه آیا اولین زمان رسیدن آنها بزرگتر از آخرین زمان خروج است یا خیر، تعیین می شود. چنین الگوریتم NTP-Dij با استفاده مستقیم از الگوریتم کلاسیک کوتاهترین مسیر (یعنی الگوریتم Dijkstra) آسان است. با این حال، نیاز به کاوش در کل شبکه دو بار دارد و منجر به سربار محاسباتی قابل توجهی می شود. با توجه به این واقعیت که گره های قابل دسترسی در NTP عموما تنها بخش کوچکی از کل شبکه هستند. برای کاهش تعداد گره های کاوش شده، Kuijpers و Othman [28 و 29 ] یک الگوریتم (به نام NTP-SN در این مطالعه) برای ساخت NTP در یک شبکه فرعی به جای کل شبکه پیشنهاد کرد. زیرشبکه با انتخاب گره ها و پیوندهای درون STP در فضای مسطح تولید می شود. با این وجود، مزیت محاسباتی این الگوریتم NTP-SN حاشیه ای است، زیرا STP در فضای مسطح به طور کلی در مقایسه با NTP واقعی بسیار بزرگ است [ 28 ، 29 ]. علاوه بر این، اگرچه چندین الگوریتم ساخت NTP توسعه یافته است، کمبود آزمایش‌های عددی در ادبیات برای بررسی سیستماتیک عملکرد محاسباتی الگوریتم‌های ساخت NTP موجود در شبکه‌های جاده واقعی وجود دارد.

برای پر کردن این شکاف، این مطالعه به بررسی مدل‌ها و الگوریتم‌های ژئومحاسباتی برای ساخت موثر NTP در شبکه‌های جاده‌ای واقعی می‌پردازد. این مطالعه از جنبه های زیر به ادبیات جغرافیای زمانی کمک می کند:

در مرحله اول، یک مدل NTP بهبود یافته با در نظر گرفتن پیچیدگی‌های شبکه‌های جاده‌ای، از جمله محدودیت‌های پیچ و جاده‌های تقسیم‌شده/تقسیم نشده، پیشنهاد می‌شود. مدل NTP پیشنهادی، جاده‌های تقسیم‌شده و تقسیم‌نشده را متمایز می‌کند و به افراد اجازه می‌دهد تا دوربرگردان انجام دهند و به پیوندهای جزئی در جاده‌های تقسیم نشده دسترسی داشته باشند. بنابراین، مدل پیشنهادی، نمایش واقعی NTP ها را در شبکه های جاده ای افزایش می دهد.

ثانیا، یک الگوریتم زمین محاسباتی کارآمد، به نام NTP-A*، برای ساخت NTPها در شبکه های جاده ای در مقیاس بزرگ توسعه یافته است. در الگوریتم NTP-A* پیشنهادی، محدودیت‌های پیچ و پیوندهای نیمه قابل دسترسی در جاده‌های تقسیم نشده به صراحت در نظر گرفته شده‌اند. تکنیک‌های A* و شاخه و کران برای بهبود عملکرد ساخت NTP با دور انداختن پیوندهای غیرقابل دسترس در طول جستجوهای کوتاه‌ترین مسیر، استفاده می‌شوند. تکنیک‌های اصلاح برچسب و برچسب‌گذاری پیوند گره ترکیبی نیز به منظور بهبود عملکرد ساخت NTP معرفی شده‌اند. بنابراین، الگوریتم NTP-A* پیشنهادی به طور قابل توجهی عملکرد ساخت و ساز NTP را در شبکه های جاده ای در مقیاس بزرگ بهبود می بخشد.

سوم، یک مطالعه موردی جامع با استفاده از چندین شبکه جاده واقعی برای بررسی عملکرد محاسباتی الگوریتم پیشنهادی NTP-A* انجام شده است. دو الگوریتم ساخت NTP موجود، NTP-Dij و NTP-SN نیز برای مقاصد مقایسه پیاده سازی شده اند. چندین تکنیک کاشت (از جمله تکنیک A *، تکنیک شاخه و کران، تکنیک تصحیح برچسب و تکنیک برچسب‌گذاری پیوند گره هیبریدی) در ساخت NTP مورد بررسی و بحث قرار می‌گیرند. نتایج مطالعه موردی نشان می‌دهد که الگوریتم NTP-A* پیشنهادی می‌تواند به طور قابل‌توجهی الگوریتم‌های NTP-Dij و NTP-SN موجود را با ضریب 100 در شبکه‌های جاده‌ای در مقیاس بزرگ بهبود بخشد.

ساختار باقیمانده این مقاله به شرح زیر است. در بخش بعدی، مدل کلاسیک STP در فضای مسطح به اختصار معرفی می شود تا زمینه لازم را فراهم کند. مدل NTP بهبود یافته در بخش 3 معرفی شده است . الگوریتم NTP-A* پیشنهادی در بخش 4 ارائه شده است . آزمایش‌های محاسباتی با استفاده از شبکه‌های جاده‌ای در دنیای واقعی در بخش 5 گزارش شده‌اند . در نهایت، نتیجه گیری و توصیه های تحقیقاتی آتی در بخش 6 ارائه شده است .

2. مدل کلاسیک منشور فضا-زمان در فضای مسطح

این بخش به طور خلاصه مدل کلاسیک فضا-زمان (STP) را در فضای مسطح معرفی می کند. شکل 1 این مدل منشور را در یک فضای سه بعدی (3 بعدی) نشان می دهد که در آن محورهای x و y فضای جغرافیایی دو بعدی (2D) و محور t نشان دهنده زمان است. فرض کنید فردی در حال برنامه ریزی برای انجام دو فعالیت ثابت در مبدا است

o = (x_{o}, y_{o})

و نمونه زمانی

t_{o}

، و مقصد

d = (x_{d}, y_{d})

و نمونه زمانی

t_{d}

، به ترتیب. STP محدوده های فضا-زمانی را برای فرد تعیین می کند تا فعالیت انعطاف پذیر دیگری را بین این دو فعالیت ثابت برنامه ریزی کند. از نظر تحلیلی، STP را می توان با تقاطع یک مخروط جلو، یک مخروط عقب و یک استوانه ساخت. مخروط جلو،

FC (t)

، شامل تمام مکان هایی است که می توان از مبدا در آن زمان به آنها دسترسی داشت

t

; مخروط عقب،

BC (t)

، شامل تمام مکان هایی است که با توجه به زمان باقی مانده می توانند به مقصد برسند

t_{s} - t

; و سیلندر،

CY (t)

، تمام مکان های جغرافیایی را در محدوده مسیر بالقوه (PPA) مشخص می کند. با توجه به مرجع [ 2 ]، STP در فضای مسطح می تواند به طور رسمی بیان شود

STP (t) = FC (t) \cap BC (t) \cap CY (t)

(1)

FC (t) = {w | t \geq تی o + تی o w E ، t \leq تی د}

(2)

قبل از میلاد (t) = {w | t \leq تی د - تی w d E ، t \geq تی o}

(3)

CY (t) = {w | تی o w E + تی w d E \leq تی د - تی o - ج دقیقه ، تی o \leq t < تی د}

(4)

جایی که $c_{min}$ حداقل مدت زمان مشارکت در فعالیت های انعطاف پذیر است، $t_{E}^{o w}$ زمان سفر اقلیدسی از مبدأ تا یک مکان است $w = (x_{w}, y_{w})$ ، و $t_{E}^{w d}$ زمان سفر اقلیدسی از محل است $w$ به مقصد در فضای مسطح، زمان‌های سفر اقلیدسی (یعنی $t_{E}^{o w}$ و $t_{E}^{w d}$ ) را می توان به سادگی به عنوان فواصل اقلیدسی محاسبه کرد (که با نشان داده می شوند $d_{E}^{o w}$ و $d_{E}^{w d}$ ) بین این دو مکان تقسیم بر حداکثر سرعت سفر $v^{max}$ .

طرح STP بر روی فضای جغرافیایی دوبعدی یک PPA را تشکیل می‌دهد که شامل تمام مکان‌های قابل دسترس برای مشارکت در فعالیت‌های انعطاف‌پذیر در فضای جغرافیایی دوبعدی است:

پ پ A = {w | تی o w E + تی w d E \leq ب}

(5)

جایی که $b = t_{d} - t_{o} - c_{min}$ حداکثر بودجه زمانی برای سفر است. ارتفاع منشور فضا-زمان در مکان $w$ حداکثر مدت زمان فعالیت را نشان می دهد، $c_{w}$ ، در محل به عنوان:

ج w = تی + w - تی - w = (تی د - تی w d E) - (تی o + تی o w E)

(6)

جایی که $t_{w}^{-} = t_{o} + t_{E}^{o w}$ اولین زمان رسیدن به محل است و $t_{w}^{+} = t_{d} - t_{E}^{w d}$ آخرین زمان خروج از محل است.

مدل STP کلاسیک فوق در فضای مسطح می تواند به راحتی ساخته شود و رسمی سازی دقیقی داشته باشد. با این حال، این مدل بر اساس یک فرض غیر واقعی است که حرکات با سرعت ثابت در همه جای فضای مسطح رخ می دهد [ 2 ، 12 ، 13 ، 15 ]. در واقعیت، مردم در مناطق شهری آزادانه در فضای مسطح حرکت نمی کنند، بلکه در داخل شبکه های جاده ای جاسازی شده فضایی حرکت می کنند. بنابراین، مدل کلاسیک STP، پیچیدگی‌های محیط واقعی سفر را بیش از حد ساده می‌کند و برای برنامه‌ریزی فعالیت و سفر یک فرد ناکافی است.

3. ساخت منشورهای فضا-زمان در شبکه های جاده ای

این بخش یک مدل منشور شبکه-زمان (NTP) را با در نظر گرفتن پیچیدگی های شبکه های جاده ای، از جمله محدودیت های پیچ و جاده های تقسیم شده/تقسیم نشده، فرموله می کند. یک شبکه جاده ای را می توان به عنوان یک نمودار جهت دار نشان داد

G (N, A, Ψ)

، شامل مجموعه ای از گره ها است

N

، مجموعه ای از پیوندها

A

، و مجموعه ای از چرخش های مجاز

Ψ

. هر لینک هدایت شده

a_{i j} \in A

یک گره دم دارد

i

، یک گره سر

j

، و زمان سفر پیوند

t_{i j}

. یک چرخش

ψ_{i j k} \in Ψ

، از طریق پیوندها عبور می کند

a_{i j}

a_{j k}

، یک حرکت مجاز در گره را نشان می دهد

j

(مثلاً گردش به راست یا دور برگردان). به علاوه،

ψ_{i j k} \notin Ψ

به این معنی است که حرکت از پیوند

a_{i j}

برای پیوند دادن

a_{j k}

در گره محدود شده است

j

(به عنوان مثال، گردش به چپ

ψ_{125}

در شکل 2 ). علاوه بر چرخش در گره ها، چرخش های U در هر مکانی در یک پیوند تقسیم نشده (مثلاً یک جاده کوچک) مجاز است، اما در یک پیوند تقسیم شده (مثلاً یک جاده شریانی) محدود می شود. مثلا،

a_{12}

a_{21}

در شکل 2 دو پیوند متضاد یک جاده تقسیم نشده وجود دارد و مسافران می توانند آزادانه بین این دو پیوند دور برگردند. لازم به ذکر است که یک جاده دو طرفه، صرف نظر از اینکه تقسیم یا تقسیم نشده باشد، با دو پیوند جهت دار مخالف نشان داده می شود، در حالی که یک جاده یک طرفه تنها با یک پیوند هدایت شده نشان داده می شود.

هر مکان

w = (x_{w}, y_{w})

در شبکه را می توان به صورت نمایش داد

(a_{i j}, θ_{w})

با استفاده از تکنیک مرجع خطی [ 23 ، 32 ]، که در آن

θ_{w} \in [0, 1]

موقعیت نسبی روی پیوند است

a_{i j} \in A

. به عنوان مثال، مکان

w = (a_{23}, 0.5)

در شکل 2 وسط پیوند را نشان می دهد

a_{23}

. زمان سفر پیوندهای جزئی

a_{i w}

a_{w j}

متناسب با فاصله آنها فرض می شود:

تی من w = θ w تی من ج

(7)

تی w j = (1 - θ w) تی من ج

(8)

اجازه دهید

p_{R}^{w l}

حداقل مسیر زمانی بین دو مکان باشد،

w = (x_{w}, y_{w})

l = (x_{l}, y_{l})

. زمان سفر مسیر،

t_{R}^{w l}

را می توان با جمع کردن زمان سفر لینک مربوطه در طول مسیر محاسبه کرد:

تی w l آر = \sum \forall آ من ج تی من ج δ w l من ج

(9)

جایی که $δ_{i j}^{w l}$ رابطه وقوع پیوند-مسیر است، $δ_{i j}^{w l} = 1$ به معنای آن پیوند (جزئی) است $a_{i j}$ در مسیر است $p_{R}^{w l}$ ، و در غیر این صورت $δ_{i j}^{w l} = 0$ . در شبکه جاده‌ای با محدودیت‌های پیچ، کمترین مسیر زمانی را می‌توان با الگوریتم کوتاه‌ترین مسیر با استفاده از تکنیک برچسب‌گذاری مبتنی بر پیوند تعیین کرد [ 33 ]. باید توجه داشت که الگوریتم کلاسیک Dijkstra مبتنی بر گره [ 34 ] محدودیت‌های نوبتی را نادیده می‌گیرد و ممکن است به مسیرهای غیرقابل اجرا منجر شود.

اجازه دهید

t_{R}^{o w}

کمترین زمان سفر از مبدا تا مکان باشد

w

، و اجازه دهید

t_{R}^{w d}

کمترین زمان سفر از مکان باشد

w

به مقصد با تعویض

t_{R}^{o w}

t_{R}^{w d}

با

t_{E}^{o w}

t_{E}^{w d}

در معادلات (1)-(4)، NTP در شبکه جاده را می توان به صورت بیان کرد

NTP (t) = FC (t) \cap BC (t) \cap CY (t)

(10)

FC (t) = {w | t \geq تی o + تی o w آر ، t \leq تی د}

(11)

قبل از میلاد (t) = {w | t \leq تی د - تی w d آر ، t \geq تی o}

(12)

CY (t) = {w | تی o w آر + تی w d آر \leq تی د - تی o - ج دقیقه ، تی o \leq t < تی د}

(13)

این NTP مکان‌های فضا-زمان قابل دسترس یک فرد را در شبکه جاده‌ای بین مبدأ مشخص می‌کند

o = (a_{o}, θ_{o})

و مقصد

d = (a_{d}, θ_{d})

در طول دوره زمانی

t_{o}

به

t_{d}

. ارتفاع NTP در محل

w

حداکثر مدت زمان فعالیت را نشان می دهد

c_{w}

در محل به صورت:

ج w = تی + w - تی - w = (تی د - تی w d آر) - (تی o + تی o w آر)

(14)

جایی که $t_{w}^{-} = t_{o} + t_{R}^{o w}$ و $t_{w}^{+} = t_{d} - t_{R}^{w d}$ به ترتیب، اولین زمان ورود و آخرین زمان خروج از محل است.

شکل 3 یک NTP ساده در یک شبکه جاده ای را نشان می دهد. همانطور که در شکل مشاهده می شود، NTP شامل مجموعه ای از چند ضلعی های فضا-زمان دو بعدی است

{\dots, Q_{i j} \dots}

در پیوندهای شبکه هر چند ضلعی فضا-زمان

Q_{i j} = {(x_{i}, y_{i}, t_{i}^{+}), \dots, (x_{j}, y_{j}, t_{j}^{+}), (x_{j}, y_{j}, t_{j}^{-}), \dots, (x_{i}, y_{i}, t_{i}^{-})}

همه مکان‌های فضا-زمان قابل دسترسی را در امتداد پیوند شبکه نشان می‌دهد

a_{i j}

[ 23 ]. طرح NTP بر روی فضای جغرافیایی دوبعدی، منطقه شبکه بالقوه (PNA) است که شامل مجموعه ای از پیوندهای قابل دسترس (جزئی) است.

{\dots, a_{i j} \dots}

. اجازه دهید

p_{R}^{o j}

کمترین مسیر زمانی از مبدأ باشد

o

به گره

j

عبور از لینک

a_{i j}

، و اجازه دهید

p_{R}^{i d}

کمترین مسیر زمانی از گره باشد

i

به مقصد

d

عبور از لینک

a_{i j}

. زمان سفر مسیر آنها می باشد

t_{R}^{o j}

t_{R}^{i d}

، به ترتیب. لینک قابل دسترسی

a_{i j} \in P N A

باید محدودیت بودجه زمان سفر زیر را برآورده کند:

تی o j آر + تی من d آر - تی من ج \leq b = تی د - تی o - ج دقیقه

(15)

از شکل 3 می توان مشاهده کرد که پیوندهای تقسیم شده و تقسیم نشده می توانند تفاوت های قابل توجهی در چند ضلعی های دو بعدی خود داشته باشند. اولاً، چند ضلعی های فضا-زمان یکسان را می توان در دو پیوند مخالف یک جاده تقسیم نشده، اما نه یک جاده تقسیم شده، ایجاد کرد. مثلاً مبدا

o = (a_{12}, 0.5)

در شکل روی پیوند تقسیم نشده قرار دارد

a_{12}

. از آنجایی که مسافران می‌توانند آزادانه در جاده‌های تقسیم‌نشده دور برگردند، چندضلعی‌های فضا-زمان یکسان (یعنی

Q_{o 2} = Q_{2 o}

Q_{o 1} = Q_{1 o}

) در پیوندهای مخالف ایجاد می شوند

a_{12}

به

a_{21}

. با این حال، وضعیت برای مقصد متفاوت است

d = (a_{36}, 0.5)

، واقع در پیوند تقسیم شده

a_{36}

. از آنجایی که مسافران نمی توانند در پیوندهای تقسیم شده چرخش U را انجام دهند، اشکال مختلف چندضلعی های فضا-زمان (به عنوان مثال،

Q_{63} \neq Q_{3 d}

Q_{63} \neq Q_{d 6}

) در پیوندهای مخالف ایجاد می شوند

a_{36}

به

a_{63}

. ثانیاً، پیوندهای جزئی در NTP فقط در جاده های تقسیم نشده و نه در جاده های تقسیم شده قابل مشاهده است. به عنوان مثال، از شکل می توان دریافت که گره 1 در PNA است، اما گره 4 نیست. به عنوان پیوند

a_{14}

بدون تقسیم است، مسافران می توانند به بخشی از مکان های موجود در پیوند دسترسی داشته باشند و به گره 1 برگردند. و بنابراین، پیوندهای جزئی

a_{1 e}

a_{e 1}

با چند ضلعی های فضا-زمان قابل دسترسی هستند

Q_{1 e}

Q_{e 1}

. همچنین از شکل می توان دریافت که پیوندهای جزئی برای پیوندهای تقسیم شده قابل دسترسی نیستند

a_{56}

a_{65}

. اگرچه گره 6 در داخل PNA قابل دسترسی است، مسافران نمی توانند به مکان های دیگر در پیوند برسند و با چرخش U بر روی پیوند تقسیم شده به گره 6 بازگردند. بنابراین، پیوندهای تقسیم شده و تقسیم نشده می توانند چند ضلعی های فضا-زمان به طور قابل توجهی متفاوت داشته باشند و باید به صراحت در مدل NTP در نظر گرفته شوند.

4. الگوریتم های ژئو محاسباتی برای ساخت منشورهای شبکه-زمان

مشابه الگوریتم NTP-Dij موجود [ 6 ، 31 ]، یک الگوریتم ساده برای ساخت یک NTP، اعمال دو جستجوی کوتاه ترین مسیر با استفاده از الگوریتم یک-همه Dijkstra مبتنی بر پیوند است [ 33 ]. جستجوی رو به جلو برای محاسبه کمترین زمان سفر استفاده می شود

t_{R}^{o j}

از مبدا

o

به هر لینک

a_{i j}

(یعنی گره سر

j

). جستجوی معکوس برای محاسبه کمترین زمان سفر است

t_{R}^{i d}

از هر لینک

a_{i j}

(یعنی گره دم

i

) به مقصد

d

. سپس، پیوندهای قابل دسترسی

\forall a_{i j} \in P N A

رضایت بخش

t_{R}^{o j} + t_{R}^{i d} - t_{i j} \leq b

را می توان شناسایی کرد. پیاده سازی این الگوریتم ساده با استفاده مستقیم از الگوریتم Dijkstra مبتنی بر پیوند موجود آسان است. با این حال، با توجه به این واقعیت که پیوندهای قابل دسترسی در NTP عموماً بخش کوچکی از کل شبکه را تشکیل می‌دهند، می‌تواند با دوبار کاوش در تمام پیوندهای شبکه منجر به سربار محاسباتی قابل توجهی شود.

در این مطالعه، یک الگوریتم کارآمد (به نام الگوریتم NTP-A*) با استفاده از تکنیک های A* و شاخه و کران پیشنهاد شده است. ثابت شده است که تکنیک A* با استفاده از یک تابع ارزیابی اکتشافی در بهبود عملکرد جستجوی کوتاهترین مسیر موثر است. تکنیک شاخه و کران سعی می کند پیوندهای غیرقابل دسترسی را کنار بگذارد

\forall a_{i j} \notin P N A

(یعنی

t_{R}^{o j} + t_{R}^{i d} - t_{i j} > b = t_{d} - t_{o} - c_{min}

) در طول جستجوهای کوتاهترین مسیر به جلو و عقب، به جای جستجوهای کوتاهترین مسیر. با استفاده از این دو تکنیک، الگوریتم NTP-A* پیشنهادی می‌تواند تعداد لینک‌های کاوش‌شده را با دو جستجوی کوتاه‌ترین مسیر به میزان قابل توجهی کاهش دهد و در نتیجه می‌تواند عملکرد ساخت NTP را بهبود بخشد. مراحل دقیق الگوریتم NTP-A* در زیر توضیح داده شده است.

مرحله 1. اصلاح شبکه راه. در الگوریتم های کلاسیک کوتاه ترین مسیر، مبدا و مقصد باید در گره های شبکه قرار گیرند. این مرحله برای رسیدگی به وضعیت مبدا در پیوند است

a_{i j}

(مقصد در لینک

a_{u v}

) با افزودن گره موقت

o

(

d

) و پیوندها

a_{i o}

a_{o j}

(

a_{u d}

a_{d v}

) به شبکه

G

. اگر لینک

a_{i j}

(

a_{u v}

) یک پیوند تقسیم نشده، پیوندهای موقت اضافی است

a_{o i}

a_{j o}

(

a_{d u}

a_{v d}

) نیز در جهت مخالف اضافه می شوند.

مرحله 2. جستجوی کوتاهترین مسیر را به جلو بفرستید. این مرحله برای تعیین کمترین زمان سفر است

t_{R}^{o j}

از مبدا به هر پیوند شبکه

a_{i j}

با استفاده از رویه R-FSP زیر (رویه جستجوی جاده- جلو). با استفاده از تکنیک A*، یک تابع ارزیابی اکتشافی

F (j) = t_{R}^{o j} + h (j)

به عنوان هزینه اکتشافی برای کوتاه ترین مسیر رو به جلو استفاده می شود

p_{R}^{o j}

از مبدا تا پیوند

a_{i j}

، جایی که

h (j)

حد پایین تخمین زده شده است

t_{R}^{i d} - t_{i j}

. از زمان سفر اقلیدسی

t_{E}^{j d}

از گره

j

به مقصد همیشه راضی می کند

t_{E}^{j d} \leq t_{R}^{i d} - t_{i j}

، این مطالعه اتخاذ می کند

t_{E}^{j d}

به عنوان قابل قبول

h (j)

ارزش. این

t_{E}^{j d}

در فضای مسطح را می توان توسط

d_{E}^{j d} / v_{R}^{max}

، جایی که

v_{R}^{max}

حداکثر سرعت حرکت در شبکه جاده ها است. با استفاده از تکنیک A*، اطلاعات هر پیوند به مقصد می تواند به طور کامل برای هدایت جستجوی کوتاه ترین مسیر به جلو مورد استفاده قرار گیرد. تکنیک شاخه و کران بیشتر در جستجوی رو به جلو گنجانده شده است تا همه مسیرها را کنار بگذارد

p_{R}^{o j}, \forall a_{i j} \in A

رضایت بخش

F (j) = t_{R}^{o j} + t_{E}^{j d} > b

. زیرا

t_{R}^{o j} + t_{R}^{i d} - t_{i j} \geq F (j) = t_{R}^{o j} + t_{E}^{j d}

همیشه برقرار است، همه مسیرها راضی کننده است

F (j) > b

می توان آنها را به عنوان پیوندهای غیرقابل دسترس خارج از NTP شناسایی کرد و بنابراین می توان آنها را در طول جستجوی رو به جلو حذف کرد. به این ترتیب، جستجوی رو به جلو تنها بخشی از پیوندها را بررسی می کند

p_{R}^{o j} \neq ϕ, \forall a_{i j} \in A

; لینک های دیگر

p_{R}^{o j} = ϕ, \forall a_{i j} \in A

خارج از NTP کاوش نمی شوند.

رویه R-FSP

ورودی ها: مبدا

o

و مقصد

d

، بودجه زمان سفر

b

خروجی ها: کمترین زمان سفر در لینک های قابل دسترسی

مرحله 1. مقداردهی اولیه:

01: برای هر پیوند

a_{i j} \in A

02: مسیر رو به جلو را تنظیم کنید

p_{R}^{o j} : = ϕ

، زمان سفر آن است

t_{R}^{o j} : = \infty

و هزینه اکتشافی

F (j) : = \infty

03: پایان برای

04: برای هر پیوند

a_{o j}

برخاسته از مبدأ

o

05: یک مسیر رو به جلو ایجاد کنید

p_{R}^{o j} : = a_{o j}

، و تنظیم کنید

t_{R}^{o j} : = t_{o j}

F (j) : = t_{o j} + t_{E}^{j d}

06: درج کنید

p_{R}^{o j}

به اسکن واجد شرایط

S E : = S E \cup {p_{R}^{o j}}

07: پایان برای

مرحله 2. انتخاب مسیر:

08: اگر

S E = ϕ

، سپس متوقف شوید؛ در غیر این صورت ادامه دهید

09: انتخاب کنید

p_{R}^{o i}

در بالای

S E

، و آن را از آن حذف کنید

S E : = S E - {p_{R}^{o i}}

مرحله 3. گسترش مسیر:

10: برای هر حرکت مجاز

ψ_{k i j}

از لینک انتخاب شده

a_{k i}

برای پیوند دادن

a_{i j}

11: یک مسیر رو به جلو ایجاد کنید

{\hat{p}}_{R}^{o j} : = p_{R}^{o i} \oplus a_{i j}

، و تنظیم کنید

{\hat{t}}_{R}^{o j} : = t_{R}^{o i} + t_{i j}

F (j) : = {\hat{t}}_{R}^{o j} + t_{E}^{j d}

12: اگر

F (j) \leq b

سپس

13: اگر

{\hat{t}}_{R}^{o j}

کمتر از هزینه سفر موجود در مسیر است

t_{R}^{o j}

سپس

14: اگر مسیر موجود باشد

p_{R}^{o j} \in S E

، سپس تنظیم کنید

S E : = S E - {p_{R}^{o j}}

15: مجموعه

p_{R}^{o j} : = {\hat{p}}_{R}^{o j}

S E : = S E \cup {{\hat{p}}_{R}^{o j}}

16: پایان اگر

17: پایان اگر

18: پایان برای

19: به مرحله 2 برگردید.

مرحله 3. جستجوی کوتاهترین مسیر به عقب. این مرحله برای تعیین کمترین زمان سفر است

t_{R}^{i d}

از هر پیوند شبکه

a_{i j}

با استفاده از روش R-BSP زیر (روش جستجوی جاده ای به عقب) به مقصد برسید. با استفاده از تکنیک A*، تابع ارزیابی اکتشافی

F (i) = t_{R}^{i d} + h (i)

به عنوان هزینه اکتشافی مسیر برای کوتاهترین مسیر از مقصد به پیوند استفاده می شود

a_{i j}

، جایی که

h (i)

یک حد پایین تخمینی است

t_{R}^{o j} - t_{i j}

. در این تحقیق کمترین زمان سفر

t_{R}^{o j} - t_{i j}

محاسبه شده در جستجوی رو به جلو به عنوان استفاده می شود

h (i)

ارزش در این جستجوی عقب افتاده است. پیوندهای ناشناخته (با

p_{R}^{o j} = ϕ, t_{R}^{o j} + t_{E}^{j d} > b

) در جستجوی رو به جلو خارج از NTP هستند و بنابراین می توان آنها را با خیال راحت در جستجوی عقب انداخت. با استفاده از این روش، نتایج جستجوی رو به جلو به طور کامل برای سرعت بخشیدن به جستجوی عقب استفاده می شود. تکنیک شاخه و کران برای کنار گذاشتن همه پیوندهای خارج از NTP (یعنی همه مسیرهای رضایت بخش) گنجانده شده است.

F (i) = t_{R}^{o j} + t_{R}^{i d} - t_{i j} > b

) در طول فرآیند جستجوی کوتاهترین مسیر به عقب. پس از جستجوی برگشتی، پیوندها را با

p_{R}^{i d} \neq ϕ, \forall a_{i j} \in A

را می توان به عنوان پیوندهای کامل در دسترس در NTP تعیین کرد.

رویه R-BSP

ورودی ها: مبدا

o

و مقصد

d

، بودجه زمان سفر

b

خروجی ها: همه پیوندهای قابل دسترسی در منشور زمان شبکه

مرحله 1. مقداردهی اولیه:

01: برای هر پیوند

a_{i j} \in A

02: مسیر عقب را تنظیم کنید

p_{R}^{i d} : = ϕ

، زمان سفر آن است

t_{R}^{i d} : = \infty

و هزینه اکتشافی

F (i) : = \infty

03: پایان برای

04: برای هر پیوند

a_{i d}

ادغام به مقصد

d

05: اگر مسیر رو به جلو باشد

p_{R}^{o d} \neq ϕ

در لینک

a_{i d}

سپس

06: یک مسیر به عقب ایجاد کنید

p_{R}^{i d} : = a_{i d}

، و تنظیم کنید

t_{R}^{i d} : = t_{i d}

F (i) : = t_{R}^{i d} + t_{R}^{o d} - t_{i d}

07: درج کنید

p_{R}^{i d}

به اسکن واجد شرایط

S E : = S E \cup {p_{R}^{i d}}

08: پایان اگر

09: پایان برای

مرحله 2. انتخاب مسیر:

10: اگر

S E = ϕ

، سپس متوقف شوید؛ در غیر این صورت ادامه دهید

11: انتخاب کنید

p_{R}^{j d}

در بالای

S E

، و آن را از آن حذف کنید

S E : = S E - {p_{R}^{j d}}

مرحله 3. گسترش مسیر:

12: برای هر حرکت مجاز

ψ_{i j k}

از لینک

a_{i j}

به لینک انتخاب شده

a_{j k}

13: اگر مسیر رو به جلو باشد

p_{R}^{o j} \neq ϕ

در لینک

a_{i j}

سپس

14: یک مسیر به عقب ایجاد کنید

{\hat{p}}_{R}^{i d} : = a_{i j} \oplus p_{R}^{j d}

، و تنظیم کنید

{\hat{t}}_{R}^{i d} : = t_{R}^{j d} + t_{i j}

F (i) : = {\hat{t}}_{R}^{i d} + t_{R}^{o j} - t_{i j}

15: اگر

F (i) \leq b

سپس

16: اگر

{\hat{t}}_{R}^{i d}

کمتر از هزینه سفر موجود در مسیر است

t_{R}^{i d}

سپس

17: اگر برچسب موجود باشد

p_{R}^{i d} \in S E

، سپس تنظیم کنید

S E : = S E - {p_{R}^{i d}}

18: مجموعه

p_{R}^{i d} : = {\hat{p}}_{R}^{i d}

S E : = S E \cup {{\hat{p}}_{R}^{i d}}

19: پایان اگر

20: پایان اگر

21: پایان اگر

22: پایان برای

23: به مرحله 2 برگردید.

مرحله 4. ساخت منطقه شبکه بالقوه. این مرحله تعیین پیوندهای کامل و جزئی قابل دسترسی در NTP است. با استفاده از نتایج مرحله 3، تمام پیوندهای کامل قابل دسترسی را می توان به راحتی به عنوان پیوندهای کاوش شده (با

p_{R}^{i d} \neq ϕ, \forall a_{i j} \in A

). در میان آنها پیوندهای کامل تقسیم شده و تقسیم نشده به ترتیب در دو مجموعه پیوند نگهداری می شوند.

D L

U L

. برای هر پیوند کامل تقسیم نشده قابل دسترسی

a_{i j} \in U L

، پیوند مقابل آن

a_{j i}

نیز در آن گنجانده شده است

U L

. همه پیوندهای جزئی قابل دسترسی شناسایی و در مجموعه دیگری ذخیره می شوند.

P L

. هر پیوند جزئی قابل دسترسی

a_{j k} \in P L

در صورت پیوند قابل شناسایی است

a_{j k}

تقسیم نشده است، ارضا می کند

a_{j k} \notin (D L \cup U L)

، و به یک پیوند قابل دسترسی متصل می شود

a_{i j} \in (D L \cup U L)

\exists ψ_{i j k} = (a_{i j}, a_{j k})

مرحله 5. ساخت منشور شبکه-زمان. این مرحله ساخت چندضلعی فضا-زمان است

Q_{i j}

برای هر پیوند قابل دسترسی (جزئی).

a_{i j}

. اشکال مختلفی از چند ضلعی های فضا-زمان برای پیوندها ساخته شده اند

D L

U L

P L

به شرح زیر است:

➢: سناریوی پیوند تقسیم شده (یعنی $a_{i j} \in D L$ ). اولین زمان ورود و آخرین زمان خروج در گره دم $i$ را می توان به صورت محاسبه کرد $t_{i}^{-} = t_{o} + t_{R}^{o j} - t_{i j}$ و $t_{i}^{+} = t_{d} - t_{R}^{i d}$ . زودترین زمان ورود و آخرین زمان خروج در سر گره $j$ به عنوان تعیین می شوند $t_{j}^{-} = t_{o} + t_{R}^{o j}$ و $t_{j}^{+} = t_{d} - t_{R}^{i d} + t_{i j}$ . چند ضلعی فضا-زمان را می توان به صورت $Q_{i j} = {(x_{i}, y_{i}, t_{i}^{+}), (x_{j}, y_{j}, t_{j}^{+}), (x_{j}, y_{j}, t_{j}^{-}), (x_{i}, y_{i}, t_{i}^{-})}$ . اگر لینک $a_{i j}$ پس یک یا چند رأس میانی دارد $(x_{w}, y_{w}, t_{w}^{-}), (x_{w}, y_{w}, t_{w}^{+})$ نیز محاسبه و درج می شوند $Q_{i j}$ برای هر رأس میانی $w$ . این $t_{w}^{-}$ و $t_{w}^{+}$ مقادیر در هر رأس $w$ را می توان از گره های دم و سر درون یابی کرد.
➢: سناریوی پیوند تقسیم نشده (یعنی $a_{i j} \in U L$ ). اول، دو چند ضلعی فضا-زمان $Q_{i j}$ و $Q_{j i}$ برای دو پیوند مخالف ساخته شده اند $a_{i j}$ و $a_{j i}$ ، با استفاده از همان روش سناریوی پیوند تقسیم شده فوق الذکر. سپس چند ضلعی ساخته شد $Q_{i j}$ و $Q_{j i}$ در یک چند ضلعی جدید ادغام می شوند ${\bar{Q}}_{i j}$ . در نهایت، چند ضلعی ادغام شده است ${\bar{Q}}_{i j}$ به عنوان چند ضلعی برای هر دو پیوند تنظیم شده است $a_{i j}$ و $a_{j i}$ .
➢: سناریوی پیوند جزئی (یعنی $a_{j k} \in P L$ ). اجازه دهید $P D S (a_{j k}) = {ψ_{i j k} = (a_{i j}, a_{j k}) \in Ψ}$ مجموعه ای از پیوندهای قبلی قابل دسترسی پیوند باشد $a_{j k}$ . زودترین زمان ورود و آخرین زمان خروج در گره $j$ به عنوان تعیین می شوند $t_{j}^{-} = min (t_{o} + t_{R}^{o j})$ و $t_{j}^{+} = max (t_{d} - t_{R}^{i d} + t_{i j})$ در میان همه پیوندهای پیشین در دسترس، $\forall a_{i j} \in P D S (a_{j k})$ . برای تعیین پیوند جزئی قابل دسترسی $a_{j e}$ ، گره انتهایی آن $e = (a_{j k}, θ_{e})$ محاسبه می شود $θ_{e} = (t_{j}^{+} - t_{j}^{-} - c_{min}) / (t_{j k} + t_{k j})$ . زودترین زمان ورود و آخرین زمان خروج آن محاسبه می شود $t_{e}^{-} = t_{j}^{-} + t_{j k} θ_{e}$ و $t_{e}^{+} = t_{j}^{+} - t_{j k} θ_{e}$ . یک چندضلعی فضا-زمان برای پیوند جزئی ساخته شده است $a_{j e}$ از طریق $ψ_{i j k}$ مانند $Q_{j e} = {(x_{j}, y_{j}, t_{j}^{+}), (x_{e}, y_{e}, t_{e}^{+}), (x_{e}, y_{e}, t_{e}^{-}), (x_{j}, y_{j}, t_{j}^{-})}$ . اگر لینک جزئی $a_{j e}$ دارای یک یا چند رأس میانی و سپس مربوطه است $(x_{w}, y_{w}, t_{w}^{-}), (x_{w}, y_{w}, t_{w}^{+})$ نیز محاسبه و درج می شوند $Q_{j e}$ برای هر راس میانی $w$ . سپس با استفاده از روش مشابه، چند ضلعی $Q_{e k}$ برای پیوند جزئی $a_{k e}$ در جهت مخالف ساخته شده است. این دو چند ضلعی ساخته شده، $Q_{j e}$ و $Q_{e k}$ ، در یک چند ضلعی جدید ادغام می شوند ${\bar{Q}}_{j k}$ . در نهایت، چند ضلعی ادغام شده است ${\bar{Q}}_{j k}$ به عنوان چند ضلعی برای هر دو جهت تنظیم شده است.

مرحله 6. ترمیم شبکه راه. این مرحله برای بازسازی شبکه جاده ای است

G

با حذف گره ها و پیوندهای موقت اضافه شده در مرحله 1.

پیچیدگی محاسباتی الگوریتم NTP-A* پیشنهادی تحلیل می‌شود. با اجرای یک صف اولویت با استفاده از ساختار F-heap [ 35 ]، هر دو جستجوی کوتاه ترین مسیر به جلو و عقب (مرحله 2 و 3) نیاز دارند.

O (| Ψ | + | A | L o g | A |)

در بدترین حالت، جایی که

| Ψ |

تعداد پیچ ها در شبکه راه ها و

| A |

تعداد پیوندهای شبکه راه است. در مراحل 4 و 5، هر دو ساخت PNA و ساخت NTP اجرا می شوند

O (| A |)

. به طور خلاصه، کل زمان محاسباتی است

O (| Ψ | + | A | L o g | A |)

. بنابراین، عملکرد الگوریتم NTP-A* تحت سلطه دو جستجوی کوتاه ترین مسیر در مراحل 2 و 3 است.

بهبود دو جستجوی کوتاه ترین مسیر (یعنی الگوریتم های R-FSP و R-BSP) می تواند عملکرد ساخت NTP را به طور قابل توجهی افزایش دهد. علاوه بر تکنیک‌های A* و شاخه و کران، چندین مسئله پیاده‌سازی می‌تواند بر عملکرد جستجوی کوتاه‌ترین مسیر تأثیر بگذارد. به طور معمول، جستجوهای کوتاهترین مسیر مبتنی بر A* از تکنیک تنظیم برچسب با استفاده از ساختارهای داده صف اولویت (به عنوان مثال، F-heap) برای پیاده سازی SE (واجد شرایط اسکن) استفاده می کنند. تکنیک تصحیح برچسب، با استفاده از ساختار داده لیست پیوندی، برای الگوریتم NTP-A* پیشنهادی به دلیل کارایی محاسباتی آن پیشنهاد شده است. در الگوریتم های R-FSP و R-BSP فوق الذکر، تکنیک برچسب گذاری مبتنی بر پیوند [ 33 ] برای در نظر گرفتن محدودیت های پیچ در شبکه جاده ها به کار گرفته شده است. اخیراً لی و همکاران [36 ] با استفاده از تکنیک برچسب‌گذاری مبتنی بر گره در گره‌ها بدون محدودیت نوبتی و یک تکنیک برچسب‌گذاری مبتنی بر پیوند در گره‌هایی با محدودیت‌های نوبتی، یک تکنیک برچسب‌گذاری پیوند-گره ترکیبی جدید پیشنهاد کرد. گزارش شد [ 36] که تکنیک برچسب‌گذاری پیوند گره ترکیبی می‌تواند کمترین مسیر زمانی را در یک شبکه جاده‌ای با محدودیت‌های پیچی تعیین کند، در حالی که عملکرد محاسباتی مشابهی با الگوریتم کلاسیک مبتنی بر گره Dijkstra بدست می‌آورد. خاطرنشان می‌شود که از نظر تئوری، این تکنیک‌ها (به عنوان مثال، تکنیک‌های A* و شاخه و کران، و تکنیک‌های تصحیح برچسب و برچسب‌گذاری پیوند گره ترکیبی) بر پیچیدگی بدترین حالت الگوریتم NTP-A* تأثیر نمی‌گذارند. که مشابه الگوریتم های NTP-Dij و NTP-SN موجود است). در عمل، این تکنیک ها می توانند به طور قابل توجهی عملکرد ساخت NTP را در شبکه های جاده ای واقعی افزایش دهند. اثربخشی چنین تکنیک هایی در بخش بعدی از طریق یک مطالعه موردی جامع مورد بررسی و بحث قرار خواهد گرفت.

5. مطالعه موردی

در این مطالعه، یک مطالعه موردی جامع با استفاده از شبکه‌های جاده‌ای دنیای واقعی برای بررسی عملکرد محاسباتی الگوریتم پیشنهادی NTP-A* انجام شده است. الگوریتم پیشنهادی NTP-A* با استفاده از زبان برنامه نویسی Visual C# پیاده سازی شد. یک ساختار فهرست مجاورت مبتنی بر پیوند [ 33] برای بارگذاری شبکه جاده در حافظه استفاده شد. تکنیک تصحیح برچسب مبتنی بر پیوند برای اجرای رویه‌های R-FSP و R-BSP به کار گرفته شد. برای مقایسه، سه الگوریتم ساخت NTP دیگر نیز با استفاده از همان زبان برنامه نویسی پیاده سازی شدند. الگوریتم اول، به نام NTP-BB، تنها از تکنیک شاخه و کران استفاده می کند، اما تابع ارزیابی اکتشافی را برای هر دو الگوریتم R-FSP و R-BSP صفر می کند. الگوریتم دوم که NTP-Dij نام دارد، نه از تکنیک A* و نه از تکنیک شاخه و کران استفاده می کند. این الگوریتم از الگوریتم ساده موجود اصلاح شد [ 31] با استفاده از الگوریتم Dijkstra مبتنی بر پیوند برای در نظر گرفتن محدودیت‌های پیچ در شبکه‌های جاده‌ای. الگوریتم سوم (به نام NTP-SN) بر اساس الگوریتم موجود ساخت NTP در یک شبکه فرعی [ 28 ، 29 ] پیاده سازی شد. در این الگوریتم NTP-SN، زیرشبکه با انتخاب گره ها و پیوندهای درون STP در فضای مسطح ساخته شد. و سپس الگوریتم NTP-Dij به طور مستقیم برای ساخت NTP ها مورد استفاده قرار گرفت. در پیاده سازی، زیرشبکه به سادگی با تنظیم یک ویژگی «فعال کردن» به عنوان درست برای گره ها و پیوندهای مربوطه در زیرشبکه ایجاد شد. حداکثر سرعت سفر (یعنی

v_{R}^{max}

) 120 کیلومتر بر ساعت تنظیم شد. در این مطالعه موردی، تمام آزمایش‌ها بر روی یک لپ‌تاپ مک‌بوک ایر با یک CPU چهار هسته‌ای اینتل i7 با فرکانس 2.0 گیگاهرتز و سیستم عامل ویندوز 7 انجام شد.

شبکه جاده در ووهان، چین، با اطلاعات دقیق از محدودیت‌های پیچ و جاده‌های تقسیم‌شده/تقسیم نشده، برای این مطالعه موردی اتخاذ شد. همانطور که در شکل 4 نشان داده شده است ، شبکه جاده ووهان از 19306 گره، 46757 پیوند و 128965 پیچ تشکیل شده است. در این شبکه جاده ای، 24909 لینک تقسیم شده است (یعنی 53.3 درصد کل پیوندها) و 21848 پیوند دیگر (یعنی 46.7 درصد از کل پیوندها) تقسیم نشده است. تعداد چرخش های محدود 1681 است که تنها 1.30٪ از کل پیچ ها را تشکیل می دهد. برای به دست آوردن زمان سفر پیوند شبکه جاده ای ووهان، داده های ماشین شناور دنیای واقعی (FCD) در یک پنجشنبه معمولی (3 سپتامبر 2009) جمع آوری شد. شکل 4زمان تخمینی سفر را در یک دوره اوج عصر (6 عصر تا 7 بعد از ظهر) نشان می دهد. برای روش دقیق برآورد این زمان سفر، خوانندگان علاقه مند می توانند به مرجع [ 5 ] مراجعه کنند.

جدول 1 عملکرد محاسباتی هر چهار الگوریتم (یعنی NTP-A*، NTP-BB، NTP-Dij و NTP-SN) را در شبکه جاده ای ووهان گزارش می کند. بودجه زمان سفر (یعنی

b

) مقادیر از 10 تا 150 دقیقه تنظیم شد. اندازه یک NTP با درصد پیوندهای درون NTP در کل شبکه اندازه گیری شد. عملکرد محاسباتی همه الگوریتم‌ها با زمان‌های محاسباتی (

\tilde{t}

) و تعداد پیوندهای انتخاب شده (

\tilde{n}

). عملکرد محاسباتی گزارش شده میانگین 100 اجرا با استفاده از جفت های مختلف مبدا و مقصد (OD) بود. 100 جفت OD به طور تصادفی در شبکه تولید شد و از همان مجموعه جفت OD برای همه الگوریتم‌ها استفاده شد.

همانطور که از جدول مشاهده می شود، عملکرد محاسباتی الگوریتم NTP-A* با افزایش بودجه زمان سفر کاهش می یابد (به عنوان مثال،

b

) ارزش های. مثلاً وقتی

b = 10

در دقیقه، الگوریتم NTP-A* تنها به 5.75 میلی ثانیه نیاز دارد. چه زمانی

b = 150

دقیقه، این زمان محاسباتی به طور قابل توجهی به 593.18 میلی ثانیه افزایش می یابد. این نتیجه بدیهی است، به دلیل افزایش اندازه NTP از 1.02٪ به 96.71٪ زمانی که

b

مقادیر از 10 به 150 دقیقه افزایش می یابد. از جدول می توان مشاهده کرد که پارامتر بودجه زمان سفر هیچ تاثیری بر عملکرد محاسباتی الگوریتم NTP-Dij ندارد که برای همه 629.23 میلی ثانیه مصرف می کند.

b

ارزش های. این به این دلیل است که الگوریتم NTP-Dij از دو جستجوی کوتاه ترین مسیر یک به همه برای تعیین اولین زمان حرکت و آخرین زمان رسیدن برای هر پیوند شبکه، صرف نظر از موارد مختلف، استفاده می کند.

b

ارزش های. بنابراین، الگوریتم NTP-Dij می‌تواند با کاوش تعداد زیادی پیوند شبکه غیر ضروری، زمانی که اندازه NTP کوچک است، سربار محاسباتی قابل توجهی داشته باشد. مثلاً وقتی

b = 10

دقیقه، زمان محاسباتی مصرف شده توسط الگوریتم NTP-Dij حدود 108 برابر (یعنی 629.23/5.75-1) بیشتر از زمان الگوریتم پیشنهادی NTP-A * بود.

در مقایسه با الگوریتم NTP-Dij، الگوریتم NTP-SN به جای کل شبکه، NTP را در یک زیرشبکه در STP در فضای مسطح می سازد. از جدول می توان دریافت که این الگوریتم NTP-SN می تواند عملکرد ساخت NTP را زمانی که بودجه زمان سفر بسیار کم است بهبود بخشد (به عنوان مثال،

b = 10

دقیقه). با این حال، این بهبود محاسباتی به سرعت با افزایش بودجه زمان سفر کاهش می یابد (به عنوان مثال،

b = 30

دقیقه). این به این دلیل است که شبکه فرعی تعریف شده توسط STP در فضای مسطح معمولاً کمی بزرگتر از NTP واقعی بود. وقتی بودجه زمان سفر زیاد می شود (به عنوان مثال،

b > 30

دقیقه)، شبکه فرعی ممکن است به کل شبکه برسد. در این حالت، تولید زیرشبکه می‌تواند بار محاسباتی اضافی ایجاد کند.

الگوریتم پیشنهادی NTP-A* از هر دو تکنیک A* و شاخه و کران برای بهبود عملکرد ساخت NTP استفاده می کند. اثربخشی تکنیک شاخه و کران از طریق مقایسه بین الگوریتم‌های NTP-Dij و NTP-BB مورد بررسی قرار گرفت. با استفاده از تکنیک شاخه و کران، الگوریتم NTP-BB می‌تواند پیوندهای شبکه غیرقابل دسترس را که زمان سفر به مقصد (یعنی،

t_{R}^{i d}

) (یا از مبدا، به عنوان مثال،

t_{R}^{o j}

) از بودجه زمان سفر داده شده بزرگتر هستند

b

. در مقایسه با الگوریتم NTP-Dij، این تکنیک شاخه و کران معرفی شده می تواند به طور قابل توجهی تعداد پیوندهای غیر ضروری بررسی شده را کاهش دهد و در نتیجه عملکرد ساخت NTP را بهبود بخشد. مثلاً وقتی

b = 10

در دقیقه، تکنیک شاخه و کران تعداد پیوندهای انتخابی را 98.96٪ کاهش داد (یعنی 1 – 7694/743853). بنابراین الگوریتم NTP-BB حدود 83 برابر سریعتر از الگوریتم NTP-Dij اجرا می شود.

b = 10

دقیقه با این وجود، می توان از جدول دریافت که اثربخشی تکنیک شاخه و کران با افزایش مقادیر بودجه زمان سفر کاهش می یابد، و زمانی که اندازه NTP به کل شبکه (یعنی 100٪) نزدیک می شود، حاشیه ای می شود.

اثربخشی تکنیک A* با مقایسه بین الگوریتم های NTP-BB و NTP-A* مورد بررسی قرار گرفت. در الگوریتم NTP-A* پیشنهادی، هر دو تکنیک A* و شاخه و کران برای کنار گذاشتن پیوندهای غیرضروری که هزینه های اکتشافی به مقصد دارند (یعنی،

t_{R}^{i d} + h (i)

) (یا از مبدا، به عنوان مثال،

t_{R}^{o j} + h (j)

) از بودجه زمان سفر داده شده بزرگتر هستند

b

. در جستجوی رو به جلو، یک تابع اکتشافی

h (j) = t_{E}^{j d}

با ترکیب اطلاعات هر پیوند به مقصد معرفی شد، در حالی که، در جستجوی عقب، تابع اکتشافی

h (i) = t_{R}^{o i}

با بهترین استفاده از نتایج جستجوی رو به جلو اتخاذ شد. در مقایسه با الگوریتم NTP-BB، تکنیک A* معرفی شده در کاهش تعداد پیوندهای انتخابی به میزان 60.75٪ موثر بود و عملکرد ساخت NTP را تا 30.78٪ بهبود بخشید.

b = 10

دقیقه اثربخشی این تکنیک A* زمانی که یک NTP با اندازه متوسط استفاده شد مشخص تر شد. مثلاً وقتی

b = 40

در دقیقه، تکنیک A* می تواند تعداد لینک های انتخابی را تا 62.63% کاهش دهد و عملکرد ساخت NTP را تا 103.90% بهبود بخشد. مشابه تکنیک شاخه و کران، اثربخشی تکنیک A* زمانی که اندازه NTP به کل شبکه نزدیک شود، حاشیه ای می شود.

چندین تکنیک پیاده سازی الگوریتم NTP-A* پیشنهادی نیز مورد بررسی قرار گرفت. ابتدا اثربخشی تکنیک تصحیح برچسب در اجرای SE مورد بررسی قرار گرفت. به طور معمول، الگوریتم کوتاه ترین مسیر نوع A از تکنیک تنظیم برچسب استفاده می کند [ 37 ، 38 ]. برای مقایسه، این تکنیک تنظیم برچسب نیز در مطالعه موردی با استفاده از ساختار داده F-heap [ 35 ] (به نام الگوریتم NTP-A*-LS) اجرا شد. شکل 5عملکرد محاسباتی الگوریتم‌های NTP-A* و NTP-A*-LS در شبکه جاده‌ای ووهان را نشان می‌دهد. همانطور که در شکل نشان داده شده است، الگوریتم NTP-A* با استفاده از تکنیک تصحیح برچسب سریعتر از الگوریتم NTP-A*-LS با استفاده از تکنیک تنظیم برچسب اجرا می شود. این به این دلیل است که ساختار صف اولویت در تکنیک تنظیم برچسب نسبت به ساختار داده لیست پیوندی که در تکنیک تصحیح برچسب استفاده می شود، از نظر محاسباتی گران بود.

سپس تکنیک‌های برچسب‌گذاری برای در نظر گرفتن محدودیت‌های نوبتی مورد بررسی قرار گرفت. الگوریتم NTP-A* (یعنی رویه‌های R-FSP و R-BSP) مبتنی بر تکنیک برچسب‌گذاری مبتنی بر پیوند را می‌توان با استفاده از تکنیک برچسب‌گذاری پیوند-گره ترکیبی [36] بهبود بخشید .]. تکنیک برچسب‌گذاری پیوند-گره ترکیبی به طور تطبیقی از تکنیک برچسب‌گذاری مبتنی بر گره برای گره‌های نامحدود بدون محدودیت نوبتی و از تکنیک برچسب‌گذاری مبتنی بر پیوند برای گره‌های محدود با محدودیت‌های نوبتی استفاده می‌کند. با استفاده از این تکنیک برچسب‌گذاری پیوند گره ترکیبی، می‌توان تعداد مسیرهای تولید، ارزیابی و نگهداری در گره‌های نامحدود را در مقایسه با روش برچسب‌گذاری مبتنی بر پیوند کاهش داد. از آنجایی که تعداد گره‌های محدود شده در اکثر شبکه‌های جاده‌ای (مثلاً شبکه ووهان) کم بود، چنین تکنیک برچسب‌گذاری پیوند-گره ترکیبی می‌تواند عملکرد محاسباتی رویه‌های R-BSP و R-BSP را به طور قابل توجهی بهبود بخشد. الگوریتم بهبود یافته برای راحتی به عنوان الگوریتم NTP-A*-HLN معرفی شد. همانطور که در شکل مشاهده می شود، الگوریتم NTP-A*-HLN 1.99 برابر سریعتر از الگوریتم NTP-A* اجرا می شود.

b = 60

دقیقه

عملکرد محاسباتی الگوریتم NTP-A*-HLN پیشنهادی با استفاده از چهار شبکه جاده با اندازه‌های مختلف بیشتر مورد بررسی قرار گرفت. دو الگوریتم موجود (NTP-Dij و NTP-SN) نیز برای مقایسه مورد بررسی قرار گرفتند. علاوه بر شبکه ووهان، سه شبکه دیگر، RTIS هنگ کنگ، شبکه منطقه ای شیکاگو و شبکه پکن، از منابع به دست آمد [ 36 ، 38 ]. جدول 2 عملکرد محاسباتی سه الگوریتم را نشان می دهد. عملکرد محاسباتی گزارش شده میانگین 100 اجرا با استفاده از جفت های OD تولید شده به طور تصادفی برای هر شبکه بود. پارامتر بودجه زمان سفر برای همه شبکه ها 30 دقیقه تنظیم شد.

همانطور که از جدول مشاهده می شود، زمان های محاسباتی سه الگوریتم با اندازه شبکه افزایش می یابد. الگوریتم NTP-A*-HLN تنها 2.85 میلی ثانیه برای ساخت NTPها در RTIS هنگ کنگ با 3655 پیوند مصرف کرد. وقتی از شبکه پکن استفاده شد، اندازه شبکه جاده‌ای 30.39 برابر و زمان محاسباتی 17.24 برابر به 52.01 میلی‌ثانیه افزایش یافت. در مقایسه با الگوریتم NTP-A*-HLN، الگوریتم NTP-Dij به میزان قابل توجهی با اندازه شبکه کاهش می یابد. به عنوان مثال، زمانی که شبکه پکن مورد تجزیه و تحلیل قرار گرفت، زمان محاسباتی مورد نیاز الگوریتم NTP-Dij حدود 890.53 برابر افزایش یافت (7809.83/8.76 – 1). این به این دلیل است که الگوریتم NTP-Dij با دوبار کاوش کل شبکه، NTP را می سازد. در این حالت، زمان محاسباتی الگوریتم NTP-Dij به اندازه شبکه حساس تر است. از جدول می توان مشاهده کرد که الگوریتم NTP-SN به روشی مشابه الگوریتم NTP-Dij اجرا می شود. این نتیجه تایید کرد که اثربخشی ساخت NTP در شبکه‌های فرعی با استفاده از STP در فضای مسطح حاشیه‌ای است.

6. نتیجه گیری

منشور فضا-زمان یک مفهوم کلیدی در جغرافیای زمانی برای تحلیل رفتار فعالیت-سفر انسان تحت محدودیت های فضا-زمان مختلف است. کاربردهای گسترده ای در بسیاری از مطالعات جغرافیایی زمانی دارد. با این حال، چند الگوریتم ژئومحاسباتی کارآمد در ادبیات برای ساخت منشورهای شبکه-زمان (NTPs) در شبکه‌های جاده‌ای واقعی توسعه داده شده‌اند. برای پر کردن این شکاف، این مطالعه مدل‌های NTP و الگوریتم‌های زمین محاسباتی را بررسی کرد. یک مدل NTP برای متمایز کردن جاده‌های تقسیم‌بندی‌شده و تقسیم‌ناپذیر پیشنهاد شد و به افراد اجازه می‌دهد تا دور برگردان انجام دهند و به پیوندهای جزئی در جاده‌های تقسیم نشده دسترسی داشته باشند. یک الگوریتم جغرافیایی محاسباتی (به نام NTP-A*) برای ساخت موثر NTP در شبکه های جاده ای در مقیاس بزرگ توسعه داده شد. در الگوریتم پیشنهادی، تکنیک‌های A* و شاخه و کران برای بهبود عملکرد ساخت NTP با دور انداختن پیوندهای غیرقابل دسترس در طول دو جستجوی کوتاه‌ترین مسیر به کار گرفته شد. تکنیک‌های برچسب‌گذاری تصحیح برچسب و پیوند گره ترکیبی برای بهبود عملکرد ساخت NTP در شبکه‌های جاده‌ای با محدودیت‌های چرخشی مورد استفاده قرار گرفتند. یک مطالعه موردی جامع با استفاده از چهار شبکه جاده واقعی برای نشان دادن مزیت محاسباتی الگوریتم NTP-A* پیشنهادی انجام شد. نتایج تجربی نشان داد که الگوریتم NTP-A* پیشنهادی می‌تواند الگوریتم‌های موجود (یعنی NTP-Dij و NTP-SN) را با ضریب 100 در شبکه‌های جاده‌ای در مقیاس بزرگ (به عنوان مثال، شبکه پکن) بهبود بخشد. تکنیک‌های برچسب‌گذاری تصحیح برچسب و پیوند گره ترکیبی برای بهبود عملکرد ساخت NTP در شبکه‌های جاده‌ای با محدودیت‌های چرخشی مورد استفاده قرار گرفتند. یک مطالعه موردی جامع با استفاده از چهار شبکه جاده واقعی برای نشان دادن مزیت محاسباتی الگوریتم NTP-A* پیشنهادی انجام شد. نتایج تجربی نشان داد که الگوریتم NTP-A* پیشنهادی می‌تواند الگوریتم‌های موجود (یعنی NTP-Dij و NTP-SN) را با ضریب 100 در شبکه‌های جاده‌ای در مقیاس بزرگ (به عنوان مثال، شبکه پکن) بهبود بخشد. تکنیک‌های برچسب‌گذاری تصحیح برچسب و پیوند گره ترکیبی برای بهبود عملکرد ساخت NTP در شبکه‌های جاده‌ای با محدودیت‌های چرخشی مورد استفاده قرار گرفتند. یک مطالعه موردی جامع با استفاده از چهار شبکه جاده واقعی برای نشان دادن مزیت محاسباتی الگوریتم NTP-A* پیشنهادی انجام شد. نتایج تجربی نشان داد که الگوریتم NTP-A* پیشنهادی می‌تواند الگوریتم‌های موجود (یعنی NTP-Dij و NTP-SN) را با ضریب 100 در شبکه‌های جاده‌ای در مقیاس بزرگ (به عنوان مثال، شبکه پکن) بهبود بخشد.

در این تحقیق زمان سفر در شبکه های جاده ای ایستا و قطعی فرض شده است. الگوریتم پیشنهادی NTP-A* را می توان به راحتی برای ساخت NTP در شبکه های پویا گسترش داد، جایی که زمان سفر پیوند با زمان روز متفاوت است. در این حالت پویا، الگوریتم‌های کوتاه‌ترین مسیر وابسته به زمان [ 39 ] باید به جای الگوریتم کلاسیک Dijkstra اتخاذ شوند. تکنیک‌های پیاده‌سازی معرفی‌شده (شامل تکنیک‌های A* و شاخه و کران) هنوز برای چنین مورد پویا مؤثر هستند. الگوریتم پیشنهادی NTP-A* همچنین می تواند برای ساخت منشورهای فضا-زمان قابل اعتماد گسترش یابد [ 17]] در شبکه های جاده ای با عدم قطعیت زمان سفر. در این مورد تصادفی، هر دو تکنیک A* و شاخه و کران موثر هستند، اما الگوریتم‌های کوتاه‌ترین مسیر قابل اعتماد [ 38 ، 40 ، 41 ] باید برای دو جستجوی کوتاه‌ترین مسیر استفاده شوند. با این حال، مشکل ساخت و ساز NTP زمانی چالش برانگیز می شود که هر دو ویژگی پویا و تصادفی زمان سفر در نظر گرفته شود. در شبکه‌های پویا و تصادفی، زمان‌های سفر مسیر غیرقابل برگشت هستند [ 42 ] و نمی‌توانند در جهت معکوس از مقصد تولید شوند. این یک سوال باز است که چگونه می توان یک رویکرد کارآمد برای تعیین آخرین زمان خروج برای همه گره های در دسترس ایجاد کرد. این بسط مهم را به تحقیقات آینده واگذار می کنیم.

منابع

Hägerstrand، T. در مورد افراد در علم منطقه چطور؟ پاپ Reg. علمی 1970 ، 24 ، 7-24. [ Google Scholar ] [ CrossRef ]
میلر، HJ نظریه اندازه گیری برای جغرافیای زمانی. Geogr. مقعدی 2005 ، 37 ، 17-45. [ Google Scholar ] [ CrossRef ]
Kwan، MP فضا-زمان و معیارهای جامع دسترسی فردی: یک تحلیل مقایسه ای با استفاده از یک چارچوب مبتنی بر نقطه Geogr. مقعدی 1998 ، 30 ، 191-216. [ Google Scholar ] [ CrossRef ]
میلر، HJ اندازه‌گیری مزایای دسترسی فضا-زمان در شبکه‌های حمل‌ونقل: نظریه پایه و روش‌های محاسباتی. Geogr. مقعدی 1999 ، 31 ، 187-212. [ Google Scholar ] [ CrossRef ]
چن، توسط; یوان، اچ. لی، QQ; وانگ، دی جی؛ شاو، اس.-ال. Lam، WHK اندازه‌گیری دسترسی مبتنی بر مکان تحت عدم قطعیت زمان سفر. بین المللی جی. جئوگر. Inf. علمی 2016 . [ Google Scholar ] [ CrossRef ]
Charleux, L. جعبه ابزار GIS برای اندازه‌گیری و نقشه‌برداری دسترسی فضا-زمان مبتنی بر شخص. ترانس. GIS 2015 ، 19 ، 262-278. [ Google Scholar ] [ CrossRef ]
منصور، س. تحلیل فضایی امکانات بهداشت عمومی در استان ریاض، عربستان سعودی: یک مطالعه مبتنی بر GIS برای ارزیابی تغییرات جغرافیایی ارائه خدمات و دسترسی. جغرافیایی تف کردن Inf. علمی 2016 ، 19 ، 26-38. [ Google Scholar ] [ CrossRef ]
تیمرمنز، اچ. آرنتز، تی. Joh, CH تجزیه و تحلیل رفتار فضا-زمان: رویکردهای جدید به مشکلات قدیمی. Prog. هوم Geogr. 2002 ، 26 ، 175-190. [ Google Scholar ] [ CrossRef ]
پندیالا، RM; یاماموتو، تی. کیتامورا، آر. در مورد فرمول‌بندی منشورهای زمان-فضا برای مدل‌سازی محدودیت‌های مربوط به فعالیت شخصی – تعامل سفر. حمل و نقل 2002 ، 29 ، 73-94. [ Google Scholar ] [ CrossRef ]
فو، ایکس. لام، WHK; Xiong، Y. مدل‌سازی تعاملات درون‌خانگی در رفتار برنامه‌ریزی فعالیت و سفر خانوار. ترانسپ A 2016 , 12 , 612-628. [ Google Scholar ] [ CrossRef ]
تانگ، ال. ژو، ایکس. میلر، طراحی شبکه حمل و نقل HJ برای به حداکثر رساندن دسترسی به فضا-زمان. ترانسپ Res. روش B. 2015 ، 81 ، 555-576. [ Google Scholar ] [ CrossRef ]
نویتنز، تی. شوانن، تی. Witlox، F. منشور زندگی روزمره: به سوی یک دستور کار تحقیقاتی جدید برای جغرافیای زمانی. ترانسپ Rev. 2011 , 31 , 25-47. [ Google Scholar ] [ CrossRef ]
میلر، HJ مدل‌سازی دسترسی با استفاده از مفاهیم منشور فضا-زمان در سیستم‌های اطلاعات جغرافیایی. بین المللی جی. جئوگر. Inf. علمی 1991 ، 5 ، 287-301. [ Google Scholar ] [ CrossRef ]
کیم، اچ.-م. کوان، ام.-پی. معیارهای دسترسی فضا-زمان: یک الگوریتم ژئومحاسباتی با تمرکز بر مجموعه فرصت های ممکن و مدت زمان فعالیت ممکن. جی. جئوگر. سیستم 2003 ، 5 ، 71-91. [ Google Scholar ] [ CrossRef ]
میلر، اچ جی; Bridwell, SA یک نظریه میدانی برای جغرافیای زمانی. ان دانشیار صبح. Geogr. 2009 ، 99 ، 49-75. [ Google Scholar ] [ CrossRef ]
وو، YH; Miller, HJ ابزارهای محاسباتی برای اندازه گیری دسترسی فضا-زمان در شبکه های حمل و نقل با جریان پویا. J. Transp. آمار 2001 ، 4 ، 1-14. [ Google Scholar ]
چن، توسط; لی، QQ; وانگ، دی جی؛ شاو، اس ال. لام، WHK; یوان، اچ. Fang، ZX قابل اعتماد منشور فضا-زمان تحت عدم قطعیت زمان سفر. ان دانشیار صبح. Geogr. 2013 ، 103 ، 1502-1521. [ Google Scholar ] [ CrossRef ]
نویتنز، تی. ویتلوکس، اف. ون د وگه، ن. د مایر، ص. فضاهای تعامل انسانی تحت عدم قطعیت. ترانسپ Res. ضبط 2007 ، 2021 ، 28-35. [ Google Scholar ] [ CrossRef ]
چن، توسط; وانگ، ی. تو، دبلیو. یوان، اچ. لی، QQ; دانشگاه ووهان، ووهان، چین. اثر منتشر نشده 2016.
Kwan، MP تصویرسازی تعاملی جغرافیایی الگوهای فعالیت سفر با استفاده از سیستم های اطلاعات جغرافیایی سه بعدی: یک کاوش روش شناختی با مجموعه داده های بزرگ. ترانسپ Res. سی ظهور. تکنولوژی 2000 ، 8 ، 185-203. [ Google Scholar ] [ CrossRef ]
شاو، اس ال. یو، HB یک رویکرد جغرافیایی زمانی مبتنی بر GIS برای مطالعه فعالیت‌ها و تعاملات فردی در یک فضای فیزیکی-مجازی ترکیبی. J. Transp. Geogr. 2009 ، 17 ، 141-149. [ Google Scholar ] [ CrossRef ]
نویتنز، تی. ون دی وگه، ن. ویتلوکس، اف. de Maeyer, P. منشور فضا-زمان مبتنی بر شبکه سه بعدی. جی. جئوگر. سیستم 2008 ، 10 ، 89-107. [ Google Scholar ] [ CrossRef ]
چن، توسط; یوان، اچ. لی، QQ; شاو، اس.-ال. لام، WHK; چن، ایکس. مدل داده های مکانی-زمانی برای تحلیل جغرافیایی زمان شبکه در عصر داده های بزرگ. بین المللی جی. جئوگر. Inf. علمی 2016 ، 30 ، 1041-1071. [ Google Scholar ] [ CrossRef ]
لانگ، ج.ا. نلسون، TA مروری بر روش‌های کمی برای داده‌های حرکتی. بین المللی جی. جئوگر. Inf. علمی 2013 ، 27 ، 292-318. [ Google Scholar ] [ CrossRef ]
تانگ، جی. آهنگ، ی. میلر، اچ جی; ژو، ایکس. تخمین محتمل ترین مسیرهای فضا-زمان، زمان اقامت و عدم قطعیت های مسیر از داده های مسیر وسیله نقلیه: یک روش جغرافیایی زمانی. ترانسپ Res. سی ظهور. تکنولوژی 2016 ، 66 ، 176-194. [ Google Scholar ] [ CrossRef ]
چن، توسط; یوان، اچ. لی، QQ; لام، WHK; شاو، اس.-ال. Yan, K. الگوریتم تطبیق نقشه برای داده های ماشین شناور با فرکانس پایین در مقیاس بزرگ. بین المللی جی. جئوگر. Inf. علمی 2014 ، 28 ، 22-38. [ Google Scholar ] [ CrossRef ]
ورسیکله، ام. نویتنز، تی. کلیس بوآرت، ام. Van de Weghe، N. اشتقاق زمانی-جغرافیایی فرصت‌های امکان حضور مشترک از داده‌های جنبش اپیزودیک محدود شده توسط شبکه. ترانس. GIS 2014 ، 18 ، 687-703. [ Google Scholar ] [ CrossRef ]
کویجپرز، بی. عثمان، دبلیو. مدل‌سازی عدم قطعیت اجسام متحرک در شبکه‌های جاده‌ای از طریق منشورهای فضا-زمان. بین المللی جی. جئوگر. Inf. علمی 2009 ، 23 ، 1095-1117. [ Google Scholar ] [ CrossRef ]
Othman, W. مدیریت عدم قطعیت در پایگاه های داده مسیر. Ph.D. پایان نامه، دانشگاه Hasselt، Diepenbeek، بلژیک، 19 مه 2009. [ Google Scholar ]
لیو، ایکس. کانگ، سی جی; گونگ، ال. لیو، ی. ترکیب الگوهای تعامل فضایی در طبقه بندی و درک کاربری زمین شهری. بین المللی جی. جئوگر. Inf. علمی 2016 ، 30 ، 334-350. [ Google Scholar ] [ CrossRef ]
یو، اچ. Shaw, SL بررسی فعالیت های بالقوه انسانی در فضاهای فیزیکی و مجازی: یک رویکرد GIS مکانی-زمانی. بین المللی جی. جئوگر. Inf. علمی 2008 ، 22 ، 409-430. [ Google Scholar ] [ CrossRef ]
میلر، اچ جی; Shaw, SL سیستم های اطلاعات جغرافیایی برای حمل و نقل: اصول و کاربردها ; انتشارات دانشگاه آکسفورد: نیویورک، نیویورک، ایالات متحده آمریکا، 2001. [ Google Scholar ]
گوتیرز، ای. Medaglia، الگوریتم برچسب‌گذاری AL برای مشکل کوتاه‌ترین مسیر با ممنوعیت چرخش با کاربرد در شبکه‌های جاده‌ای در مقیاس بزرگ. ان اپراتور Res. 2008 ، 157 ، 169-182. [ Google Scholar ] [ CrossRef ]
Dijkstra، EM یادداشتی در مورد دو مشکل در ارتباط با نمودارها. عدد. ریاضی. 1959 ، 1 ، 269-271. [ Google Scholar ] [ CrossRef ]
فردمن، ام ال. هپ های ترجان، RE فیبوناچی و استفاده از آنها در الگوریتم های بهبود یافته بهینه سازی شبکه. J. ACM 1987 ، 34 ، 596-615. [ Google Scholar ] [ CrossRef ]
لی، QQ; چن، توسط; وانگ، ی. Lam، WHK یک رویکرد پیوند-گره ترکیبی برای یافتن کوتاه‌ترین مسیرها در شبکه‌های جاده‌ای با محدودیت‌های پیچ. ترانس. GIS 2015 ، 19 ، 915-929. [ Google Scholar ] [ CrossRef ]
زنگ، دبلیو. Church, RL یافتن کوتاه ترین مسیرها در شبکه های جاده ای واقعی: مورد A*. بین المللی جی. جئوگر. Inf. علمی 2009 ، 23 ، 531-543. [ Google Scholar ] [ CrossRef ]
چن، توسط; لام، WHK; سومالی، ع. لی، QQ; شائو، اچ. Fang, ZX یافتن کوتاه‌ترین مسیرهای قابل اعتماد در شبکه‌های جاده‌ای در شرایط عدم قطعیت. شبکه تف کردن اقتصاد 2013 ، 13 ، 123-148. [ Google Scholar ] [ CrossRef ]
چابینی، آی. Lan, S. انطباق‌های الگوریتم A* برای محاسبه سریع‌ترین مسیرها در شبکه‌های دینامیکی زمان گسسته قطعی. IEEE Trans. هوشمند ترانسپ سیستم 2002 ، 3 ، 60-74. [ Google Scholar ] [ CrossRef ]
چن، توسط; لام، WHK; سومالی، ع. Li، ZL یافتن کوتاه ترین مسیر قابل اعتماد در شبکه های تصادفی با زمان سفر پیوند همبسته فضایی. بین المللی جی. جئوگر. Inf. علمی 2012 ، 26 ، 365-386. [ Google Scholar ] [ CrossRef ]
چن، توسط; لام، WHK; الگوریتم راه حل کارآمد لی، QQ برای یافتن کوتاه ترین مسیر قابل اعتماد وابسته به فضایی در شبکه های جاده ای. J. Adv. ترانسپ 2016 ، 50 ، 1413-1431. [ Google Scholar ] [ CrossRef ]
چن، توسط; لام، WHK; سومالی، ع. لی، QQ; Tam, ML مشکلات کوتاه ترین مسیر قابل اعتماد در شبکه های تصادفی وابسته به زمان. جی. اینتل. ترانسپ سیستم 2014 ، 18 ، 177-189. [ Google Scholar ] [ CrossRef ]

شکل 1. منشور فضا-زمان و مفاهیم مرتبط.

شکل 2. یک شبکه جاده ساده.

شکل 3. یک منشور شبکه-زمان تصویری.

شکل 4. شبکه جاده شهر ووهان.

شکل 5. زمان های محاسباتی سه پیاده سازی مختلف از الگوریتم NTP-A*.

جدول 1. عملکرد محاسباتی چهار الگوریتم.

جدول 2. زمان های محاسباتی سه الگوریتم ساخت NTP بر حسب میلی ثانیه.

© 2016 توسط نویسندگان؛ دارنده مجوز MDPI، بازل، سوئیس. این مقاله یک مقاله با دسترسی آزاد است که تحت شرایط و ضوابط مجوز Creative Commons Attribution (CC-BY) (http://creativecommons.org/licenses/by/4.0/) توزیع شده است.

;کاربردهای GIS مقالات

درخواست مشاوره

09120049370

8 صبح تا 12 شب

09120049370

خلاصه

1. معرفی

2. مدل کلاسیک منشور فضا-زمان در فضای مسطح

3. ساخت منشورهای فضا-زمان در شبکه های جاده ای

4. الگوریتم های ژئو محاسباتی برای ساخت منشورهای شبکه-زمان

5. مطالعه موردی

6. نتیجه گیری

منابع

قبلییک رویکرد مدیریت کاشی نقشه برداری موثر مبتنی بر NoSQL

بعدیPDE های مورفولوژیکی روی نمودارها برای پردازش تصویر روی سطوح و ابرهای نقطه ای

بدون نظر

دیدگاهتان را بنویسید لغو پاسخ