Title: Simulated annealing-based algorithm for the capacitated hub routing problem

Authors: P.N. Ram Kumar; Appa Iyer Sivakumar

Addresses: Indian Institute of Management Kozhikode, Kozhikode, Kerala – 673 570, India ' School of MAE, Nanyang Technological University, 639 798 – Singapore

Abstract: Routing traffic across a capacitated hub-and-spoke network is very common in freight transportation and telecommunications. Most of the hub-and-spoke network models available in the literature assume a fully inter-connected hub network and allow traffic to pass through a maximum of two hubs. In the absence of a fully inter-connected hub network, the traffic may have to be routed through more than two hubs. In this paper, we develop a mathematical model and a simulated annealing (SA)-based solution methodology for routing freight through not more than three hubs in a given capacitated network. We generate test problem instances to evaluate the efficacy of the mathematical model and the meta-heuristic procedure. The effect of each network parameter on the performance of the SA procedure is analysed thoroughly with extensive computational experiments and relevant statistical tests. The results show that near-optimal solutions for large problem instances can be derived in little computational time.

Keywords: freight transport; hub-and-spoke networks; capacitated nodes; mathematical modelling; simulated annealing; capacitated hub routing; metaheuristics.

DOI: 10.1504/IJSOM.2013.051830

International Journal of Services and Operations Management, 2013 Vol.14 No.2, pp.221 - 235

Published online: 30 Aug 2013 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article