The Access Control Problem on Capacitated FIFO Networks with Unique O-D Paths is Hard

Alan L. Erera, Carlos F. Daganzo and David J. Lovell

University of California Transportation Center, Working Papers from University of California Transportation Center

Abstract: This paper is concerned with the performance of multi-commodity capacitated networks in a deterministic but time-dependent environment. For a given time-dependent origin-destination table, the paper asks if it is easy to find a way of regulating the input flows into the network so as to avoid queues from growing internally; i.e., to avoid capacity violations. Problems of this type are conventionally approached in the traffic/transportation field with variational methods such as control theory (if time is continuous) and with mathematical programming (if time is discrete). However, these approaches can only be expected to work well if the set of feasible solutions is convex. Unfortunately, it is found in this paper that this is not the case. It is shown that continuous- time versions of the problem satisfying the smoothness conditions of control theory can have a finite but very large number of feasible solutions. The same happens for the discrete-time case. These difficulties arise even with the simplest versions of the problem (with unique origin-destination paths, perfect information and deterministic travel times). The paper also shows that the continuous-time feasibility problem is NP-hard, and that if we restrict our attention to (practical) problems whose data can be described with a finite number of bits (e.g., in discrete time), then the problem is NP-complete. These results are established by showing that the problem instances of interest can be related to the Directed Hamiltonian Path problem by a polynomial transformation.

Keywords: Social; and; Behavioral; Sciences (search for similar items in EconPapers)
Date: 2001-01-01
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.escholarship.org/uc/item/67v2w02f.pdf;origin=repeccitec (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cdl:uctcwp:qt67v2w02f

Access Statistics for this paper

More papers in University of California Transportation Center, Working Papers from University of California Transportation Center Contact information at EDIRC.
Bibliographic data for series maintained by Lisa Schiff ().