Assegnazione route - Route assignment

Assegnazione route , scelta del percorso , o l'assegnazione del traffico riguarda la selezione dei percorsi (percorsi alternativi chiamato) tra le origini e le destinazioni in reti di trasporto . È la quarta fase del convenzionale previsione trasporto modello, seguendo generazione viaggio , distribuzione degli spostamenti , e la scelta modalità . L'analisi di interscambio zonale della distribuzione viaggio fornisce tavoli viaggio origine-destinazione. Analisi scelta Modalità dice che i viaggiatori utilizzeranno il quale modalità . Per determinare le esigenze degli impianti e dei costi e benefici, abbiamo bisogno di sapere il numero dei viaggiatori su ciascuna rotta e il collegamento della rete (un percorso è semplicemente una catena di collegamenti tra una partenza e arrivo). Abbiamo bisogno di intraprendere il traffico (o viaggio) assegnazione. Supponiamo che ci sia una rete di autostrade e sistemi di trasporto e di una proposta di aggiunta. Per prima cosa vogliamo sapere l'attuale modello di ritardo del traffico e poi cosa sarebbe successo se l'aggiunta sono state fatte.

assegnazione automatica

tecniche di lunga data

Il problema di stimare quanti utenti sono su ogni percorso è di lunga data. Pianificatori iniziato a guardare duro come autostrade e superstrade ha cominciato ad essere sviluppato. L'autostrada ha offerto un livello superiore di servizio sul sistema stradale e locale, e deviato il traffico dal sistema locale. In un primo momento, la deviazione era la tecnica. Rapporti di tempo di viaggio sono stati utilizzati, temperato da considerazioni di costo, la comodità e livello di servizio .

I Chicago Area Servizi di trasporto Study (CATS) i ricercatori hanno sviluppato le curve di deviazione per autostrade contro strade locali. C'era molto lavoro in California anche, per la California ha avuto le prime esperienze con la pianificazione autostrada. Oltre al lavoro di un diversivo sorta, i gatti hanno attaccato alcuni problemi tecnici che sorgono quando si lavora con le reti complesse. Un risultato è stato l' algoritmo di Bellman-Ford-Moore per la ricerca di percorsi più brevi sulle reti.

La questione l'approccio diversione non ha gestito è stato il feedback da parte la quantità di traffico su collegamenti e percorsi. Se un sacco di veicoli tenta di utilizzare una struttura, l'impianto diventa tempo aumenta congestionate e di viaggio. In assenza di qualche modo per prendere in considerazione il feedback, studi di pianificazione primi (in realtà, la maggior parte nel periodo 1960-1975) ignorato feedback. Hanno usato l'algoritmo di Moore per determinare i percorsi più brevi e assegnati tutto il traffico a percorsi più brevi. Questo si chiama tutto o assegnazione niente perché o tutto il traffico da i a j si muove lungo un percorso o non è così.

Il più corto assegnazione del percorso di tutto o niente o non è banale da un punto di vista tecnico-computazionale. Ogni zona traffico è collegato a n - 1 zone, quindi ci sono numerosi percorsi da considerare. Inoltre, siamo in ultima analisi, interessati a traffico sui link. Un collegamento può essere una parte di diversi percorsi, e il traffico lungo i sentieri deve essere riassunta anello per anello.

Un argomento può essere fatto favorendo l'approccio tutto-o-niente. Va in questo modo: Lo studio di pianificazione è quello di sostenere gli investimenti in modo che un buon livello di servizio è disponibile su tutti i link. Utilizzando i tempi di viaggio associate al livello previsto del servizio, calcoli indicano come il traffico scorrerà una volta miglioramenti sono in atto. Conoscere le quantità di traffico sui link, la capacità da fornire per soddisfare il livello di servizio desiderato può essere calcolato.

procedure euristiche

Per tener conto degli effetti del carico di traffico sui tempi di viaggio e gli equilibri del traffico, diverse euristiche sono state sviluppate procedure di calcolo. Un'euristica procede in modo incrementale. Il traffico da assegnare è diviso in parti (in genere 4). Assegnare la prima parte del traffico. Calcolare nuovi tempi di percorrenza e assegnare la parte successiva del traffico. L'ultimo passo è ripetuto fino a quando viene assegnato tutto il traffico. I gatti usato una variante di questa; esso assegnato riga per riga nella tabella OD.

