back start next


[start] [ 1 ] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51]


1

VIII

CONTENTS

Reference Notes Appendix 73

Ctiapter 4

Multi-Facility Location 77

4.1 The Rectangular Distance Model

4.2 The 2„ Distance Model 86

Exercises 91 Reference Notes Appendix 93

Ctiapter 5

Duality 95

5.1 The Single-Facility Euclidean Dual 95 The Dual Form with Linear Constraints The Multi-Facility Euclidean Dual 102

5.2 5.3 5.4 5.5

The Multi-Facility £„ Dual 104

Solution Methods for the Dual Form 107

Exercises 107

Reference Notes 109

Appendix 109

CONTENTS ix

Exercises 164 Reference Notes 169 Appendix 170

Chapter 8

Site Selecting Location-Allocation Models 173

8.1 Set-Covering Models for Site Selection 173

8.2 Single-stage, Single-Commodity Distribution System Design 186

8.3 Two-Stage, Multi-Commodity Distribution System Design 199

8.4 Demand Point Aggregation Issues Revisited 212 Exercises 214

Reference Notes 223 Appendix 224

Chapter 9

Floor Layout-The Quadratic Assignment Problem 227

9.1 Solving Problem (QAP) by a Branch-and-Bound Technique 231

9.2 Heuristic Procedures-CRAFT and HC63-66 242

9.3 The Hall m-Dimensional Quadratic Placement Algorithm 245 Exercises 251

Reference Notes 254

Chapter 6

Site Generation Under the Minimax Criterion 113

6.1 Euclidean Distances 117

6.2 Rectangular Distances 125

6.3 Addenda to Minimax Location 131 Exercises 135

Reference Notes 139 Appendix 140

Chapter 7

Site-Generating Location-Allocation Models 143

7.1 One-Dimensional Location-Allocation by Dynamic Programming 146

7.2 Solving the Two-Facility Euclidean Distance Problem 150

7.3 Solving Rectangular Distance Problems as m-Median Problems 152

7.4 Location-Allocation Heuristics 157

7.5 Location-Allocation with Continuous Existing Facilities 162

Chapter 10

Mathematical Models of Travel Distances 255

Empirical Distance Functions 256 Empirical Studies 258 The Weighted One-Infinity Norm 264 Empirical "Metrics," Convexity, and Optimal Location 266 Large Region Metrics 268 Modeling Vehicle Tour-Distances 271 Exercises 271 Reference Notes 273 Appendix 274

Bibliography 277 index 291

10.1 10.2 10.3 10.4 10.5 10.6



Preface

Soon after arriving (in Hong Kong) in 1978, the Citibank vice president moved to a new office building. To please his office staff he followed local custom and hired a geomancer called a fung shui man to analyze the offices omens.

The fung shui man toured the office ... (and then gave the vice president) the bad news. Great harm would befall him unless he installed an aquarium with six black fish and put his desk in an inconvenient spot near his office door. Despite his staffs concern, Mr. Russell ignored the warning.

Within days Mr. Russell developed a painful back problem .. . while in the hospital, his secretary installed the fish tank and rearranged the furniture. Today, Mr. Russell sits by the door, near the six fish. He says his health is better than ever before. Business has boomed.. . .

.Fung shui, which literally means wind and water, is based on a simple concept. It holds that if buildings, furniture, roads, and other man-made objects are placed in harmony with nature, they can bring good fortune. If not, they can wreak disaster.*

Certain facility location decisions will be dictated by overriding con-(iderations. The successful analyst recognizes situations wherein analysis on mathematical models is of little potential benefit (see Woolsey .986]). This book addresses the remaining cases. We have written this >k to provide a cohesive account of models and methods of analysis ftt might support decision making when:

a. answering the question of where is an integral part of a study;

*From The Wall Street Journal, December 19, 1983, p. 1.



PREFACE

b. the harmony sought with nature can be expressed through constraints; and

c. the good fortune sought can be adequately quantified through an objective function.

