Operational Research and Networks E-Book

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 402

Veröffentlichungsjahr: 2013

Beschreibung

This book presents the principal concepts of operations research (OR), the tools for the planning support and the management of various types of networks. The term "network" is meant to include physical networks, for instance road and rail networks, as well as logical networks that are used in the planning of complex projects. In this case, the vertices of the network correspond to activities and the connections describe temporal relations.

Leseprobe

Table of Contents

Introduction

Chapter 1. Linear Programming

1.1. Fundamental concepts

1.2. Software

1.3. Indivisible units

1.4. Modeling with integer variables

1.5. Conclusion

1.6. Bibliography

Chapter 2. Graphs and Networks

2.1. The concept of a graph

2.2. Sub-structures and exploration

2.3. Edge- and vertex-connectivity

2.4. Directed graphs

2.5. Valued graphs and networks

2.6. Assignment and coloring

2.7. Flow in networks

2.8. Conclusion

2.9. Bibliography

Chapter 3. Classical Combinatorial Problems and Solution Techniques

3.1. Introduction

3.2. Classical optimization problems

3.3. Complexity

3.4. Solution of hard problems

3.5. Conclusion

3.5. Conclusion

Chapter 4. Project Scheduling

4.1. Presentation

4.2. Scheduling and graphs without cycles

4.3. Fundamental problem

4.4. Visualizations

4.5. Probabilistic PERT

4.6. Sequencing with disjunctive constraints

4.7. Sequencing with cumultative constraints: serial methods

4.8. Time-cost trade-off problem

4.9. Conclusion

4.10. Bibliography

Chapter 5. Operations Management in Transportation Networks

5.1. Introduction

5.2. Fundamental notions

5.3. A mechanism of decomposition

5.4. Diversity of the local restrictions

5.5. Applications in large transportation networks

5.6. What does the future look like?

5.7. Bibliography

Chapter 6. Pickup and Delivery Problems with Services on Nodes or Arcs of a Network

6.1. Introduction

6.2. Node routing problems

6.3. Arc routing problems

6.3. Arc routing problems

6.5. Bibliography

Chapter 7. Telecommunication Networks

7.1. Introduction

7.2. Optimal synthesis of backbone networks

7.3. Topology and dimensioning of the nominal network

7.4. Dimensioning of spare capacities

7.5. Conception of cellular networks

7.6. Antenna positioning and configuration

7.7. Frequency assignment

7.8. Conclusion

7.9. Bibliography

Chapter 8. Mission Planning for Observation Satellites

8.1. Introduction

8.2. Description of the problem of planning satellite shots.

8.3. Models and formulations of induced combinatorial problems

8.4. Algorithms for MS and MSO

8.5. Experiments and numerical results

8.6. Conclusion

8.7. Bibliography

List of Authors

Index

First published in France in 2002 by Hermes Science/Lavoisier entitled: “Recherche opérationnelle et réseaux: Méthodes d’analyse spatiale”

First published in Great Britain and the United States in 2008 by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUK

John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA

www.iste.co.uk

www.wiley.com

© ISTE Ltd 2008

© LAVOISIER, 2002

The rights of Gerd Finke to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Operations research and networks / edited by Gerd Finke.

p. cm.

Includes bibliographical references and index.

ISBN 978-1-84821-092-9 (alk. paper)

1. Network analysis (Planning) 2. Operations research. I. Finke, Gerd.

T57.85.O64 2008

658.4'032--dc22

2008030338

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN: 978-1-84821-092-9

Introduction1

This volume presents the principal operations research (OR) tools that help in the planning and management of all sorts of networks. The term “network” is to be understood in a very broad sense. In effect, this term also designates physical networks, such as road or railway networks, as well as logical networks, used for complex project planning for example. In this case, the network elements correspond to activities, and the interconnections describe temporal relations.

OR considers real problems in two phases: a modeling phase that corresponds to the development of a mathematical model is followed by a solution procedure, exact or approximate, and in general algorithmic. These two phases are closely connected and OR proposes collections of models, adapted to numerous applications, as well as the corresponding resolution techniques.

The models can be classified in two large categories, those based on an algebraic formulation and those founded on the concept of graphs. These two models are presented in Chapters 1 and 2 and the general solution approaches are in Chapter 3. Then, in Chapters 4 to 8, some chosen applications are detailed. They concern project management, collection and distribution networks, telecommunication networks and graph models for mission planning of observation satellites.

Chapter 1 presents the main ideas of linear programming. This model is based on basic notions of linear algebra. The goal is to optimize a linear function (maximize profit, minimize distance covered, minimize transportation cost, etc.) by satisfying certain conditions (constraints). These constraints are linear (equations or inequations) and model the use of finite capacity resources, distance limits, budget restrictions, etc.

The fundamental concepts of linear programming are described: the type of solution (basic solution), duality and the economic interpretation. However, the goal of this chapter is situated more at the level of modeling than developing theory. Software is easily accessible, mostly in standard form. The objective of this chapter is to describe the use of a type of software and to show how the results can be interpreted. Modeling by linear programming is very flexible and enables an efficient solution to the problems, thanks to the simplex algorithm. But there is an essential restriction: fractional value solutions must be accepted. Unfortunately, for many of the problems, discrete variables (of integer values) must be considered and they often take values 0 or 1 indicating a decision (a site, chosen or not, or a resource, used or not). For these integer programming problems, an efficient universal algorithm does not exist. The task of creating a “good” model becomes much more difficult and requires us to exploit the particular structure of the problem.

