EXACT SOLUTION METHODOLOGIES FOR THE P-CENTER PROBLEM UNDER SINGLE AND MULTIPLE ALLOCATION STRATEGIES
Not available
Résumé
The p-center problem is a relatively well known facility location problem that
involves locating p identical facilities on a network to minimize the maximum
distance between demand nodes and their closest facilities. The focus of the
problem is on the minimization of the worst case service time. This sort of
objective is more meaningful than total cost objectives for problems with a time
sensitive service structure. A majority of applications arises in emergency service
locations such as determining optimal locations of ambulances, fire stations and
police stations where the human life is at stake. There is also an increased
interest in p-center location and related location covering problems in the contexts
of terror fighting, natural disasters and human-caused disasters. The p-center
problem is NP-hard even if the network is planar with unit vertex weights, unit
edge lengths and with the maximum vertex degree of 3. If the locations of the
facilities are restricted to the vertices of the network, the problem is called the
vertex restricted p-center problem; if the facilities can be placed anywhere on the
network, it is called the absolute p-center problem. The p-center problem with
capacity restrictions on the facilities is referred to as the capacitated p-center
problem and in this problem, the demand nodes can be assigned to facilities with
single or multiple allocation strategies. In this thesis, the capacitated p-center
problem under the multiple allocation strategy is studied for the first time in the
literature.
The main focus of this thesis is a modelling and algorithmic perspective in
the exact solution of absolute, vertex restricted and capacitated p-center problems.
The existing literature is enhanced by the development of mathematical
formulations that can solve typical dimensions through the use of off the-shelf
commercial solvers. By using the structural properties of the proposed formulations,
exact algorithms are developed. In order to increase the effciency of the
proposed formulations and algorithms in solving higher dimensional problems,
new lower and upper bounds are provided and these bounds are utilized during
the experimental studies. The dimensions of problems solved in this thesis are
the highest reported in the literature.
Not available
Domaines
Recherche opérationnelle [math.OC]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...