Tranzit tugunlarini yo'naltirish - Transit node routing

Yilda amaliy matematika, tranzit tugunlarini yo'naltirish tezlashtirish uchun ishlatilishi mumkin eng qisqa yo'nalish uzoq kirish uchun tegishli bo'lgan umumiy tarmoq tugunlari orasidagi kichik tarmoqqa ulanishlarni oldindan hisoblash orqali.^[1]

Tarkib sifatida tranzit tugunlarini marshrutlash 2007 yilda tashkil etilgan^[1] va tarmoqlardan foydalanish yondashuvlari, avtomagistrallar ierarxiyalari kabi ko'plab aniq dasturlar keyingi yillarda yuzaga keldi^[2] va qisqarish ierarxiyalari.^[3] Tranzit tugunlarini yo'naltirish - bu grafadagi muhim tugunlar orasidagi juftlik masofalarini oldindan qayta ishlashni talab qiladigan statik yondashuv (quyida ushbu tugunlar qanday tanlanganiga qarang). Dinamik yondashuv nashr etilmagan.^[4]

Sezgi

Xuddi shu kirish tugunlaridan foydalanib, shaharlararo yo'llar tarmog'iga bir nechta marshrutlar.

Uzoq masofalarga sayohat odatda pastki qism bo'ylab haydashni o'z ichiga oladi yo'l tarmog'i kabi avtomagistrallar o'rniga, masalan. shahar yo'llari. Ushbu kichik tarmoqni faqat kam tarqatilgan kirish tugunidan foydalanish orqali kiritish mumkins. Bir-biriga taqqoslaganda, bir nechta uzoq masofa marshrutlar bir xil joydan boshlab har doim ushbu tarmoqqa kirish uchun boshlang'ich manzilga yaqin bir xil miqdordagi kirish tugunlaridan foydalaning. Xuddi shu tarzda, shunga o'xshash maqsad joylariga har doim ularga yaqin bo'lgan bir xil kirish tugunlari yordamida erishiladi. Ushbu sezgi faqat uzoq masofalarga sayohat qilish uchun mo'ljallangan. Qisqa masofalarga sayohat qilishda bunday kirish tugunlari hech qachon ishlatilmasligi mumkin, chunki maqsadga eng tez yo'l faqat mahalliy yo'llardan foydalanadi.

Bunday kirish tugunlari soni yo'l tarmog'idagi tugunlarning umumiy soniga nisbatan kam bo'lganligi sababli, ushbu tugunlarni bir-biri bilan bog'laydigan barcha qisqa yo'nalishlar oldindan hisoblab chiqilishi va saqlanishi mumkin. Eng qisqa yo'lni hisoblashda shuning uchun faqat startga va maqsadga yaqin bo'lgan tugunlarga kirish yo'llarini hisoblash kerak.

Umumiy asos

Tranzit tugunlarini yo'naltirish tranzit tugunlarini tanlash bilan boshlanadi ${ displaystyle T subseteq V}$ barcha tugunlarning to'plami sifatida ${ displaystyle V}$ yo'l tarmog'ining.
Har bir tugun uchun ${ displaystyle v in V}$ oldinga kirish tugunlarining maxsus to'plamlari ${ displaystyle { overrightarrow {A}} (v) subseteq T}$ va orqaga kirish tugunlari ${ displaystyle { overleftarrow {A}} (v) subseteq T}$ barcha tranzit tugunlaridan tanlanadi.
Endi tranzit tugunlari orasidagi juftlik masofasi ${ displaystyle D_ {T}}$ va tugunlar orasidagi masofa ${ displaystyle v}$ va ularga tegishli kirish tugunlari ${ displaystyle d_ {A}}$ hisoblab chiqiladi va saqlanadi.
Endi ikkita tugun orasidagi masofani quyidagicha hisoblash mumkin ${ displaystyle d (s, t) = min _ {u in { oververtarrow {A}} (s), v in { overleftarrow {A}} (t)} d_ {A} (s, u ) + D_ {T} (u, v) + d_ {A} (v, t)}$

Joylashuv filtri

Yaqin start va maqsad joylar orasidagi qisqa yo'nalishlar tranzit tugunlarini talab qilmasligi mumkin. Bunday holda, yuqoridagi ramka noto'g'ri masofalarga olib keladi, chunki u kamida bitta tranzit tuguniga tashrif buyurishga majbur qiladi.

