A discrete equal-capacity p-Median problem

TR Number

Date

1992

Journal Title

Journal ISSN

Volume Title

Publisher

Virginia Tech

Abstract

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.

Description

Keywords

Citation

Collections