Variable neighbourhood search heuristics for the probabilistic multi-source Weber problem

• Published in: The Journal of the Operational Research Society 2011-10, Vol.62 (10), p.1813-1826
• Main Authors: Altınel, İ K, Aras, N, Özkısacık, K C
• Format: Article
• Language: English
• Subjects: Applied sciences; Approximation; Arithmetic mean; Business and Management; Coordinate systems; Customers; Datasets; Determinism; Distance functions; Exact sciences and technology; Expected values; facility location-allocation; General Paper; General Papers; Geodetic position; Heuristic; Heuristics; Location analysis; Logistics; Management; Marketing strategies; Mathematical programming; Operational research and scientific management; Operational research. Management science; Operations research; Operations Research/Decision Theory; probabilistic Weber problem; Random variables; Restaurants; Studies; variable neighbourhood search
• ISSN: 0160-5682; 1476-9360
• DOI: 10.1057/jors.2010.159

The Multi-source Weber Problem (MWP) is concerned with locating m facilities in the Euclidean plane, and allocating these facilities to n customers at minimum total cost. The deterministic version of the problem, which assumes that customer locations and demands are known with certainty, is a non-convex optimization problem and difficult to solve. In this work, we focus on a probabilistic extension and consider the situation where customer locations are randomly distributed according to a bivariate distribution. We first present a mathematical programming formulation for the probabilistic MWP called the PMWP. For its solution, we propose two heuristics based on variable neighbourhood search (VNS). Computational results obtained on a number of test instances show that the VNS heuristics improve the performance of a probabilistic alternate location-allocation heuristic referred to as PALA. In its original form, the applicability of the new heuristics depends on the existence of a closed-form expression for the expected distances between facilities and customers. Unfortunately, such an expression exists only for a few distance function and probability distribution combinations. We therefore use two approximation methods for the expected distances, which make the VNS heuristics applicable for any distance function and bivariate distribution of customer locations.