Continuous Facility Location with Backbone Network Costs

Transportation Science - Tập 49 Số 3 - Trang 433-451 - 2015
John Gunnar Carlsson1, Jiadong Fan1
1Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455#TAB#

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

10.1016/j.tre.2003.08.005

10.1017/S0305004100034095

10.1017/CBO9780511762109

10.1007/978-1-4612-5355-6_19

10.1287/opre.44.2.286

Cachon GP (2014) Retail store density and the cost of greenhouse gas emissions. Management Sci. 60(8):1907–1925.

Campbell JF, 1990, J. Bus. Logist., 11, 159

10.1287/trsc.27.4.330

10.1109/HICSS.2011.335

10.1287/ijoc.2013.0564

10.1016/0191-2615(84)90027-4

10.1002/net.3230160202

10.1007/BF02060476

10.1112/S0025579300000784

10.1080/05695557908974448

Grünbaum B, 2012, Tilings and Patterns

10.1287/moor.10.4.527

10.1007/BF01874389

10.1016/0191-2615(95)00035-6

10.1007/978-3-642-22012-8_5

10.1287/trsc.18.1.1

Melkote S, 2001, Transportation Res. Part A, 35, 515

10.1016/j.tre.2003.08.006

10.1016/j.ejor.2006.04.004

10.1137/0125037

10.1016/0191-2615(86)90008-1

Pinedo M, 2008, Scheduling: Theory, Algorithms, and Systems

10.1214/aoap/1177004902

Rodrigue JP, 2009, The Geography of Transport Systems

10.1111/j.1538-4632.1978.tb00666.x

10.1214/aop/1176994411

10.1007/BF01874390

Thông tin
Thông tin xuất bản

Transportation Science

Tập 49 Số 3

433-451

Thông tin tác giả