Optimization Online


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

Lázaro Cánovas (lcanovas***at***um.es)
Sergio García (sgarcia***at***um.es)
Alfredo Marín (amarin***at***um.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.


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society