Skip to main content

Advertisement

SpringerLink
Log in

A genetic ant colony optimization based algorithm for solid multiple travelling salesmen problem in fuzzy rough environment

  • Methodologies and Application
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

In this paper, a genetic-ant colony optimization algorithm has been presented to solve a solid multiple Travelling Salesmen Problem (mTSP) in fuzzy rough environment. In solid mTSP, a set of nodes (locations/cities) are given, and each of the cities must be visited exactly once by the salesmen such that all of them start and finish at a depot using different conveyance facility. A solid mTSP is an extension of mTSP where the travellers use different conveyance facilities for travelling from one city to another. To solve an mTSP, a hybrid algorithm has been developed based on the concept of two algorithms, namely genetic algorithm (GA) and ant colony optimization (ACO) based algorithm. Each salesman selects his/her route using ACO and the routes of different salesmen (to construct a complete solution) are controlled by the GA. Here, a set of simple ACO characteristics have further been modified by incorporating a special feature namely ‘refinement’. In this paper, we have utilized cyclic crossover and two-point’s mutation in the proposed algorithm to solve the problem. The travelling cost is considered as imprecise in nature (fuzzy-rough) and is reduced to its approximate crisp using fuzzy-rough expectation. Computational results with different data sets are presented and some sensitivity analysis has also been made.

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
Fig. 6
Fig. 7

Similar content being viewed by others

