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

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.