Elsevier < Decision Sciences Publications < Handbooks in Operations Research and Management Science < Volume 8: Network Routing < Preface

NETWORK ROUTING
Edited by M.O. Ball, T.L. Magnanti, C.L. Monma and G.L. Nemhauser

PREFACE

Whenever we use a telephone, shop at our neighborhood food store or mall, read our mail or fly for business or for pleasure, we are the beneficiaries of some system that has routed messages, goods or people from one place to another. Indeed, many great advances in the evolution of civilization (the telephone, trains, airplanes) represent quantum leaps in our ability to transport information, goods or services.

The papers in this volume consider a general area of study known as network routing. The underlying problems are conceptually simple, yet mathematically complex and challenging. How can we best route material or people from one place to another? Or, how can we best design a system (e.g., locate facilities) to provide services and goods as efficiently and equitably as possible?

The problems encountered in answering these questions often have an underlying combinatorial structure, for example, either we dispatch a vehicle or we don't, or we use one particular route or another. The problems also typically have an underlying network structure (a communication or transportation network). In addition, models for these problems often are very large with hundreds or thousands of constraints and variables.

Over the past three decades, researchers have made enormous progress in developing theory, models and solution methods for addressing these problems. Indeed, the advances in this general problem domain have been one of the major success stories of operations research and applied mathematics. With contributions by many individuals who have fuelled this success, this volume attempts simultaneously to describe the exciting challenges of the field of network routing and the enormous progress in modeling and solving these problems.

The first five chapters deal with several topics whose development has primarily been motivated by transportation applications, particularly those involving routing and scheduling issues. Chapter 1 by Fisher treats the "core" vehicle routing problem. While the traveling salesman problem can be interpreted as the problem of finding a best route for a single vehicle, the vehicle routing problem requires the determination of optimal routes for a fleet of vehicles, each with capacity limitations. In many cases, vehicle routing applications involve one of many possible time constraints. Chapter 2 by Desrosiers, Solomon and Sournis treats this class of problems. Frequently, practitioners need to solve routing problems repeatedly with changing, uncertain requirements. Such environments lead to the type of stochastic and dynamic problems that Powell, Jaillet and Odoni cover in Chapter 3. In Chapter 4, Federgruen and Sirachi-Levi address the worst case and asymptotic analysis of routing algorithms. Analyses of this type have been useful not only in comparing algorithms, but also in investigating the overall design of distribution systems that involve inventory and other considerations. The classical vehicle routing problem associates demands with network nodes. Arc routing problems arise when service requirements are associated with network arcs. These problems, which trace their history back to the "first problem in graph theory", the K6nigsburg; bridge problem, are treated in Chapter 5 by Assad and Golden.

The second set of chapters deal with a diverse set of routing related issues which arise in several different application domains. Network equilibrium problems, which are addressed in Chapter 6 by Florian and Hearn, arise when several users compete for the limited resources of a network. Practitioners use this class of models for a wide range of problems, including the prediction of traffic patterns within an urban transportation system and the traffic flows within a telecommunications network. Chapter 7 by Labbé, Peters and Thisse treats location problems defined on networks. Networks serve as a very rich framework for modeling location problems and for developing efficient location algorithms. Chapter 8 by Mohring, Wagner and Wagner treats a new, but very significant application area for network optimization, the design of VI-SI networks. Chapter 9 by Sharkey takes a broad look at economic equilibrium models arising in a network setting. Included are topics from the economic literature as well as closely related topics from non-cooperative game theory.

A companion volume in the Handbook series, entitled "Network Models", treats basic network models such as minimum cost flows, matching and the traveling salesman problem, as well as, several complex network topics, not directly related to routing, such as network design and network reliability.

An examination of the chapters in this volume reveals network routing to be an area of particular dynamism. The majority of the material in several of the chapters was developed over the past ten years. The intellectual advances represented by the recent work in this area, the ability of the models studied to solve practical problems and advances in computing technology indicate that this area can have a tremendous impact on research and practice in the coming years. Our hope is that this volume will help network routing achieve its full potential.

Michael Ball
Tom Magnanti
Clyde Monma
George Nemhauser

 Complete chapters on ScienceDirect

[Description and order information]

Important links:

• Member Order Form
  
• Proposals for further Handbook Volumes
  

Related Websites:

• Decision Sciences Publications
• Handbooks in Information Systems
• Handbooks in Economics
• Handbooks in Finance

<< back