Ruteopgave - Route assignment

Rutetildeling , rutevalg eller trafiktildeling vedrører valg af ruter (alternativ kaldet stier) mellem oprindelser og destinationer i transportnet . Det er det fjerde trin i den konventionelle transportprognosemodel , der følger turgenerering , turfordeling og valg af tilstand . Den zonale udvekslingsanalyse af turdistribution giver rejsetabeller med oprindelsesdestination. Analyse af valg af tilstand fortæller, hvilke rejsende vil bruge, hvilken tilstand . For at bestemme facilitetens behov og omkostninger og fordele skal vi vide antallet af rejsende på hver rute og link på netværket (en rute er simpelthen en kæde af forbindelser mellem en oprindelse og destination). Vi er nødt til at påtage os trafik (eller tur). Antag, at der er et netværk af motorveje og transportsystemer og en foreslået tilføjelse. Vi vil først vide det nuværende mønster af trafikforsinkelse og derefter, hvad der ville ske, hvis tilføjelsen blev foretaget.

Generelle tilgange

Langvarige teknikker

Problemet med at estimere, hvor mange brugere der er på hver rute, er langvarigt. Planlæggere begyndte at se hårdt på det, da motorveje og motorveje begyndte at blive udviklet. Motorvejen tilbød et overordnet serviceniveau over det lokale gadesystem og omdirigerede trafikken fra det lokale system. Først var omdirigering teknikken. Forholdstiden for rejsetid blev brugt, hærdet af hensyn til omkostninger, komfort og serviceniveau .

Den Chicago Area Transport Study (CATS) forskere udviklet omdirigering kurver til motorveje versus lokale gader. Der var også meget arbejde i Californien, for Californien havde tidlige erfaringer med motorvejsplanlægning. Ud over arbejde af en aflednings sort angreb CATS nogle tekniske problemer, der opstår, når man arbejder med komplekse netværk. Et resultat var Bellman – Ford – Moore-algoritmen til at finde de korteste stier på netværk.

Spørgsmålet, som viderestillingsmetoden ikke håndterede, var feedback fra mængden af ​​trafik på links og ruter. Hvis mange køretøjer forsøger at bruge en facilitet, bliver anlægget overbelastet, og rejsetiden øges. Mangler nogen måde at overveje feedback, tidlige planlægningsundersøgelser (faktisk mest i perioden 1960-1975) ignoreret feedback. De brugte Moore-algoritmen til at bestemme de korteste stier og tildelte al trafik til de korteste stier. Det kaldes tildeling af alt eller intet, fordi enten al trafikken fra i til j bevæger sig langs en rute, eller den ikke gør det.

Alt-eller-ingenting eller korteste sti-tildeling er ikke trivielt set fra et teknisk-beregningsmæssigt synspunkt. Hver trafikzone er forbundet til n - 1 zoner, så der er adskillige stier, der skal overvejes. Derudover er vi i sidste ende interesseret i trafik på links. Et link kan være en del af flere stier, og trafik langs stier skal summeres link via link.

Et argument kan fremmes for at tilgodese alt-eller-intet-metoden. Det går denne vej: Planlægningsundersøgelsen er at støtte investeringer, så et godt serviceniveau er tilgængeligt på alle links. Ved hjælp af de rejsetider, der er knyttet til det planlagte serviceniveau, angiver beregninger, hvordan trafikken vil flyde, når forbedringer er på plads. Når man kender mængden af ​​trafik på links, kan den kapacitet, der skal leveres for at opfylde det ønskede serviceniveau, beregnes.

Heuristiske procedurer

For at tage højde for virkningen af ​​trafikbelastning på rejsetider og ligevægte i trafikken blev der udviklet flere heuristiske beregningsprocedurer. Ét heuristisk forløb trinvist. Den trafik, der skal tildeles, er opdelt i dele (normalt 4). Tildel den første del af trafikken. Beregn nye rejsetider, og tildel den næste del af trafikken. Det sidste trin gentages, indtil al trafik er tildelt. CATS brugte en variation på dette; det tildeles række for række i OD-tabellen.

Heuristikken, der er inkluderet i FHWA- samlingen af ​​computerprogrammer, fortsætter på en anden måde.

