상세정보

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 (for instance 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 do not, 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 are often very large with hundreds or thousands of constraints and variables. A companion volume in the "Handbook" series, entitled "Network Models", treats basic network models such as minimum cost flows, matching and the travelling salesman problem, as well as, several complex network topics, not directly related to routing, such as network design and network reliability.

정보제공 :

CONTENTS

Preface = ⅴ

CHAPTER 1 Vehicle Routing / M. Fisher = 1

 1. Introduction = 1

 2. Generation one-simple heuristics = 7

 3. Generation two-mathmatical programming based heuristics = 10

 4. Generation three-what are new frontiers? = 15

 References = 30

CHAPTER 2 Time Constrained Routing and Scheduling / J. Desrosiers ; Y. Dumas ; M. M. Solomon ; F. Soumis = 35

 1. Introduction = 35

 2. Fixed schedule problems = 37

 3. The traveling salesman problem with time windows = 54

 4. Constrained shortest path problem = 70

 5. the vehicle routing problem with time windows = 80

 6. Pick-up and delivery problems with time windows = 102

 7. A unified framework for fleet and crew scheduling problems = 116

 8. Conclusions and perspectives = 127

 References = 130

CHAPTER 3 Stochastic and Dynamic Networks and Routing / W. B. Powell ; P. Jaillet ; A. Odoni = 141

 1. Introduction = 141

 2. A Priori (two-stage) stochastic models = 146

 3. Modelling issues for dynamic problems = 181

 4. Dynamic models in transportation and logistics = 191

 5. Algorithms and formulations for deterministic dynamic networks = 221

 6. Infinite horizon network models = 234

 7. Stochastic programming for networks = 246

 8. Stochastic programming models in networks with routing = 256

 9. Approximations for networks with random arc capacities = 263

 10. Evaluating dynamic models = 279

 References = 371

CHAPTER 4 Analysis of Vehicle Routing and Inventory-Routing Problems / A. Federgruen ; D. Simchi-Levi = 297

 1. Introduction = 297

 2. The capacitated vehicle routing problem (CVRP) with split demands = 299

 3. The CVRP with unequal demands = 320

 4. Invertory-routing models = 336

 5. The multi-depot CVRP = 351

 6. Generalizations and extensions = 364

 References = 371

CHAPTER 5 Arc Routing Methods and Applications / A. A. Assad ; B. L. Golden = 375

 1. Introduction = 375

 2. The classical postman problems = 385

 3. The rural postman problem = 392

 4. The capacitated arc routing problem = 400

 5. Algorithms for capacitated arc routing problems = 411

 6. Variants of postman problems = 420

 7. Arc routing for sanitation services = 428

 8. Postal delivery routing problems = 440

 9. Routing for meter reading and snow control = 456

 10. Applications in manufacturing and other areas = 465

 11. Conclusions = 475

 References = 476

CHAPTER 6 Network Equilibrium Models and Algorithms / M. Florian ; D. Hearn = 485

 1. introduction = 485

 2. Equivalent problems - existence and uniqueness of solutions = 490

 3. Some optimization reformulations = 495

 4. Algorithms for the symmetric NEM = 502

 5. Solving the asymmetric NEM = 514

 6. Stochastic network equilibrium = 521

 7. Other network equilibrium models = 524

 8. Reference notes = 534

 References = 542

CHAPTER 7 Location on Networks / M. Labb$$e'$$ ; D. Peeters ; J. -F. Thisse = 551

 1. Introduction = 551

 2. The general framework and its properties = 553

 3. The median (minisum) problems = 556

 4. The center (minimax) problems = 576

 5. Economic models of location = 588

 6. Discrete location problems = 600

 7. Conclusion = 616

 References = 617

CHAPTER 8 VLSI Network Design / R. H. M$$\ddot O$$hring ; D. Wagner ; F. Wagner = 625

 Introduction = 625

 Part Ⅰ. The General Layout Problem = 626

  1. Layout by graph partitioning = 627

  2. The divide-and-conquer layout algorithm = 629

  3. Bifurcatiors and separators = 632

  4. Bipartitioning = 637

 Part Ⅱ. Routing = 640

  5. From planar graphs to switchboxes = 641

  6. Channel routing in the knock-knee mode = 647

  7. Layer assignment = 654

  8. Manhattan routing = 664

  9. Via Minimization = 669

  10. Single layer routing = 672

 Part Ⅲ. Linear Layout Methods = 674

  11. The VLSI background = 676

  12. Graph-theoretic formulations and related problems = 682

  13. Complexity results = 696

  14. Algorithms = 702

 References = 705

CHAPTER 9 Network Models in Economics / W. W. Sharkey = 713

 1. Cost allocation on networks = 715

 2. Matching models in economics = 737

 3. Optimal pricing and allocation of waiting time in stochastic service systems = 751

 4. Concluding comments = 760

 References = 761

Biographical Information = 767

Subject Index = 773

Contents of Previous Volumes = 781