Skip to main content

Advertisement

SpringerLink
Log in

Models and Algorithm for the Orienteering Problem in a Fuzzy Environment

  • Published:
International Journal of Fuzzy Systems Aims and scope Submit manuscript

Abstract

The orienteering problem is a classical decision-making problem that can model many applications in logistics, tourism , and several other fields. In the orienteering problem, a graph is given, in which each vertex is associated with a score and the travel time along each edge is provided. The goal of this problem is to find a path that maximizes the sum of the collected scores, such that the total travel time along the path is below a given time limit. In the real world, the scores and the travel time may be uncertain, especially when the historical data are not sufficient. In this paper, we study the orienteering problem in a fuzzy environment and represent the scores and the travel time as fuzzy variables. Based on credibility theory, three fuzzy programming models under different decision criteria are proposed. For cases where the fuzzy variables are of some specific types, crisp equivalents of the models are constructed. In order to solve the proposed models, we design a hybrid intelligent algorithm integrating fuzzy simulation with genetic algorithm. A series of numerical experiments are performed to show the effectiveness and robustness of our hybrid intelligent algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Chao, I., Golden, B.L., Wasil, E.A.: The team orienteering problem. Eur. J. Oper. Res. 88(3), 464–474 (1996)

    Article  MATH  Google Scholar 

  2. Golden, B.L., Levy, L., Vohra, R.: The orienteering problem. Naval Res. Logist. 34(3), 307–318 (1987)

    Article  MATH  Google Scholar 

  3. Souffriau, W., Vansteenwegen, P., Vertommen, J., Berghe, G.V., Van Oudheusden, D.: A personalized tourist trip design algorithm for mobile tourist guides. Appl. Artif. Intell. 22(10), 964–985 (2008)

    Article  Google Scholar 

  4. Tsiligirides, T.: Heuristic methods applied to orienteering. J. Oper. Res. Soc. 35(9), 797–809 (1984)

    Article  Google Scholar 

  5. Hayes, M., Norman., J.M.: Dynamic programming in orienteering: route choice and the siting of controls. J. Oper. Res. Soc. 35(9), 791–796 (1984)

    Article  Google Scholar 

  6. Laporte, G., Martello, S.: The selective travelling salesman problem. Discrete Appl. Math. 26(2), 193–207 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  7. Boussier, S., Feillet, D., Gendreau, M.: An exact algorithm for team orienteering problems. 4OR 5(3), 211–230 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  8. Jorge Riera-Ledesma and Juan Jose Salazar-Gonzalez: Solving the team orienteering arc routing problem with a column generation approach. Eur. J. Oper. Res. 262(1), 14–27 (2017)

    Article  MathSciNet  Google Scholar 

  9. Golden, B.L., Qiwen, W., Liu, L.: A multifaceted heuristic for the orienteering problem. Nav. Res. Logist. (NRL) 35(3), 359–366 (1988)

    Article  MATH  Google Scholar 

  10. Chao, I., Golden, B.L., Wasil, E.A., et al.: A fast and effective heuristic for the orienteering problem. Eur. J. Oper. Res. 88(3), 475–489 (1996)

    Article  MATH  Google Scholar 

  11. Tasgetiren, F.: A genetic algorithm with an adaptive penalty function for the orienteering problem. J. Econ. Soc. Res. 4(2), 1–26 (2002)

    Google Scholar 

  12. Wang, X., Golden, B.L., Edward A, W.: Using a genetic algorithm to solve the generalized orienteering problem. In: The Vehicle Routing Problem: Latest Advances and New Challenges. Springer, New York (2008)

    Book  MATH  Google Scholar 

  13. Sevkli, Z., Sevilgen, F.E.: Variable neighborhood search for the orienteering problem. In: Computer and Information Sciences—ISCIS 2006, pp. 134–143. Springer (2006)

  14. Palomo-Martinez, P.J., Salazar-Aguilar, M.A., Laporte, G.: A hybrid variable neighborhood search for the orienteering problem with mandatory visits and exclusionary constraints. Comput. Oper. Res. 78, 408–419 (2017)

    Article  MathSciNet  Google Scholar 

  15. Bouly, H., Dang, D.-C., Moukrim, A:. A memetic algorithm for the team orienteering problem. 4OR, 8(1), 49–70 (2010)

  16. Matl, P., Nolz, P.C., Ritzinger, U., Ruthmair, M., Tricoire, F.: Bi-objective orienteering for personal activity scheduling. Comput. Oper. Res. 82, 69–82 (2017)

    Article  MathSciNet  Google Scholar 

  17. Gedik, R., Kirac, E., Milburn, A.B., Rainwater, C.: A constraint programming approach for the team orienteering problem with time windows. Comput. Ind. Eng. 107, 178–195 (2017)

    Article  Google Scholar 

  18. Mei, Y., Salim, F.D., Li, X.: Efficient meta-heuristics for the multi-objective time-dependent orienteering problem. Eur. J. Oper. Res. 254, 443–457 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  19. Keshtkaran, M., Ziarati, K., Bettinelli, A., Vigo, D.: Enhanced exact solution methods for the team orienteering problem. Int. J. Prod. Res. 54, 591–601 (2016)

    Article  Google Scholar 

  20. Gavalas, D., Konstantopoulos, C., Mastakas, K., Pantziou, G., Vathis, N.: Heuristics for the time dependent team orienteering problem: application to tourist route planning. Comput. Oper. Res. 62, 36–50 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  21. Ilhan, T., Iravani, S.M.R., Daskin, M.S.: The orienteering problem with stochastic profits. IIE Trans. 40(4), 406–421 (2008)

    Article  Google Scholar 

  22. Tang, H., Miller-Hooks, E.: Algorithms for a stochastic selective travelling salesperson problem. J. Oper. Res. Soc. 56(4), 439–452 (2005)

    Article  MATH  Google Scholar 

  23. Campbell, A.M., Gendreau, M.: The orienteering problem with stochastic travel and service times. Ann. Oper. Res. 186(1), 61–81 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  24. Zadeh, L.A.: Fuzzy sets. Inf. Control 8(3), 338–353 (1965)

    Article  MATH  Google Scholar 

  25. Nahmias, S.: Fuzzy variables. Fuzzy Sets Syst. 1, 97–110 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  26. Zadeh, L.A.: Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets Syst. 1, 3–28 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  27. Liu, B., Liu, Y.-K.: Expected value of fuzzy variable and fuzzy expected value models. IEEE Trans. Fuzzy Syst. 10(4), 445–450 (2002)

    Article  Google Scholar 

  28. Liu, B.: A survey of credibility theory. Fuzzy Optim. Decis. Mak. 5(4), 387–408 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  29. Zheng, Y., Liu, B.: Fuzzy vehicle routing model with credibility measure and its hybrid intelligent algorithm. Appl. Math. Comput. 176(2), 673–683 (2006)

    MathSciNet  MATH  Google Scholar 

  30. Ni, Y.: Fuzzy minimum weight edge covering problem. Appl. Math. Model. 32(7), 1327–1337 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  31. Qin, Z., Ji, X.: Logistics network design for product recovery in fuzzy environment. Eur. J. Oper. Res. 202(2), 479–490 (2010)

    Article  MATH  Google Scholar 

  32. Barak, S., Abessi, M., Modarres, M.: Fuzzy turnover rate chance constraints portfolio model. Eur. J. Oper. Res. 228(1), 141–147 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  33. Yahia Zare Mehrjerdi and Ali Nadizadeh: Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands. Eur. J. Oper. Res. 229(1), 75–84 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  34. Ni, Y.: Edge covering problem under hybrid uncertain environments. Appl. Math. Comput. 219(11), 6044–6052 (2013)

    MathSciNet  MATH  Google Scholar 

  35. Ali Nadizadeh and Hasan Hosseini Nasab: Solving the dynamic capacitated location-routing problem with fuzzy demands by hybrid heuristic algorithm. Eur. J. Oper. Res. 238(2), 458–470 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  36. Ni, Y., Zhao, Z.: Two-agent scheduling problem under fuzzy environment. J. Intell. Manuf. 28(3), 739–748 (2017)

    Article  Google Scholar 

  37. Liu, B.: Uncertainty theory: an introduction to its axiomatic foundations, volume 154. Springer (2004)

  38. Liu, Y.-K., Gao, J.: The independence of fuzzy variables in credibility theory and its applications. Int. J. Uncertain. Fuzziness Knowl.-Based Syst. 12(5), 1–20 (2007)

    Article  Google Scholar 

  39. Liu, Y.-K., Liu, B.: Expected value operator of random fuzzy variable and random fuzzy expected value models. Int. J. Uncert. Fuzziness Knowl.-Based Syst. 11(2), 195–215 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  40. Vansteenwegen, P., Souffriau, W., Van Oudheusden, D.: The orienteering problem: a survey. Eur. J. Oper. Res. 209(1), 1–10 (2011)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This work was supported by National Natural Science Foundation of China (Nos. 71471038, 71371141) and Program for Huiyuan Distinguished Young Scholars, UIBE.

Author information

Authors and Affiliations

  1. School of Information Technology and Management, University of International Business and Economics, Beijing, 100029, China

    Yaodong Ni

  2. Division of Information Technology and Operations Management, Nanyang Business School, Nanyang Technological University, Singapore, Singapore

    Yi Chen

  3. School of Economics and Management, Tongji University, Shanghai, China

    Hua Ke

  4. Department of Mathematical Sciences, University of Cincinnati, Cincinnati, OH, USA

    Dan A. Ralescu

Authors
  1. Yaodong Ni
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yi Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hua Ke
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Dan A. Ralescu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yaodong Ni.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ni, Y., Chen, Y., Ke, H. et al. Models and Algorithm for the Orienteering Problem in a Fuzzy Environment. Int. J. Fuzzy Syst. 20, 861–876 (2018). https://doi.org/10.1007/s40815-017-0369-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40815-017-0369-z

Keywords

Search

Navigation