Abstract
The analysis of transportation phenomena by quantitative approaches naturally gives rise to network models that represent the spatial characteristics of the transport infrastructure. This paper surveys the nonlinear cost models that arise in transportation analysis and points out the principal methods used for their solution in practice. We discuss the network equilibrium problem, the problem of estimating an origin/destination matrix and certain concave cost network flow problems.
This research was supported by a grant from the Natural Sciences and Engineering Research Council of Canada.
Preview
Unable to display preview. Download preview PDF.
References
H. Aashtiani and T. Magnanti, “A linearization and decomposition algorithm for computing urban traffic equilibrium”, Proceedings of the 1982 IEEE large scale systems symposium (October, 1982).
H. Aashtiani and T. Magnanti, “Equilibria on a congested transportation network,” SIAM Journal on Algebraic and Discrete Methods 2 (1981) 213–226.
M. Abdulaal and L. Leblanc, “Methods for combining model split equilibrium assignment models”, Transportation Science 13 (1979) 292–314.
B. Ahn, Computation of market equilibria for policy analysis: The Project Independence Evaluation System (PIES) approach (Garland, New York, 1979).
B. Ahn and W. Hogan, “On convergence of the PIES algorithm for computing equilibria”, Operations Research 33 (1982) 281–300.
P.A. Andersson, “On the convergence of iterative methods for the distribution balancing problem”, Transportation Research B 15B (1981) 173–201.
R. Asmuth, “Traffic network equilibria”, Technical Report SOL 78-2, Department of Operations Research, Stanford University (Stanford, CA, 1978).
A. Auslender, Optimisation, méthodes numériques (Masson, Paris, 1976).
M.J. Beckmann, C.B. McGuire, and C.B. Winsten, Studies in the economics of transportation (Yale University Press, New Haven, 1956).
D.P. Bertsekas, “Optimal routing and flow control methods for communications networks”, in: A. Bensoussan and J.L. Lions, eds., Analysis and optimization of systems (Springer-Verlag, Berlin, New York, 1982) pp. 615–643.
D.P. Bertsekas and E.M. Gafni, “Projection methods for variational inequalities with application to the traffic assignment problem”, Mathematical Programming Study 17 (1982) 139–159.
D. Boyce, “A framework for constructing network equilibrium models of urban location”, Transportation Science 14 (1980) 71–96.
L.M. Bregman, “The relaxation method for finding the common point of convex sets and its application to the solution of problems in convex programming”, USSR Computational Mathematics and Mathematical Physics 7 (1967) 200–217.
A. Bruynooghe, A. Gibert and M. Sakarovitch, “Une méthode d’affectation du traffic”, Proceedings of the fourth symposium on the theory of traffic flow (Karlsruhe, 1968).
J.E. Burrel, “Multiple route assignment: A comparison of two methods”, in: M. Florian, ed., Traffic equilibrium methods, Lecture Notes in Economics and Mathematical Systems 118 (Springer-Verlag, Berlin, 1976) pp. 229–239.
D. Cantor and M. Gerla, “Optimal routing in a packet switched computer network”, IEEE Transactions on Computers 10 (1974) 1062–1068.
S. Dafermos, “An extended traffic assignment model with applications to two-way traffic”, Transportation Science 4 (1971) 336–389.
S. Dafermos, “The traffic assignment problem for multiclass-usertransportation networks”, Transportation Science 6 (1972) 73–87.
S. Dafermos, “Traffic equilibrium and variational inequalities”, Transportation Science 14 (1980), 42–54.
S. Dafermos, “Relaxation algorithms for the general asymmetric traffic equilibrium problem”, Transportation Science 16 (1982a) 231–240.
S. Dafermos, “The general multimodal network equilibrium problem with elastic demand”, Networks 12 (1982b) 57–72.
S. Dafermos, “An iterative scheme for variational inequalities”, Mathematical Programming 26 (1983). 40–47.
S. Dafermos and A. Nagurney, “Sensitivity analysis for the general asymmetric network equilibrium problem”, Technical Report LCDS M-82-7, Lefschetz Center for Dynamical Systems, Brown University (Providence, RI, 1982).
S. Dafermos and T. Sparrow, “The traffic assignment problem for a general network”, Journal of Research of the National Bureau of Standards B 73B (1969) 91–117.
C.F. Daganzo, “Unconstrained extremal formulations of some transportation equilibrium problems”, Transportation Science 16 (1982) 332–360.
R.S. Dembo, “Progress in large scale nonlinear optimization”, presented at XI. International Symposium on Mathematical Programming (Bonn, West Germany, 1982).
R.S. Dembo and J.G. Klincewicz, “A scale reduced, gradient algorithm for network flow problems with convex separable costs”, Mathematical Programming Study 15 (1981) 125–147.
R.S. Dembo and U. Tulowitzki, “Successive inexact quadratic programming and its application to traffic problems”, Working Paper Series B, No. 65, School of Organization and Management, Yale University (New Haven, 1983).
W.E. Deming and F.F. Stephan, “On a least squares adjustment of a sampled frequency table when the expected marginal totals are known”, Annals of Mathematical Statistics 11 (1940) 427–444.
R.B. Dial, “A probabilistic multipath traffic assignment model which obviates path enumeration”, Transportation Research 5 (1971) 83–111.
P. Dow and D. Van Vliet, “Capacity restrained road assignment”, Traffic Engineering and Control 20 (1979) 296–305.
R.E. Erickson, C.L. Monma and A.F. Veinott, Jr., “Minimum concave cost network flows” Technical Report (1981). Forthcoming in Mathematics of Operations Research.
S. Erlander, S. Nguyen and N. Stewart, “On the calibration of the combined distribution-assignment model”, Transportation Research B 13B (1979) 259–267.
S.P. Evans, “Derivation and analysis of some models for combining trip distribution and assignment”, Transportation Research 10 (1976) 37–57.
S.P. Evans and H.R. Kirby, “A three-dimensional furness procedure for calibrating gravity models”, Transportation Research 10 (1976) 37–57.
S.P. Evans and H.R. Kirby, “A three-dimensional Furness procedure for calibrating gravity models”, Transportation Research 8 (1974) 105–122.
J.A. Ferland, “Minimum cost multicommodity circulation problems with convex arc-costs”, Transportation Science 8 (1974) 355–360.
C. Fisk, “Some developments in equilibrium traffic assignment”, Transportation Research 14B (1980) 243–255.
C. Fisk and D. Boyce, “Alternative variational inequality formulations of the network equilibrium—Travel Choice Problem”, Transportation Science 17 (1983) 454–463.
C. Fisk and D. Boyce, “A note on trip matrix estimation from link traffic count data”, Transportation Research B 17B (1983) 245–250.
C. Fisk and S. Nguyen, “Existence and uniqueness properties of an asymetric two-mode equilibrium model”, Transportation Science 16 (1982) 318–328.
M. Florian, “A traffic equilibrium model of travel by car and public transit modes”, Transportation Science 8 (1977a) 166–179.
M. Florian, “An improved linear approximation algorithm for the network equilibrium (packet switching) problem”, IEEE Proceedings, Decision and Control (1977b) 812–818.
M. Florian, “An introduction to network models used in transportation planning”, in: M. Florian, ed., Transportation planning models (North-Holland, Amsterdam, 1984) pp. 137–152.
M. Florian, R. Chapleau, S. Nguyen, C. Achim, L. James-Lefebvre and C. Fisk, “Validation and application of EMME: An equilibrium based two-mode urban transportation planning method”, Transportation Research Record 728 (1979) 14–22.
M. Florian and S. Nguyen, “A method for computing network equilibrium with elastic demand”, Transportation Science 8 (1974) 321–332.
M. Florian and S. Nguyen, “An application and validation of equilibrium trip assignment methods”, Transportation Science 10 (1976) 374–389.
M. Florian and S. Nguyen, “A combined trip distribution modal split and trip assignment model”, Transportation Research 12 (1978) 241–246.
M. Florian, J. Ferland and S. Nguyen, “On the combined distribution-assignment of traffic”, Transportation Science 9 (1975) 43–53.
M. Florian, J. Guelat and H. Spiess, “An efficient implementation of the PARTAN variant of the linear approximation method for the network equilibrium problem”, Publication #395, Centre de Recherche sur les Transports, Université de Montréal (1983).
M. Florian, M. Rossin-Arthiat and D. de Werra, “A property of minimum concave cost flows in capacitated networks”, Canadian Journal of Operational Research 9 (1971) 293–304.
M. Florian and H. Spiess, “The convergence of diagonalization algorithms for asymmetric equilibrium problems”, Transportation Research B 16B (1982) 477–483.
M. Florian and H. Spiess “On binary mode choice/assignment models”, Transportation Science 17 (1983) 32–47.
C. Frank, “A study of alternative approaches to combined trip distribution-assignment modelling”, Ph.D. Thesis Department of Regional Science, University of Pennsylvania (Philadelphia, 1978).
M. Frank and P. Wolfe, “An algorithm for quadratic programming”, Naval Research Logistics Quarterly 3 (1956) 95–110.
L. Fratta, M. Gerla and L. Kleinrock, “The flow deviation method: An approach to store and forward communication network design”, Networks 3 (1973) 97–133.
G. Gallo and C. Sodini, “Adjacent extreme flows and application to min concave cost flow problems”, Networks 9 (1979) 95–122.
G. Gallo, C. Sandi and C. Sodini, “An algorithm for the min concave cost flow problem”, European Journal of Operations Research 4 (1980) 249–255.
G. Gallo and S. Pallotino, “Shortest path methods in transportation models”, in: M. Florian, ed., Transportation planning models (North-Holland, Amsterdam, 1984) pp. 227–256.
A. Gibert, “A method for the traffic assignment problem when demand is elastic”, unpublished report LBS TNT-B5 (1968).
B. Golden, “A minimum cost multi-commodity, network flow problem concerning imports and exports”, Networks 5 (1975) 331–356.
J. Guélat, “Algorithmes pour le probleme d’affectation du trafic avec demandes fixes—Comparaisons”, Publication #299, Centre de Recherche sur les Transports Université de Montréal (1982).
M.D. Hall, D. Van Vliet and L.G. Willumsen, “SATURN—A simulation assignment model for the evaluation of traffic management schemes”, Traffic Engineering and Control (1980) 168–176.
D.W. Hearn, “The gap function of a convex program”, Operations Research Letters 1 (1982) 67–71.
D.W. Hearn and S. Nguyen, “Dual and saddle functions related to the gap function”, Research Report 82-4, Department of Industrial and Systems Engineering, University of Florida (Gainesville, 1982).
W.W. Hogan, “Energy policy models for Project Independence”, Computers and Operations Research 2 (1975) 251–271.
C.A. Holloway, “An extension of the Frank and Wolfe method of feasible directions”, Mathematical Programming 6 (1974) 14–27.
B. Hutchinson, “Land use transport planning models”, in: M. Florian, ed., Transportation Planning models (North-Holland, Amsterdam, 1984) pp. 499–510.
E. Jaynes, “Information theory and statistical mechanics”, Physical Review 106 (1957a) 171–190.
E. Jaynes, “Information theory and statistical mechanics”, Physical Review 108 (1957b) 620–630.
T.R. Jefferson and C.H. Scott, “The analysis of entropy models with equality and inequality constraints”, Transportation Research B 13B (1979) 123–132.
K. Jornsten and S. Nguyen, “On the estimation of a trip matrix from network data”, Publication #153, Centre de Recherche sur les Transports, Université de Montréal (1979).
N. Josephy, “Newton’s method for generalized equations”, Technical Report 1965, Mathematics Research Center, University of Wisconsin (Madison, 1979).
D. Kinderlehrer and G. Stampacchia, An introduction to variational inequalities and applications (Academic Press, New York, 1980).
F. H. Knight, “Some fallacies in the interpretation of social cost”, Quarterly Journal of Economics 38 (1924) 582–606.
J. Kruithof, “Calculation of telephone”, De Ingenieur 52 (1937) E15–E25. [in Flemish.]
S. Kullback, Information theory and statistics (Wiley, New York, 1959).
B. Lamond and N.F. Stewart, “Bregman’s balancing method”, Transportation Research B 15B (1981) 239–248.
S. Lawphongpanich and D.W. Hearn, “Simplicial decomposition of the asymmetric traffic assignment problem,” Research Report 82-12, Department of Industrial and Systems Engineering, University of Florida (Gainesville, 1982).
L. Le Blanc, “Global solutions for a non convex, non concave rail network model”, Mathematical Science 23 (1978) 131–139.
L. Le Blanc and K. Farhangian, “Efficient algorithms for solving elastic demand traffic assignment problems and mode split assignment problems”, Transportation Science 15 (1981) 306–312.
L.J. Leblanc, R.V. Helgason and D.E. Boyce, “Improved efficiency of the Frank-Wolfe algorithm”, Working Paper 381-131, Owen Graduate School of Management, Vanderbilt University (Nashville, TN, 1982).
L.J. Le Blance, E.K. Morlok and W.P. Pierskalla, “An efficient approach to solving the road network equilibrium traffic assignment problem”, Transportation Research 5 (1975) 309–318.
T. Leventhal, G. Nemhauser and L.E. Trotter, Jr., “A column generation algorithm for optimal traffic assignment”, Transportation Science 7 (1973) 168–176.
M. Los, “Combined residential-location and transportation models”, Environment and Planning A 11 (1979) 1241–1265.
D.G. Luenberger, Introduction to linear and nonlinear programming (Addison-Wesley, Reading, MA, 1973).
T.L. Magnanti, “Equilibria and congested networks: Modeling and computation”, ORSA/TIMS Bulletin 10 (1980).
T.L. Magnanti, “Models and algorithms for predicting urban traffic equilibrium”, in: M. Florian, ed., Transportation planning models (North-Holland, Amsterdam, 1984) pp. 153–186.
J.D. Murchland, “Road network traffic distribution in equilibrium”, in: Proceedings of the conference “Mathematical methods in economic sciences”, Mathematisches Forschungsinstitut, Oberwolfach (W. Germany, 1969).
B. Murtagh and M.A. Saunders, “MINOS: A large-scale nonlinear programming system—User’s guide”, Technical Report SOL 77-9, Systems Optimization Laboratory, Department of Operations Research, Stanford University (Stanford, CA, 1977).
S. Nguyen, “A mathematical programming approach to equilibrium methods of traffic assignment”, Publication #138, Département d’informatique et de recherche opérationnelle, Université de Montréal (1973).
S. Nguyen, “An algorithm for the traffic assignment problem”, Transportation Science 8 (1974) 203–216.
S. Nguyen, “A unified approach to equilibrium methods for traffic assignment”, in: M. Florian, ed., Traffic equilibrium methods, Lecture Notes in Economics and Mathematical Systems 118 (Springer-Verlag, Berlin, 1976) pp. 148–182.
S. Nguyen, “Estimating an OD matrix from network dates: A network equilibrium approach”, Publication #60, Centre de Recherche sur les Transports, Université de Montréal (1977a).
S. Nguyen, “Procedures for equilibrium traffic assignment with elastic demand”, Publication #339, Centre de recherche sur les Transports, Université de Montréal (1977b).
S. Nguyen, “Modeles de distribution spatiale tenant compte des itineraires”, Publication #225, Centre de Recherche sur les Transports, Université de Montréal (1981). To appear in INFOR.
S. Nguyen and C. Dupuis, “An efficient method for computing traffic equilibria in network with asymmetric transportation costs”, Transportation Science 18 (1984) 185–232.
A. Ohuchi and I. Kaji, “An algorithm for the Hitchcock transportation problems with quadratic cost functions”, Journal of the Operations Research Society of Japan 24 (1981) 170–191.
J.-S. Pang and D. Chan, “Gauss-Seidel methods for variational inequality problems over product sets”, Working Paper, GSIA, Carnegie-Mellon University (Pittsburgh, PA, 1982).
J.-S. Pang and D. Chan, “Iterative methods for variational and complementarity problems”, Mathematical Programming 24 (1982) 284–313.
E.R. Peterson and D.M. Tulett, “An algorithm for calculating equilibrium demand with fixed traffic routing”, Technical Report, School of Business, Queens University (Kingston, Ontario, Canada, 1982).
R.B. Potts and R.M. Oliver, Flows in transportation networks (Academic Press, New York, 1972).
W.B. Powell and Y. Sheffi, “The convergence of equilibrium algorithms with predetermined step sizes”, Transportation Science 16 (1982) 45–55.
P. Rech and L.G. Barton, “A non-convex transportation algorithm,” in: E.M.L. Beale, ed., Applications of mathematical programming techniques (American Elsevier, New York, 1970) pp. 250–260.
P. Robillard and N.F. Stewart, “Iterative numerical methods for trip distribution problems”, Transportation Research 8 (1974) 575–582.
B. Roy, Algebre moderne et théorie des graphes, Tome 2 (Dunod, Paris, 1970).
R. Rust and C. Bornstein, “Um algorithmo branch-and-bound para problemas de localizqçao com custos expressos por funçoes escadas”, Technical Report, COPPE, Federal University of Rio de Janeiro (1982).
B.V. Shah, R.J. Buehler and O. Kempthorne, “Some algorithms for minimizing a function of several variables”, SIAM Journal on Applied Mathematics 12 (1964) 74–92.
M.J. Smith, “Existence, uniqueness and stability of traffic equilibria”, Transportation Research B 1B (1979) 295–304.
F. Snickars and J.W. Weibull, “A minimum information principle, theory and practice”, Regional Science and Urban Economics 7 (1977) 137–168.
R.M. Soland, “Optimal facility location with concave costs”, Operations Research 22 (1974) 373–382.
F. Soumis, “Planification d’une flotte d’avions”, Publication #133, Centre de Recherche sur les Transports, Université de Montréal (1978).
N.F. Stewart, “Notes on the mathemtical structure of equilibrium models”, Technical Report LiTH-MAT-12-79-8, Department of Mathematics, Linkøping Institute of Technology (Linkøping, Sweden, 1979).
J. Wardrop, “Some theoretical aspects of road traffic research”, in: Proceedings of the Institute of Civil Engineers, Part II, Vol. 1 (1952) 325–378.
A. Weintraub and J. Gonzales, “An algorithm for the traffic assignment problem”, Networks. 10 (1980) 191–210.
A.G. Wilson, “A statistical theory of spatial distribution models”, Transportation Research 1 (1967) 253–269.
A.G. Wilson, Entropy in urban and regional modelling (Pion, London, 1970).
P. Wolfe, “Convergence theory in nonlinear programming,” in: J. Abadie, ed., Nonlinear and integer programming (North-Holland, Amsterdam, 1970) pp. 1–36.
B. Yaged, Jr., “Minimum cost routing for static network models,” Networks 1 (1971) 139–172.
N. Zadeh, “On building minimum cost communication networks”, Networks 3 (1973) 315–331.
N. Zadeh, “On building minimum cost communication networkds over time”, Networks 4 (1974) 19–34.
W.I. Zangwill, “Minimum concave cost flows in certain networks”, Management Science 14 (1968) 429–450.
W.I. Zangwill, Nonlinear programming: A unified approach (Prentice-Hall, Englewood, Cliffs, NJ, 1969).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1986 The Mathematical Programming Society, Inc.
About this chapter
Cite this chapter
Florian, M. (1986). Nonlinear cost network models in transportation analysis. In: Gallo, G., Sandi, C. (eds) Netflow at Pisa. Mathematical Programming Studies, vol 26. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0121092
Download citation
DOI: https://doi.org/10.1007/BFb0121092
Received:
Revised:
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00922-8
Online ISBN: 978-3-642-00923-5
eBook Packages: Springer Book Archive