Lagrangian relaxation approach for capacitated p-center problem with backup center and budget constraint

The p-center problem involves determination oflocations of p facilities while minimizing themaximum distance between demand points andfacilities. The main application areas of p-centerproblem are emergency service locations such as fireand police stations, hospitals and ambulanceservices. This paper deals with a generalized versionof the capacitated p-center problem. The model takesinto account the possibility that a center might suffera disruption and assumes that every site will becovered by its closest available center. We presentthe mathematical model and use lagrangianrelaxation for obtaining the suitable lower bound.Also, the CPLEX solver and Lagrangian relaxationmethod used to solve the model and highperformance of the Lagrangian relaxation method isshown in numerical example.

Keywords:

P-center problem , capacitated p-center problem , Lagrangian relaxation