Graphs are extremely useful structures to describe and understand numerous problems. These impressive modeling tools are detailed in Chapter 2. The graphs are made up of vertices (depots, cities, clients) and of connections between these vertices (routes, cables). Often other information is given, for example the quantity of available merchandise in a vertex and the length or the cost of a connection (edge, arc) connecting two vertices. These graphs, called valued graphs, constitute what are called abstract networks. In this chapter, a large number of examples illustrate the richness of this model. The usual concepts are introduced – paths, trees and flows – with sometimes unexpected applications. Graph theory has created its own algorithmic solution. These procedures can be an alternative to linear programming with integer variables, or even in certain cases give the only possible access to an efficient solution.

Chapter 3 presents the spectrum of diverse solution techniques. Some elements of the complexity theory are given, distinguishing the easy problems, such as linear programming in fractional variables or minimal length paths in graphs, and difficult problems, such as integer linear programming or the traveling salesman problem. Solution techniques are presented, including exact methods (branch and bound, dynamic programming) and, in particular, approximate methods: heuristics and metaheuristics (simulated annealing, tabu method and genetic algorithms).

Chapter 4 addresses the management and scheduling of large projects and, in particular, describes the Program Evaluation and Review Technique (PERT). It is a quite general tool, applicable to complex projects, such as construction of an apartment building, a ship or a dam, as well as large agricultural projects. This method is based on a network of events whose arcs indicate the succession of the different work phases necessary to realize the project. Without giving an exhaustive list, some large spatial problems are described in the following chapters.

In Chapter 5, the management of large urban transportation networks, both air and rail, is considered. Real applications are numerous: school transportation, transport of the handicapped, assignment and determination of the hours of bus drivers and locomotive engineers and crew rotation for an airline. It is remarkable that for this multitude of applications a sole structure, described by paths that respect a time interval in a space-time network, is applicable. The number of possible paths, and thus the number of variables of choice in these models, can reach several million. Consequently, even the linear relaxations of the problem can no longer be solved directly by the simplex method. Other more elaborate procedures must be used; for example the method of column generation, the object of recent research.

Chapter 6 presents other aspects in transportation networks that are connected to the distribution and collection of goods to the clients. Two types of models emerge, depending on the position of the clients. If they are found on the vertices of the network (cities for example), the problem studied is a problem of vehicle tours, related to the traveling salesman problem. On the other hand, if the clients are situated along the roads, the problems lead to so-called Chinese postman problems.

In Chapter 7, large telecommunication networks are studied. Many actors intervene in these networks and the quality of service becomes dominant for the users. There are two large categories of telecommunication networks: fixed networks with cable connections and mobile networks where communications are made by radioelectric waves for clients who are moving in a certain territory. The methods are different for these two types of networks. A whole range of OR techniques is applied here: linear programming or algorithms in graphs, for example coloring for the frequency assignment in a mobile radio network.

Finally (Chapter 8), the last problem presented concerns mission planning for observation satellites. Satellite users demand images of terrestrial strips to be made while the satellite turns around the earth on its orbit. A uniform graph model is developed to describe a sequence of images without conflict and respecting all the constraints.

Thus, based on the two types of OR formulations, linear programming and graphs, numerous applications, especially in networks, have been described and modeled. By then calling upon OR solution techniques it was possible to obtain efficient algorithmic solution methods, exact or approximate, in order to help in the decision-making process.

1 Introduction written by Gerd FINKE.

Chapter 1

Linear Programming1

1.1. Fundamental concepts

This chapter concerns the problems whose objective is to optimize a function by respecting constraints. Linear programming, more precisely, studies the cases where the function to optimize (or objective function) and the constraints are expressed linearly. This model, which can seem rather specialized, is in fact very flexible. We will show in this chapter that it allows us to model a great many important applications.

Numerous studies describe linear programming techniques. We cite, not wanting to give a long list, some reference studies in French [CHA 96, MIN 83] and in English [BAZ 90, CHV 83, DAN 63, MUR 85, SAK 83, NEM 88].

We first describe an example that illustrates the allocation of resources: the company Biereco produces two varieties of beer, B1 and B2, from three ingredients: corn, hops and malt. These cereals are available in quantities of 80, 30 and 40 parts. Each barrel of beer B1 uses one part corn, one part hops and two parts malt, while each barrel of B2 must have two parts corn, one part hops and one part malt. A barrel of B1 is sold at 50 monetary units and a barrel of B2 is sold at 40 monetary units. The objective of the producer is to maximize the profit. Table 1.1 gives the data for this problem.

Table 1.1.Data for the Biereco example

We model this problem with the help of a linear program. The decision variables x1 and x2 represent the number of barrels of beer B1 and B2 to be produced. In order for the solution obtained to be realistic, these variables must be non-negative. The limits on the quantity of available resources and the composition of the beers involve the following constraints:

The linearity of the objective function and the constraints is natural for this type of problem. In effect, the profits and the consumption of the resources are additives.

Figure 1.1 describes the set of feasible solutions R: the elements of R satisfy all the constraints. The constraints are inequations. They are thus represented by halfplanes (in the figure, the arrows indicate which half-plane is to be considered). By definition, is the intersection of these half-planes.