The Multi-commodity Capacitated Multi-facility Weber Problem: Heuristics and Confidence Intervals

The Capacitated Multi-facility Weber Problem is concerned with locating I capacitated facilities in the plane to satisfy the demand of J customers with the minimum total transportation cost of a single commodity. This is a non-convex optimization problem and difficult to solve. In this work, we focus on a multi-commodity extension and consider the situation where K distinct commodities are shipped to the customers subject to capacity and demand constraints. Customer locations, demands and capacities for each commodity are known a priori. The transportation costs, which are proportional to the distance between customers and facilities, depend on the commodity type. We first present a mathematical programming formulation of the problem. Then we propose an alternate location-allocation heuristic and a discrete approximation method which are used to statistically estimate confidence intervals on the optimal objective values. Computational experiments on randomly generated test instances are also included.