Solution of the multisource weber and conditional weber problems by d.-c. programming

被引:34
作者
Chen, PC
Hansen, P
Jaumard, B
Tuy, H
机构
[1] GERAD, Montreal, PQ, Canada
[2] Ecole Hautes Etud Commerciales, Montreal, PQ, Canada
[3] Math Inst, Hanoi, Vietnam
关键词
D O I
10.1287/opre.46.4.548
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
D.-c. programming is a recent technique of global optimization that allows the solution of problems whose objective function and constraints can be expressed as differences of convex (i.e., d.-c.) functions. Many such problems arise in continuous location theory. The problem first considered is to locate a known number of source facilities to minimize the sum of weighted Euclidean distances between a user's fixed location and the source facility closest to the location of each user. We also apply d.-c. programming to the solution of the conditional Weber problem, an extension of the multisource Weber Problem, in which some facilities are assumed to be already established. In addition, we consider a generalization of Weber's problem, the facility location problem with limited distances, where the effective service distance becomes a constant when the actual distance attains a given value. Computational results are reported for problems with up to 10,000 users and two new facilities, 50 users and three new facilities, 1,000 users, 20 existing facilities and one new facility or 200 users, 10 existing and two new facilities.
引用
收藏
页码:548 / 562
页数:15
相关论文
共 71 条
[1]  
Aho A.V., 1974, The Design and Analysis of Computer Algorithms
[2]   A PIVOTING ALGORITHM FOR CONVEX HULLS AND VERTEX ENUMERATION OF ARRANGEMENTS AND POLYHEDRA [J].
AVIS, D ;
FUKUDA, K .
DISCRETE & COMPUTATIONAL GEOMETRY, 1992, 8 (03) :295-313
[3]  
Avriel M., 2003, NONLINEAR PROGRAMMIN
[4]  
BAXTER J, 1981, J OPER RES SOC, V32, P815, DOI 10.1057/jors.1981.159
[5]   AN OVERVIEW OF REPRESENTATIVE PROBLEMS IN LOCATION RESEARCH [J].
BRANDEAU, ML ;
CHIU, SS .
MANAGEMENT SCIENCE, 1989, 35 (06) :645-674
[6]   A STABLE ALGORITHM FOR SOLVING THE MULTIFACILITY LOCATION PROBLEM INVOLVING EUCLIDEAN DISTANCES [J].
CALAMAI, PH ;
CONN, AR .
SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1980, 1 (04) :512-526
[7]   NONLINEAR MINIMAX OPTIMIZATION AS A SEQUENCE OF LEAST PTH OPTIMIZATION WITH FINITE VALUES OF P [J].
CHARALAMBOUS, C ;
BANDLER, JW .
INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE, 1976, 7 (04) :377-391
[8]   ONLINE AND OFF-LINE VERTEX ENUMERATION BY ADJACENCY LISTS [J].
CHEN, PC ;
HANSEN, P ;
JAUMARD, B .
OPERATIONS RESEARCH LETTERS, 1991, 10 (07) :403-409
[9]   WEBER PROBLEM WITH ATTRACTION AND REPULSION [J].
CHEN, PC ;
HANSEN, P ;
JAUMARD, B ;
TUY, H .
JOURNAL OF REGIONAL SCIENCE, 1992, 32 (04) :467-486
[10]  
CHEN PC, 1992, 1092 RUTG U