Continuous Facility Location with Backbone Network Costs

John Gunnar Carlsson () and Fan Jia ()
Additional contact information
John Gunnar Carlsson: Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455
Fan Jia: Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455

Transportation Science, 2015, vol. 49, issue 3, 433-451

Abstract: We consider a continuous facility location problem in which our objective is to minimize the weighted sum of three costs: (1) fixed costs from installing the facilities, (2) backbone network costs incurred from connecting the facilities to each other, and (3) transportation costs incurred from providing services from the facilities to the service region. We first analyze the limiting behavior of this model and derive the two asymptotically optimal configurations of facilities: one of these configurations is the well studied honeycomb heuristic , and the other is an Archimedean spiral. We then give a fast constant-factor approximation algorithm for finding the placement of a set of facilities in any convex polygon that minimizes the sum of the three aforementioned costs.

Keywords: continuous facility location; backbone network design (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2013.0511 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:49:y:2015:i:3:p:433-451

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().