• 0. Start med at indlæse al trafik ved hjælp af en alt eller intet-procedure.
• 1. Beregn de resulterende køretider og tildel trafik.
• 2. Begynd nu at tildele igen ved hjælp af vægte. Beregn de vægtede køretider i de foregående to belastninger, og brug dem til den næste opgave. Den seneste iteration får en vægt på 0,25 og den foregående får en vægt på 0,75.
• 3. Fortsæt.

Disse procedurer ser ud til at fungere "temmelig godt", men de er ikke nøjagtige.

Frank-Wolfe algoritme

Dafermos (1968) anvendte Frank-Wolfe-algoritmen (1956, Florian 1976), som kan bruges til at tackle problemet med trafikbalance. Antag, at vi overvejer et motorvejsnetværk. For hvert link er der en funktion, der angiver forholdet mellem modstand og trafikmængde. Den Bureau of offentlige veje (BPR) udviklet et link (bue) overbelastning (eller volumen-forsinkelse, eller ydeevne link) funktion, som vi vil sigt S _en (v _en )

${\ displaystyle S_ {a} \ venstre ({v_ {a}} \ højre) = t_ {a} \ venstre ({1 + 0,15 \ venstre ({\ frac {v_ {a}} {c_ {a}}} \ højre) ^ {4}} \ højre)}$

• t _a = frit flow rejsetid på link a pr. tidsenhed
• v _a = trafikmængde på link a pr. tidsenhed (noget mere præcist: flow, der forsøger at bruge link a ).
• c _a = kapacitet for link a pr. tidsenhed
• S _a (v _a ) er den gennemsnitlige rejsetid for et køretøj på link a

Der er andre overbelastningsfunktioner. CATS har længe brugt en anden funktion end den, der bruges af BPR, men det ser ud til at være ringe forskel mellem resultaterne, når CATS og BPR-funktionerne sammenlignes.

Ligevægttildeling

For at tildele trafik til stier og links skal vi have regler, og der er de velkendte Wardrop-ligevægtsbetingelser . Essensen af ​​disse er, at rejsende vil bestræbe sig på at finde den korteste (mindst modstandsdygtige) sti fra oprindelse til destination, og netværksbalance opstår, når ingen rejsende kan mindske rejseindsatsen ved at skifte til en ny sti. Disse betegnes som optimale brugerbetingelser, for ingen brugere vil drage fordel af at ændre rejseveje, når systemet er i ligevægt.

Brugeren optimal ligevægt kan findes ved at løse følgende ulineære programmering problem

${\ displaystyle \ min \ sum _ {a} {\ int _ {0} ^ {v_ {a}} {S_ {a} \ venstre (x \ højre)}} dx}$

underlagt:

${\ displaystyle v_ {a} = \ sum _ {i} {\ sum _ {j} {\ sum _ {r} {\ alpha _ {ij} ^ {ar} x_ {ij} ^ {r}}}} }$

${\ displaystyle \ sum _ {r} {x_ {ij} ^ {r} = T_ {ij}}}$

${\ displaystyle v_ {a} \ geq 0, \; x_ {ij} ^ {r} \ geq 0}$

hvor er antallet af køretøjer på sti r fra oprindelse i til destination j . Så begrænsning (2) siger, at al rejse skal finde sted - i = 1 ... n; j = 1 ... n${\ displaystyle x_ {ij} ^ {r}}$

${\ displaystyle \ alpha _ {ij} ^ {ar}}$= 1, hvis link a er på sti r fra i til j; ellers ellers. Så begrænsning (1) summerer trafik på hvert link. Der er en begrænsning for hvert link på netværket. Begrænsning (3) sikrer ingen negativ trafik.

Eksempel

Et eksempel fra Eash, Janson og Boyce (1979) illustrerer løsningen på det ikke-lineære programproblem. Der er to links fra knudepunkt 1 til knudepunkt 2, og der er en modstandsfunktion for hvert link (se figur 1). Områder under kurverne i figur 2 svarer til integrationen fra 0 til a i ligning 1, de udgør 220.674. Bemærk, at funktionen for link b er afbildet i modsat retning.

${\ displaystyle S_ {a} = 15 \ venstre ({1 + 0,15 \ venstre ({\ frac {v_ {a}} {1000}} \ højre) ^ {4}} \ højre)}$

${\ displaystyle S_ {b} = 20 \ venstre ({1 + 0,15 \ venstre ({\ frac {v_ {b}} {3000}} \ højre) ^ {4}} \ højre)}$

${\ displaystyle v_ {a} + v_ {b} = 8000}$

