Navigating the Network Economy
By Anna Nagurney
Networks 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:
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 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 Environment
Fifteen 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."
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.
OR/MS Today copyright © 2000 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
506 Roswell Street, Suite 220, Marietta, GA 30060, USA
Phone: 770-431-0867 | Fax: 770-432-6969
Web Site © Copyright 1999, 2000 by Lionheart Publishing, Inc. All rights reserved.