A hybrid algorithm for the path center problem

Authors

1 Department of Mathematics, Shahrood University of Technology, University Blvd., Shahrood, Iran

2 Department of Mathematics, Damghan University, Damghan, Iran

Abstract

Let a graph G = (V;E) be given. In the path center problem we want to find a path P in G such that the maximum weighted distance of P to every vertex in V is minimized. In this paper a genetic algorithm and a
hybrid of genetic and ant colony algorithms are presented for the path center problem. Some test problems are examined to compare the algorithms. The results show that for almost all examples the hybrid method results better solutions than genetic algorithm.

Keywords

References

1. O. Alp, E. Erkut and Z. Drezner, An efficient genetic algorithm for the p-Median Problem, Annals of Operations Research, 122, 21-42 (2003).
2. J.E. Beasley, OR-Library: distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 1069-1072 (1990).
3. E. Bonabeau, M. Dorigo and G. Theraulaz, From natural to artifical swarm inteligence, New York: Oxford University Press (1999).
4. Y.C. Chiou and L.W. Lan, Genetic clustring algorithms, European Journal of Operational Research, 135, 413-427 (2001).
5. M. Dorigo and G. Di Caro, The ant colony optimization meta-heuristic, In New ideas in optimization (D. Corne, M. Dorigo and F. Glover, Eds.), Maidenhead, UK: McGraw-Hill, (1999).
6. M. Dorigo, V. Maniezzo and A. Colorni, Positive feedback as a search strategy, Technical Report 91-016, Milan, Italy: Politecnico di Milano (1991).
7. M. Dorigo, V. Maniezzo and A. Colorni, The Ant System: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and CyberneticsPart B, 26, 1-13 (1996).
8. M. Dorigo and T. St¨utzle, Ant Colony Optimization, MIT Press, Cambridge (MA), (2004).
9. J. Fathali, A genetic algorithm for the p-median problem with pos/neg weights, Applied Mathematics and Computation, 183, 1071-1083 (2007).
10. J. Fathali, H.T. Kakhki and R.E. Burkard, An ant colony algorithm for the pos/neg weighted p-median problem, Central European Journal of Operations Research, 14, 229- 246 (2006).
11. D.E. Goldberg, Genetic Algorithms In Search, Optimization And Machine Learning. Menlo Park, CA: Addison-Weseley (1989).
12. S.L. Hakimi, E.F. Schmeichel and M. Labbe, On locating path- or tree-shaped facilities on networks, Networks, 23, 543-555 (1993).
13. S.M. Hedetniemi, E.J. Cockaine and S.T. Hedetniemi, Linear algorithms for finding the jordan center and path center of a tree, Transportation Science, 15, 98-114 (1981).
14. M. Labbe, G. Laporte and I. Rodriguez Martin, Path, tree cycle location, In Fleet Management and Logistics (T.G. Crainic and G. Laporte, Eds.), Kluwer (1998).
15. E. Minieka, The optimal location of a path or tree in a tree network, Networks, 15, 309-321 (1985).
16. C.R. Reeves, Genetic Algorithms, In Modern Heuristic Techniques for Combinatorial Problems, (C.R Reeves, Eds.), Chapter 4 (1993).
17. P.J. Slater, Locating central paths in a graph, Transportation Science, 16: 1-18 (1982).
18. Z. Stanimirovic, J. Kratica and D. Dugosija, Genetic algorithms for solving the discrete ordered median problem, European Journal of Operational Research, 182, 983-1001 (2007).
19. M. Zaferanieh and J. Fathali, Ant colony and simulated annealing algorithms for finding the core of a graph, World Applied Sciences Journal, 7, 1335-1341 (2009).
Global Analysis and Discrete Mathematics
Volume 1, Issue 2 - Serial Number 2
November 2016
Pages 83-92

Files

History

  • Receive Date: 21 October 2015
  • Revise Date: 15 November 2015
  • Accept Date: 27 August 2016

Share

How to cite

Statistics