A DISTRIBUTED GENETIC ALGORITM AND A-PRIORI ALGORITHM FOR THE HUB AND FACILITY LOCATION PROBLEMS

  • Nasir Ahmad Department of Electronic and Electrical Engineering, Loughborough University, UK
Keywords: Hub Location Problem, A-Priori, Genetic Algorithms, Data Mining, Heuristic, Distributed Computing

Abstract

A-priori is an influential data mining algorithm employed in market basket analysis to understand the purchase
behavior of buyers. It has many other applications. In this study, we combine a-priori with a genetic algorithm (GA)
to solve two classical NP-hard location problems namely the Un-capacitated Single Allocation Problem (USAHLP)
and Un-capacitated Facility Location Problem (UFLP). A distributed model of the proposed algorithm has been
implemented. The performance of the algorithm has been evaluated with standard benchmark problems for USAHLP
and UFLP. Results have been found encouraging.

References

1. Chen, J. F., (2007), “A hybrid heuristic for the single
allocation hub location problem”, Omega, vol.35,
no. 2, pp. 211-220.
2. Lazic, N., Frey, B. J., and Arabi, P. (2010), “Solving
the uncapacitated facility location problem using
message passing algorithm”, AISTATS, vol.9 pp.
429-436.
3. Edlecamp, S., (2011), Heuristic Search: Theory and
Applications, Morgan Kaufman.
4. Lionel, D., (2008), “Branch and bound algorithm
for a facility location problem with concave site
dependent cost”, International Journal of Production
Economics, vol.112, no. 1, pp. 245-254.
5. Darrel, W., (1994), “A Genetic Algorithm Tutorial”,
Statistics and Computing, vol.4, no. 2, pp. 65-85.
6. Maqsood, S., Noor, S., Khan, M. K. and Wood, A.,
(2012). “Hybrid Genetic Algorithm (GA) for job
shop scheduling problems and its sensitivity analysis.”
International Journal of Intelligent Systems
Technologies and Applications, vol.11, no. 1-2, pp.
49-62.
7. Silva, M. R., Cunha, B. C., (2002), “New simple
and efficient heuristics for the uncapacitated single
allocation hub location problem”, Computer and
Operation Research, vol.36, no. 12, pp. 3152-3165.
8. OR-Library, Un-capacitated warehouse location
problem,http://people.brunel.ac.uk/~mastjjb/jeb/
orlib/uncapinfo.html.
9. Naeem, M., (2009), “Using Genetic Algorithm forthe Single Allocation Hub Location Problem”, M.
Sc. Thesis, Brock University, unpublished.
10. Maqsood, S. (2014). “The scheduling of manufacturing
systems using Artificial Intelligence (AI)
techniques in order to find optimal/near-optimal
solutions.” Thesis, University of Bradford, UK
11. Markus, H., (2005), “The A-Priori Algorithm-a
Tutorial”, WSPC/Lecture Notes Series.
12. Sue, A. H., (1998), “A Hybrid Heuristic for the
Un-capacitated Hub Location Problem”, European
Journal of Operational Research, vol.106, no. 2-3,
pp. 489-499.
13. Topcuoglo, C., Ermis, Y., (2005), “Solving the
Un-capacitated Hub Location Problem Using Genetic
Algorithm”, Computer and Operations Research,
vol.32, no. 4, pp. 967-984.
14. Sibel, A., Bahar, K., (2008), “Network Hub Location
Problem: State of the Art”, European Journal of
Operational Research, vol.190, no. 1, pp. 1-21.
15. Bailey, A., Ombuki-Berman, B., Asobiela, S., (2013),
“Discrete PSO for the single allocation hub location
problem”, IEEE Workshop on Computational
Intelligence In Production and Logistic Systems,
Singapore.
16. Peker, M., Kara, B.Y., Campbell, J.F. et al., (2016)
“Spatial analysis of single allocation hub location
problem, Springer Link, vol. 16, no. 4, pp. 1075-1101.
17. Tohoyama, H., Ida, K., Matsueda, J., (2011), “A
genetic algorithm for the un-capacitated facility
location problem”, Electronics and Communication
in Japan, vol. 94, no. 5, pp. 47-54.
18. Resendo, G. C. M., Werneck, F. R., (2006), “A hybrid
multistart heuristic for the uncapacitated facility
location problem”, European Journal of Operational
Research, vol. 174, no. 1, pp. 54-68.
19. Silva, M., Cunha, C. B. D., (2009), “New simple
and efficient heuristic for the uncapacitated single
allocation hub location problem”, Computers and
Operation Research, vol. 36, no. 12, pp. 3152-3165.
20. OR-Library, Hub location problem, http://people.
brunel.ac.uk/~mastjjb/jeb/orlib/phubinfo.html.
Accessed on 12/10/2015.
Published
2017-11-20