Figur 1: To-rutenetværk

Figur 2: Grafisk løsning på problemet med ligevægtstildeling

Figur 3: Tildeling af køretøjer, der ikke opfylder ligevægtsbetingelserne

Ved ligevægt er der 2.152 køretøjer på link a og 5847 på link b . Rejsetid er den samme på hver rute: ca. 63.

Figur 3 illustrerer en tildeling af køretøjer, der ikke er i overensstemmelse med ligevægtsopløsningen. Kurverne er uændrede. Men med den nye tildeling af køretøjer til ruter, skal det skraverede område inkluderes i løsningen, så fig. 3-løsningen er større end løsningen i figur 2 af området for det skraverede område.

Integrering af rejsevalg

Byplanlægningsmodellen udviklede sig som et sæt trin, der skal følges, og modeller udvikledes til brug i hvert trin. Nogle gange var der trin inden for trin, som det var tilfældet med den første erklæring om Lowry-modellen . I nogle tilfælde er det blevet bemærket, at trin kan integreres. Mere generelt abstraherer trinnene fra beslutninger, der kan træffes samtidig, og det ville være ønskeligt at gentage det bedre i analysen.

Modtagne efterspørgselsmodeller blev først udviklet til at behandle problemet med valg af tilstand. Dette problem antager, at man har besluttet at tage en tur, hvor den tur vil gå, og på hvilket tidspunkt turen vil blive foretaget. De er blevet brugt til at behandle den implicitte bredere kontekst. Typisk vil en indlejret model blive udviklet, fx starte med sandsynligheden for, at der foretages en tur, derefter undersøge valget mellem steder og derefter valg af tilstand. Rejsetidspunktet er lidt sværere at behandle.

Wilsons dobbelt begrænsede entropimodel har været udgangspunktet for indsatsen på det samlede niveau. Denne model indeholder begrænsningen

${\ displaystyle t_ {ij} c_ {ij} = C}$

hvor det er linkets rejseomkostninger, henviser til trafik på et link, og C er en ressourcebegrænsning, der skal dimensioneres, når modellen monteres med data. I stedet for at bruge den form for begrænsning, kan den monotonisk stigende modstandsfunktion, der bruges i trafiktildeling, bruges. Resultatet bestemmer bevægelser fra zone til zone og tildeler trafik til netværk, og det giver meget mening ud fra den måde, man kan forestille sig, at systemet fungerer - zone-til-zone-trafik afhænger af modstanden som følge af overbelastning. ${\ displaystyle c_ {ij}}$${\ displaystyle t_ {ij}}$

Alternativt kan forbindelsesmodstandsfunktionen inkluderes i objektivfunktionen (og den samlede omkostningsfunktion elimineres fra begrænsningerne).

En generaliseret uoverensstemmende valgmetode er udviklet, ligesom en generaliseret samlet tilgang. Det store spørgsmål er forholdet mellem dem. Når vi bruger en makromodel, vil vi gerne vide den uensartede adfærd, den repræsenterer. Hvis vi laver en mikroanalyse, vil vi gerne vide de samlede implikationer af analysen.

Wilson henter en tyngdekraftlignende model med vægtede parametre, der siger noget om attraktiviteten af ​​oprindelser og destinationer. Uden for meget matematik kan vi skrive sandsynlighed for valgsætninger baseret på attraktivitet, og disse tager en form, der ligner nogle sorter af forskellige efterspørgselsmodeller.

Integrering af rejseefterspørgsel med rutetildeling

Det har længe været erkendt, at rejseefterspørgsel er påvirket af netforsyning. Eksemplet på en ny broåbning, hvor ingen var før, der inducerede yderligere trafik, er blevet bemærket i århundreder. Meget forskning er gået i at udvikle metoder til at lade prognosesystemet direkte tage højde for dette fænomen. Evans (1974) offentliggjorde en doktorafhandling om en matematisk streng kombination af tyngdekraftsfordelingsmodellen med ligevægttildelingsmodellen. Den tidligste citation af denne integration er Irwin og Von Cube's arbejde, som det er relateret af Florian et al. (1975), der kommenterer Evans 'arbejde:

