Simplicial Decomposition with Disaggregated Representation for the Traffic Assignment Problem

Torbjörn Larsson · Michael Patriksson

265 citations0/0 files storedTransportation Science

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Transportation Planning and Optimization Complexity and Algorithms in Graphs Vehicle Routing Optimization Methods

Abstract

The class of simplicial decomposition (SD) schemes has shown to provide efficient tools for nonlinear network flows. When applied to the traffic assignment problem, shortest route subproblems are solved in order to generate extreme points of the polyhedron of feasible flows, and, alternately, master problems are solved over the convex hull of the generated extreme points. We review the development of simplicial decomposition and the closely related column generation methods for the traffic assignment problem; we then present a modified, disaggregated, representation of feasible solutions in SD algorithms for convex problems over Cartesian product sets, with application to the symmetric traffic assignment problem. The new algorithm, which is referred to as disaggregate simplicial decomposition (DSD), is given along with a specialized solution method for the disaggregate master problem. Numerical results for several well known test problems and a new one are presented. These experimentations indicate that only few shortest route searches are needed; this property is important for large-scale applications. The modification proposed maintains the advantages of SD, and the results show that the performance of the new algorithm is at least comparable to that of state-of-the-art codes for traffic assignment. Moreover, the reoptimization capabilities of the new scheme are significantly better; this is a main motive for considering it. The reoptimization facilities, especially with respect to changes in origin-destination flows and network topology, make the new approach highly profitable for more complex models, where traffic assignment problems arise as subproblems.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 265 citations exist upstream.

References

1933The Economics of Welfare 1957Studies in the Economics of Transportation.1980Traffic Equilibrium and Variational Inequalities 1979The existence, uniqueness and stability of traffic equilibria 1975An efficient approach to solving the road network equilibrium traffic assignment problem 1969Traffic assignment problem for a general network 1984An Efficient Method for Computing Traffic Equilibria in Networks with Asymmetric Transportation Costs 1972The Traffic Assignment Problem for Multiclass-User Transportation Networks

Cited by

1995Bilevel programming in traffic planning: Models, methods and challenge 1994A FASTER PATH-BASED ALGORITHM FOR TRAFFIC ASSIGNMENT 2010Traffic assignment by paired alternative segments 1995An augmented lagrangean dual algorithm for link capacity side constrained traffic assignment problems 2000Traffic equilibrium problem with route-specific costs: formulation and algorithms 2003

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.