June 2000EssayNavigating the Network EconomyBy Anna NagurneyNetworks permeate our daily lives, underpinning our societies and economies while providing the infrastructure for business, science and technology, social systems and education. Transportation networks give us the means to cross physical distances in order to conduct business, to visit colleagues, friends and family members, and to explore new vistas and expand our horizons. Transportation networks provide us with access to food and consumer products, and come in myriad forms: road, air, rail and waterway. According to the U. S. Department of Transportation, U.S. consumers, businesses and governments spent $950 billion on transportation in 1998. Communication networks allow us to communicate across cities, regions and national boundaries. Through such innovations as the Internet, communications networks have transformed the manner in which we live, work and conduct business. Communication networks allow the transmission of voice, data and video, and involve telephones, computers, satellites and microwaves. The trade publication Purchasing reports that corporate America spent $517.6 billion on telecommunications goods and services in 1999.Energy networks fuel the transportation and communication sectors and are essential to the very existence of the network economy. Energy networks provide electricity to run computers and light businesses, oil and gas to heat homes and power vehicles, and water for our very survival. The U. S. Department of Commerce estimates that energy expenditures in the United States totaled $515.8 billion in 1995. The management of networks dates to ancient times, and includes such classical examples as the Roman public road network and the "time of day" chariot policy, whereby chariots were banned from ancient Rome at particular times of the day. The formal study of networks began around 1940 and involves the mathematical modeling of, among other applications, the modern-day equivalent of the chariot policy. Using nodes, links and flows as primary building blocks, researchers construct mathematical representations of the network. They design algorithms to effectively solve the resulting "modeled" problem. The study of networks — interdisciplinary in nature due to the breadth of applications — is based on scientific techniques drawn from applied mathematics, computer science and engineering. Applications are as varied as finance and biology. The field of operations research has taken the lead in fostering both the development and application of network models and tools that are widely used by businesses, industries and governments. The following are examples of basic network problems: 1. the shortest path problem (determine the most efficient path from an origin node to a destination node), 2. the maximum flow problem (determine the maximum flow from an origin node to a destination node, given that there are capacities on the links that cannot be exceeded), and 3. the minimum cost flow problem (satisfy the demands at the destination nodes, given supplies at the origin nodes, at minimal total cost associated with shipping the flows without exceeding the arc capacities).
Shortest path problem applications are found in transportation and telecommunications, while maximum flow problems typically arise in machine scheduling and network reliability settings. Applications of the minimum cost flow problem range from warehousing and distribution to vehicle fleet planning and scheduling.Networks also appear in surprising and fascinating ways for problems that initially may not appear to involve networks at all. A variety of financial problems, for example, involve networks, as does knowledge production and dissemination. The study of networks, therefore, is not limited to physical networks where nodes coincide with locations in space but also to abstract networks. The ability to model a network provides a competitive advantage since: - many business problems are concerned with flows, be they material, human, capital or informational over space and time,
- modeling provides a graphical or visual depiction of different problems, and
- modeling may identify similarities and differences in distinct problems through their underlying network structure.
The characteristics of modern networks — their large-scale nature and complexity and the effect of congestion, alternative behavior of network users (which may lead to paradoxical phenomena) and interactions among multiple networks — emphasizes the importance of applying operations research methodologies to effectively harness their power. Let's look at these characteristics one at a time. Large-scale nature and complexity. To appreciate the size and complexity of the underlying topology inherent in many of today's networks, consider the following examples. The Chicago Regional Transportation Network includes 12,982 nodes, 39,018 links and 2,297,945 origin/destination pairs. AT&T's telecommunications network has 100,000 origin/destination pairs, while the company's detailed graph application (in which nodes are phone numbers and edges are calls) features 300 million nodes and 4 billion edges.Congestion. Road congestion results in $100 billion in lost productivity a year in the United States and an estimated $150 billion in Europe. The problem will only get worse since the number of cars is expected to grow 50 percent by 2010 and to double by 2030.Congestion is also playing an increasing role in telecommunications networks. An estimated 270 million people currently use the Internet. The Federal Communications Commission reports that the volume of Internet traffic is doubling every 100 days, a remarkable statistic given that telephone traffic has typically increased only by about 5 percent a year. As individuals increasingly access the Internet through wireless communication devices such as handheld computers and cellular phones, experts fear that the heavy use of the airwaves will create additional bottlenecks and congestion that could impede the further development of the technology. Operations research can assist not only in the modeling of congestion itself but also in the design of appropriate policies for congestion management. System-optimization vs. user-optimization. In many of today's networks, the "noncooperative" behavior of users aggravates the congestion problem. For example, in the case of urban transportation networks, travelers select their routes of travel from an origin to a destination so as to minimize their own travel cost or travel time. Although this behavior is "optimal" from an individual's perspective (user-optimization), it may not be optimal from a societal one (system-optimization) where one has control over the flows on the network and seeks to minimize the total cost in the network and the total loss of productivity. Consequently, in making any kind of policy decisions in such networks, decision-makers must take into consideration the users of the particular network.This point is vividly illustrated through a famous example known as the Braess paradox, in which it is assumed that the underlying behavioral principle is that of user-optimization. In the Braess network, the addition of a new road with no change in the travel demand or behavior results in all travelers in the network incurring a higher travel cost. In other words, they are all worse off than before the road was built. Interestingly, as reported in the The New York Times, this phenomenon has been observed in practice in New York City and Stuttgart, Germany. In 1990, 42nd Street in New York was closed for Earth Day, and the traffic flow in the area actually improved. An analogous situation was observed in Stuttgart where a new road was added to downtown, but the traffic flow worsened. Following complaints, the new road was removed.The phenomenon is also relevant to telecommunications networks and, in particular, to the Internet, which is another example of a "noncooperative network." Network tools from operations research, which specifically consider "noncooperative networks," have proven quite useful in this setting while addressing congestion management and network design. Network interactions. Clearly, one of the principal facets of the Network Economy is the interaction among networks themselves. For example, the increasing use of e-commerce, especially in business-to-business transactions, is changing not only the utilization and structure of the underlying logistical networks, but it is revolutionizing how business itself is transacted, as well as the structure of firms and industries. Cellular phones are used as vehicles move dynamically over transportation networks, resulting in dynamic evolutions of the topologies themselves. The interaction among transportation, telecommunication and other networks creates supernetworks that can greatly benefit from the discipline of operations research.Financial SystemsFinancial networks date to Francoise Quesnay, who, in his "Tableau Economique," published in the mid-1700s, conceptualized the circular flow of funds in an economy as a network. Two centuries later, Morris Albert Copeland, in his book, "A Study of Moneyflows in the United States," raised the question, Does money flow like water or like electricity? The classical portfolio optimization problem of Nobel Prize winner Harry Markowitz is actually a nonlinear network flow problem. Recently, the author and June Dong and Stavros Siokos of Salomon Smith Barney used networks to visualize sectors and their investment decisions in economies where one needs to determine the sectors' optimal holdings of assets, liabilities and instrument prices (and exchange rates). This application setting demonstrates that network topologies themselves evolve over time, and that the network structure of the financial economy in equilibrium is distinct from it in disequilibrium. Transportation and the EnvironmentFifteen percent of the world's emissions of carbon dioxide, 50 percent of the emissions of nitrogen oxide and 90 percent of emissions of carbon monoxide are due to motor vehicles. Given those figures, the growing demand for transportation raises serious questions regarding the sustainability of the existing auto-oriented transportation infrastructure. In this setting, emission paradoxes may occur. Thus, any policy aimed at pollution abatement must incorporate the network topology and the relevant cost and demand structure as well as the behavior of the users. Operations research has played a key role in the development of appropriate policy tools in the form of "emission pricing" and "tradable pollution permits." References- Abello, J., Pardalos, P. M., and Resende, M. G. C. (1999), "On Maximum Clique Problems in Very Large Graphs," in
*External Memory Algorithms,*J. Abello and J. Vitter, editors, AMS-DIMACS Series on Discrete Mathematics and Theoretical Computer Science - Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. (1993),
*Network Flows: Theory, Algorithms, and Applications*}, Prentice Hall, Upper Saddle River, New Jersey. - Banister, D., and Button, K. J. (1993), "Environmental Policy and Transport: An Overview" in
*Transport, Environment, and Sustainable Development,*D. Banister and K. J. Button, editors, E.&F. N., London, England. - Bar-Gera, H. (1999), "Origin-Based Algorithms for Transportation Network Modeling," National Institute of Statistical Sciences, Technical Report \# 103, PO Box 14006, Research Triangle Park, North Carolina 27709.
- Bass, T. (1992), "Road to Ruin,"
*Discover,*May, 56-61. - Beckmann, M. J. (1995), "Economic Models of Knowledge Networks," in
*Networks in Action,*D. Batten, J. Casti, and R. Thord, editors, pp, 150-174, Springer-Verlag, Berlin, Germany. - Beckmann, M. J., McGuire, C. B., and Winsten, C, B. (1956),
*Studies in the Economics of Transportation,*Yale University Press, New Haven, Connecticut. - Braess, D. (1968), "Uber ein Paradoxon der Verkehrsplanung," Unternehmenforschung, 12, 258-268.
- Cohen, J. E., and Kelly, F. P. (1990), "A Paradox of Congestion in a Queuing Network,"
*Journal of Applied Proability,*27, 730-734. - Copeland (1952),
*A Study of Moneyflows in the United States,*National Bureau of Economic Research, New York. - Dafermos, S., and Nagurney, A. (1984), "On Some Traffic Equilibrium Theory Paradoxes,"
*Transportation Research,*18B, 101-110. - Dafermos, S. C., and Sparrow, F. T. (1969), "The Traffic Assignment Problem for a General Network,"
*Journal of Research of the National Bureau of Standards,*73B, 91-118. - Dhanda, K. K., Nagurney, A., and Ramanujam, P. (1999),
*Environmental Networks: A Framework for Economic Decision-Making and Policy Analysis,*Edward Elgar Publishers, Cheltenham, England. - Kolata, G. (1990), "What if They Closed 42d Street and Nobody Noticed?"
*The New York Times,*Dec. 25, 1990. - Korilis, Y., Lazar, A. A., and Orda, A. (1999), "Avoiding the Braess Paradox in Non-Cooperative Networks,"
*Journal of Applied Probability,*36, 211-222. - Labaton, S. (2000), "F.C.C. to Promote a Trading System to Sell AirWaves,"
*The New York Times,*March 13, 2000. - Markowitz, H. M. (1952), "Portfolio Selection,"
*The Journal of Finance,*7, 77-91. - Mulvey, J. M. (1987), "Nonlinear Networks in Finance," in
*Advances in Mathematical Programming and Financial Planning,*1, 253-271. - Nagurney, A. (1999),
*Network Economics: A Variational Inequality Approach,*second and revised edition, Kluwer Academic Publishers, Dordrecht, The Netherlands. - Nagurney, A. (2000),
*Sustainable Transportation Networks*, Edward Elgar Publishers, Cheltenham, England. - Nagurney, A., and Siokos (1997),
*Financial Networks: Statics and Dynamics,*Springer-Verlag, Heidelberg, Germany. - Nagurney, A., and Siokos, S. (1998), "Dynamics of International Financial Networks: Modeling, Stability Analysis, and Computation," in
*Networks and Knowledge in a Dynamic Economy,*M. J. Beckmann, B. Johansson, F. Snickars, and R. Thord, editors, Springer-Verlag, Heidelberg, Germany, pp. 119-150. - Purchasing (2000), "Corporate Buyers Spent $517.6 Billion on Telecommunication," 128, 110.
- Quesnay, F. (1758), Tableau Economique, reproduced in facsimile with an introduction by H. Higgs by the British Economic Society, 1895.
- Resende, M. G. C. (2000), personal communication.
- US Department of Commerce (2000), Statistical Abstract of the United States, Bureau of the Census, Washington, DC.
- US Department of Transportation (1999),
*Guide to Transportation,*Bureau of Transportation Statistics, BTS99-06, Washington, DC. - Wu, J. H., Florian, M., and He, S. G. (2000), "EMME/2Implementation of the SCAG-II Model: Data Structure, System Analysis and Computation," submitted to the Southern California Association of Governments, INRO Solutions Internal Report, Montreal, Quebec, Canada.
Anna Nagurney is the John F. Smith Memorial Professor at the Isenberg School of Management at the University of Massachusetts at Amherst. This essay evolved from her Distinguished Faculty Lecture given at UMASS in April.Table of ContentsOR/MS Today Home Page copyright © 2000 by the Institute for Operations Research and the Management Sciences. All rights reserved.OR/MS TodayLionheart Publishing, Inc.506 Roswell Street, Suite 220, Marietta, GA 30060, USA Phone: 770-431-0867 | Fax: 770-432-6969 E-mail: lpi@lionhrtpub.com URL: http://www.lionhrtpub.com Web Site © Copyright 1999, 2000 by Lionheart Publishing, Inc. All rights reserved. |