Transit nod routing

I tillämpad matematik kan routing för transitnoder användas för att påskynda routing med kortaste vägen genom att förberäkna anslutningar mellan gemensamma åtkomstnoder till ett undernätverk som är relevant för långdistansresor .

Transit nod routing som ett ramverk etablerades 2007 och många konkreta implementeringar har dykt upp under åren efter, såsom tillvägagångssätt som använder rutnät, motorvägshierarkier och kontraktionshierarkier . Transit nod routing är ett statiskt tillvägagångssätt som kräver förbearbetning av parvisa avstånd mellan viktiga noder i grafen (se nedan hur dessa noder väljs). Ett dynamiskt tillvägagångssätt har inte publicerats.

Intuition

Flera rutter som använder samma accessnoder till långväga vägnät.

Långdistansresor innebär vanligtvis att man kör längs en delmängd av vägnätet som motorvägar istället för t.ex. stadsvägar. Detta undernätverk kan endast kommas in genom att använda glest fördelade åtkomstnoder . Jämfört med varandra använder flera långdistansrutter som börjar på samma plats alltid samma lilla mängd åtkomstnoder nära startplatsen för att komma in i detta nätverk. På samma sätt nås alltid liknande målplatser genom att använda samma accessnoder nära dem. Denna intuition gäller bara för långväga resor. När du reser korta sträckor kanske sådana accessnoder aldrig används eftersom den snabbaste vägen till målet endast använder lokala vägar.

Eftersom antalet sådana accessnoder är litet jämfört med det totala antalet noder i ett vägnät, kan alla kortaste vägar som förbinder dessa noder med varandra förberäknas och lagras. Vid beräkning av en kortaste väg behöver därför endast rutter till accessnoder nära start och målplats beräknas.

Allmän ram

Transitnodsrutt börjar med ett urval av transitnoder $T\subseteq V$ som en delmängd av alla noder $V$ i vägnätet.
För varje nod $v\in V$ dedikerade uppsättningar av framåtåtkomstnoder ${\overrightarrow {A}}(v)\subseteq T$ och bakåtåtkomstnoder ${\overleftarrow {A}}(v)\subseteq T$ väljs från alla transitnoder.
beräknas och lagras parvisa avstånd mellan transitnoder $D_{T}$ och avstånd mellan noder $v$ och deras motsvarande accessnoder ${\displaystyle d_{A}} .$
Ett avstånd mellan två noder kan nu beräknas som $d(s,t)=\min _{u\in {\overrightarrow {A}}(s),v\in {\overleftarrow {A}}(t)}d_{ A}(s,u)+D_{T}(u,v)+d_{A}(v,t)$

Lokalitetsfilter

Korta rutter mellan nära start- och målplatser kanske inte kräver några transitnoder. I det här fallet leder ovanstående ramverk till felaktiga avstånd eftersom det tvingar rutter att besöka minst en transitnod.

För att förhindra denna typ av problem kan ett lokalitetsfilter användas. För givna start- och målplatser bestämmer lokalitetsfiltret om routing för transitnod ska tillämpas eller om en reservrutin ska användas (lokal fråga).

Konkreta instanser

Transit nod routing är inte en algoritm utan bara ett ramverk för att påskynda ruttplanering. Det allmänna ramverket lämnar öppna några frågor som måste besvaras för att implementera det:

Hur väljs transitnoder?
Hur väljs åtkomstnoder?
Vilket lokalitetsfilter ska användas?
Hur ska lokala frågor hanteras?

Följande exempelimplementeringar av detta ramverk besvarar dessa frågor med hjälp av olika underliggande metoder som att gruppera noder i celler i ett överlagringsnät och en mer sofistikerad implementering baserad på kontraktionshierarkier .

Geometriskt tillvägagångssätt med hjälp av rutnät

I ett rutnätsbaserat tillvägagångssätt är den gränsande kvadraten för alla noder lika uppdelad i kvadratiska celler.

