01099138

Component

https://doi.org/10.3141/2089-07

http://scholar.google.com...Chan&publication_year=2008

To achieve the desired computational speed, existing algorithms for time-dependent (or dynamic) shortest-path problems call for the unrealistic aggregation of travel time as multiples of a given time increment. While the time increment can be varied between, say, peak and off-peak periods, it still has its obvious limitation on granularity. An improved solution algorithm is proposed for the all-to-one or one-to-all time-dependent versions of the problem. The algorithms are solidly founded on Bellman’s principle of optimality and apply to continuous or real-value arc travel times (rather than the current practice of discrete-time specifications). The new algorithms are practical in computational speed, and they capture a more realistic metric for route choice. In this case, a relatively coarse time increment can be used throughout the analysis, yet it is compatible with any continuous or real-value arc travel times. To support these claims, computational results that consider various network sizes, densities, and numbers of time increments are provided. For future extensions, a non-first-in-first-out fastest-path and minimum-cost-path algorithm is proposed. A generalized cost (or disutility arc function) is defined to combine the two, on the basis of which route choices are made. For route-choice decisions, it is stipulated that adoption of such a disutility specification mandates a continuous valuation of arc time and cost. Instead of an all-to-one implementation, a one-to-all implementation is suggested under these circumstances. The latter approach, when complemented by the speed of algorithmic execution, facilitates real-world applications. It allows the driver to value incident delay and risks in route choice on a real-time basis.

01121598

English

pp 51-57

2008

Transportation Research Record: Journal of the Transportation Research Board

9780309126014

Print

Figures (3) ; References (17) ; Tables (1)

Incident management; Route choice; Shortest path algorithms; Time dependence; Traffic delays; Traffic incidents; Travel time

Computational efficiency

Highways; Operations and Traffic Management; Planning and Forecasting; I72: Traffic and Transport Planning; I73: Traffic Control

TRIS, TRB, ATRI

Jan 29 2008 3:05PM

• Combination of Multiple Ant Colony System and Simulated Annealing for the Multidepot Vehicle-Routing Problem with Time Windows
• Efficient Implementation of Improvement Procedures for Vehicle Routing with Time-Dependent Travel Times
• Equity and Efficiency Analysis of Pricing Strategies in a Bimodal Network with Heterogeneous User Groups
• Heuristic Framework for Optimizing Hurricane Evacuation Operations
• Incorporating Environmental Justice Measures into Equilibrium-Based Network Design
• Integrating Equity Objectives in a Road Network Design Model
• Location Routing Approach for the Humanitarian Prepositioning Problem
• Maximal Dynamic Expected Flows Problem for Emergency Evacuation Planning
• New Methodology for Optimizing Transit Priority at the Network Level
• Optimizing Distance-Based Fares and Headway of an Intercity Transportation System with Elastic Demand and Trip Length Differentiation
• Planning Approximations to the Average Length of Vehicle Routing Problems with Varying Customer Demands and Routing Constraints
• Solution Algorithm for Long-Haul Freight Network Design Using Shipper–Carrier Freight Flow Prediction with Explicit Capacity Constraints