# Multi-period facility location problem with an uncertain number of servers (CD)

##### By: Vatsa, Amit Kumar.

Material type: BookPublisher: Ahmedabad Indian Institute of Management Ahmedabad 2016Description: 125 p.Subject(s): Tabu search | Capacitated problemsDDC classification: TH 2016-02 Summary: Abstract Facility location problems reported in the literature generally assume the problem parameter values (like cost, budget, etc.) to be known with complete certainty, even if they change over time (as in multi-period versions). However, in reality, there may be some uncertainty about the exact values of these parameters. Specifically, in the context of locating primary health centers (PHCs) in developing countries, there is generally a high level of uncertainty in the availability of servers (doctors) joining the facilities in different time periods. Furthermore, for transparency and efficient assignment of the doctors to PHCs, it is desirable to decide the facility opening sequence (assigning doctors to unmanned PHCs) at the start of the planning horizon. The extant facility location literature does not account for such an uncertainty regarding server availability. This uncertainty may lead to a facility opening sequence being considered, which may be far from an optimal ex-post decision. We work on the uncapacitated and capacitated versions of this problem where facilities can only meet demand which falls within a covering distance. Further, in place of a crisp covering distance, we generalize the problems by considering a gradual covering where coverage function is a non-increasing function of distance. We provide two formulations for each of these versions using minimax regret approach and show that one of the formulations is stronger. We provide Benders' decomposition based solution method, along with several refinements for each of the problem variants. For instances that CPLEX MIP solver could solve within a time limit of 20 hours, our proposed solution methods turns out to be of the order of 100 - 5000 times faster. To solve larger size problem instances, we also provide tabu search (TS) implementations that gives good solution for most of the test instances. Thesis Advisory Committee Prof. Diptesh Ghosh Prof. Sachin Jayaswal Prof. T. BandyopadhyayItem type | Current location | Collection | Call number | Status | Date due | Barcode |
---|---|---|---|---|---|---|

Thesis (FPM) | Vikram Sarabhai Library Audio Visual | Reference | TH 2016-02 (Browse shelf) | Not for Issue | CD002458 |

Contents:

Abstract 1

Acknowledgments 2

1 Introduction 9

1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Scope and structure of the proposed work . . . . . . . . . . . . . . . . . . . 14

2 Literature review 16

2.1 Uncapacitated maximal covering location problem with complete coverage . 18

2.2 Uncapacitated maximal covering location problem with gradual coverage . . 20

2.3 Capacitated maximal covering location problem with complete coverage . . . 21

2.4 Solution methods for facility location problems . . . . . . . . . . . . . . . . . 23

2.5 Gaps in the literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3 Problem formulation 26

3.1 Uncapacitated problem with complete coverage . . . . . . . . . . . . . . . . 26

3.1.1 First formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.1.2 Second formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.1.3 Comparison between two formulations . . . . . . . . . . . . . . . . . 33

3.2 Uncapacitated problem with gradual coverage . . . . . . . . . . . . . . . . . 37

3.3 Capacitated problems (compete or gradual coverage) . . . . . . . . . . . . . 39

4 Solution methodology 42

I Uncapacitated problems 50

5 Benders decomposition based solution method 51

5.1 Complete coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3

5.2 Gradual coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.3 Implementation of Benders decomposition cuts using callback . . . . . . . . 59

5.4 Computational study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.4.1 Data generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.4.2 Computational results . . . . . . . . . . . . . . . . . . . . . . . . . . 61

6 Tabu search based solution method 68

6.1 Neighborhood search based methods . . . . . . . . . . . . . . . . . . . . . . 68

6.2 Computational study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

6.2.1 Data generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

6.2.2 Computational results . . . . . . . . . . . . . . . . . . . . . . . . . . 71

II Capacitated problems 83

7 Benders decomposition based solution method 84

7.1 Benders decomposition for complete and gradual coverage . . . . . . . . . . 84

7.2 Computational study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

7.2.1 Data generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

7.2.2 Computational results . . . . . . . . . . . . . . . . . . . . . . . . . . 91

8 Tabu search based solution method 97

8.1 Neighborhood structures for TS . . . . . . . . . . . . . . . . . . . . . . . . . 98

8.2 Computational study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

8.2.1 Data generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

8.2.2 Computational results . . . . . . . . . . . . . . . . . . . . . . . . . . 102

9 Conclusions 109

9.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

9.2 Contributions and key _ndings . . . . . . . . . . . . . . . . . . . . . . . . . . 111

9.3 Limitations and future research . . . . . . . . . . . . . . . . . . . . . . . . . 112

Abstract

Facility location problems reported in the literature generally assume the problem parameter values (like cost, budget, etc.) to be known with complete certainty, even if they change over time (as in multi-period versions). However, in reality, there may be some uncertainty about the exact values of these parameters. Specifically, in the context of locating primary health centers (PHCs) in developing countries, there is generally a high level of uncertainty in the availability of servers (doctors) joining the facilities in different time periods. Furthermore, for transparency and efficient assignment of the doctors to PHCs, it is desirable to decide the facility opening sequence (assigning doctors to unmanned PHCs) at the start of the planning horizon.

The extant facility location literature does not account for such an uncertainty regarding server availability. This uncertainty may lead to a facility opening sequence being considered, which may be far from an optimal ex-post decision. We work on the uncapacitated and capacitated versions of this problem where facilities can only meet demand which falls within a covering distance. Further, in place of a crisp covering distance, we generalize the problems by considering a gradual covering where coverage function is a non-increasing function of distance. We provide two formulations for each of these versions using minimax regret approach and show that one of the formulations is stronger.

We provide Benders' decomposition based solution method, along with several refinements for each of the problem variants. For instances that CPLEX MIP solver could solve within a time limit of 20 hours, our proposed solution methods turns out to be of the order of 100 - 5000 times faster. To solve larger size problem instances, we also provide tabu search (TS) implementations that gives good solution for most of the test instances.

Thesis Advisory Committee

Prof. Diptesh Ghosh

Prof. Sachin Jayaswal

Prof. T. Bandyopadhyay

There are no comments for this item.