An Improved Algorithm for Fixed-Hub Single Allocation Problems

doi:10.1007/s40305-016-0143-1

CORC > 上海财经大学 > 上海财经大学

	An Improved Algorithm for Fixed-Hub Single Allocation Problems
	Ge, Dong-Dong 1; Wang, Zi-Zhuo 2; Wei, Lai 3; Zhang, Jia-Wei 4
刊名	JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA
	2017-09
卷号	5 期号:3 页码:319-332
关键词	Hub location Network design Linear programming Worst-case analysis
ISSN号	2194-668X
DOI	10.1007/s40305-016-0143-1
英文摘要	This paper discusses the fixed-hub single allocation problem (FHSAP). In this problem, a network consists of hub nodes and terminal nodes. Hubs are fixed and fully connected; each terminal node is assigned to a single hub which routes all its traffic. The goal is to minimize the cost of routing the traffic in the network. In 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 solution. We 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 solution. We also formulate a robust version of the FHSAP and show that it can guard against data uncertainty with little costs.
WOS研究方向	Operations Research & Management Science
语种	英语
出版者	SPRINGER HEIDELBERG
WOS记录号	WOS:000417401300002
内容类型	期刊论文
源URL	[http://10.2.47.112/handle/2XS4QKH4/895]
专题	上海财经大学
通讯作者	Ge, Dong-Dong
作者单位	1.Shanghai Univ Finance & Econ, Sch Informat Management & Engn, Shanghai 200433, Peoples R China; 2.Univ Minnesota, Dept Ind & Syst Engn, Minneapolis, MN 55455 USA; 3.Univ Michigan, Stephen M Ross Sch Business, Ann Arbor, MI 48109 USA; 4.NYU, Leonard N Stern Sch Business, New York, NY 10012 USA
推荐引用方式 GB/T 7714	Ge, Dong-Dong,Wang, Zi-Zhuo,Wei, Lai,et al. An Improved Algorithm for Fixed-Hub Single Allocation Problems[J]. JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA,2017,5(3):319-332.
APA	Ge, Dong-Dong,Wang, Zi-Zhuo,Wei, Lai,&Zhang, Jia-Wei.(2017).An Improved Algorithm for Fixed-Hub Single Allocation Problems.JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA,5(3),319-332.
MLA	Ge, Dong-Dong,et al."An Improved Algorithm for Fixed-Hub Single Allocation Problems".JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA 5.3(2017):319-332.