On covering location problems in networks with uncertain edge demands

Abstract

Location problems with covering objectives in networks are widely extended in the service sector (bus stops, bank branches, etc.) as well as in the location of emergency facilities (ambulances, automated external defibrillators, etc.). Almost all models proposed in the literature to deal with these situations assume that demand only occurs at the nodes of the network. However, in the location of emergency facilities or othersituations where the coverage areas are extremely distance-dependent this assumption is not realistic. Therefore, assuming that the demand is concentrated at nodes may lead to gaps in service levels that are not acceptable, rendering the solutions useless. Hence, our goal is to solve the single-facility location problem trying to cover the maximum demand on a network where the demand is distributed along the edges. A framework to deal with this kind of problems was presented in, the resolution method proposed assume that the demand is known exactly along the edges. Nevertheless, the demand for a specific service is often uncertain and usually varies from one day to another or even within a day. Hence, we have to find locations for those facilities that provide an adequate level of service even under changing and unknown service demands. For this reason, we will treat demands as being unknown. However, we are usually able to estimate the minimal and the maximal demand, so we assume thatdemand lie within a known range. In the face of this situation of total uncertainty in the demand, we propose to employ concepts from robust optimization, more concretely minimizing the maximal regret, a well-known criterion used by many researchers, seee.g. In this talk, we provide mathematical models considering that demand is uncertain and distributed along the edges of a network and that the service facilities can, essentially, be located anywhere along the network. Furthermore, we will propose polynomial time algorithms for finding the location that minimizes the maximal regret assuming that the demand lies within a known range and it is constant or linear on each edge.