Login | Register

Lagrangian Relaxation for q-Hub Arc Location Problems


Lagrangian Relaxation for q-Hub Arc Location Problems

Bazrafshan, Majid (2014) Lagrangian Relaxation for q-Hub Arc Location Problems. Masters thesis, Concordia University.

[thumbnail of BAZRAFSHAN_MASc_F2014.pdf]
Text (application/pdf)
BAZRAFSHAN_MASc_F2014.pdf - Accepted Version


The topic of this Master thesis is an in-depth research study on a specific type of network systems known as hub-and-spoke networks. In particular, we study q-Hub Arc Location Problems that consist, at a strategical level, of selecting q hub arcs and at most p hub nodes, and of the routing of commodities through the so called hub level network. We propose strong formulations to two variants of the problem, namely the q-hub arc location problem and the $q$-hub arc location problem with isolated hub nodes.
We present a Lagrangian relaxation that exploits the structure of these problems by decomposing them into |K|+2 independent easy-to-solve subproblems and develop Lagrangian heuristics that yield high quality feasible solutions to both models. We, further, provide some insights on the structure of the optimal solutions to both models and investigate the cost benefit of incomplete hub networks with and without isolated hub nodes. Finally, computational results on a set of benchmark instances with up to 100 nodes are reported to assess the performance of the proposed MIP formulations and of our algorithmic approach.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Mechanical and Industrial Engineering
Item Type:Thesis (Masters)
Authors:Bazrafshan, Majid
Institution:Concordia University
Degree Name:M.A. Sc.
Program:Industrial Engineering
Date:26 July 2014
Thesis Supervisor(s):Contreras, Ivan and Bulgak, Akif A.
ID Code:978791
Deposited On:04 Nov 2014 15:34
Last Modified:18 Jan 2018 17:47
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top