L'euristica incluso nella collezione FHWA di programmi per computer procede in un altro modo.

• 0. Inizia caricando tutto il traffico utilizzando una procedura di tutto o niente.
• 1. Calcolare i tempi di percorrenza e conseguenti riassegnare il traffico.
• 2. Ora, cominciano a riassegnare utilizzando pesi. Calcolare i tempi di percorrenza ponderata negli ultimi due carichi e utilizzare quelli per l'assegnazione seguente. L'ultima iterazione ottiene un peso di 0,25 e il precedente ottiene un peso di 0,75.
• 3. Continuare.

Queste procedure sembrano funzionare “abbastanza bene”, ma non sono esatti.

algoritmo di Frank-Wolfe

Dafermos (1968) ha applicato l'algoritmo di Frank-Wolfe (1956, Florian 1976), che può essere utilizzato per affrontare il problema del traffico di equilibrio. Supponiamo che stiamo considerando una rete autostradale. Per ogni link v'è una funzione che indica il rapporto tra resistenza e volume di traffico. Il Bureau of Public Roads (BPR) ha sviluppato un collegamento (ARC) di congestione (o il volume di ritardo, o un link performance) funzione, che chiameremo S _un (v _una )

${\ Displaystyle S_ {a} \ left ({V_ {a}} \ right) = t_ {a} \ left ({1 + 0,15 \ sinistra ({\ frac {V_ {a}} {c_ {a}}} \ right) ^ {4}} \ right)}$

