Time-Dependent, Label-Constrained Shortest Path Problems with Applications

Sherali, Hanif D.; Hobeika, Antoine G.; Kangwalklai, Sasikul
August 2003
Transportation Science;Aug2003, Vol. 37 Issue 3, p278
Academic Journal
In this paper, we consider a variant of shortest path problems where, in addition to congestion related time-dependent link travel times on a given transportation network, we also have specific labels for each arc denoting particular modes of travel. The problem then involves finding a time-dependent shortest path from an origin node to a destination node that also conforms with some admissible string of labels. This problem arises in the Route Planner Module of Transportation Analysis Simulation System (TRANSIMS), which is developed by the Los Alamos National Laboratory and is part of a multitrack Travel Model Improvement Program sponsored by the U.S. Department of Transportation (DOT) and the Environmental Protection Agency (EPA). We propose an effective algorithm for this problem by adapting efficient existing partitioned shortest path algorithmic schemes to handle time dependency along with the label constraints. We also develop several heuristics to curtail the search based on various route restrictions, indicators of progress, and projected travel times to complete the trip. The proposed methodology is applied to solve some real multimodal test problems related to the Portland, Oregon, transportation system. Computational results for both the exact method and the heuristic curtailing schemes are provided.


Related Articles

  • On Insensitivities in Urban Redistricting and Facility Location. Larson, Richard C.; Stevenson, Keith A. // Operations Research;May/Jun72, Vol. 20 Issue 3, p595 

    This paper considers one class of problems associated with urban service systems that dispatch vehicles from fixed facilities. Given the limited resources available, one important issue is the location of the facilities and the design of their response districts to minimize average response time...

  • Updating Paths in Time-Varying Networks Given Arc Weight Changes. Miller-Hooks, Elise; Baiyu Yang // Transportation Science;Nov2005, Vol. 39 Issue 4, p451 

    Many transportation applications, including applications in intelligent transportation systems, require the solution of a series of shortest path problems in which only the travel time along a set of arcs of the network change from one problem instance to the next. One could use an existing path...

  • Parameter transfer of common-metric attributes in choice analysis: implications for willingness to pay. Hensher, David; Layton, David // Transportation;May2010, Vol. 37 Issue 3, p473 

    There is a growing literature that promotes the presence of a mix of compensatory and semi-compensatory processing strategies in the way that individuals evaluate packages of attributes in real or hypothetical markets, and make choices. This paper proposes a specification for the utility form in...

  • Airport Gate Scheduling with Time Windows. Lim, A.; Rodrigues, B.; Zhu, Y. // Artificial Intelligence Review;Sep2005, Vol. 24 Issue 1, p5 

    In contrast to the existing airport gate assignment studies where flight have fixed schedules, we consider the more realistic situation where flight arrival and departure times can change. Although we minimize walking distances (or travel time) in our objective function, the model is easily...

  • Webinar to Highlight Transportation Systems Management and Operations Improvement SHRP2 Tool.  // AASHTO Journal: Weekly Transportation Report;12/6/2013, p2 

    The article offers information on a January 8, 2013 Webinar on a second Strategic Highway Research Program product, the Capability Maturity Model which is developed to help transportation agencies seeking to execute operations programs that improve travel time reliability.

  • MDOT displays select travel times in Jackson.  // Jackson Advocate;7/16/2015, Vol. 77 Issue 41, p9A 

    The article reports on the travel time messages being displayed by the Mississippi Department of Transportation (MDOT) on its Dynamic Message Signs (DMS) in the metropolitan areas of Jackson.

  • Travel Time Valuation through Hedonic Regression. Edmonds Jr., Radcliffe G. // Southern Economic Journal;Jul83, Vol. 50 Issue 1, p83 

    The objective of this paper is to present a different and more thorough approach to an analysis of the valuation of travel time. Rather than merely providing a single estimate, use of an hedonic price function and marginal valuation functions allows analysis of how time savings benefits vary...

  • Value of Time Guidance.  // Logistics & Transport Focus;Dec2000, Vol. 2 Issue 10, p4 

    Reports that a research study conducted by the Institute for Transport Studies at the University of Leeds for the Department of the Environment, Transport and the Regions of Great Britain, will provide expert guidance on how work and non-working travel time should be valued in transport...

  • Time-Varying Travel Times in Vehicle Routing. Fleischmann, Bernhard; Gietz, Martin; Gnutzmann, Stefan // Transportation Science;May2004, Vol. 38 Issue 2, p160 

    Models and algorithms for vehicle routing are usually based on known constant travel times between all relevant locations, an assumption that is far from reality, particularly for urban areas. But the consideration of travel times that vary with the time of day poses two serious problems: the...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics