The continuous network design problem that occurs when the origindestination time-dependent demands are random variables with known probability distributions is described. A chance-constraint and two-stage linear programming formulation are introduced based on a system optimum dynamic traffic assignment model that propagates traffic according to the cell transmission model. The introduced approaches are limited to continuous link improvements and do not provide for new link additions. The chance-constrained model is tested on an example network that resembles a freeway corridor to demonstrate the simplicity and applicability of the approach. Initial results suggest that planning for an inflated demand may produce benefits in terms of system performance and reduced variance.
Get full access to this article
View all access options for this article.
References
1.
WallerS. T., ZiliaskopoulosA. K., and MouskosK.. A Linear Model for Continuous Network Design. European Journal of Operations Research, 1998(submitted).
2.
ZiliaskopoulosA. K.A Linear Programming Model for the Single Destination System Optimum Dynamic Traffic Assignment Problem. Transportation Science, Vol. 34, 2000, pp. 1–12.
3.
DaganzoC. F.The Cell Transmission Model: A Simple Dynamic Representation of Highway Traffic Consistent with the Hydrodynamic Theory. Transportation Research B, Vol. 28, No. 4, 1994, pp. 269–287.
4.
CharnesA., and CooperW. W.. Deterministic Equivalents for Optimizing and Satisfying Under Chance Constraints. Operations Research, Vol. 11, 1963, pp. 18–39.
5.
EisnerM. J., KaplanR. S., and SodenJ. V.. Admissible Decision Rules for the E-Model of Chance-Constrained Programming. Management Science, Vol. 17, 1971, pp. 337–353.
6.
WallerS. T., and ZiliaskopoulosA. K.. A Chance-Constrained Based Stochastic DTA Model: Analysis Formulation & Solution Algorithm. Tristan III Proceedings, Vol. 2, No. B2, 1998.
7.
DantzigG. C.Linear Programming Under Uncertainty. Management Science, Vol. 1, No. 155, 1955, pp. 197–206.
8.
BoyceD. E. Introduction.Transportation Research B, Vol. 13, 1979, pp. 1–3.
9.
MagnantiT. L., and WongR. T.. Network Design and Transportation Planning: Models and Algorithms. Transportation Science, Vol. 18, No. 1, 1984, pp. 1–55.
10.
YangH., and BellM. G. H.. Models and Algorithms for Road Network Design: A Review and Some New Developments. Transport Reviews, Vol. 18, No. 3, 1998, pp. 257–278.
11.
LeBlancL. J.An Algorithm for the Discrete Network Design Problem. Transportation Science, Vol. 9, 1975, pp. 183–199.
12.
DantzigG. B., HarveyR. P., LandsowneZ. F., RobinsonD. W., and MaierS. F.. Formulating and Solving the Network Design Problem by Decomposition. Transportation Research B, Vol. 13, 1979, pp. 5–17.
13.
SteenbrinkP. A.Optimization of Transportation Networks. Wiley, London, 1974.
14.
LeBlancL. J., and AbdulaalM.. An Efficient Dual Approach to the Urban Road Network Design Problem. Computers and Mathematics with Applications, Vol. 5, 1979, pp. 11–19.
15.
HoangH. H.Topological Optimization of Networks: A Non-Linear Mixed Integer Model Employing Generalized Benders Decomposition. IEEE Transactions on Automated Control, Vol. 27, 1982, pp. 164–169.
16.
LeBlancL. J., and AbdulaalM.. A Comparison of the User-Optimum Versus System-Optimum Traffic Assignment in Transportation Network Design. Transportation Research B, Vol. 18, 1984, pp. 115–121.
17.
AbdulaalM., and LeBlancL. J.. Continuous Equilibrium Network Design Models. Transportation Research B, Vol. 13, 1979, pp. 19–32.
18.
MarcotteP.Network Optimization with Continuous Control Parameters. Transportation Science, Vol. 17, 1983, pp. 181–197.
19.
LeBlancL. J., and BoyceD.. A Bi-Level Programming Algorithm for the Exact Solution of the Network Design Problem with User-Optimal Traffic Flows. Transportation Research B, Vol. 20, 1986, pp. 259–265.
20.
SuwansirikulC., FrieszT. L., and TobinR. L.. Equilibrium Decomposed Optimization: A Heuristic for the Continuous Equilibrium Network Design Problem. Transportation Science, Vol. 21, 1987, pp. 254–263.
21.
FrieszT. K., ChoH., MehtaN., TobinR., and AnandalingamG.. A Simulated Annealing Approach to the Network Design Problem with Variational Inquality Constraints. Transportation Science, Vol. 26, 1992, pp. 18–25.
22.
MouskosK.A Taboo-Search Based Approach for Network Design. Ph.D. dissertation. University of Texas, Austin, 1992.
23.
DavisG. A.Exact Local Solution of the Continuous Network Design Problem via Stochastic User Equilibrium Assignment. Transportation Research B, Vol. 28, 1994, pp. 61–75.
24.
FrieszT. K., BernsteinD., SmithT. E., TobinR. L., and WieB. W.. A Variational Inequality Formulation of the Dynamic Network User Equilibrium Problem. Operations Research, Vol. 41, 1993, pp. 179–191.
25.
TzengG. H., and TsaurC.. Application of Multiple Criteria Decision Making for Network Improvement Plan Model. Journal of Advanced Transportation, Vol. 31, 1997, pp. 48–74.
26.
JansonB. N.Network Design Effects of Dynamic Traffic Assignment. Journal of Transportation Engineering, Vol. 121, No. 1, 1995, pp. 1–13.
27.
DaganzoC. F.The Cell Transmission Model. Part II: Network Traffic. Transportation Research B, Vol. 29, No. 2, 1995, pp. 79–93.
28.
BirgeJ. R., and LouveauxF.. Introduction to Stochastic Programming. Springer-VerlagNew York, 1997.
29.
Van SlykeR., and WetsR. J.-B.. L-Shaped Linear Programs with Application to Optimal Control and Stochastic Program. SIAM Journal of Applied Mathematics, Vol. 17, 1969, pp. 638–663.
30.
HammersleyJ. M., and HandscombD. C.. Monte Carlo Methods. Wiley, New York, 1964.
