Greedy WOA for Travelling Salesman Problem | SpringerLink
Skip to main content
Springer Nature Link
Log in

Greedy WOA for Travelling Salesman Problem

  • Conference paper
  • First Online:
Advances in Computing and Data Sciences (ICACDS 2018)

Part of the book series: Communications in Computer and Information Science ((CCIS,volume 905))

Included in the following conference series:

  • 1248 Accesses

Abstract

Travelling salesman problem (TSP) is an NP-hard combinatorial problem and exhaustive search for an optimal solution is computationally intractable. The present work proposes a discrete version of Whale optimization algorithm (WOA) to find an optimal tour for a given travelling salesman network. Further, a greedy technique is incorporated in WOA (GWOA) to generate new tours which avoid the creation and analysis of non-optimal tours during successive iterations. Standard TSPLIB dataset is used for validation of the proposed technique. Further robustness of GWOA is evaluated on random TSP walks. It is observed from the results that proposed GWOA provides near optimal solution in less number of iterations as compared to WOA and Genetic algorithm (GA) for a given network of TSP.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Warren, R.: Special cases of the traveling salesman problem. Appl. Math. Comput. 60, 171–177 (1994)

    MathSciNet  MATH  Google Scholar 

  2. Marinakis, Y., Marinaki, M., Dounias, G.: A hybrid particle swarm optimization algorithm for the vehicle routing problem. Eng. Appl. Artif. Intell. 23, 463–472 (2010)

    Article  Google Scholar 

  3. Savla, K., Frazzoli, E., Bullo, F.: Traveling salesperson problems for the Dubins vehicle. IEEE Trans. Autom. Control 53, 1378–1391 (2008)

    Article  MathSciNet  Google Scholar 

  4. Plante, R., Lowe, T., Chandrasekaran, R.: The product matrix traveling salesman problem: an application and solution heuristic. Oper. Res. 35, 772–783 (1987)

    Article  MathSciNet  Google Scholar 

  5. Lenstra, J., Kan, A.: Some simple applications of the travelling salesman problem. Oper. Res. Q. 26(717), 1970–1977 (1975)

    Google Scholar 

  6. Bellman, R.: Dynamic programming treatment of the travelling salesman problem. J. ACM 9, 61–63 (1962)

    Article  MathSciNet  Google Scholar 

  7. Langevin, A., Desrochers, M., Desrosiers, J., Gélinas, S., Soumis, F.: A two-commodity flow formulation for the traveling salesman and the makespan problems with time windows. Networks 23, 631–640 (1993)

    Article  MathSciNet  Google Scholar 

  8. Yang, J., Wu, C., Lee, H., Liang, Y.: Solving traveling salesman problems using generalized chromosome genetic algorithm. Prog. Nat. Sci. 18, 887–892 (2008)

    Article  MathSciNet  Google Scholar 

  9. Yang, J., Shi, X., Marchese, M., Liang, Y.: An ant colony optimization method for generalized TSP problem. Prog. Nat. Sci. 18, 1417–1422 (2008)

    Article  MathSciNet  Google Scholar 

  10. Lo, C.-C., Hsu, C.-C.: An annealing framework with learning memory. IEEE Trans. Syst. Man Cybern.-Part A: Syst. Hum. 28, 648–661 (1998)

    Article  Google Scholar 

  11. Meer, K.: Simulated annealing versus metropolis for a TSP instance. Inf. Process. Letters 104, 216–219 (2007)

    Article  MathSciNet  Google Scholar 

  12. Wang, L., Tian, F., Soong, B., Wan, C.: Solving combinatorial optimization problems using augmented lagrange chaotic simulated annealing. Differ. Equ. Dyn. Syst. 19, 171–179 (2011)

    Article  MathSciNet  Google Scholar 

  13. Mirjalili, S., Lewis, A.: The whale optimization algorithm. Adv. Eng. Softw. 95, 51–67 (2016)

    Article  Google Scholar 

  14. Bhesdadiya, R., Parmar, S., Trivedi, I., Jangir, P., Bhoye, M., Jangir, N.: Optimal active and reactive power dispatch problem solution using whale optimization algorithm. Indian J. Sci. Technol. 9 (2016)

    Google Scholar 

  15. Kaveh, A., Rastegar Moghaddam, M.: A hybrid WOA-CBO algorithm for construction site layout planning problem. Sci. Iran. (2017)

    Google Scholar 

  16. Aljarah, I., Faris, H., Mirjalili, S.: Optimizing connection weights in neural networks using the whale optimization algorithm. Soft Comput. (2016)

    Google Scholar 

  17. Jain, M., Singh, V., Rani, A.: A novel nature-inspired algorithm for optimization: squirrel search algorithm. Swarm Evol. Comput. (2018)

    Google Scholar 

  18. Jain, M., Maurya, S., Rani, A., Singh, V.: Owl search algorithm: a novel nature-inspired heuristic paradigm for global optimization. J. Intell. Fuzzy Syst. 34, 1573–1582 (2018)

    Article  Google Scholar 

  19. Goldbogen, J., Friedlaender, A., Calambokidis, J., McKenna, M., Simon, M., Nowacek, D.: Integrative approaches to the study of baleen whale diving behavior, feeding performance, and foraging ecology. Bioscience 63, 90–100 (2013)

    Article  Google Scholar 

  20. Reinelt, G.: Tsplib95. Interdisziplinäres Zentrum für Wissenschaftliches Rechnen (IWR), Heidelberg (1995)

    Google Scholar 

  21. Singh, M., Srivastava, V.M., Gaurav, K., Gupta, P.K.: Automatic test data generation based on multi-objective ant lion optimization algorithm. In: Pattern Recognition Association of South Africa and Robotics and Mechatronics (PRASA-RobMech), Bloemfontein, pp. 168–174 (2017)

    Google Scholar 

  22. Akay, B., Karaboga, D.: A modified Artificial Bee Colony algorithm for real-parameter optimization. Inf. Sci. Int. J. 192, 120–142 (2012)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. COE Division, Netaji Subhas Institute of Technology, University of Delhi, Sec-3, Dwarka, New Delhi, India

    Rishab Gupta & Nilay Shrivastava

  2. ICE Division, Netaji Subhas Institute of Technology, University of Delhi, Dwarka, New Delhi, India

    Mohit Jain, Vijander Singh & Asha Rani

