A Data-Driven Approach for the Maximum Capture Problem in Competitive Facility Location

Abstract

This thesis concerns the maximum capture problem in competitive facility location, which refers to the problem of selecting a set of locations to open new facilities in competitive market such that the captured demand of customers is maximized, assuming that each customer selects a facility among all available ones according to a probabilistic choice model. This is an important problem in location analysis and can have applications in many sectors, including, for instance, transportation planning, education, retail, healthcare services. In the context, a location planning decision consists of two main steps, namely, (i) training a probabilistic choice model to predict customers’ demand, (ii) and solving an optimization model to find an optimal decision (i.e. a set of locations to locate new facilities). For the first step, existing studies only use parametric discrete choice models, in which they assume that the information about the locations, i.e. the features/attributes of the locations that drive customers’ decisions, are all available to the analyst. This is however not the case in many contexts. In this thesis, we present a two-step approach to deal with the problem under limited data. More precisely, in the first step, we use only observations of how customers select facilities to train a generic ranking-based nonparametric choice model [14]. This model is known to be able to represent any choice model based on random utility maximization. In the second step, using the trained model, we show that an optimal decision can be found by solving a mixed-integer linear proiigramming model, which is scalable and flexible to deal with different types of business constraints. We test our approach using data sets generated from the multinomial logit (MNL) model. We show that the choice model can be trained in reasonable computing time using the column generation algorithm proposed by [8]. For the optimization step, we show that our approach is tractable solving instances of large number of locations.