For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Linear Relaxation for Hub Network Design Problems
Hiro-o SAITO Shiro MATUURA Tomomi MATSUI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2002/05/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
linear programming, hub location problem, Hitchcock transportation problem, dual transportation polyhedra,
Full Text: PDF(215.4KB)>>
In this paper, we consider a network design problem with hub-and-spoke structure. We propose a relaxation technique for the problem where the location of hub nodes is given and decides the allocation of non-hub nodes to one of the hub nodes. We linearize the non-convex quadratic objective function of the original problem, introducing Hitchcock transportation problems defined for each pair of non-hub nodes. We provide two linear relaxation problems, one based on the Hitchcock transportation problems and the other on the dual Hitchcock transportation problems. We show the tightness of the lower bounds obtained by our formulations by computational experiences.