A Variable Neighborhood Search Algorithm for Network Expansion Deferment in a Hub Network

A Variable Neighborhood Search Algorithm for Network Expansion Deferment in a Hub Network

Masoud Rabbani (School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran), Amir Farshbaf-Geranmayeh (School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran), Mohsen Hasani (School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran) and Mahyar Rezaei (School of Industrial EngineeringCollege of Engineering, University of Tehran, Tehran, Iran)
Copyright: © 2015 |Pages: 16
DOI: 10.4018/ijsds.2015010102

Abstract

The hub network expansion problem over planning horizon is addressed in this paper. In the extensive literature on hub network problem, it has widely been assumed that all P hub facilities must be located in current period and they do not take into account variation of demands, investment opportunities and net present cost. In this study, it is supposed that P hub facilities should have been located over planning horizon under variation of demands of every pair of nodes over time periods and also considering congestion effects at hub nodes. In this study, a mixed integer nonlinear programming formulation which minimizing the net present cost of planning horizon is presented. The Variable Neighborhood Search (VNS) algorithm is developed and successfully solved many instances of standard Childhood and Beyond (CAB) dataset and the results verify applicability of the proposed model and algorithm.
Article Preview

2. Literature Review

O’Kelly (1998) discussed about economies of scale that has known by discounted factor (α). He present a non-linear cost function in which the inter hub costs are a function of flows. Klincewicz (1998) provide a review on the architectures of hub location networks. The author divided such networks into tributary networks, which connect nodes to hubs, and a backbone network, which interconnects the hubs. The author also reviews and explains the various factors that must be taken to account in order to design these tributary and backbone networks like: cost, capacity, reliability, performance and demand pattern. Sasaki et al. (1999) defined a 1-stop multiple allocation P-hub median problem and proposed 2 solution methods, a branch-and-bound method and a greedy-type heuristic method. Note that the 1-stop model means that there is one hub in the path of each origin-destination pair. Sohn and Park (1999) propose a single allocation problem in which there is 3 fixed hub location and hubs are fully connected. They show that the single allocation problem is NP-hard (nondeterministic polynomial time) and propose a mixed integer formulation for solving it.

Ebery et al. (2000) proposed a multiple allocation hub location problems (MILP) formulation and solutions approaches for the capacitated multiple allocation hub location problems and choose postal delivery for case study. They take into account capacity restriction on the volume of traffic entering a hub node and also discounting factor for inter-hub links. Podnar et al. (2002) develop a model that has not hub facilities and use great discounting factor to motivate users to use few discounted links in order to have lower interconnected links between demand nodes. The authors define a threshold for making decision to use discount factor or not.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 9: 4 Issues (2018): 2 Released, 2 Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing