One of the first steps in analyzing transport problems is the explicit enumeration of the paths to be considered. In realistically-sized networks, the number of paths that can be constructed is virtually infinite. This article addresses the path generation problem, defined as the problem of generating a path-set of manageable size that contains the most relevant paths for a specific transport problem. The authors begin with an overview of existing algorithmic approaches to the path enumeration problem, then focuses on K-shortest path algorithms in general and Lawler's algorithm in particular. Next, the new CKSP (constrained K-shortest paths) algorithm is proposed in a description that is largely parallel to the explanation of Lawler's algorithm. The authors also provide a numerical example in the context of path enumeration. Constraints are defined that eliminate all overly circuitous and strongly overlapping paths. The authors conclude that, as opposed to the conventional method, the proposed implementation of the CKSP method displays only a limited sensitivity to the level of restriction of the constraints. Thus, the proposed method can enumerate paths for realistically sized networks.

  • Availability:
  • Corporate Authors:


    The Boulevard, Langford Lane
    Kidlington, Oxford  United Kingdom  OX5 1GB
  • Authors:
    • Van der Zijpp, N J
    • Catalano, S F
  • Publication Date: 2005-7


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 00988898
  • Record Type: Publication
  • Files: TRIS, ATRI
  • Created Date: Apr 4 2005 12:00AM