Intuitionistic Fuzzy Orienteering Problem and Its Work-Depth Analysis

Authors

  • Madhushi Verma  
  • K. K. Shukla  

Keywords:

Centroid of Centroids, Fuzzy Optimization, Intuitionistic Fuzzy Orienteering Problem, Orienteering Problem, Trapezoidal Intuitionistic Fuzzy Number.

Abstract

Orienteering is an NP-hard problem that originated from a water sport where a player is required to visit a set of control points connecting the source and the destination, collect the maximum possible rewards or scores associated with the control points and arrive at the destination within the time bound. It finds its application in the tourism industry, telecommunication networks and other computational problems where things like human behaviour and hesitancy of the decision maker must be considered. To tackle the uncertainty involved in the parameters we represent them using trapezoidal intuitionistic fuzzy numbers (TIFN) resulting in intuitionistic fuzzy orienteering problem (IFOP). A technique based on max-min formulation is presented to deal with IFOP using a new method for ranking TIFNs. Also, a work-depth analysis for the parallel version of IFOP is presented to show that IFOP is work-preserving and can be implemented on a multiprocessor model like PRAM to obtain the solution for large instances efficiently.

References

  1. P. Vansteenwegen, W. Souffriau, D. V. Oudheusden, "The orienteering problem: A survey", European Journal of Operational Research, vol. 209, pp. 1-10, 2011.
  2. Jun Ye, "Expected value method for intuitionistic trapezoidal fuzzy multicriteria decision-making problems", Expert Systems with Applications, vol. 38, pp. 11730-11734, 2011.
  3. T. Tsiligirides, "Heuristic methods applied to orienteering", Journal of the Operational Research Society, vol. 35, pp. 797–809, 1984.
  4. B. Golden, L. Levy, R. Vohra, "The orienteering problem", Naval Research Logistics, vol. 34, pp. 307–318, 1987.
  5. R. Ramesh, K. Brown, "An efficient four-phase heuristic for the generalized orienteering problem", Computers and Operations Research, vol. 18, pp. 151–165, 1991.
  6. Q. Wang, X. Sun, B. Golden, J. Jia, "Using artificial neural networks to solve the orienteering problem", Annals of Operations Research, vol. 61, pp. 111–120, 1995.
  7. I. Chao, B. Golden, E. Wasil, "Theory and methodology – a fast and effective heuristic for the orienteering problem", European Journal of Operational Research, vol. 88, pp. 475–489, 1996.
  8. M. Tasgetiren, "A genetic algorithm with an adaptive penalty function for the orienteering problem", Journal of Economic and Social Research, vol. 4, no. 2, pp. 1–26, 2001.
  9. M. Gendreau, G. Laporte, F. Semet, " A tabu search heuristic for the undirected selective travelling salesman problem" European Journal of Operational Research, vol. 106, pp. 539–545, 1998a.
  10. Y. Liang, S. Kulturel-Konak, A. Smith, "Meta heuristics for the orienteering problem", Proceedings of the 2002 Congress on Evolutionary Computation, Hawaii, Honolulu, pp. 384–389, 2002.
  11. M. Fischetti, J. Salazar, P. Toth, "Solving the orienteering problem through branch-and-cut", INFORMS Journal on Computing, vol. 10, pp. 133–148, 1998.
  12. M. Schilde, K. F. Doerner, R. F. Hartl, G. Kiechle, "Metaheuristics for the bi-objective orienteering problem", Swarm Intelligence, vol. 3, pp. 179-201, 2009.
  13. V. Campos, R. Marti, J. Sanchez-Oro, A. Duarte, "GRASP with Path Relinking for the Orienteering Problem", 2013. http://www.uv.es/rmarti/paper/docs/routing7.pdf
  14. A. Blum, S. Chawla, D. R. Karger, T. Lane, A. Meyerson, M. Minkoff, "Approximation Algorithms for Orienteering and Discounted-Reward TSP", Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS’03), pp. 1-10, 2003.
  15. D. Johnson, M. Minkoff, S. Phillips, "The prize collecting steiner tree problem: Theory and practice", Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.760–769, 2000.
  16. F. V. Fomin, A. Lingas, "Approximation algorithms for time-dependent orienteering", Information Processing Letters, vol. 83, pp. 57–62, 2002.
  17. K. Atanassov, "Intuitionistic fuzzy sets", Fuzzy Sets and Systems, vol. 20, pp. 87-96, 1986. 
  18. P. Grzegorzewski, "Distances and orderings in a family of intuitionistic fuzzy numbers", Proceedings of the 3rd Conference of the European Society for Fuzzy Logic and Technology (EUSFLAT, 2003), Germany, pp. 223-227, September 10-12, 2003.
  19. M. Jimenez, M. Arenas, A. Bilbao, M. V. Rodriguez, "Linear programming with fuzzy parameters: An interactive method resolution", European Journal of Operational Research, vol. 177, pp. 1599–1609, 2007.
  20. D. P. Loucks, E. V. Beek, "Water Resources Systems Planning and Management: An Introduction to Methods", Models and Applications, UNESCO Publishing, pp. 135-144, 2005.
  21. U. Kaymak, J.M. Sousa, "Weighted Constraints in Fuzzy Optimization, Publications in the Report Series Research in Management" , ERIM Research Program: Business Processes, Logistics and Information Systems, pp. 1-21, 2001. http://repub.eur.nl/res/pub/85/erimrs20010403174009.pdf
  22. J. Ramik, "Soft Computing: Overview and Recent Developments in Fuzzy Optimization", 2001. http://irafm.osu.cz/research_report/118_softco01.pdf
  23. H. J. Zimmermann, "Fuzzy set theory", WIREs Computational Statistics, vol. 2, pp. 317-332, 2010.
  24. F. JARRAY, "Discrete Tomography and Fuzzy Integer Programming", Iranian Journal of Fuzzy Systems, vol. 8, pp. 41-48, 2011.
  25. G. E. Blelloch, "Programming Parallel Algorithms ", Communications of the ACM, vol. 39, no. 3, pp. 85-97, 1996.
  26. M. Verma, K. K. Shukla, "Application of Fuzzy Optimization to the Orienteering Problem", Advances in Fuzzy Systems, vol. 2015, pp. 1-12, 2015.

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, K. K. Shukla, " Intuitionistic Fuzzy Orienteering Problem and Its Work-Depth Analysis, IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology(IJSRCSEIT), ISSN : 2456-3307, Volume 2, Issue 7, pp.302-310, September-2017.