This task was undertaken in response to encouragement by Saul Gass, Editor of the Publications in Operations Research Series under the auspices of the Operations Research Society of America. Our mandate was to produce a state-of-the-art book in the field of facilities location. The hallmark of operations research is the use of models. This explains our concentration on problem formulation, model construction, and solution techniques for locating objects in a rational manner.

With their optimization viewpoint, location-allocation models are of interest to many disciplines including economics, engineering, geography, and management. However, from the seventeenth century to the middle of the twentieth century location models were developed mainly by rnath-emalicians. Moreover, until the 1960s, a decade which coincided with a great increase in the availability of digital computers, there did not exist a unified field of study called facilities location. The simultaneous introduction of computers along with an increased emphasis on using quantitative methods in most traditional fields has coincided with a veritable explosion of research and publications on the subject.

The field seems to have developed three main topic areas. The first and oldest category contains the continuous models which allow facility locations to be anywhere on the plane or subset of the plane. The second type has arisen out of modern practice and stems from the application of mathematical programming to solving location-allocation problems. These are known as discrete models; the possible locations are specified in advance and are finite in number. The third type of location models are those which utilize graph and network theory. This book is concerned only with the first two categories since we have emphasized these in our own research. The reader interested in the third type is referred to the books by Handler and Mirchandani (1979) and Larson and Odoni (1981). Finally, we omit discussion of evaluating multiple objective impacts since the book by Keeney (1980) nicely addresses this issue in the context of siting facilities.

The material in this book has its origins in graduate seminars on location-allocation organized in the late lQ60s by Robert Love at the University of Wisconsin at Madison. The growth of interest in the subject in the 1970s was reflected in the first U.S. conference on facilities location being held at St. Olaf College in the summer of 1977. This event was organized by Alan Goldman and was sponsored by the National Science Foundation and the American Mathematical Association. The first international conference was organized by Michael Goodchild and the late

% PREFACE

Jonathan Halpern in 1978 and was held at Banff, Alberta. A second conference was held at Copenhagen in the summer of 1981 and was organized by Soren Jacobsen, Jakob Krarup, Oli Madsen, and Peter Pru-zan. A third international conference, organized by a steering committee chaired by Jeffrey Osleeb and Samuel Ratick, was held in 1984 in Boston, and a fourth conference was held in Belgium in 1987; it was planned by a committee chaired by Francois Louveaux.

In order to completely understand the material in this book the reader should have studied differential and integral calculus, Unear and nonlinear programming, and should have a rudimentary knowledge of probability theory. We have attempted to augment the material where possible with practical examples, typically abstracted from actual studies. It is intended that the scope and coverage of material will be broad enough to provide material for a rigorous senior level course or graduate seminar. To this end exercises are appended to the chapters. Mathematical appendix notes contain material of interest to those readers who wish to consider derivations. The chapters have annotated bibliographies which cite recent articles, review articles, and classical articles. These connections to the research literature are intended to overcome some of the inherent bias toward our own research. Continued growth of the literature can be followed in such journals as European Journal of Operational Research, Geographical Analysis, HE Transactions, INFOR, International Abstracts in Operations Research, Journal of the Operational Research Society, Journal of Regional Science, Management Science, Naval Research Logistics, Operations Research, Regional Science and Urban Economics, and Transportation Science.

OUTLINE OF THE BOOK

Chapter 1 contains a preview of coming attractions and introduces the basic elements of a location model. Chapter 2 elaborates on the basic single-facility model using Euclidean, rectangular, and Sp distances. Chapter 3 indicates some of the variations on the basic model, that is, location on the sphere, linear facility location, and probabilistic and dynamic models. Chapter 4 considers the case of locating several new facilities when flows between facilities are known. Dual models are considered in Chapter 5. This chapter involves more analysis than most other chapters and the material is of specialized interest. Except for the preamble to Property 7.4 in Chapter 7, a knowledge of duality is not a prerequisite tor reading Chapters 6 through 10.

Chapter 6 introduces location under the minimax criterion, an alternative to the minisum objectives of previous models. The location-allocation problem is treated in Chapter 7. Here the assignments of flows to the new facilities are to be determined simultaneously with the loca-



[start] [ 1 ] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51]