Comprehensive study of stochastic hub location problems with profit maximisation: models and exact algorithms

Abstract

Motivated by the strategic importance of revenue management in logistics and transportation systems particularly in uncertain environments, this thesis focuses on one of the most popular locational problems, hub-and-spoke network design. The thesis presents a comprehensive study to design such network from profit maximisation point of view. The aim of the research is to explore new approaches and methodologies that help simulating hub-and-spoke systems more realistically. This is done by formulating the problem using practical features like elastic uncertain demand and/or uncertain flow, pricing decision, and flow-dependent cost and flow-dependent revenue. The thesis will add to the body of the literature by introducing new hub location problems, developing formulations for these problems, exploring structure of the formulations to design efficient exact solution techniques, and extracting useful and relevant managerial insights to help practitioners making informed decisions.

The thesis begins with the development of new formulations for both capacitated and uncapacitated single allocation hub location problem with elastic and uncertain demand. In this model, interaction between demand and price is captured by a linear function and it is controlled by a parameter named as demand-price sensitivity factor. The problem is modelled as a two-stage stochastic program in which strategic decision of locating hubs are taken in the first stage and rest of the decisions including allocation of demand, routing and pricing are made in the second stage after realisation of demand. The objective of the model is to find optimal number and location of hub facilities, allocation of demand to these facilities, routing the flow throughout the network and finding the optimal price to serve demand between each origin-destination pair in such a way to maximise total profit.

Two efficient exact algorithms namely, an enhanced Lagrangian relaxation and a Benders decomposition algorithm, have been proposed to solve large instances of the problem. Performance of the two algorithms have been evaluated and favourably compared with a commercial solver using extensive numerical experiments. Computational results highlight the importance and necessity of simultaneous consideration of demand uncertainty and pricing decisions in designing hub-and-spoke networks with profit maximisation. The proposed formulation for the capacitated problem is then extended by relaxing the assumption of using fixed discount factors on inter-hub links to calculate the transportation cost. The new formulation employs a flow-dependent cost function. This feature is embedded into the problem’s integer programming formulation using a piece-wise linear approximation scheme. The resulting model is solved for medium-sized instances using the commercial solver AIMMS and a modified variant of the Lagrangian relaxation algorithm that was developed earlier for the model with fixed discount factor. Comparing the results with and without a flow-dependent discount factor highlights and confirms an important and interesting issue about overestimating profit in networks with fixed discount factor. Results also show that the proposed algorithm solves instances of the problem for which commercial solver is unable to return any solution and outperforms the commercial solver in terms required computing time in the rest of the problem instances.

The subject is further extended by investigating another variant of the uncapacitated hub location problem with profit maximisation. This new problem jointly employs flow-dependent cost and flow-dependent revenue. An important feature of the new problem is about the way revenue is calculated. In the new formulation, potential revenue generated from serving demand between origin-destination nodes is calculated separately for each segment of the path (i.e., collection, transfer and distribution links). This feature allows to calculate the network profit using flow-dependent revenue on both inter-hub and distribution links. To solve instances of the problem, a new Lagrangian relaxation algorithm combined with a branch-and-Benders-cut scheme is proposed. Numerical experiments have been conducted to compare solutions produced by the new model with those returned by the model with only flow dependent cost feature. Analysis of the results show that the model with both flow-dependent cost and flow-dependent revenue offers solutions with higher profit.