En lösning ges för vad som verkar vara ett 30-årigt problem som handlar om upptäckten av de mest effektiva algoritmer som är möjliga att beräkna all-till-en kortaste vägar i diskreta dynamiska nätverk. Detta problem ligger i centrum för effektiva lösningar på dynamiska nätverksmodeller som uppstår i dynamiska transportsystem, såsom intelligenta transportsystem (ITS-tillämpningar). De allt-till-ett dynamiska kortaste banor problem och de one-to-all snabbaste banor problem studeras. Tidiga resultat återbesöks och nya fastigheter etableras. Komplexiteten i dessa problem är etablerad, och lösningsalgoritmer som är optimala för körtiden utvecklas. En ny och enkel lösningsalgoritm föreslås för allt-till-ett, alla avgångstidsintervall, kortaste sökvägar problem. Det är teoretiskt bevisat att den nya lösningen algoritm har en optimal körtid komplexitet som motsvarar komplexiteten i problemet. Datorimplementationer och experimentella utvärderingar av olika lösningsalgoritmer stöder de teoretiska resultaten och visar hur effektiv den föreslagna lösningsalgoritmen är. Resultaten bör vara till stor nytta för forsknings- och utvecklingsverksamhet inom området dynamisk förvaltning, särskilt realtidsförvaltning, och för kontrollen av storskaliga intelligenta transportsystem. Det kortaste problemet i nätverken har varit föremål för omfattande forskning under många år (1). Analysen av transportnät är ett av de många tillämpningsområden där beräkning av kortaste vägar är ett av de mest grundläggande problemen. Majoriteten av den publicerade forskningen om kortaste vägar algoritmer, dock, handlade om statiska nätverk som har fast topologi och fasta länkkostnader. Intresset för begreppet dynamisk förvaltning av transportsystem har ökat. Nya framsteg har väckt nytt intresse för studien av kortaste vägar problem med en ny twist: Link kostnader beror i allmänhet på inträdestiden för en länk. Detta resulterar i en ny familj av kortaste vägar problem som kallas dynamiska, eller tidsberoende, kortaste vägar problem. Chabini (2) skiljer olika typer av dynamiska kortaste banproblem beroende på följande: a) snabbast kontra lägsta kostnad (eller kortaste) vägproblem; b) diskret kontra kontinuerlig representation av tid; c) första-in-first-out (FIFO) nätverk kontra icke-FIFO-nätverk, där man kan avgå senare i början av en eller flera bågar och komma tidigare i slutet; d) vänta är tillåtet kontra vänta är inte tillåtet vid noder; e) typer av kortaste väg frågor frågade: en-to-all för en viss avgångstid eller alla avgångstider, och allt-till-ett för alla avgångstider; och f ) heltal kontra verkliga värderade länk restider och länk resekostnader. Vid snabbast möjliga vägproblem är kostnaden för en länk resetiden för den länken. När det gäller problem med minimikostnader kan kopplingskostnaderna vara av allmän karaktär. Även om problemet med de snabbaste vägarna är ett särskilt fall av problemet med minimikostnadsvägar, är distinktionen mellan de två särskilt viktig för utformningen av effektiva lösningsalgoritmer. Tidsberoende marginalresor i systemoptimala dynamiska modeller för trafiktilldelning är ett exempel på allmänna formkostnader. Beroende på hur tid behandlas, kan dynamiska kortaste vägar problem delas in i två typer: diskret och kontinuerlig. I diskreta dynamiska nätverk modelleras tiden som en uppsättning heltal. Orda och Rom (3) etablerar olika egenskaper för kontinuerliga dynamiska nätverk där tiden behandlas som reella tal. Resultaten för oneto-all snabbaste banor problem studeras här gäller för både diskreta och kontinuerliga representationer av tid. Det är viktigt att notera att ett diskret dynamiskt nätverk kan ses alternativt som ett statiskt nätverk som erhålls genom att använda en tidrymdsexpansion representation. Storleken på motsvarande representation beror på väntande policy vid noder. Som man kan förvänta sig är det inte det bästa sättet att uttryckligen använda tidsrymdens expansionsrepresentation för att beräkna dynamiska kortaste vägar. Tid-rymd-expansionsnätverket har dock vissa särskilda egenskaper som kan utnyttjas i utformningen av effektiva kortaste vägar algoritmer. Utmaningen är att upptäcka särskilda egenskaper hos dessa nätverk och på lämpligt sätt utnyttja dem i utformningen av bättre algoritmer. Jämfört med att för statiska kortaste vägar problem, litteraturen på dynamiska versioner är mycket begränsad. Det viktigaste kända resultatet är det tillstånd under vilket statiska kortaste banalgoritmer kan användas, utan extra kostnad, för att lösa problemet med one-to-all snabbaste vägar i dynamiska nätverk: Arc restider måste uppfylla FIFO villkor. Gömd bakom detta resultat finns olika begränsningar: 1. Detta resultat gäller endast problemet med de snabbaste vägarna och inte problemet med de lägsta kostnaderna. 2. Utgångspunkten är följande: Detta resultat är begränsat till endast framåtsökande algoritmer. Transporttillämpningar behöver beräkna snabbaste vägar från alla noder till en uppsättning destinationer. Därför skulle statiska metoder normalt först beräkna snabbaste vägar från alla noder till alla noder och sedan extrahera nödvändiga lösningar. Eftersom antalet destinationer i ett transportnät vanligtvis är en liten del av det totala antalet noder, kan en statisk strategi inte leda till bästa möjliga lösningsalgoritm. 3. Vad är det som händer? Transporttillämpningar uppfyller inte nödvändigtvis FIFO-villkoret. 4. Vad är det som händer? En statisk algoritm beräknar kortaste vägar för ett avgångstidsintervall endast, men kortaste vägar för alla möjliga avgångstidsintervall eftersträvas i allmänhet. Trafikledningscentra i intelligenta transportsystem (ITS) måste fungera i realtid. Den tid det tar att samla in uppgifter, bearbeta dem och sända de uppgifter som blir resultatet kan komma att
En annan viktig routing control tillvägagångssätt är Decreasing Order of Time (DOT) algoritm REF, som effektivt finner den tidsberoende kortaste vägen (använder restid) inom ett användarvalt tidsfönster.
Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time
{'venue': '234 I. Chabini. Minimum expected travel times in stochastic time-dependent networks revisited. Internal Report. MIT', 'journal': None, 'mag_field_of_study': ['Computer Science']}