A minisum location problem with regional demand considering farthest Euclidean distances. (3rd May 2016)

• Record Type: Journal Article
• Authors: Dinler, Derya; Tural, Mustafa Kemal
• Is Part Of: Optimization methods and software. Volume 31:Number 3(2016)
• Page Start: 446
• Page End: 470
• Publication Date: 2016-05-03
• Subjects: facility location problem -- demand region -- minisum problem -- second-order cone programming; 90B85 -- 90C11 -- 90C25; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2015.1121486
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : We consider a continuous multi-facility location-allocation problem that aims to minimize the sum of weighted farthest Euclidean distances between (closed convex) polygonal and/or circular demand regions, and facilities they are assigned to. We show that the single facility version of the problem has a straightforward second-order cone programming formulation and can therefore be efficiently solved to optimality. To solve large size instances, we adapt a multi-dimensional direct search descent algorithm to our problem which is not guaranteed to find the optimal solution. In a special case with circular and rectangular demand regions, this algorithm, if converges, finds the optimal solution. We also apply a simple subgradient method to the problem. Furthermore, we review the algorithms proposed for the problem in the literature and compare all these algorithms in terms of both solution quality and time. Finally, we consider the multi-facility version of the problem and model it as a mixed integer second-order cone programming problem. As this formulation is weak, we use the alternate location-allocation heuristic to solve large size instances.