Optimization Online


The Uncapacitated Single Allocation p-Hub Median Problem with Stepwise Cost Function

Borzou Rostami (bo.rostami***at***gmail.com)
Christoph Buchheim (christoph.buchheim***at***math.tu-dortmund.de )

Abstract: In this paper, we address a new version of the Uncapacitated Single Allocation p-Hub Median Problem (USApHMP) in which transportation costs on each edge are given by piecewise constant cost functions. In the classical USApHMP, transportation costs are modelled as linear functions of the transport volume, where a fixed discount factor on hub-hub connections is introduced to simulate economies of scale. We argue that, in many cases, it is more realistic to replace the discount factor by decision variables representing the number of vehicles required on the given edge. Introducing integral variables for vehicle numbers makes the resulting optimization problem significantly harder, especially for the existing state-of-the-art MILP solvers. We propose an exact branch-and-bound algorithm where lower bounds are computed by considering a Lagrangian relaxation procedure. The Lagrangian relaxation exploits the problem structure and decomposes the problem into a set of smaller subproblems that can be solved efficiently. In particular, some of the latter can be reduced to continuous knapsack problems that can be solved quickly. We report exact solutions for instances with up to 50 nodes, i.e., significantly larger instances than those solvable by MILP solvers.

Keywords: Hub location, Lagrangian Relaxation, Branch and Bound

Category 1: Applications -- OR and Management Sciences

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 07/31/2015
Entry Accepted: 07/31/2015
Entry Last Modified: 10/19/2017

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 Optimization Society