Abstract

In this talk we describe a location model where the value of individual facilities and groups of facilities can be based on a complex evaluation function. The model was originally developed to address an application for an organization that wished to deploy new facilities which competed, at least partially, with the organization's existing facilities and other new facilities. To formulate an instance of the model, a value is defined for each individual facility and a value decrement (interaction term) is defined for certain pairs of facilities. The overall value of a proposed set of facilities is the sum of the values for the individual facilities in the set minus the sum of the interaction terms for all pairs of facilities in the set. There is a natural integer programming formulation of this model which is closely related to the maximum weight node packing problem. The model can be viewed as an approximation for the problem of finding a maximum weight collection of facilities where the value of any set of facilities is given by a submodular set function. Viewed in this general form there are many potential applications. We discuss the use of this model within a decision support system developed for the US Postal Service. Specifically, a geographic information system was used to generate the data for the model and heuristics were developed and tested for solving the model. We also present some more recent results with an integer programming approach for solving it.