Distance Constrained Facility Location Problem

被引：0

作者：

Weng, Kerui ^{[1
]}

机构：

[1] China Univ Geosci, Sch Econ & Management, Wuhan 430074, Peoples R China

来源：

2009 IITA INTERNATIONAL CONFERENCE ON SERVICES SCIENCE, MANAGEMENT AND ENGINEERING, PROCEEDINGS | 2009年

关键词：

facility location; service distance; approximation algorithm; hub location; APPROXIMATION ALGORITHMS;

D O I：

10.1109/SSME.2009.66

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The distance constrained facility location problem (DCFLP) seeks to the optimal way of locating facilities to minimize total costs (opening costs plus routing costs), while satisfying all the clients could be serviced by facilities within given distance. The paper first proposes a mixed 0-1 integer programming model for the DCFLP Then, we present a Inn+1 approximation algorithm to solve the problem. We also extend the model and algorithm to the distance constrained hub location problem which obtains a 21nn+1-approximation algorithm.

引用

页码：358 / 361

页数：4

共 15 条

[1]

AMBUHL C, 2006, P APPROX RANDOM, P3

[2] MEDI-CENTER LOCATION-PROBLEMS [J].

BERMAN, O ;

YANG, EK .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1991, 42 (04) :313-322

[3]

BYRKA J, 2006, OPER RES LETT

[4]

Byrka J, 2007, LECT NOTES COMPUT SC, V4627, P29

[5] Improved combinatorial algorithms for facility location problems [J].

Charikar, M ;

Guha, S .

SIAM JOURNAL ON COMPUTING, 2005, 34 (04) :803-824

[6]

Choi I.-C., 1993, Locat. Sci., V1, P235

[7] Improved approximation algorithms for the uncapacitated facility location problem [J].

Chudak, FA ;

Shmoys, DB .

SIAM JOURNAL ON COMPUTING, 2003, 33 (01) :1-25

[8]

Dai F, 2008, AD HOC SENS WIREL NE, V5, P1

[9] A threshold of in n for approximating set cover [J].

Feige, U .

JOURNAL OF THE ACM, 1998, 45 (04) :634-652

[10]

Huang Y., 2008, J COMB OPTIM, P1573

← 1 2 →