"Evans 'arbejde ligner noget af algoritmerne, der er udviklet af Irwin og Von Cube [" Kapacitetsbegrænsning i Multi-Travel Mode Assignment Programs "HRB Bulletin 347 (1962)] til en transportundersøgelse af Toronto . Deres arbejde giver mulighed for feedback mellem overbelastet tildeling og turfordeling, selvom de anvender sekventielle procedurer. Fra en initial løsning af distributionsproblemet tildeles de interzonale ture til de første korteste ruter. For successive iterationer beregnes nye korteste ruter, og deres længder bruges som adgangstider til input fordelingsmodellen. De nye interzonale strømme tildeles derefter i en vis proportion til de allerede fundne ruter. Proceduren stoppes, når de interzonale tider for successiv iteration er kvasi-lige. "

Florian et al. foreslog en noget anden metode til løsning af den kombinerede distributionstildeling ved direkte anvendelse af Frank-Wolfe-algoritmen. Boyce et al. (1988) opsummerer forskningen på Network Equilibrium Problems, herunder opgaven med elastisk efterspørgsel.

Diskussion

Et problem med tre forbindelser kan ikke løses grafisk, og de fleste transportnetproblemer involverer et stort antal noder og links. Eash et al. Studerede for eksempel vejnettet på DuPage County, hvor der var omkring 30.000 envejsforbindelser og 9.500 knudepunkter. Da problemerne er store, er der behov for en algoritme for at løse tildelingsproblemet, og Frank-Wolfe-algoritmen (med forskellige moderne ændringer siden først offentliggjort) bruges. Start med en alt eller intet tildeling, og følg derefter den regel, der er udviklet af Frank-Wolfe for at iterere mod minimumværdien af ​​objektivfunktionen. (Algoritmen anvender successive gennemførlige løsninger for at opnå konvergens til den optimale løsning. Den bruger en effektiv søgeprocedure for at flytte beregningen hurtigt mod den optimale løsning.) Rejsetider svarer til de dobbelte variabler i dette programmeringsproblem.

Det er interessant, at Frank-Wolfe-algoritmen var tilgængelig i 1956. Dens anvendelse blev udviklet i 1968, og det tog næsten to årtier, før den første ligevægttildelingsalgoritme blev integreret i almindeligt anvendt transportplanlægningssoftware ( Emme og Emme / 2 , udviklet af Florian og andre i Montreal). Vi ønsker ikke at drage nogen generel konklusion fra den langsomme anvendelsesobservation, hovedsageligt fordi vi kan finde modeksempler om tempo og mønster for teknikudvikling. F.eks. Blev simplex-metoden til løsning af lineære programmeringsproblemer udarbejdet og anvendt i vid udstrækning inden udviklingen af ​​meget af programmeringsteorien.

Problemopgørelsen og algoritmen har generelle anvendelser på tværs af anlægsvirksomhed - hydraulik, konstruktioner og konstruktion. (Se Hendrickson og Janson 1984).

Empiriske studier af rutevalg

Rutetildelingsmodeller er i det mindste til en vis grad baseret på empiriske undersøgelser af, hvordan folk vælger ruter i et netværk . Sådanne undersøgelser er generelt fokuseret på en bestemt tilstand og gør brug af enten angivet præference eller afslørede præferencemodeller .

Cykel

Cyklister har vist sig at foretrække udpegede cykelstier og undgå stejle bakker.

Offentlig transport

Offentlig transport er længe blevet overvejet i forbindelse med rutetildeling, og der er foretaget mange undersøgelser af valg af transitrute. Blandt andre faktorer forsøger transitbrugere at minimere den samlede rejsetid, tid eller afstand gåafstand og antallet af overførsler.

Se også

• Rutevalg (disambiguation)

Noter

Generelle referencer

• Dafermos, Stella. C. og FT Sparrow Trafikdelingsproblemet for et generelt netværk. ” J. fra Res. fra National Bureau of Standards, 73B, s. 91-118. 1969.
• Florian, Michael red., Traffic Equilibrium Methods, Springer-Verlag, 1976.
• Eash, Ronald, Bruce N. Janson og David Boyce Equilibrium Trip Assignment: Fordele og implikationer for praksis, transportforskningsrekord 728, s. 1-8, 1979.
• Evans, Suzanne P.. "Afledning og analyse af nogle modeller til at kombinere rejsedistribution og tildeling." Transportforskning, bind 10, s. 37–57 1976
• Hendrickson, CT og BN Janson, “En fælles netværksflowformulering til flere civilingeniørproblemer” Civil Engineering Systems 1 (4), s. 195–203, 1984