×

Network and discrete location. Models, algorithms and applications. Incl. disk. (English) Zbl 0870.90076

Wiley-Interscience Series in Discrete Mathematics and Optimization. New York, NY: Wiley. xvi, 498 p. (1995).
Within mathematical optimization, location theory distinguishes itself among others for two reasons: Its models can be used to tackle a wealth of applications and it combines many other areas of optimization such that it is an ideal subject to teach mathematical optimization and operations research. One usually separates location theory into three parts: continuous location, network location and discrete location, the latter two being represented in the title of this book.
The book consists of three parts, an introduction to the location problem and necessary mathematical background (Chapters 1-3), the core of network and discrete location (Chapters 4-7), and some extensions and context discussion (Chapters 8 and 9). The appendices – which could be considered a fourth part – contains guides for the software package SITATION which is distributed along with the book.
Chapter 1 introduces location problems and describes various versions of it. Chapter 2 very briefly introduces linear programming with specific emphasis on duality and its application in solving transportation, shortest path and network flow problems. Chapter 3 covers the basic facts of complexity theory. The goal of this part is to provide the necessary notions and tools for location theory. As a general introduction into the respective subjects it seems not useful (and is obviously not intended by the author to serve as such).
The second part starts in Chapter 4 with a discussion of covering problems. Integer programming problems formulations for min (cardinality) and max (weighted) covering problems are given. Basic heuristics and a branch-and-bound procedure are explained. Chapter 5 deals with center problems, i.e. location problems where the maximal distance between new and existing facilities is minimized and its interrelation to min and max covering problems. Algorithms for center problems on trees and the unweighted center problem on general graphs are considered. Chanter 6 duplicates these topics for median problems, i.e. location problems where the sum of the distance between new and existing facilities is minimized. In both chapters I would have liked to see a more detailed discussion of the interrelation between vertex and absolute problems. Chapter 7 deals with a classic of the integer programming literature – the fixed charge location problem. Heuristics and Lagrangean techniques are introduced.
Chapter 8 discusses various extensions of the models introduced in the previous four chapters, including multicriteria problems, interacting new facilities, location/routing problems, hub location and undesirable facilities. Chapter 9 discusses the strategic importance of location processes embedded in a 4-stage planning process.
Daskin’s book is an introductory, stand-alone textbook which can be used by practitioners and students to get into the subjects without any further help. It is not a mathematics book – and was obviously designed this way by the author. Mathematicians will look in vain for a text following the definition-result-proof pattern. Instead it contains many helpful examples and comes with a software package which allows the reader to get some hand-on experiences.

MSC:

90B80 Discrete location and assignment
90C10 Integer programming
PDFBibTeX XMLCite