Flower Pollination Algorithm for the Orienteering Problem

Authors(4) :-Madhushi Verma, Tanvi Bothra, Surabhi Agarwal, K. K. Shukla

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.

Authors and Affiliations

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

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

  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

Publication Details

Published in : Volume 2 | Issue 7 | September 2017
Date of Publication : 2017-09-30
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 226-231
Manuscript Number : CSEIT174428
Publisher : Technoscience Academy

ISSN : 2456-3307

Cite This Article :

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

Article Preview

Follow Us

Contact Us