An Improved Algorithm for Fixed-Hub Single Allocation Problems

作     者：Dong-Dong Ge Zi-Zhuo Wang Lai Wei Jia-Wei Zhang 

作者机构：School of Information Management and EngineeringShanghai University of Finance and EconomicsShanghai 200433China Department of Industrial and Systems EngineeringUniversity of MinnesotaMinneapolisMN 55455USA Stephen M.Ross School of BusinessUniversity of MichiganAnn ArborMI 48109USA Leonard N.Stern School of BusinessNew York UniversityNew YorkNY 10012USA 

出 版 物：《Journal of the Operations Research Society of China》 (中国运筹学会会刊（英文）)

年 卷 期：2017年第5卷第3期

页      面：319-332页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：the National Natural Science Foundation of China(No.11471205) 

主　　题：Hub location Network design Linear programming Worst-case analysis 

摘      要：This paper discusses the fixed-hub single allocation problem(FHSAP).In this problem,a network consists of hub nodes and terminal *** are fixed and fully connected;each terminal node is assigned to a single hub which routes all its *** goal is to minimize the cost of routing the traffic in the *** this paper,we propose a new linear programming(LP)relaxation for this problem by incorporating a set of validity constraints into the classical formulations by Ernst and Krishnamoorthy(Locat Sci 4:139–154,Ann Op Res 86:141–159).A geometric rounding algorithm is then used to obtain an integral solution from the fractional *** show that by incorporating the validity constraints,the strengthened LP often provides much tighter upper bounds than the previous methods with a little more computational effort and the solution obtained often has a much smaller gap with the optimal *** also formulate a robust version of the FHSAP and show that it can guard against data uncertainty with little costs.