Skip to main content

2020 | OriginalPaper | Buchkapitel

5. Parallel Decomposition of a Road Network

verfasst von : Alexander Krylatov, Victor Zakharov, Tero Tuovinen

Erschienen in: Optimization Models and Methods for Equilibrium Traffic Assignment

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this chapter a new road network decomposition approach is proposed. Necessary statements are proved in the first section, and the formal description of the approach as well as a brief review on relevant references are presented. The offered approach is completely based on the very features of the equilibrium traffic assignment and, consequently, forms the methodological basis for direct solving algorithms. The implementation of the developed approach to a single-commodity network can be found in the second section. A new decomposition technique for route-flow assignment in a general topology network is presented in the third section. The fourth section is reserved for a decomposition technique for link-flow assignment in a general topology network. Moreover, capabilities for route-flows aggregation and link-flows disaggregation which appeared by virtue of the new approach are discussed.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Bertsekas DP, Tsitsiklis JN (1989) Parallel and distributed computation: numerical methods. Prentice-Hall, LondonMATH Bertsekas DP, Tsitsiklis JN (1989) Parallel and distributed computation: numerical methods. Prentice-Hall, LondonMATH
2.
Zurück zum Zitat Greenbaum A (1989) Synchronization costs on multiprocessors. Parallel Comput 10:3–14CrossRef Greenbaum A (1989) Synchronization costs on multiprocessors. Parallel Comput 10:3–14CrossRef
3.
Zurück zum Zitat Hockney RW, Jesshope CR (1988) Parallel computers 2: architecture, programming and algorithms. Adam Hilger, BristolMATH Hockney RW, Jesshope CR (1988) Parallel computers 2: architecture, programming and algorithms. Adam Hilger, BristolMATH
4.
Zurück zum Zitat Hwang K, Briggs FA (1985) Computer architecture and parallel processing. McGraw-Hill, SingaporeMATH Hwang K, Briggs FA (1985) Computer architecture and parallel processing. McGraw-Hill, SingaporeMATH
5.
Zurück zum Zitat Kung HT (1976) Synchronized and asynchronous parallel algorithms for multiprocessors. In: Traub JF (ed) Algorithms and complexity: new directions and recent results. Academic Press, NY. 1, pp 53–200 (1976) Kung HT (1976) Synchronized and asynchronous parallel algorithms for multiprocessors. In: Traub JF (ed) Algorithms and complexity: new directions and recent results. Academic Press, NY. 1, pp 53–200 (1976)
6.
Zurück zum Zitat Bertsekas DP, Castañon DA (1991) Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Comput 17:707–732CrossRef Bertsekas DP, Castañon DA (1991) Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Comput 17:707–732CrossRef
7.
Zurück zum Zitat Chajakis ED, Zenios SA (1991) Synchronous and asynchronous implementations of relaxation algorithms for nonlinear network optimization. Parallel Comput 17:873–894CrossRef Chajakis ED, Zenios SA (1991) Synchronous and asynchronous implementations of relaxation algorithms for nonlinear network optimization. Parallel Comput 17:873–894CrossRef
8.
Zurück zum Zitat Tseng P (1992) On the rate of convergence of a partially asynchronous gradient projection algorithm. SIAM J Optim 1:603–619MathSciNetCrossRef Tseng P (1992) On the rate of convergence of a partially asynchronous gradient projection algorithm. SIAM J Optim 1:603–619MathSciNetCrossRef
9.
Zurück zum Zitat Tsitsiklis JN, Bertsekas DP, Athans M (1986) Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE Trans Autom Control AC-31:803–812MathSciNetCrossRef Tsitsiklis JN, Bertsekas DP, Athans M (1986) Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE Trans Autom Control AC-31:803–812MathSciNetCrossRef
10.
Zurück zum Zitat Tsitsiklis JN, Bertsekas DP (1986) Distributed asynchronous optimal routing in data networks. IEEE Trans Autom Control AC-31:325–332MathSciNetCrossRef Tsitsiklis JN, Bertsekas DP (1986) Distributed asynchronous optimal routing in data networks. IEEE Trans Autom Control AC-31:325–332MathSciNetCrossRef
11.
Zurück zum Zitat Feijoo B, Meyer RR (1988) Piecewise-linear approximation methods for nonseparable convex optimization. Manag Sci 34:411–419MathSciNetCrossRef Feijoo B, Meyer RR (1988) Piecewise-linear approximation methods for nonseparable convex optimization. Manag Sci 34:411–419MathSciNetCrossRef
13.
Zurück zum Zitat Larsson T, Migdalas A, Patriksson M (1993) A partial linearization method for the traffic assignment problem. Optimization 28:47–61MathSciNetCrossRef Larsson T, Migdalas A, Patriksson M (1993) A partial linearization method for the traffic assignment problem. Optimization 28:47–61MathSciNetCrossRef
14.
Zurück zum Zitat Rosen JB (1960) The gradient projection method for nonlinear programming, Part I: linear constraints. J Soc Ind Appl Math 8:181–271CrossRef Rosen JB (1960) The gradient projection method for nonlinear programming, Part I: linear constraints. J Soc Ind Appl Math 8:181–271CrossRef
15.
Zurück zum Zitat Schwartz M, Cheung CK (1976) The gradient projection algorithm for multiple routing in message-switched networks. IEEE Trans Commun COM-24:449–456CrossRef Schwartz M, Cheung CK (1976) The gradient projection algorithm for multiple routing in message-switched networks. IEEE Trans Commun COM-24:449–456CrossRef
16.
Zurück zum Zitat Devarajan S (1981) A note on network equilibrium and noncooperative games. Transp Res Part B 15B(6):421–426MathSciNetCrossRef Devarajan S (1981) A note on network equilibrium and noncooperative games. Transp Res Part B 15B(6):421–426MathSciNetCrossRef
Metadaten
Titel
Parallel Decomposition of a Road Network
verfasst von
Alexander Krylatov
Victor Zakharov
Tero Tuovinen
Copyright-Jahr
2020
DOI
https://doi.org/10.1007/978-3-030-34102-2_5

    Premium Partner