Canada Research Chair in Distribution Management | GERAD Seminar

Title: Exact Solution Methodologies for the Capacitated p-Center Problem

Speaker: ÇALIK, Hatice (HEC Montréal, Canada)

Abstract:
The capacitated p-center problem is an NP-Hard facility location problem that requires locating p facilities on a given network and assigning clients (nodes) to these facilities by respecting their service capacities so that the maximum of the distances between clients and the facilities they are assigned to is minimized. We study the problem in its most general form where the nodes of the given network may have non-identical demands and capacities. Existing studies in the capacitated p-center problem on general networks undertake the single allocation assumption in that the demand of each node has to be satisfied by a single facility. We study the problem with both this assumption and its relaxation that allows allocation of demand nodes to multiple facilities, i.e., multiple allocation. We propose new mathematical formulations and exact algorithms based on decomposition of our formulations. We are able to solve problems with up to 900 nodes while the largest problem solved in the current literature has 402 nodes.