Minmax Regret Maximal Covering on Networks with Edge Demands

Abstract

In this work, we focus our research on covering location problems. Almost all models analyzed in the literature assume that demand only occurs at the nodes of the network. However, there are some applications where this assumption is not realistic; e.g. the location of emergency facilities where the coverage areas are extremely distance-dependent. Thus, assuming that the demand is concentrated at nodes may lead to gaps inservice levels that are not acceptable in some situations, 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. In the literature, see [1], some models are proposed to solve the deterministic version of this problem. Nevertheless, one of the big challenges is that the demand for a specific service is often not known exactly, but only approximately. 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 usually have a good idea of what the minimal or maximal demand will be, so that we can at least assume demand to 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, see e.g. Our first aim is to 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.