Optimization Online


Solving Classical and New Single Allocation Hub Location Problems on Euclidean Data

J. Fabian Meier(meier***at***itl.tu-dortmund.de)
Uwe Clausen(clausen***at***itl.tu-dortmund.de)

Abstract: Transport networks with hub structure organise the exchange of shipments between many sources and sinks. All sources and sinks are connected to a small number of hubs which serve as transhipment points, so that only few, strongly consolidated transport relations exist. While hubs and detours lead to additional costs, the savings from bundling shipments, i.e. economies of scale, usually outweigh these costs. Typical applications for hub networks are in cargo, air freight, postal and parcel transport services. In this paper we consider three classical and two recent formulations of single allocation hub location problems, i.e. hub location problems in which every source and sink is connected to exactly one hub. Solving larger instances of these problems to optimality is difficult because the inherent quadratic structure of the problem has to be linearised: This leads to a sharp rise in variable numbers. Our new approach relies on the fact that many instances - including the famous CAB and AP data sets - have a Euclidean structure: The distances between the possible hub locations are Euclidean distances in the plane. This enables us to construct a new linearisation together with a row generation procedure which solves instances up to 200 nodes to optimality.

Keywords: Hub Location; Quadratic Programming; Row generation

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

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

Category 3: Nonlinear Optimization (Quadratic Programming )

Citation: Institute of Transport Logistics, TU Dortmund March 2015

Download: [PDF]

Entry Submitted: 03/12/2015
Entry Accepted: 03/12/2015
Entry Last Modified: 03/12/2015

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