References

  • Applegate D, Cook W, Dash S (2002) Solution of a min–max vehicle routing problem. Inf J Comput 14(2):132–143

    Article  MathSciNet  MATH  Google Scholar 

  • Bektas T (2006) The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34:209–219

    Article  Google Scholar 

  • Bertazzi L, Maggioni F (2014) Solution approaches for the stochastic capacitated traveling salesmen location problem with recourse. J Optim Theory Appl 166(1):321–342

    Article  MathSciNet  MATH  Google Scholar 

  • Bigras LP, Gamache M, Savard G (2008) The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times. Discrete Optim 5(4):685–699

    Article  MathSciNet  MATH  Google Scholar 

  • Borne S, Mahjoub AR, Taktak R (2013) A branch-and-cut algorithm for the multiple steiner TSP with order constraints. Electron Notes Discrete Math 41(5):487–494

    Article  Google Scholar 

  • Carter AE, Ragsdale CT (2006) A new approach to solving the multiple traveling salesperson problem using genetic algorithms. Eur J Oper Res 175:246–257

    Article  MathSciNet  MATH  Google Scholar 

  • Changdar C, Maiti MK, Maiti M (2013) A constrained solid tsp in fuzzy environment: two heuristic approaches. Iran J Fuzzy Syst 10(1):1–28

    MathSciNet  MATH  Google Scholar 

  • Colorni A, Dorigo M, Maniezzo V (1991) Distributed optimization by ant colonies. In: Proceedings of the first European conference on artificial life, Paris, pp 134–142

  • Colorni A, Dorigo M, Maniezzo V, Trubian M (1994) Ant system for job-shop scheduling. Belgian J Oper 34:39–53

    MATH  Google Scholar 

  • Deer L, Verbiest N, Cornelis C, Godo L (2015) A comprehensive study of implicator–conjunctor-based and noise-tolerant fuzzy rough sets: definitions, properties and robustness analysis. Fuzzy Sets Syst 275(15):1–38

    Article  MathSciNet  Google Scholar 

  • Dorigo M, Colorni A (1996) The ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern Part B 26(1):1–13

    Article  Google Scholar 

  • Dorigo M, Gambardella LM (1997) Ant colonies for the travelling salesman problem. Bio Syst 43(2):73–81

    Google Scholar 

  • Dorigo M, Gambardella LM (1997) Ant colony system: a cooperative learning approach to the travelling salesman problem. IEEE Trans Evolut Comput 1(1):53–66

    Article  Google Scholar 

  • Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern Part-B Cybern 26(1):29–41

    Article  Google Scholar 

  • Dubois D, Prade H (1987) Twofold fuzzy sets and rough sets—some issues in knowledge representation. Fuzzy Sets Syst 23(1):3–18

    Article  MathSciNet  MATH  Google Scholar 

  • Dubois D, Prade H (1990) Rough fuzzy sets and fuzzy rough sets. Int J Gen Syst 17:191–208

    Article  MATH  Google Scholar 

  • Engelbrech AP (2005) Fundamentals of computational swarm intelligence. Wiley, New York

  • Gen M, Cheng R (1997) Genetic Algorithms and Engineering Design. Wiley, USA

    Google Scholar 

  • Goldbarg MC, Bagi LB, Goldbarg EFG (2008) Transgenetic algorithm for the traveling purchaser problem. Eur J Oper Res 199:36–45

    Article  MATH  Google Scholar 

  • Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Boston

    MATH  Google Scholar 

  • Gwiazda TD (2006) Genetic algorithms reference: crossover for single-objective numerical optimization problems, vol I. Springer, Berlin

    Google Scholar 

  • Holland JH (1975) Adaptation in natural and artificial systems. MIT Press, Cambridge

    Google Scholar 

  • Hsu C, Tsai M, Chen W (1991) A study of feature-mapped approach to the multiple travelling salesmen problem. IEEE Int Sympos Circuits Syst 3:1589–1592

    Google Scholar 

  • Kiraly A, Christidou M, Chován T, Karlopoulos E, Abonyi J (2015) Minimization of off-grade production in multi-site multi-product plants by solving multiple traveling salesman problem. J Clean Prod (accepted manuscript, available online 19 May 2015)

  • Kota L, Jarmai K (2015) Mathematical modeling of multiple tour multiple traveling salesman problem using evolutionary programming. Appl Math Model 39(12):3410–3433

    Article  MathSciNet  Google Scholar 

  • Liu B (2002) Theory and practice of uncertain programming. Physica, Heidelberg

    Book  MATH  Google Scholar 

  • Liu M, Chen D, Wu C, Li H (2006) Fuzzy reasoning based on a new fuzzy rough set and its application to scheduling problems. Comput Math Appl 51:1507–1518

    Article  MathSciNet  MATH  Google Scholar 

  • Ma J, Li M, Zhang Y, Zhou H (2014) Firefly algorithm solving equal-task multiple traveling salesman problem. Commun Comput Inf Sci 472:304–307

    Google Scholar 

  • Michalewicz Z (1992) Genetic algorithms \(+\) data structures \(=\) evolution programs. Springer, Berlin

    Book  MATH  Google Scholar 

  • Mladenović N, Urošević D, Hanafi S, Ilić A (2012) A general variable neighbourhood search for the one-commodity pickup-and-delivery travelling salesman problem. Eur J Oper Res 220(1):270–285

    Article  MATH  Google Scholar 

  • Ouaarab A, Ahiod B, Yang XS (2013) Discrete cuckoo search algorithm for the travelling salesman problem. Neural Comput Appl 24(7–8):1659–1669

    Google Scholar 

  • Orloff DS (1974) Routing a fleet of M vehicles to/from a central facility. Networks 4:147–162

    Article  MathSciNet  Google Scholar 

  • Pawlak Z (1982) Rough sets. Int J Comput Inf Sci 11(5):341–356

    Article  MATH  Google Scholar 

  • Pratihar DK (2008) Soft computing. Narosa Publishing House, New Delhi

  • Radzikowska AM, Kerre EE (2002) A comparative study of fuzzy rough sets. Fuzzy Sets Syst 126:137–156

    Article  MathSciNet  MATH  Google Scholar 

  • Ryan JL, Bailey TG, Moore JT, Carlton WB (1998) Reactive tabu search in unmanned aerial reconnaissance simulations. The 30th conference on winter simulation. IEEE Computer Society Press, Los Alamitos, pp 873–879

    Google Scholar 

  • Salazar-González J, Santos-Hernández B (2015) The split-demand one-commodity pickup-and-delivery travelling salesman problem. Transp Res Part B Methodol 75:58–73

  • Sarin SC, Sherali HD, Judd JD, Tsai P-F (2014) Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations. Comput Oper Res 51:64–89

    Article  MathSciNet  MATH  Google Scholar 

  • Shen Q, Richard J (2004) Selecting informative features with fuzzy-rough sets and its application for complex systems monitoring. Pattern Recognit 37:1351–1363

    Article  MATH  Google Scholar 

  • Tsai PF (2006) Tight flow-based formulations for the asymmetric traveling salesman problem and their applications to some scheduling problems. Ph.D. dissertation. Virginia Polytechnic Institute and State University, Blacksburg

  • Wang Y (2003) Mining stock price using fuzzy rough set system. Expert Syst Appl 24:3–23

    Article  Google Scholar 

  • Wang CY, Hu BQ (2015) Granular variable precision fuzzy rough sets with general fuzzy relations. Fuzzy Sets Syst 275(15):39–57

  • Xu J, Zhao L (2008) A class of fuzzy rough expected value multi-objective decision making model and its application to inventory problems. Comput Math Appl 56:2107–2119

    Article  MathSciNet  MATH  Google Scholar 

  • Zadeh LA (1965) Fuzzy sets. Inf Control 8(3):338–353

    Article  MATH  Google Scholar 

  • Zhao J, Liu Q, Wang W, Wei Z, Shi P (2011) A parallel immune algorithm for traveling salesman problem and its application on cold rolling scheduling. Inf Sci 181 7(1):1212–1223

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Raja N.L. Khan Women’s College, Midnapore, 721102, West Bengal, India

    Chiranjit Changdar

  2. Department of Computer Science and Engineering, University of Calcutta, Calcutta, 700 098, West Bengal, India

    Rajat Kumar Pal

  3. Department of Mathematics, National Institute of Technology, Puducherry, 609605, Karaikal, India

    G. S. Mahapatra

Authors
  1. Chiranjit Changdar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rajat Kumar Pal
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. G. S. Mahapatra
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Chiranjit Changdar.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Communicated by V. Loia.

Appendix

Appendix

Table 5 Fuzzy-rough cost matrix for 7-city problem
Full size table

In Table 5, each fuzzy-rough travel cost has six components; the first and the last components are L and R, respectively as described in Lemma 2. The second, third, fourth, and fifth components are a, b, c,  and d,  respectively (rough number components), that have also been described in Lemma 2. Here 1stvh, 2ndvh, and 3rdvh indicate cost of travel using the first, second, and third type vehicle, respectively.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Changdar, C., Pal, R.K. & Mahapatra, G.S. A genetic ant colony optimization based algorithm for solid multiple travelling salesmen problem in fuzzy rough environment. Soft Comput 21, 4661–4675 (2017). https://doi.org/10.1007/s00500-016-2075-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-016-2075-4

Keywords

Search

Navigation