Solving the uncapacitated multiple allocation hub location problem by means of a dual-ascent technique

Lázaro Cánovas (lcanovasum.es)
Sergio García (sgarciaum.es)
Alfredo Marín (amarinum.es)

Abstract: This problem deals with the uncapacitated multiple allocation hub location problem. The dual problem of a four-indexed formulation is considered and a heuristic method, based on a dual-ascent technique, is designed. This heuristic, which is reinforced with several specifical subroutines and does not require any external linear problem solver, is the core tool embedded in an exact branch-and-bound framework. Besides, the heuristic provides the branch-and-bound algorithm with good lower bounds for the nodes of the branching tree. The results of the computational experience (with the classical AP and CAB data sets) are included, showing the great effectiveness of this approach: instances of up to 120 nodes are solved.

Keywords: Location; Integer Programming; Hub location; Dual-ascent technique

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Combinatorial Optimization (Other )

Citation: European Journal of Operational Research, to appear.

Download:

Entry Submitted: 01/16/2004
Entry Accepted: 01/16/2004
Entry Last Modified: 05/10/2006

Modify/Update this entry