Assigning Traffic over Essentially-Least-Cost Paths

Abstract

The concept of a least-cost path is generalized. The simplest of all traffic assignment models assumes that all trip makers from a single origin-destination (O-D) pair take a single path, for example, the minimum cost path or the equilibrium path. However, in many applications, it is observed that trips from a single O-D do not all take the same path. It is not difficult to imagine commuters from a large residential area using different routes to travel to a common workplace simply because each has a different disutility function. In reality no two routes have exactly the same cost; however, when modeled deterministically as network graphs, these graphs invariably have O-Ds with degenerate (multiple) shortest paths. The ability to measure the “best” route should also be seriously questioned. Given the level of uncertainty that exists in any link attribute, the variance of the accumulated uncertainty of that attribute over any given route can easily be such as to make many routes statistically indistinguishable from the deterministic best route. An algorithm for generating the set of paths that are essentially indistinguishable from the least-cost path is presented. These paths are constructed from the set of “locally acceptable” detours that are within a given cost threshold. This is different from the classic “k” least-cost path problem in that it operates on a cost threshold as opposed to a predetermined number of paths. Methods are then presented for assigning traffic to this subnetwork of essentially-least-cost paths.