System-Optimal Stochastic Transportation Network Design
Abstract
In transportation engineering, the network design problem (NDP) aims at finding an optimal link improvement in a network for given demand. Although traffic demand is essentially uncertain, many previous studies assumed it to be deterministic. The demand stochasticity is incorporated and formulas are developed for system-optimal (SO) flow stochastic NDP. The SO assumption is justified by comparing results from SO deterministic NDP with those of user-equilibrium NDP. The difference in social cost between the two approaches is found to be less than 5%. Two two-stage stochastic programs with recourse formulations are proposed: one with penalty function and the other without. The main advantage of the first formulation is that a planner can exert better control on improvement by appropriately weighing reduction in the congestion versus improvement costs. The challenge, however, lies in selecting an appropriate penalty function. A nonlinear penalty function is found suitable for the test network studied. The second formulation does not require penalty function but results in a large number of scenarios. Nonanticipativity constraints are introduced in the second formulation to arrive at uniform improvement over all scenarios. Both formulations are solved on a test network. It is found that necessary improvements and the total costs with both models are more than those for average demand.
Get full access to this article
View all access and purchase options for this article.
References
1. LeBlanc L. J. An Algorithm for the Discrete Network Design Problem. Transportation Science, Vol. 9, 1975, pp. 183–199.
2. Abdulaal M., and LeBlanc L. J. Continuous Equilibrium Network Design Models. Transportation Research B, Vol. 13, 1979, pp. 19–32.
3. Friesz T. L., Cho H. J., Mehta N. J., Tobin R. L., and Anandalingham G. A Simulated Annealing Approach to the Network Design Problem with Variational Inequality Constraints. Transportation Science, Vol. 26, 1992, pp. 18–26.
4. Marcotte P., and Marquis G. Efficient Implementation of Heuristic for the Continuous Network Design Problems. Annals of Operations Research, Vol. 34, 1992, pp. 163–176.
5. Meng Q., Yang H., and Bell M. G. H. An Equivalent Continuously Differentiable Model and a Locally Convergent Algorithm for the Continuous Network Design Problem. Transportation Research B, Vol. 35, 2001, pp. 83–105.
6. Suwansirikul C., Friesz T. L., and Tobin R. L. Equilibrium Decomposed Optimization: A Heuristic for the Continuous Equilibrium Network Design Problem. Transportation Science, Vol. 21, 1987, pp. 254–263.
7. Ukkusuri S. Accounting for Uncertainty, Robustness and Online Information in Transportation Networks. PhD thesis. University of Texas, Austin, 2005.
8. Waller T. S., and Ziliaskopoulos A. K. Stochastic Dynamic Network Design Problem. In Transportation Research Record: Journal of the Transportation Research Board, No. 1771, TRB, National Research Council, Washington, D.C., 2001, pp. 106–113.
9. Flyvbjerg B., Holm M. K. S., and Buhl S. L. How (In)Accurate are Demand Forecasts in Public Works Projects? The Case of Transportation. Journal of the American Planning Association, Vol. 71, No. 2, 2005, pp. 131–146.
10. LeBlanc L. J., and Abdulaal M. A Comparison of User Optimum Versus System Optimum Traffic Assignment in Transportation Network Design. Transportation Research B, Vol. 18, No. 2, 1984, pp. 115–121.
11. Dantzig G. B., and Maier S. F. Formulating and Solving the Network Design Problem by Decomposition. Transportation Research B, Vol. 13, 1979, pp. 5–17.
12. Chen M., and Alfa A. S. A Network Design Algorithm Using a Stochastic Incremental Traffic Assignment Approach. Transportation Science, Vol. 25, 1991, pp. 215–224.
13. Gao Z., Wu J., and Sun H. Solution Algorithm for the Bilevel Discrete Network Design Problem. Transportation Research B, Vol. 39, 2005, pp. 479–495.
14. Magnanti T. L., and Wong R. T. Network Design and Transportation Planning: Models and Algorithms. Transportation Science, Vol. 18, 1984, pp. 1–55.
15. Yang H., and Bell M. G. H. Models and Algorithms for Road Network Design: A Review and Some New Developments. Transport Review, Vol. 18, 1998, pp. 257–278.
16. Ukkusuri S. V., Karoonsoontawong A., and Waller S. T. A. Stochastic Dynamic User Optimal Network Design Model Accounting for Demand Uncertainty. In International Conference on Transportation Systems Planning and Operations (TRANSPO2004). IIT Madras, Chennai, India, 2004.
17. Riis M., and Anderson K. A. Capacited Network Design with Uncertain Demand. INFORMS Journal of Computing, Vol. 14, No. 3, 2002, pp. 247–260.
18. Andrade R., Lisser A., Maculan N., and Plateau G. B and B Framework for the Capacity Expansion of High Speed Telecommunication Network Under Uncertainty. Annals of Operations Research, Vol. 140, 2005, pp. 49–65.
19. Cole Smith J., Schaefer A. J., and Yen J. W. A Stochastic Integer Programming Approach to Solving a Synchronous Optical Network Ring Design Problem. Networks, Vol. 44, No. 1, 2004, pp. 12–26.
20. Ahmed S., and Sahinidis N. V. An Approximate Scheme for Stochastic Integer Programs Arising in Capacity Expansion. Operations Research, Vol. 51, No. 3, 2003, pp. 461–471.
21. Waltz R. A., and Plantenga T. KNITRO 5.0 User's Manual. Ziena Optimization, Inc., Evanston, Ill., 2006.
22. Czyzyk J., Mesnier M., and Mor J. The NEOS Server. IEEE Journal on Computational Science and Engineering, Vol. 5, 1998, pp. 68–75.
23. Kall P., and Wallace S. W. Stochastic Programming, 2nd ed. John Wiley and Sons, New York, 1994.
Cite article
Cite article
Cite article
OR
Download to reference manager
If you have citation software installed, you can download article citation data to the citation manager of your choice
Information, rights and permissions
Information
Published In
Article first published: January 2007
Issue published: January 2007
Authors
Metrics and citations
Metrics
Journals metrics
This article was published in Transportation Research Record: Journal of the Transportation Research Board.
VIEW ALL JOURNAL METRICSArticle usage*
Total views and downloads: 37
*Article usage tracking started in December 2016
Altmetric
See the impact this article is making through the number of times it’s been read, and the Altmetric Score.
Learn more about the Altmetric Scores
Articles citing this one
Receive email alerts when this article is cited
Web of Science: 0
Crossref: 25
- Investigating machine learning for simulating urban transport patterns...
- Towards clean transportation systems: Infrastructure planning for EVs ...
- Dynamic wireless charging lanes location model in urban networks consi...
- Macroscopic Fundamental Diagram Based Discrete Transportation Network ...
- Network Design Model to Integrate Shelter Assignment with Contraflow O...
- Hybrid machine learning and optimisation method to solve a tri‐level r...
- Flexible Emergency Vehicle Network Design considering Stochastic Deman...
- Single‐commodity stochastic network design under demand and topologica...
- Stochastic Modeling of Natural Gas Infrastructure Development in Europ...
- Model and a solution algorithm for the dynamic resource allocation pro...
- A Sustainable Road Network Design Problem with Land Use Transportation...
- Demand clustering in freight logistics networks
- Alternative Model for Determining the Optimal Concession Period in Man...
- Sustainable Transportation Network Design with Stochastic Demands and ...
- Model and a Solution Algorithm for the Dynamic Resource Allocation Pro...
- Evolutionary Marginal Cost Pricing Scheme Implementation Based on Stoc...
- A Distributionally Robust Joint Chance Constrained Optimization Model ...
- Dynamic Resource Allocation Problem for Transportation Network Evacuat...
- Optimization models for differentiating quality of service levels in p...
- Global optimization methods for the discrete network design problem
- Stochastic Congestion Pricing among Multiple Regions: Competition and ...
- Hybrid Evolutionary Metaheuristics for Concurrent Multi-Objective Desi...
- A STUDY OF PERSPECTIVE OF ROAD TRANSPORTATION RELIABILITY ON THE NETWO...
- The evacuation optimal network design problem: model formulation and c...
- Reliable System-Optimal Network Design...
Figures and tables
Figures & Media
Tables
View Options
Get access
Access options
If you have access to journal content via a personal subscription, university, library, employer or society, select from the options below:
loading institutional access options
Alternatively, view purchase options below:
Purchase 24 hour online access to view and download content.
Access journal content via a DeepDyve subscription or find out more about this option.
