A 2-phase algorithm for solving the single allocation p-hub center problem

doi:10.1016/j.cor.2008.07.011

Return

A 2-phase algorithm for solving the single allocation p-hub center problem

2009-12-01

PRE

Trisha Meyer *

Andreas Ernst

Mohan Krishnamoorthy

DOI：10.1016/j.cor.2008.07.011

Original

Original request for help

Save

Abstract

En 中文

The single allocation p-hub center problem is an NP-hard location-allocation problem which consists of locating hub facilities in a network and allocating non-hub nodes to hub nodes such that the maximum distance/cost between origin-destination pairs is minimized. In this paper we present an exact 2-phase algorithm where in the first phase we compute a set of potential optimal hub combinations using a shortest path based branch and bound. This is followed by an allocation phase using a reduced sized formulation which returns the optimal solution. In order to get a good upper bound for the branch and bound we developed a heuristic for the single allocation p-hub center problem based on an ant colony optimization approach. Numerical results on benchmark instances show that the new solution approach is superior over traditional MIP-solver like CPLEX. As a result we are able to provide new optimal solutions for larger problems than those reported previously in literature. We are able to solve problems consisting of up to 400 nodes in reasonable time. To the best of our knowledge these are the largest problems solved in the literature to date. (C) 2008 Elsevier Ltd. All rights reserved.

Keywords:

Hub location

Branch and bound

Ant colony optimization

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.