Exact solution methods for uncapacitated location problems with convex transportation costs

被引:54
作者
Holmberg, K [1 ]
机构
[1] Linkoping Inst Technol, Dept Math, Div Optimizat, S-58183 Linkoping, Sweden
关键词
mathematical programming; location; dual ascent; branch-and-bound; benders decomposition;
D O I
10.1016/S0377-2217(98)00039-3
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
In this paper we study exact solution methods for uncapacitated facility location problems where the transportation costs are nonlinear and convex. An exact linearization of the costs is made, enabling the formulation of the problem as an extended, linear pure zero-one location model. A branch-and-bound method based on a dual ascent and adjustment procedure is developed, and compared to application of a modified Benders decomposition method. The specific application studied is the simple plant location problem (SPLP) with spatial interaction, which is a model suitable for location of public facilities. Previously approximate solution methods have been used for this problem, while we in this paper investigate exact solution methods. Computational results are presented. (C) 1999 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:127 / 140
页数:14
相关论文
共 15 条
[1]   LAGRANGEAN HEURISTICS FOR LOCATION-PROBLEMS [J].
BEASLEY, JE .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1993, 65 (03) :383-399
[2]  
CORNUEJOLS G, 1990, DISCRETE LOCATION TH, P120
[3]   DUAL-BASED PROCEDURE FOR UNCAPACITATED FACILITY LOCATION [J].
ERLENKOTTER, D .
OPERATIONS RESEARCH, 1978, 26 (06) :992-1009
[4]  
ERLENKOTTER D, 1985, SISTEMI URBANI, V1, P29
[5]  
Holmberg K., 1996, Location Science, V4, P83, DOI 10.1016/S0966-8349(96)00013-7
[6]  
Holmberg K., 1996, Optimization, V36, P139, DOI 10.1080/02331939608844172
[7]  
HOLMBERG K, 1995, LITHMATR199513 DEP M
[8]  
HOLMBERG K, 1990, P M 5 EURO WORK GROU
[9]  
HOLMBERG K, 1993, IN PRESS MATH PROGRA
[10]  
JACOBSEN SK, 1986, 1086 IMSOR DTH