Authors
  1. Rishab Gupta
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nilay Shrivastava
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mohit Jain
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Vijander Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Asha Rani
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rishab Gupta .

Editor information

Editors and Affiliations

  1. University of KwaZulu-Natal, Durban, South Africa

    Mayank Singh

  2. Jaypee University of Information Technology, Solan, India

    P. K. Gupta

  3. Jaypee University of Engineering and Technology, Guna, Madhya Pradesh, India

    Vipin Tyagi

  4. Institute of Information Theory and Automation, Prague 8, Czech Republic

    Jan Flusser

  5. University of Ottawa, Ottawa, Canada

    Tuncer Ören

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer Nature Singapore Pte Ltd.

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Gupta, R., Shrivastava, N., Jain, M., Singh, V., Rani, A. (2018). Greedy WOA for Travelling Salesman Problem. In: Singh, M., Gupta, P., Tyagi, V., Flusser, J., Ören, T. (eds) Advances in Computing and Data Sciences. ICACDS 2018. Communications in Computer and Information Science, vol 905. Springer, Singapore. https://doi.org/10.1007/978-981-13-1810-8_32

Download citation

  • DOI: https://doi.org/10.1007/978-981-13-1810-8_32

  • Published:

  • Publisher Name: Springer, Singapore

  • Print ISBN: 978-981-13-1809-2

  • Online ISBN: 978-981-13-1810-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics