A discrete equal-capacity p-Median problem

TR Number
Journal Title
Journal ISSN
Volume Title
Virginia Tech

This thesis deals with the analysis of a discrete equal-capacity p-median problem, where the costs are directly proportional to the shipping distance and the amount shipped. A mixed integer programming formulation of the unbalanced, but equal capacitated case is analyzed. First we develop a dynamic programming procedure for a p-median problem on a chain graph. In the second part we develop an algorithm to solve a p-median problem on a general network. First a heuristic algorithm is used to obtain an upper bound on the problem. Next, we obtain a lower bound on the problem by solving a Lagrangian relaxation of a reformulated problem via a conjugate subgradient optimization procedure. We obtain Benders’ cuts from the above procedures and proceed to a modified Benders’ approach to solve the continuous relaxation of the original problem. Finally a branch-and-bound algorithm that enumerates over the location decision variable space is used to obtain an integer optimal solution. Computational experience is provided to demonstrate the efficacy of the algorithm.