Hur väljs åtkomstnoder?

Åtkomstnoder (röda prickar) för en cell C (röd) med inre område I (orange) och yttre område O (blå)

För varje cell $C$ kan en uppsättning åtkomstnoder hittas genom att titta på ett inre område $I$ på 5x5 celler och ett yttre område $O$ på 9x9 celler runt ${\ displaystil C}$ . Med fokus på att korsa noder (ändarna av kanter som korsar gränsen för ${\displaystyle C} ,$ I $\displaystyle I}$ eller ${\displaystyle O} ),$ är åtkomstnoderna för ${\displaystyle C} de noderna för$ $I$ som är en del av en kortaste väg från någon nod i $C$ till en nod i $O$ . Som accessnoder för en godtycklig nod ${\displaystyle v\in C} är$ alla accessnoder för $C$ valda (röda prickar i bilden till höger).

Hur väljs transitnoder?

Uppsättningen av transitnoder är exakt föreningen av alla uppsättningar av accessnoder.

Vilket lokalitetsfilter ska användas?

Sättet som accessnoder väljs innebär att om källan och målet är mer än fyra rutnätsceller från varandra måste en transitnod passeras på den kortaste vägen och avståndet kan beräknas enligt beskrivningen ovan. Om de ligger närmare varandra används en fallback-algoritm för att få fram avståndet.

Hur ska lokala frågor hanteras?

Lokala förfrågningar behövs bara om start och mål redan ligger nära varandra, därför kan varje lämplig algoritm för kortaste vägen, såsom Dijkstras algoritm eller tillägg därav, väljas.

Utrymmeskrav

De förberäknade avstånden mellan varje nod och motsvarande accessnod samt de parvisa avstånden mellan transitnoder måste lagras i avståndstabeller.

I den rutnätsbaserade implementeringen som beskrivs ovan resulterar detta i 16 byte lagring som krävs för varje nod i vägdiagrammet. En fullständig graf över USA:s vägnät har 23 947 347 noder. Därför ca. 383 MB lagringsutrymme skulle krävas för att lagra avståndstabellerna.

Använda kontraktionshierarkier

Hur väljs transitnoder?

Per definition flyttar en kontraktionshierarki viktiga noder (dvs noder som är en del av många kortaste vägar) till toppen av hierarkin. En uppsättning transitnoder kan därför väljas som de $k$ högsta noderna i kontraktionshierarkin.

Hur väljs åtkomstnoder?

Framåtkomstnoder för en nod $v$ kan hittas genom att köra sökningen uppåt i kontraktionshierarkin med början på $v$ . Under sökningen uppåt är kanter som lämnar tidigare hittade transitnoder inte avslappnade. När sökningen inte har fler uppåtgående noder kvar att avgöra, är de transitnoder som har avgjorts accessnoderna för $v$ . Bakåtåtkomstnoder kan hittas analogt.

Vilket lokalitetsfilter ska användas?

Om den högsta noden i en kortaste upp-ned-väg i hierarkin inte är en del av uppsättningen transitnoder, då var frågan lokal. Detta innebär att varken upp-delen av vägen (som börjar vid startnoden) eller neddelen av vägen (slutar vid målnoden) kan innehålla en transitnod och det måste finnas en gemensam nod i båda vägarna. Under beräkningen av accessnoderna kan sökutrymmet (alla besökta noder mot toppen av hierarkin) för varje nod lagras utan att inkludera transitnoder. När en fråga utförs, kontrolleras dessa sökutrymmen för start- och målnod för en korsning. Om dessa utrymmen är osammanhängande kan routing för transitnod användas eftersom upp- och nedvägarna måste mötas vid en transitnod. Annars kan det finnas en kortaste väg utan en transitnod.

Hur ska lokala frågor hanteras?

Lokala frågor använder den vanliga frågealgoritmen för sammandragningshierarkin.

Se även