×

An improved origin-based algorithm for solving the combined distribution and assignment problem. (English) Zbl 1149.90319

Summary: This paper is to further study the origin-based (OB) algorithm for solving the combined distribution and assignment (CDA) problem, where the trip distribution follows a gravity model and the traffic assignment is a user-equilibrium model. Recently, the OB algorithm has shown to be superior to the Frank-Wolfe (FW) algorithm for the traffic assignment (TA) problem and better than the Evans’ algorithm for the CDA problem in both computational time and solution accuracy. In this paper, a modified origin-destination (OD) flow update strategy proposed by Huang and Lam [Huang, H.J., Lam, W.H.K., 1992. Modified Evans’ algorithms for solving the combined trip distribution and assignment problem. Transportation Research B 26 (4), 325-337] for CDA with the Evans’ algorithm is adopted to improve the OB algorithm for solving the CDA problem. Convergence proof of the improved OB algorithm is provided along with some preliminary computational results to demonstrate the effect of the modified OD flow update strategy embedded in the OB algorithm.

MSC:

90B20 Traffic problems in operations research
90B80 Discrete location and assignment
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bar-Gera, H., Origin-based algorithm for the traffic assignment problem, Transportation Science, 36, 4, 398-417 (2002) · Zbl 1134.90469
[2] Bar-Gera, H.; Boyce, D., Origin-based algorithms for combined travel forecasting models, Transportation Research B, 37, 5, 405-422 (2003)
[3] Bar-Gera, H.; Boyce, D., Solving a non-convex combined travel forecasting model by the method of successive averages with constant step sizes, Transportation Research B, 40, 5, 351-367 (2006)
[4] Beckmann, M.; McGuire, C. B.; Winsten, C. B., Studies in the Economics of Transportation (1956), Yale University Press: Yale University Press New Haven, CT
[5] Boyce, D. E., Urban transportation network equilibrium and design models: Recent achievements and future prospects, Environment and Planning, A16, 1445-1474 (1984)
[6] Boyce, D. E., Is the sequential travel forecasting procedure counterproductive?, Journal of Urban Planning and Development, 128, 169-183 (2002)
[7] Boyce, D.; Bar-Gera, H., Multiclass combined models for urban travel forecasting, Network and Spatial Economics, 4, 115-124 (2004) · Zbl 1079.90017
[8] Boyce, D.; Xiong, C., Forecasting travel for very large cities: Challenges and opportunities for China, Transportmetrica, 3, 1, 1-19 (2007)
[9] Evans, S. P., A relationship between the gravity model for trip distribution problem in linear programming, Transportation Research, 7, 1, 39-61 (1973)
[10] Evans, S. P., Derivation and analysis of some models for combining trip distribution and assignment, Transportation Research, 10, 1, 37-57 (1976)
[11] Florian, M.; Nguyen, S., A combined trip distribution mode split and trip assignment model, Transportation Research, 12, 3, 241-246 (1978)
[12] Florian, M.; Nguyen, S.; Ferland, J., On the combined distribution-assignment of traffic, Transportation Science, 9, 1, 43-53 (1975)
[13] Frank, H.; Wolfe, P., An algorithm for quadratic programming, Naval Research Logistics Quarterly, 3, 95-110 (1956)
[14] Fratar, T. S., Vehicular trip distribution by successive approximation, Traffic Quarterly, 8, 53-56 (1954)
[15] Friesz, T. L., An equivalent optimization problem for combined multiclass distribution, assignment, and model split which obviates symmetry restrictions, Transportation Research B, 15, 5, 361-369 (1981)
[16] Garret, M.; Wachs, M., Transportation Planning on Trial (1996), Thousand Oaks: Thousand Oaks California
[17] Ho, H. W.; Wong, S. C., Housing allocation problem in a continuum transportation system, Transportmetrica, 3, 1, 21-39 (2007)
[18] Ho, H. W.; Wong, S. C.; Loo, B. P.Y., Combined distribution and assignment model for a continuum traffic equilibrium problem with multiple user classes, Transportation Research B, 40, 633-650 (2006)
[19] Horowitz, A. J., Tests of an ad hoc algorithm of elastic-demand equilibrium traffic assignment, Transportation Research B, 23, 3, 309-313 (1989)
[20] Huang, H. J.; Lam, W. H.K., Modified Evans’ algorithms for solving the combined trip distribution and assignment problem, Transportation Research B, 26, 4, 325-337 (1992)
[21] Lam, W. H.K.; Huang, H. J., A combined trip distribution and assignment model for multiple user classes, Transportation Research B, 26, 3, 275-287 (1992)
[22] Larsson, T.; Patriksson, M., Simplicial decomposition with disaggregated representation for the traffic assignment problem, Transportation Science, 26, 1, 4-17 (1992) · Zbl 0764.90033
[23] LeBlanc, L. J.; Farhangian, K., Efficient algorithm for solving elastic demand traffic assignment problems and model split-assignment problems, Transportation Science, 15, 306-317 (1981)
[24] LeBlanc, L. J.; Morlok, E. K.; Pierskalla, W. P., An efficient approach to solving the road network equilibrium traffic assignment problem, Transportation Research, 9, 4, 309-318 (1975)
[25] Lee, D.-H.; Meng, Q.; Wu, L., Equity based land use and transportation problem, Journal of Advanced Transportation, 40, 1, 75-93 (2006)
[26] Lin, J. J.; Feng, C. M., A bi-level programming for the land use network design problem, Annals of Regional Science, 37, 93-105 (2003)
[27] Lundgren, J. T.; Patriksson, M., An algorithm for the combined distribution and assignment model, (Bell, M. G.H., Transportation Networks: Recent Methodological Advances (1998), Pergamon Press: Pergamon Press Amsterdam), 239-253
[28] McNally, M. G., The activity-based approach, (Hensher, D. A.; Button, K. J., Handbook of Transport Modelling (2000), Pergamon: Pergamon Oxford), 53-69
[29] Oppenheim, N., Equilibrium trip distribution/assignment with variable destination costs, Transportation Research B, 27, 3, 207-217 (1993)
[30] Oppenheim, N., Urban Travel Demand Modeling (1995), John Wiley and Sons: John Wiley and Sons New York
[31] Ortuzar, J.de D.; Willumsen, L. G., Modeling Transport (2001), Wiley: Wiley New York
[32] Patriksson, M., The Traffic Assignment Problem: Models and Methods (1994), VSP: VSP Utrecht, The Netherlands · Zbl 0828.90127
[33] Rockafellar, R. T., Convex programming and systems of elementary monotonic relations, Journal of Mathematical Analysis and Applications, 19, 543-564 (1967) · Zbl 0152.38006
[34] Safwat, K. N.; Magnanti, T. L., A combined trip generation, trip distribution, model split, and trip assignment model, Transportation Science, 18, 14-30 (1988) · Zbl 0639.90032
[35] Tam, M. L.; Lam, H. K.W., Maximum car ownership under constraints of road capacity and parking space, Transportation Research B, 34, 3, 145-170 (2000)
[36] Wong, K. I.; Wong, S. C.; Wu, J. H.; Yang, H.; Lam, W. H.K., A combined distribution, hierarchical mode choice, and assignment network model with multiple user and mode classes, (Lee, D. H., Urban and Regional Transportation Modeling: Essays in Honor of David Boyce (2004), Edward Elgar Publishing: Edward Elgar Publishing Northampton, USA), 25-42
[37] Yim, K.W., 2005. A Reliability-based Land Use and Transportation Optimization Model. M.S. Thesis, University of Hong Kong, Hong Kong.; Yim, K.W., 2005. A Reliability-based Land Use and Transportation Optimization Model. M.S. Thesis, University of Hong Kong, Hong Kong.
[38] Yang, H.; Bell, M. G.H.; Meng, Q., Modeling the capacity and level of service of urban transportation networks, Transportation Research B, 34, 2, 255-275 (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.