Location, location, location and location: Facility location incorporating demand uncertainty, logistic network design, product heterogeneity and competition.

摘要

Choosing locations to provide service under various constraints and objectives is an essential logistic activity in several contexts. Manufacturers choose locations for facilities and sales depots, government agencies choose locations for fire stations and other service installations, politicians choose ideological positions in the space of political agendas, etc. The field of location theory is devoted to the analysis and development of strategies for choosing locations to optimize certain objectives while meeting various requirements.; Traditional models of location involve a fixed set of constraints with fully specified data and a relatively simple set of location points. Examples of such models include the uncapacitated facility location problem and the k-center problem. Real-world location, however, often involves several other imponderables. This research addresses some of these extraneous issues in location analysis: (1) Demand uncertainty: Locations have to be chosen before the demand is fully revealed, although forecasts are available. (2) Logistic network design: Transshipment networks have to be constructed in addition to choosing locations. (3) Product heterogeneity: Demand for several different products has to be served, with economies of scale in manufacturing multiple commodities at the same location. (4) Competition: More than one agent is competing for the same demand, so locations have to be chosen strategically.; Barring the last chapter, all of our work is from the perspective of approximation algorithms. We provide polynomial time approximation algorithms for various location models in the contexts described above. For the competitive location model, we provide bounds for payoffs of the agents choosing the locations, and strategies for achieving those payoffs.