Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation

Research output: Contribution to journalArticleResearchpeer-review

38 Citations (Scopus)

Abstract

Hub and spoke type networks are often designed to solve problems that require the transfer of large quantities of commodities. This can be an extremely difficult problem to solve for constructive approaches such as ant colony optimisation due to the multiple optimisation components and the fact that the quadratic nature of the objective function makes it difficult to determine the effect of adding a particular solution component. Additionally, the amount of traffic that can be routed through each hub is constrained and the number of hubs is not known a-priori. Four variations of the ant colony optimisation meta-heuristic that explore different construction modelling choices are developed. The effects of solution component assignment order and the form of local search heuristics are also investigated. The results reveal that each of the approaches can return optimal solution costs in a reasonable amount of computational time. This may be largely attributed to the combination of integer linear preprocessing, powerful multiple neighbourhood local search heuristic and the good starting solutions provided by the ant colonies.

Original languageEnglish
Pages (from-to)239-261
Number of pages23
JournalComputational Optimization and Applications
Volume39
Issue number2
DOIs
Publication statusPublished - Mar 2008

Fingerprint

Hub Location
Ant colony optimization
Location Problem
Local Search
Heuristics
Neighborhood Search
Particular Solution
Ant Colony
Metaheuristics
Preprocessing
Assignment
Objective function
Optimal Solution
Traffic
Integer
Optimization
Costs
Modeling
Hub location
Location problem

Cite this

@article{b8364dcd80284bef80971f13daae8815,
title = "Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation",
abstract = "Hub and spoke type networks are often designed to solve problems that require the transfer of large quantities of commodities. This can be an extremely difficult problem to solve for constructive approaches such as ant colony optimisation due to the multiple optimisation components and the fact that the quadratic nature of the objective function makes it difficult to determine the effect of adding a particular solution component. Additionally, the amount of traffic that can be routed through each hub is constrained and the number of hubs is not known a-priori. Four variations of the ant colony optimisation meta-heuristic that explore different construction modelling choices are developed. The effects of solution component assignment order and the form of local search heuristics are also investigated. The results reveal that each of the approaches can return optimal solution costs in a reasonable amount of computational time. This may be largely attributed to the combination of integer linear preprocessing, powerful multiple neighbourhood local search heuristic and the good starting solutions provided by the ant colonies.",
author = "Marcus Randall",
year = "2008",
month = "3",
doi = "10.1007/s10589-007-9069-1",
language = "English",
volume = "39",
pages = "239--261",
journal = "Computational Optimization and Applications",
issn = "0926-6003",
publisher = "Springer",
number = "2",

}

Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation. / Randall, Marcus.

In: Computational Optimization and Applications, Vol. 39, No. 2, 03.2008, p. 239-261.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation

AU - Randall, Marcus

PY - 2008/3

Y1 - 2008/3

N2 - Hub and spoke type networks are often designed to solve problems that require the transfer of large quantities of commodities. This can be an extremely difficult problem to solve for constructive approaches such as ant colony optimisation due to the multiple optimisation components and the fact that the quadratic nature of the objective function makes it difficult to determine the effect of adding a particular solution component. Additionally, the amount of traffic that can be routed through each hub is constrained and the number of hubs is not known a-priori. Four variations of the ant colony optimisation meta-heuristic that explore different construction modelling choices are developed. The effects of solution component assignment order and the form of local search heuristics are also investigated. The results reveal that each of the approaches can return optimal solution costs in a reasonable amount of computational time. This may be largely attributed to the combination of integer linear preprocessing, powerful multiple neighbourhood local search heuristic and the good starting solutions provided by the ant colonies.

AB - Hub and spoke type networks are often designed to solve problems that require the transfer of large quantities of commodities. This can be an extremely difficult problem to solve for constructive approaches such as ant colony optimisation due to the multiple optimisation components and the fact that the quadratic nature of the objective function makes it difficult to determine the effect of adding a particular solution component. Additionally, the amount of traffic that can be routed through each hub is constrained and the number of hubs is not known a-priori. Four variations of the ant colony optimisation meta-heuristic that explore different construction modelling choices are developed. The effects of solution component assignment order and the form of local search heuristics are also investigated. The results reveal that each of the approaches can return optimal solution costs in a reasonable amount of computational time. This may be largely attributed to the combination of integer linear preprocessing, powerful multiple neighbourhood local search heuristic and the good starting solutions provided by the ant colonies.

UR - http://www.scopus.com/inward/record.url?scp=38949102636&partnerID=8YFLogxK

U2 - 10.1007/s10589-007-9069-1

DO - 10.1007/s10589-007-9069-1

M3 - Article

VL - 39

SP - 239

EP - 261

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

SN - 0926-6003

IS - 2

ER -