Bunday muammoning oldini olish uchun, a mahalliy filtr foydalanish mumkin. Berilgan boshlang'ich va maqsadli joylar uchun tranzit tugunlari marshrutizatsiyasi qo'llanilishi kerakmi yoki qo'shimcha rejim ishlatilishi kerak bo'lsa, mahalliy filtr qaror qabul qiladi (mahalliy so'rov).

Beton misollar

Tranzit tugunlarini yo'naltirish algoritm emas, balki marshrutni rejalashtirishni tezlashtirish uchun asosdir. Umumiy asos uni amalga oshirish uchun javob berish kerak bo'lgan bir nechta savollarni ochib beradi:

Tranzit tugunlari qanday tanlanadi?
Kirish tugunlari qanday tanlangan?
Qaysi mahalliy filtrdan foydalanish kerak?
Mahalliy so'rovlarni qanday hal qilish kerak?

Ushbu ramkaning quyidagi misollarni bajarilishi, ushbu savollarga qoplama katakchalaridagi tugunlarni guruhlash kabi turli xil usullardan foydalangan holda javob beradi panjara^[2] va unga asoslangan yanada murakkab dastur qisqarish ierarxiyalari.^[3]

Panjara yordamida geometrik yondashuv

A panjara - asoslangan yondashuv cheklovchi barcha tugunlarning kvadrati kvadrat kataklarga teng ravishda bo'linadi.

Kirish tugunlari qanday tanlangan?

Ichki maydoni I (to'q sariq) va tashqi maydoni O (ko'k) bo'lgan C (qizil) hujayra uchun tugunlarga (qizil nuqta) kirish

Har bir hujayra uchun ${ displaystyle C}$ , kirish tugunlari to'plamini ichki maydonga qarab topish mumkin ${ displaystyle I}$ 5x5 hujayradan va tashqi maydondan iborat ${ displaystyle O}$ atrofida 9x9 hujayradan iborat ${ displaystyle C}$ . Kesish tugunlariga e'tibor bering (chegarasini kesib o'tuvchi qirralarning uchlari ${ displaystyle C}$ , ${ displaystyle I}$ yoki ${ displaystyle O}$ ) uchun kirish tugunlari ${ displaystyle C}$ ning tugunlari ${ displaystyle I}$ ba'zi tugunlardan eng qisqa yo'lning bir qismi ${ displaystyle C}$ tugunga ${ displaystyle O}$ . Ixtiyoriy tugun uchun kirish tugunlari sifatida ${ displaystyle v in C}$ ning barcha kirish tugunlari ${ displaystyle C}$ tanlangan (o'ngdagi rasmdagi qizil nuqta).

Tranzit tugunlari qanday tanlanadi?

Tranzit tugunlari to'plami - bu barcha kirish tugunlari to'plamining birlashishi.

Qaysi mahalliy filtrdan foydalanish kerak?

Kirish tugunlarini tanlash usuli shuni anglatadiki, agar manba va maqsad to'rtdan ortiq katakchadan ajratilgan bo'lsa, tranzit tugunini eng qisqa yo'ldan o'tkazish kerak va masofani yuqorida tavsiflangan tarzda hisoblash mumkin. Agar ular bir-biriga yaqinroq yotishsa, masofani olish uchun xato-algoritm ishlatiladi.

Mahalliy so'rovlarni qanday hal qilish kerak?

Mahalliy so'rovlar faqat boshlang'ich va maqsad allaqachon bir-biriga yaqinlashganda kerak bo'ladi, shuning uchun har bir eng qisqa yo'l algoritmi, masalan Dijkstra algoritmi yoki uning kengaytmalarini tanlash mumkin.

Joy talablari

Har bir tugun va tegishli kirish tuguni orasidagi oldindan hisoblab chiqilgan masofalar, shuningdek tranzit tugunlari orasidagi juftlik masofalari masofaviy jadvallarda saqlanishi kerak.

Yuqorida keltirilgan tarmoqqa asoslangan dasturda bu yo'l grafikasining har bir tuguni uchun zarur bo'lgan 16 bayt saqlashga olib keladi. AQSh yo'l tarmog'ining to'liq grafigi 23 947 347 tugunga ega.^[5] Shuning uchun taxminan. Masofaviy jadvallarni saqlash uchun 383 MB xotira kerak bo'ladi.

Kasılma iyerarxiyalaridan foydalanish

Tranzit tugunlari qanday tanlanadi?

Ta'rifga ko'ra, a qisqarish iyerarxiyasi muhim tugunlarni (ya'ni eng qisqa yo'llarning bir qismi bo'lgan tugunlarni) ierarxiyaning yuqori qismiga o'tkazadi. Shuning uchun tranzit tugunlari to'plami sifatida tanlanishi mumkin ${ displaystyle k}$ qisqarish iyerarxiyasining eng yuqori tugunlari.

Kirish tugunlari qanday tanlangan?

Tugunning kirish tugunlarini oldinga yo'naltirish ${ displaystyle v}$ dan boshlangan qisqarish iyerarxiyasini yuqoriga qarab qidirish orqali topish mumkin ${ displaystyle v}$ . Davomida yuqoriga qarab qidirish, ilgari topilgan tranzit tugunlarini tark etuvchi qirralarning bo'shashmasligi. Qidiruv tugashi uchun yuqoriga ko'tarish tugunlari qolmaganida, ushbu tranzit tugunlari kirish tugunlari hisoblanadi. ${ displaystyle v}$ . Orqaga kirish tugunlarini o'xshash topish mumkin.

Qaysi mahalliy filtrdan foydalanish kerak?

Agar ierarxiyadagi eng past yuqoriga ko'tarilish yo'lining eng yuqori tuguni tranzit tugunlari to'plamiga kirmasa, u holda so'rov mahalliy bo'lgan. Bu shuni anglatadiki, na yo'lning yuqorigi qismi (boshlang'ich tugundan boshlanadi), na yo'lning pastki qismida (maqsad tugunida tugaydi) tranzit tugunini o'z ichiga olmaydi va ikkala yo'lda ham umumiy tugun bo'lishi shart emas. Kirish tugunlarini hisoblash paytida har bir tugun uchun qidiruv maydoni (barcha tashrif buyurgan tugunlar iyerarxiyaning yuqori qismiga) tranzit tugunlarini kiritmasdan saqlanishi mumkin. So'rovni bajarishda boshlash va maqsad tugunlarini qidirish joylari kesishgan joy uchun tekshiriladi. Agar bu bo'shliqlar bo'lsa ajratish, tranzit tugunlari marshrutizatsiyasidan foydalanish mumkin, chunki yuqoriga va pastga yo'nalishlar tranzit tugunida uchrashishi kerak. Aks holda tranzit tugunisiz eng qisqa yo'l bo'lishi mumkin.

Mahalliy so'rovlarni qanday hal qilish kerak?

Mahalliy so'rovlar odatdagidan foydalanadi so'rov algoritmi qisqarish iyerarxiyasining

Shuningdek qarang

Adabiyotlar

^ ^a ^b Bast, H.; Funke, S .; Sanders, P .; Shultes, D. (2007-04-27). "Tranzit tugunlari bo'lgan yo'l tarmoqlarida tezkor yo'nalish". Ilm-fan. 316 (5824): 566. Bibcode:2007 yil ... 316..566B. doi:10.1126 / science.1137521. ISSN 0036-8075. PMID 17463281.
^ ^a ^b Bast, Xolger; Funke, Stefan; Matievich, Domagoj; Sanders, Piter; Shultes, Dominik (2007-01-06), "Yo'l tarmog'idagi doimiy so'rovlarga doimiy ravishda o'tish", 2007 Algoritm muhandislik va tajribalar bo'yicha to'qqizinchi seminar ishi (ALENEX), Sanoat va amaliy matematika jamiyati, 46–59 betlar, doi:10.1137/1.9781611972870.5, ISBN 9781611972870
^ ^a ^b Arz, Julian; Lyuks, Denis; Sanders, Piter (2013), "Tranzit tugunlari yo'nalishi qayta ko'rib chiqildi", Eksperimental algoritmlar, Springer Berlin Heidelberg, 55-66 betlar, arXiv:1302.5611, Bibcode:2013arXiv1302.5611A, doi:10.1007/978-3-642-38527-8_7, ISBN 9783642385261
^ Shultes, Dominik; Sanders, Piter (2007), "Dinamik magistral-tugun yo'nalishi", Eksperimental algoritmlar, Kompyuter fanidan ma'ruza matnlari, 4525, Springer Berlin Heidelberg, 66-79 betlar, doi:10.1007/978-3-540-72845-0_6, ISBN 9783540728443
^ "9-DIMACSni amalga oshirish bo'yicha choralar: eng qisqa yo'llar". foydalanuvchilar.diag.uniroma1.it. Olingan 2019-07-15.

[:0-1] Bast, H.; Funke, S .; Sanders, P .; Shultes, D. (2007-04-27). "Tranzit tugunlari bo'lgan yo'l tarmoqlarida tezkor yo'nalish". Ilm-fan. 316 (5824): 566. Bibcode:2007 yil ... 316..566B. doi:10.1126 / science.1137521. ISSN 0036-8075. PMID 17463281.

[:1-2] Bast, Xolger; Funke, Stefan; Matievich, Domagoj; Sanders, Piter; Shultes, Dominik (2007-01-06), "Yo'l tarmog'idagi doimiy so'rovlarga doimiy ravishda o'tish", 2007 Algoritm muhandislik va tajribalar bo'yicha to'qqizinchi seminar ishi (ALENEX), Sanoat va amaliy matematika jamiyati, 46–59 betlar, doi:10.1137/1.9781611972870.5, ISBN 9781611972870

[:2-3] Arz, Julian; Lyuks, Denis; Sanders, Piter (2013), "Tranzit tugunlari yo'nalishi qayta ko'rib chiqildi", Eksperimental algoritmlar, Springer Berlin Heidelberg, 55-66 betlar, arXiv:1302.5611, Bibcode:2013arXiv1302.5611A, doi:10.1007/978-3-642-38527-8_7, ISBN 9783642385261

[4] Shultes, Dominik; Sanders, Piter (2007), "Dinamik magistral-tugun yo'nalishi", Eksperimental algoritmlar, Kompyuter fanidan ma'ruza matnlari, 4525, Springer Berlin Heidelberg, 66-79 betlar, doi:10.1007/978-3-540-72845-0_6, ISBN 9783540728443

[5] "9-DIMACSni amalga oshirish bo'yicha choralar: eng qisqa yo'llar". foydalanuvchilar.diag.uniroma1.it. Olingan 2019-07-15.

[1]

[2]

[3]

[4]

[5]