liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A comment on some test networks for the traffic assignment problem
Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
(English)Manuscript (preprint) (Other academic)
Abstract [en]

We show that many published test problems for traffic assignment algorithms have peculiarities. First and foremost, several of them have incorrectly specified attributes, such as the number of nodes. In other test-problems, the network contains subnetworks with constant travel times; subnetworks which to a large extent can be reduced or eliminated. In further test problems, the constant travel time subnetworks imply that the solution has nonunique arc flows.

National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-85563OAI: oai:DiVA.org:liu-85563DiVA: diva2:571692
Available from: 2012-11-23 Created: 2012-11-23 Last updated: 2012-11-23
In thesis
1. Convex multicommodity flow problems: a bidual approach
Open this publication in new window or tab >>Convex multicommodity flow problems: a bidual approach
2005 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The topic of this dissertation, within the subfield of mathematics known as optimization, is the development of a new dual ascent method for convex multicommodity flow problems. Convex multicommodity flow problems arize in many different routing problems such as the design of packet switched computer networks and the computation of traffic network equilibria. The dual problem of a strictly convex twice differentiable convex multicommodity flow problem is an essentially unconstrained maximization problem with a piecewise twice differentiable concave objective. The idea behind this new dual ascent algorithm is to compute Newton-like ascent directions in the current differentiable piece and performing line searches in those directions combined with an active set type treatment of the borders between the differentiable pieces. The first contribution in this dissertation is a detailed investigation of this special structure. The insights gained are then used to explain the proposed algorithm. The algorithm is also tested numerically on well known traffic equilibrium problem instances. The computational results are very promising. The second contribution is a new approach for verifying feasibility in multicommodity flow problems. These feasibility problems arizes naturally in the new dual ascent algorithm proposed. The background of the problem is that if a certain representation of a solution to the dual convex multicommodity flow problem is proved to be feasible for the convex muticommodity flow problem aswell, an optimal solution is found. Hence, it is natural to seek a method for verifying feasibility of a given candidate solution for the multicommodity flow problem. The core of the approach is a distance minimizing method for verifying feasibility and hence for demonstrating optimality. This method is described in detail and some computational results in a traffic assignment setting is also given. Finally, a short note illustrating that many published test problems for traffic assignment algorithms have peculiarities are given. First and foremost, several of them have incorrectly specified attributes, such as the number of nodes. In other testproblems, the network contains subnetworks with constant travel times; subnetworks which to a large extent can be reduced or eliminated. In further test problems, the constant travel time subnetworks imply that the solution has nonunique arc flows.

Place, publisher, year, edition, pages
Linköping: Linköpings universitet, 2005. 12 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 954
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-28478 (URN)13625 (Local ID)91-8529-963-4 (ISBN)13625 (Archive number)13625 (OAI)
Public defence
2005-06-02, BL32, B-huset, Campus Valla, Linköpings universitet, Linköping, 10:00 (English)
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2012-11-23Bibliographically approved

Open Access in DiVA

No full text

Authority records BETA

Hägglöf, KristofferLindgren, Per Olov

Search in DiVA

By author/editor
Hägglöf, KristofferLindgren, Per Olov
By organisation
Department of MathematicsThe Institute of Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 28 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf