Lagrangian heuristics for the location-allocation problem with stochastic demand and congestion

Location-allocation problems with stochastic demand and congestion (LAPSDC) arise in several planning contexts that require deciding the location of service facilities and their capacities; and the allocation of the stochastic demand of the user zones to the located service facilities. Examples include location of emergency medical clinics; preventive healthcare centers; refuse collection and disposal centers; stores and service centers; bank branches and automated banking machines; internet mirror sites; web service providers (servers); and distribution centers in supply chains. The problem seeks to simultaneously determine the location and capacities of service facilities, and allocate user’s stochastic demand to these facilities such that the total cost, which consists of the fixed cost of opening facilities with sufficient capacities, the access cost of users’ travel to facilities, as well as the congestion cost at the facilities as a result of user’s waiting due to stochastic demand rate and service times, is minimized. We present two approaches, namely Lagrangian relaxation and Lagrangian decomposition, to obtain lower bounds to the problem. While lower bounds are provided by the Lagrangian sub-problems, two heuristics are proposed that uses the solution of the sub-problems to construct an over-all feasible solution. Computational results to test the two approaches in terms of lower bound and optimality gap are presented