Updating Paths in Time-Varying Networks Given Arc Weight Changes

Miller-Hooks, Elise; Baiyu Yang
November 2005
Transportation Science;Nov2005, Vol. 39 Issue 4, p451
Academic Journal
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 algorithm to solve each problem instance independently as it arises. However, significant savings in computation time can often be achieved through the use of a reoptimization algorithm that would begin from the prior solution in determining the updated optimal solution for the given arc travel-time changes. Such quick solution is critical for providing routing instructions to travelers in real time as travel-time information is retrieved from the traffic network. Numerous works have presented reoptimization techniques for use in updating shortest path trees in deterministic and static networks; however, it appears that no reoptimization technique exists in the literature for updating paths where future travel times in time-varying networks change. In this paper, such procedures are proposed. The proposed techniques can provide updated solutions given simultaneous and arbitrary changes (increasing and decreasing in value) in any number of network arcs. Further, this technique can be extended for use in stochastic networks.


Related Articles

  • Time Dependent Vehicle Routing Problem with Fuzzy Traveling Times Under Different Traffic Conditions. Demirel, Tufan; Demirel, Nihan Cetin; Tasdelen, Belgin // Journal of Multiple-Valued Logic & Soft Computing;2008, Vol. 14 Issue 3-5, p387 

    The basic vehicle routing problem model usually needs to be extended in order to solve real-world vehicle routing problems. Time dependent vehicle routing problem is a vehicle routing problem in which travel costs along the network are dependent upon the time of day during which travel is to be...

  • Modified K-Shortest Paths Algorithm for Solving the Earliest Arrival Problem on the Time-Dependent Model of Transportation Systems. Yang Yang; Shuai Wang; Xiaolin Hu; Jianmin Li; Bingji Xu // Proceedings of the International MultiConference of Engineers & ;2012, Special section p1 

    We are concerned with solving the K-earliest arrival problem on the timetable information-based public transportation systems. The problem is like this: given a departure time window at station A, find K best itineraries from station A to station B in terms of the earliest arrival time at...

  • Transfer Optimization in a Transit Network. Bookbinder, James H.; Désilets, Alain // Transportation Science;May92, Vol. 26 Issue 2, p106 

    Transfer optimization attempts to minimize the overall inconvenience to passengers who must transfer between lines in a transit network. Bus trips are scheduled to depart from their terminal so as to minimize some objective function measuring that inconvenience. In this paper, the transit...

  • Optimal Locations of Bus Stops Connecting Subways near Urban Intersections. Cui, Yuan; Chen, Shao-kuan; Liu, Jian-feng; Jia, Wen-zheng // Mathematical Problems in Engineering;2/23/2015, Vol. 2015, p1 

    Unsuitable locations of bus stops which provide feeder transportation connecting subways near urban intersections usually lead to the low efficiency of public transport and level of passenger service. A multiobjective optimization model to distribute such stop locations is proposed to attain the...

  • A Relaxation Approach for Estimating Origin–Destination Trip Tables. Nie, Yu Marco; Zhang, H. M. // Networks & Spatial Economics;Mar2010, Vol. 10 Issue 1, p147 

    The problem of estimating origin-destination travel demands from partial observations of traffic conditions has often been formulated as a network design problem (NDP) with a bi-level structure. The upper level problem in such a formulation minimizes a distance metric between measured and...

  • Time-Dependent, Label-Constrained Shortest Path Problems with Applications. Sherali, Hanif D.; Hobeika, Antoine G.; Kangwalklai, Sasikul // Transportation Science;Aug2003, Vol. 37 Issue 3, p278 

    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...

  • 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...

  • 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.


Read the Article

Courtesy of your local library

Public Libraries Near You (See All)
Looking for a Different Library?

Other Topics