Location-allocation problems with multi-commodity flows: exact and approximate solution methods

Abstract

A multi-commodity and capacitated extension of the Multi-facility Location-Allocation Problem, namely the Multi-commodity Capacitated Multi-facilityWeber Problem (MCMWP) is considered, and exact and approximate solution methods are proposed. The MCMWP is new in the literature and aims to locate new facilities on the plane in order to meet the demand of customers for multiple types of products. The objective is to minimize total transportation costs, which are proportional to the distances measured with lr-norm for 1 · r < 1 between the facilities and customers, while satisfying the demand and capacity restrictions. The MCMWP has a non-convex objective function and it is difficult to solve. In the first part of this work, approximate solution methods are suggested. The first one of them is based on the Cooper's alternate location-allocation (ALA) heuristic and both contin- uous and discrete variants of the ALA heuristics are developed for the MCMWP. The second approximate solution method employs Discrete Approximation (DA) strategies. When the location of facilities are selected from a finite set of candidate sites it is possible to obtain approximate solutions of the MCMWP. The proposed DA strategies enable to obtain not only upper bounds but also lower bounds on the MCMWP. The third approximate solution method employs a Lagrangean Relaxation (LR) scheme. The MCMWP is relaxed such that the LR subproblems are variants of Multi-facility Weber Problems (MWP) with no capacity restrictions. The last approximate solution method produces confidence intervals for the optimal solution of the MCMWP using the Fisher-Tippett's theorem. In the second part of this work, exact solution methods are developed for both the Capacitated MWP (CMWP) and MCMWP. In particular, two different branch-and-bound (BB) algorithms, which partition allocation and location spaces, are suggested to exactly solve the CMWP and MCMWP. Lastly, a beam search heuristic using the location space based BB algorithm is implemented.