Flower Pollination Algorithm for the Orienteering Problem

Authors

  • Madhushi Verma  Department of Computer Science Engineering, Bennett University, Greater Noida, UP, India
  • Tanvi Bothra  Department of Computer Science and Engineering, IIT(BHU), Varanasi, UP, India
  • Surabhi Agarwal  Department of Computer Science and Engineering, IIT(BHU), Varanasi, UP, India
  • K. K. Shukla  Department of Computer Science and Engineering, IIT(BHU), Varanasi, UP, India

Keywords:

Flower pollination algorithm, Metaheuristic, Orienteering problem, NP-Hard problems.

Abstract

The orienteering problem is an NP-Hard combinatorial optimization problem where the aim is to determine a Hamiltonian path that connects the stated source and target and includes a subset of the vertex set V such that the total collected score is maximized within the given time bound (T_max ). Orienteering problem finds application in logistics, transportation, tourism industry etc. We have proposed an algorithm FPA_OP that can be implemented on complete graphs and its performance has been evaluated using standard benchmarks. Also, the results thus obtained have been compared against the latest heuristic for OP i.e. GRASP and it has been shown that for larger T_max, FPA_OP outperforms GRASP. Therefore, the decision maker can implement FPA_OP if he is willing to achieve a larger total collected score at the cost of time delay.

References

  1. Williamson, D.P., and Shmoys, D.B. The Design of Approximation Algorithms, Cambridge University Press, (2010).
  2. Yang, X.S. Flower Pollination Algorithm for Global Optimization, LNCS 7445, (2012): 240–249.
  3. Yang, X.S., Karamanoglu, M. and He, X. "Multi-objective Flower Algorithm for Optimization." Proceedings of the International Conference on Computational Science, ICCS 2013, (2013): 861 – 868.
  4. Fister, Jr. I., Yang, X. S., Fister, I., Brest, J., and Fister, D. "A Brief Review of Nature-Inspired Algorithms for Optimization." Elektrotehniski Vestnik 80, no. 3 (2013): 1–7.
  5. Vansteenwegen, P., Souffriau, W., and Oudheusden, D. V. "The orienteering problem: A survey." European Journal of Operational Research 209, (2011): 1–10.
  6. Laporte, G., and Martello, S. "The Selective Traveling Salesman Problem." Discrete Applied Mathematics 26, (1990): 193-207.
  7. Hayes, M., and Norman, J. M. "Dynamic Programming in Orienteering: Route Choice and the Siting of Controls." Journal of the Operational Research Society 35, no. 9 (1984): 791-796.
  8. Fischetti, M., Salazar, J., and Toth, P. "Solving the orienteering problem through branch-and-cut." INFORMS Journal on Computing 10, (1998): 133–148.
  9. Tsiligirides, T. "Heuristic methods applied to orienteering." Journal of the Operational Research Society 35, (1984): 797–809.
  10. Ramesh, R., and Brown, K. "An efficient four-phase heuristic for the generalized orienteering problem." Computers and Operations Research 18, (1991): 151–165.
  11. Golden, B., Levy, L., and Vohra, R. "The orienteering problem." Naval Research Logistics 34, (1987): 307–318.
  12. Wang, Q., Sun, X., Golden, B. L., and Jia, J. "Using artificial neural networks to solve the orienteering problem." Annals of Operations Research 61, (1995): 111–120.
  13. Gendreau, M., Laporte, G., and Semet, F. "A tabu search heuristic for the undirected selective travelling salesman problem." European Journal of Operational Research 106, (1998): 539–545.
  14. Schilde, M., Doerner, K. F., Hartl, R. F., and Kiechle, G. "Metaheuristics for the bi-objective orienteering problem." Swarm Intelligence 3, (2009): 179-201.
  15. Campos, V., Marti, R., Sanchez-Oro, J., and Duarte, A. "GRASP with Path Relinking for the Orienteering Problem." Journal of the Operational Research Society 2013, (2013): 1–14.
  16. Blum, A., Chawla, S., Karger, D. R., Lane, T., Meyerson, A., and Minkoff, M. "Approximation Algorithms for Orienteering and Discounted-Reward TSP." Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS’03), (2003): 1-10.
  17. Johnson, D., Minkoff, M., and Phillips, S. "The prize collecting steiner tree problem: Theory and practice." Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, (2000): 760–769.
  18. Fomin, F. V., and Lingas, A. "Approximation algorithms for time-dependent orienteering." Information Processing Letters 83, (2002): 57–62.
  19. Ostrowski, K., and Koszelew, J. "The Comparison of Genetic Algorithms which Solve Orienteering Problem using Complete and Incomplete Graph." Informatyka 8, (2011): 61-77.
  20. Verma, M., Gupta, M., Pal, B., and Shukla, K. K. "Roulette Wheel Selection based Heuristic Algorithm for the Orienteering Problem." International Journal of Computers and Technology 13, no. 1 (2014): 4127-4145.
  21. Verma, M., Gupta, M., Pal, B., and Shukla, K. K. "A Stochastic Greedy Heuristic Algorithm for the Orienteering Problem." Proceedings of the 5th International Conference on Computer and Communication Technology (ICCCT), (2014): 59-65.
  22. Verma, M., and Shukla, K. K. "Application of Fuzzy Optimization to the Orienteering Problem." Advances in Fuzzy Systems 2015, (2015): 1-12.
  23. Verma, M., and Shukla, K. K. "Fuzzy Metric Space Induced by Intuitionistic Fuzzy Points and Its Application to the Orienteering Problem." IEEE Transactions on Fuzzy Systems, 24, no. 2 (2016): 483-488

IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology

Downloads

Published

2017-09-30

Issue

Volume 2, Issue 7, September-2017

Section

Research Articles

License

Copyright (c) IJSRCSEIT

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
Madhushi Verma, Tanvi Bothra, Surabhi Agarwal, K. K. Shukla, " Flower Pollination Algorithm for the Orienteering Problem, IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology(IJSRCSEIT), ISSN : 2456-3307, Volume 2, Issue 7, pp.226-231, September-2017.