• t _un = flusso libero tempo di viaggio a navigare una per unità di tempo
• v _un = volume di traffico sul collegamento di una per unità di tempo (un po 'più preciso: il flusso di tentare di utilizzare collegamento un ).
• c _un = capacità di collegamento una per unità di tempo
• S _un (v _una ) è il tempo medio di marcia per un veicolo su link in un

Ci sono altre funzioni di congestione. CATS ha utilizzato lungo una funzione differente da quello utilizzato dal BPR, ma sembra che ci sia poca differenza tra risultati quando i gatti e funzioni BPR vengono confrontati.

assegnazione Equilibrium

Per assegnare il traffico verso percorsi e collegamenti che dobbiamo avere regole, e ci sono il noto equilibrio Wardrop (1952) condizioni. L'essenza di questi è che i viaggiatori si adopererà per trovare il (minor resistenza) percorso dall'origine più breve per raggiungere la destinazione e l'equilibrio della rete si verifica quando nessun viaggiatore può diminuire lo sforzo di viaggio spostando ad un nuovo percorso. Questi sono definiti condizioni ottimali utente, per nessun utente guadagnerà di modificare i percorsi di viaggio una volta che il sistema è in equilibrio.

L'equilibrio ottimale utente può essere trovata risolvendo il seguente problema di programmazione non lineare

${\ Displaystyle \ min \ somma _ {a} {\ int _ {0} {^ v_ {a}} {S_ {a} \ left (x \ right)}}} dx$

soggetto a:

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

${\ Displaystyle \ somma _ {r} {x_ {ij} ^ {r} = T_ {ij}}}$

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

dove è il numero di veicoli sul percorso r dall'origine i alla destinazione j . Così vincolo (2) dice che tutte le deve avvenire - i = 1 ... n; j = 1 ... n${\ Displaystyle x_ {ij} ^ {r}}$

${\ Displaystyle \ alpha _ {ij} ^ {ar}}$= 1 se il collegamento a è sul percorso r da i a j; zero altrimenti. Così vincolo (1) riassume il traffico su ogni link. C'è un vincolo per ogni link sulla rete. Vincolo (3) assicura senza traffico negativo.

Esempio

Un esempio da Eash, Janson, e Boyce (1979) illustrerà la soluzione del problema non lineare programma. Ci sono due collegamenti da nodo 1 a nodo 2, e v'è una funzione di resistenza per ciascun collegamento (vedere Figura 1). Aree sotto le curve nella figura 2 corrispondono alla integrazione da 0 a un nell'equazione 1, si sommano a 220.674. Si noti che la funzione per il link B è tracciata nella direzione inversa.

${\ Displaystyle S_ {a} = 15 \ a sinistra ({1 + 0,15 \ sinistra ({\ frac {V_ {a}} {1000}} \ right) ^ {4}} \ right)}$

${\ Displaystyle S_ {b} = 20 \ a sinistra ({1 + 0,15 \ sinistra ({\ frac {V_ {b}} {3000}} \ right) ^ {4}} \ right)}$

${\ Displaystyle v_ {a} + V_ {b} = 8000}$

Figura 1: Due Route di rete

Figura 2: soluzione grafica al Assignment problema dell'equilibrio

Figura 3: assegnazione dei veicoli che non soddisfano la condizione di equilibrio

All'equilibrio ci sono 2.152 veicoli sul collegamento di una e 5847 sul collegamento b . Il tempo di percorrenza è la stessa su ogni percorso: circa 63.

La Figura 3 illustra un'allocazione di veicoli che non è coerente con la soluzione di equilibrio. Le curve sono invariati. Ma con la nuova assegnazione di veicoli a percorsi l'area ombreggiata deve essere incluso nella soluzione, quindi la soluzione figura 3 è maggiore della soluzione in figura 2 con l'area della zona ombreggiata.

assegnazione di transito

Ci sono anche metodi che sono stati sviluppati da assegnare ai passeggeri di veicoli in transito.

L'integrazione di scelte di viaggio

Il modello di pianificazione trasporto urbano si è evoluto come una serie di passi da seguire e modelli evoluti per l'uso in ogni passo. A volte ci sono stati passi all'interno di passi, come è avvenuto per la prima dichiarazione del modello di Lowry . In alcuni casi, è stato osservato che le fasi possono essere integrati. Più in generale, i passaggi astratte dalle decisioni che possono avvenire simultaneamente, e sarebbe auspicabile replicare meglio che nell'analisi.

modelli di domanda disaggregare sono stati sviluppati per trattare il problema di scelta modalità. Quel problema presuppone che si è deciso di fare un viaggio, in cui quel viaggio andrà, e in quale momento sarà fatto il viaggio. Essi sono stati utilizzati per il trattamento di un contesto più ampio implicita. In genere, un modello nidificato sarà sviluppato, per esempio, a partire dalla probabilità di un viaggio compiuti, quindi esaminando la scelta tra i luoghi, e quindi scelta la modalità. Il tempo di viaggio è un po 'più difficile da trattare.

modello di entropia doppiamente vincolata di Wilson è stato il punto di partenza per gli sforzi a livello aggregato. Quel modello contiene il vincolo

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

dove la sono le spese di viaggio di collegamento, si riferisce al traffico su un link, e C è un vincolo di risorse per essere dimensionati nel montaggio del modello con i dati. Invece di utilizzare tale forma di vincolo, la funzione monotona crescente resistenza utilizzato in assegnazione traffico può essere utilizzato. Il risultato determina movimenti zone-a-zone e assegna il traffico verso le reti, e che rende molto senso dal modo in cui si potrebbe immaginare il sistema funziona - zone-to-zona a traffico dipende dalla resistenza causata dalla congestione. ${\ Displaystyle c_ {ij}}$${\ Displaystyle t_ {ij}}$

In alternativa, la funzione di resistenza di collegamento può essere incluso nella funzione obiettivo (e la funzione di costo totale eliminati dai vincoli).

Un approccio disaggregato scelta generalizzata è evoluto come ha un approccio generalizzato aggregato. La grande questione è quella dei rapporti tra di loro. Quando usiamo un modello macro, vorremmo conoscere il comportamento disaggregato che rappresenta. Se stiamo facendo una micro analisi, vorremmo conoscere le implicazioni aggregati dell'analisi.

Wilson deriva un modello di gravità come con parametri ponderati che dicono qualcosa circa l'attrattiva di origine e di destinazione. Senza troppa matematica possiamo scrivere probabilità di dichiarazioni scelta basata su attrattiva, e questi assumere una forma simile ad alcune varietà di modelli di domanda disaggregati.

L'integrazione della domanda di trasporto con assegnazione percorso

Da tempo è stato riconosciuto che la domanda di trasporto è influenzata dall'offerta di rete. L'esempio di una nuova apertura ponte dove è stato prima di indurre ulteriore traffico è stato notato nessuno per secoli. Molta ricerca è stato fatto per mettere a punto metodi per permettere al sistema di previsione per tenere conto direttamente di questo fenomeno. Evans (1974) ha pubblicato una tesi di dottorato su un matematicamente rigoroso combinazione del modello di distribuzione gravità con il modello di assegnazione equilibrio. La prima citazione di questa integrazione è il lavoro di Irwin e Von Cube, come riferito da Florian et al. (1975), che commentare il lavoro di Evans:

"Il lavoro di Evans assomiglia un po 'gli algoritmi sviluppati da Irwin e Von Cube [‘moderazione capacità nei programmi Assegnazione modalità multi-viaggio’HRB Bulletin 347 (1962)] per uno studio trasporto di Toronto, in Canada. Il loro lavoro permette un feedback tra congestionata distribuzione assegnazione e viaggio, benché si applichi procedure sequenziali. Partendo da una prima soluzione del problema della distribuzione, i viaggi interzonale vengono assegnati ai percorsi più brevi iniziali. per iterazioni successive, nuovi percorsi più brevi sono calcolate, e le loro lunghezze sono utilizzati come i tempi di accesso per inserire il modello di distribuzione. i nuovi flussi interzonale vengono poi assegnati in qualche proporzione ai percorsi già trovato. la procedura viene interrotta quando i tempi interzonale per iterazione successiva sono quasi uguali."

Florian et al. proposto un metodo un po 'diverso per risolvere l'assegnazione di distribuzione combinati, applicando direttamente l'algoritmo di Frank-Wolfe. Boyce et al. (1988) riassumere la ricerca sui problemi di equilibrio della rete, tra cui l'assegnazione con domanda elastica.

Discussione

Un problema dei tre link non può essere risolto graficamente, e la maggior parte dei problemi di rete di trasporto coinvolgere un gran numero di nodi e collegamenti. Eash et al., Per esempio, ha studiato la rete stradale di DuPage County dove c'erano circa 30.000 a senso unico link e 9.500 nodi. Perché i problemi sono grandi, è necessario un algoritmo per risolvere il problema di assegnazione, e viene utilizzato l'algoritmo di Frank-Wolfe (con varie modifiche moderni poiché pubblicato). Inizia con un tutto o niente assegnazione, e quindi seguire la regola sviluppato da Frank-Wolfe per scorrere verso il valore minimo della funzione obiettivo. (L'algoritmo si applica successive soluzioni realizzabili per raggiungere la convergenza alla soluzione ottimale. Esso utilizza una procedura di ricerca efficace per spostare rapidamente il calcolo verso la soluzione ottimale.) I tempi di viaggio corrispondono al duplice variabili di questo problema di programmazione.

E 'interessante il fatto che l'algoritmo di Frank-Wolfe era disponibile nel 1956. La sua applicazione è stata sviluppata nel 1968, e ci sono voluti quasi altri due decenni prima il primo algoritmo di assegnazione equilibrio è stato incorporato nel software di pianificazione dei trasporti di uso comune ( Emme e Emme / 2 , sviluppati da Florian e altri a Montreal). Non vorremmo trarre alcuna conclusione generale dall'osservazione applicazione lento, soprattutto perché siamo in grado di trovare esempi contatore sul ritmo e modello di sviluppo tecnica. Ad esempio, il metodo simplex per la soluzione di problemi di programmazione lineare è stato elaborato ed ampiamente applicato prima dello sviluppo di gran parte della teoria programmazione.

La dichiarazione del problema e l'algoritmo hanno applicazioni generali in tutta ingegneria civile - l'idraulica, strutture e costruzioni. (Vedere Hendrickson e Janson 1984).

Guarda anche

• Routing (reti di computer)

Riferimenti

• Dafermos, Stella. C. e FT Sparrow L'assegnazione problema del traffico di rete generale.”J. della Res. del National Bureau of Standards, 73B, pp. 91-118. 1969.
• Florian, Michael ed., Traffico Metodi di equilibrio, Springer-Verlag, 1976.
• Wardrop, JC alcuni aspetti teorici della circolazione stradale Research,”Atti, Institution of Civil Engineers, parte 2, 9, pp. 325-378. 1952
• Eash, Ronald, Bruce N. Janson, e David Boyce Equilibrium viaggio di assegnazione: Vantaggi e Implicazioni per la pratica, Transportation Research Record 728, pp 1-8, 1979..
• Evans, Suzanne P.. "Derivazione e analisi di alcuni modelli per la combinazione di Distribuzione di viaggio e di assegnazione." Transportation Research, Vol 10, pp 37-57 1976
• Hendrickson, CT e BN Janson, “una rete comune di flusso Formulazione a diversi problemi di ingegneria civile” Sistemi di Ingegneria Civile 1 (4), pp. 195-203, 1984