Flexible location planning taking reliability and congestion into account

  • contact:

    Stefan Nickel

  • funding:

    Deutscher Akademischer Austausch Dienst (DAAD)

Objective target

There are two shortcomings of many location models considered in the past. Firstly only two objectives, namely the median and center objective have been investigated. Secondly effects of uncertainty have not been taken into account, e.g., concerning the reliability of facilities or the consideration of congestion effects, limiting their use in practical applications. In the last few years there has been a considerable improvement in both directions, however, only very “isolated” and not in terms of an integrated approach.

Concerning the first shortcoming, in the last years the so called Ordered Median Function has been introduced, which allows modeling nearly all classical location objective functions. Moreover, equity type of objective functions taking a social focus or ideas from robust statistics can be formulated. One of the central questions when dealing with practical location decisions is the allocation of clients (customers) to a facility. A widely used concept when dealing with public facility location is the covering approach. Here, a customer or patient is called covered if he is within a given distance of one of the facilities. However, these models are usually too insensitive to customers on the borderline of the covering radius. For example, it is unlikely that a person goes to Hospital A while his neighbor is just outside the coverage radius and therefore visits Hospital B or has no health service at all. To overcome this problem, gradual cover location problems have been introduced, which allow a kind of soft transition between fully covered and not covered.

Another area where some isolated progress has been achieved is facility location problems with failure and/or congestion. Failure means that a facility has to be shut down (or is simply not working) and congestion refers to a working but occupied facility which is not able to provide service to a customer due to an excessive waiting queue. For example, during the SARS outbreak in Toronto in 2003, many hospitals in the Toronto area had to be quarantined for extended periods of time during which they were not able to provide most of the regular services. Moreover, at the same time, nearby hospitals not being quarantined were highly congested leading to long waiting times for patients.

All this extensions lead to more practical location models, but only in an integrated model and not as a collection of different models.

The following work plan will structure and guide our project:

  1. Identifying and modeling appropriate objective functions for typical practical problems: We are going to collect and classify practical location problems which need a flexible objective function and which also have some inherent uncertainty. A very good example here is the location of hospitals where the availability of service is uncertain and an objective function has to be sought for which takes several demographic, medical and social aspects into account.
  2. As a second step we have to extend existing covering models through the list of requirements identified in Step 1 and find appropriate mathematical formulations.
  3. In a third step we have to investigate the queuing models related to the practical examples in order to have a better insight into the congestion aspects and to make the models more applicable.
  4. Since already the basic location models at hand are NP-hard, standard solution approaches are likely to fail for problems of relevant size. Therefore we intent to use specific cutting plane and column generation approaches developed for location problems with flexible objective functions as well as for gradual covering models. Probably we are able to transfer some valid inequalities to the new integrated model formulations.
  5. Finally, we want to use the new integrated models and the corresponding solution methods to have a closer look at the often underestimated effect of co-location. Co-location is especially important in the above mentioned hospital example, where a crucial decision is if several services should be concentrated in one location or not.