Location covering models. History, applications and advancements (Q1755145)

Location covering problems are concerned with optimal choice of facilities to provide a certain level of service to given demand. Applications abound in widely differing areas such as surveillance, sensors and antennas, warning systems, emergency response, relief, security and communication provision, fair access to public services, nature reserve design, franchising, marketing, archeaology, hazardous facilities, etc., each calling for its own meaning of optimality, facility, service level, demand, etc. In particular, the notion of coverage itself, usually thought of as lying within a given distance bound, may in fact come in many more disguises. This book gives an overview of the many shapes such problems may take in practice and how these have been or can be formalised as mixed integer programming models (MIP), to be solved to optimality using off the shelf solvers. The following topics are covered throughout the chapters. After a semi-historical introductory chapter on general location questions and their application areas, the two major covering model paradigms are introduced: either complete coverage of demand at least cost (location set covering) or covering the most demand possible under limited budget (maximal covering). Their simple MIP formulations introduce the basic notation for data and variables, which the authors try to maintain throughout the book. Some attention goes to an alternative formulation as \(p\)-median problems. These models are then extended to incorporate additional complications such as multiple coverage provision, multiple service levels, multiple objectives, backup coverage, coordination between facilities and/or hierarchical facility systems. Coverage also often involves uncertainty and risk obliging planners to think probabilistically and consider the reliability of the system design to be optimised, which may be done in several ways. Situations where coverage is not desirable but rather detrimental call for new so-called anti-cover models, which turn out to be much harder to formulate and solve. Some minimal separation oriented models are developed. Coverage may also be not as clear-cut, and a chapter discusses how to model multiple coverage levels, either in discrete steps or continuously, e.g. gradually degrading with distance. Such models may be useful e.g. when considering equity in service provision. Facility location in the retail sector is primarily driven by competition against actors offering similar services. The aim is then to attract customer patronage, taking various customer behaviour patterns into account. This leads to so-called capture models which have a tendency to open many shops. Facility size should remain adapted to the customer base, so capacities must be taken into account. And franchisors are sensitive to cannibalisation effects, so don't want too many shops. In all these models, demand is assumed to be concentrated in a relatively small number of points. In some applications, e.g. in forestry or when demand is mobile, such as in telecommunication, this view is not tenable. Demand must then be considered continuously distributed leading to totally different nonlinear model formulations which turn out to be much harder to tackle.This remains a largely uncharted territory. Attempts to approximate by discrete demand models are prone to large errors. A new type of problems that is being investigated only recently is robust system design, optimised to still offer adequate service after one or several disruptions, such as facility or travel infrastructure failure, be it accidental or intentional. Termed interdiction, defense or fortification models, most of such problems are of Stackelberg type considering the disruption to be worst case, and cannot be formulated as MIP models, although their subproblems can. Solution therefore remains in most cases extremely complicated due to a lack of adequate general theory. Even heuristic approaches often behave rather poorly. The last type of covering problems discussed involve coverage of demand points provided not by point facilities but by network substructures, such as paths, tours, trees, etc. Formulation of such models is much more involved and has to adress each feature of the underlying network by one or more variables. Undesirable subtours may appear and must be eliminated by special constraints. In the final chapter, the authors describe what they consider as the grand challenges remaining in location covering. On the one hand, these center around the overwhelming amount of data that is being made available nowadays, in contrast to the difficulty of yesterday to obtain some data. This means that the level of detail at which the modelling is done has become a major solvability concern. And even after drastic data aggregation, which unfortunately already wipes out a lot of detail, one still remains with too many variables to be able to obtain exact optimal solutions, obliging to fall back to heuristics of rarely guaranteed performance. On the other hand, most spatially oriented datahandling and visualisation being done through a GIS interface, a better integration of such software with optimisation engines is called for. This book will primarily be of interest to the student and practitioner in spatial questions, mainly with a geography, economics or engineering background and having already some basic knowledge of mathematical optimisation. It will be invaluable as a common source of ideas around the modeling of all kinds problems of optimal covering type. The reader is amply provided with pointers to the modeling and application literature through the selected bibliography available at the end of each chapter. Mathematicians will probably be somewhat frustrated by the absence of more technical matters such as discussion of alternative optimal solutions, alternate formulations, valid inequalities, constraint generation, the curse of `big M' constraints, etc. Almost all questions regarding the actual solution process and how to possibly speed it up are left in the dark, relying with complete confidence in the solver's capacities. The theoretical and technical difficulties faced in presence of multiple objectives or multiple level optimisation are only vaguely hinted at. In contrast to the widespread literature, the authors made a laudable attempt to harmonise notations throughout their model formulations. Unfortunately, it seems that this aim led to a number of errors, most probably due to last minute changes.