IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v26y1992i1p4-17.html
   My bibliography  Save this article

Simplicial Decomposition with Disaggregated Representation for the Traffic Assignment Problem

Author

Listed:
  • Torbjörn Larsson

    (Linköping Institute of Technology, S-581 83 Linköping, Sweden)

  • Michael Patriksson

    (Linköping Institute of Technology, S-581 83 Linköping, Sweden)

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.

Suggested Citation

  • Torbjörn Larsson & Michael Patriksson, 1992. "Simplicial Decomposition with Disaggregated Representation for the Traffic Assignment Problem," Transportation Science, INFORMS, vol. 26(1), pages 4-17, February.
  • Handle: RePEc:inm:ortrsc:v:26:y:1992:i:1:p:4-17
    DOI: 10.1287/trsc.26.1.4
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.26.1.4
    Download Restriction: no

    File URL: https://libkey.io/10.1287/trsc.26.1.4?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:26:y:1992:i:1:p:4-17. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.