A New Formulation of the Hamiltonian p Median Problem

Location-Routing problems involve locating a number of facilities among candidate sites and establishing delivery routes to a set of users in such a way that the total system cost is minimized. A special case of these problems is Hamiltonian p Median Problem (HpMP). In attempting to solve this problem, numerous mathematical formulations have been proposed. Most of them have in common that their descriptions as integer optimization problems are not polyhedral ones (ILP formulation). In this paper, an ILP formulation, based on the formulation of vehicle routing problem, is presented. The proposed formulation is simpler and more practicable than those have been proposed up to now