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
Additional contact information
Alan L. Erera: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Carlos F. Daganzo: Department of Civil and Environmental Engineering, University of California, Berkeley, California 94720
David J. Lovell: Department of Civil and Environmental Engineering, University of Maryland, College Park, Maryland 20742

Operations Research, 2002, vol. 50, issue 4, 736-743

Abstract: This paper is concerned with the performance of multicommodity capacitated networks in a deterministic but time-dependent environment. For a given time-dependent origin-destination table, this paper asks if it is easy to find a way of regulating the input flows into the network 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 ifthe set off easible 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 off easible 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 ofbits (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: Traffic models: control of freeway systems; Multicommodity networks: optimization with FIFO queues (search for similar items in EconPapers)
Date: 2002
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.50.4.736.2863 (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:inm:oropre:v:50:y:2002:i:4:p:736-743

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().