A CONSTRAINED SOLID TSP IN FUZZY ENVIRONMENT: TWO HEURISTIC APPROACHES

Document Type : Research Paper

Authors

1 Department of Computer Science, Raja N.L. Khan Women's College, Midnapore, Paschim- Medinipur, West Bengal, India-721102

2 Department of Mathematics, Mahishadal Raj College, Mahishadal, Purba- Medinipur, West Bengal, India-721628

3 Department of Mathematics, Vidyasagar University, Midnapore, Paschim- Medinipur, West Bengal, India-721102

Abstract

A solid travelling salesman problem (STSP) is a travelling salesman
problem (TSP) where the salesman visits all the cities only once in his
tour using di
erent conveyances to travel from one city to another. Costs
and environmental e
ect factors for travelling between the cities using di
erent
conveyances are di
erent. Goal of the problem is to nd a complete tour
with minimum cost that damages the environment least. An ant colony optimization
(ACO) algorithm is developed to solve the problem. Performance
of the algorithm for the problem is compared with another soft computing
algorithm, Genetic Algorithm(GA). Problems are solved with crisp as well as
fuzzy costs. For fuzzy cost and environmental e
ect factors, cost function as
well as environment constraints become fuzzy. As optimization of a fuzzy objective
function is not well de ned, fuzzy possibility approach is used to get
optimal decision. To test the eciency of the algorithm, the problem is solved
considering only one conveyance facility ignoring the environmental e
ect constraint,
i.e., a classical two dimensional TSP (taking standard data sets from
TSPLIB for solving the problem). Di
erent numerical examples are used for
illustration.

Keywords

References

[1] A. Berrichi, F. Yalaoui, L. Amodeo and M. Mezghiche,Bi-Objective ant colony optimization approach to optimize production and maintenance scheduling, Computers and Operations Research,37 (2010), 1584-1596.
[2] L. Bianchi, M. Dorigo and L. M. Gambardella, Ant colony optimization approach to the probabilistic travelling salesman problem, PPSN VII, LNCS,2439 (2002), 883-892.
[3] T. Chang, Y. Wan and W. T. OOI.,A stochastic dynamic travelling salesman problem with hard time windows, European Journal of Operational Research, 198(3) (2009),748-759.
[4] S. Chen and C. Chien,Multi-objective ant colony optimisation: parallelized genetic ant colony systems for solving the traveling salesman problem, Expert Systems with Applications, 38(2011), 3873-3883.
[5] W. C. Chiang and R. A. Russell,Simulated annealing metaheuristics for the vehicle routine problem with time windows, Annals of Operations Research, 63 (1996), 3-27.
[6] G. B. Dantzig, D. R. Fulkerson, S. M. Johnson,Solution of large-scale travelling salesman problem, Operations Research, 2 (1954), 393-410.
[7] M. Dorigo and L. M. Gambardella,Ant colony system: an cooperative learning approach to the travelling salesman problem, IEEE Transactions on Evolutionary Computation,1(1)(1997).
[8] M. Dorigo and T. Stutzle,Ant colony optimization, prentice hall of India private limitde,New Delhi, 2006 
[9] D. Dubois and H. Prade,Fuzzy sets and system - theory and application, Academic, NewYork, 1980. 
[10] A. P. Engelbrech,Fundamentals of computational swarm intelligence, Wiley, 2005.
[11] O. Ergan and J. B. Orlin,A dynamic programming methodology in very large sccale neigh-bourhood applied to travelling Salesman problem, Discrete Optimization, 3 (2006), 78-85.
[12] F. Focacci, A. Lodi, M. Milano ,A hybrid exact algorithm for the TSPTW, INFORM Journal on Computing,14(4) (2002),403-417.
[13] D. E. Goldberg,Genetic algorithms: search, optimization and machine learning, Addison Wesley, assachusetts, 1989. 
[14] T. Ibaraki, S. Imahori, M. Kubo, T. Masuda, T. Uno and M. Yagiura,fective local search algorithm for routing and scheduling problems with general time window constraints, Transportation Science,39(2)(2005), 206-232.
[15] J. Knox,The application of Tabu search to the symmetric traveling salesman problem, h.D.Dissertation, University of Colorado, 1989. 
[16] A. Kumar, A. Gupta and M. K. Sharma,Application of Tabu search for solving the bi-objective warehouse problem in a fuzzy environment, Iranian Journal of Fuzzy Systems, 9(1)(2012), 1-19.
[17] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys,The traveling salesman problem: G. E. Re Guided tour of combinatorial optimization, Wiley and Sons, New York,1985. 
[18] S. Lin and B. W. Kernighan,An effective heuristic algorithm for the traveling salesman problem, erations Research, 21 (1973), 498-516.
[19] Y. Liu ,Dierent initial solution generators in genetic algorithms for solving the probabilistic traveling salesman problem, Applied Mathematics and Computation, 216 (2010), 125-137.
[20] I. Mahdavi, N. Madhavi-Amiri AND S. Nejati,Algorithms for biobjective shortest path prob-lems in fuzzy networks, Iranian Journal of Fuzzy Systems, 8(4) (2011), 7-37.
[21] M. K. Maiti and M. Maiti,Two-storage inventory model with lot-size dependent fuzzy lead-time under possibility constraints via genetic algorithm, European Journal of Operational Research,179 (2007), 352-371.
[22] M. K. Maiti and M. Maiti,Fuzzy inventory model with two warehouses under possibility constraints, Fuzzy Sets and Systems, 157 (2006), 52-73.
[23] A. K. Majumder and A. K. Bhunia,Genetic algorithm for asymatric traveling salesman problem with imprecise travel times, Journal of Computational and Applied Mathematics,235(9)(2011), 3063-3078.
[24] Z. Michalewicz,Genetic Algorithms + data structures= evolution programs, Springer, Berlin,1992. 
[25] L. A. Moncayo-Martinez and D. Z. Zhang,Multi-objective ant colony optimisation : a meta-heuristic approach to supply chain design, International Journal of Production Economics,1(131)(2011), 407420.
[26] C. Moon, J. Ki, G. Choi and Y. Seo,An ecient genetic algorithm for the traveling salesman problem with precedence constraints, European Journal of Operational Research, 140(2002),606-617.
[27] H. Nezamabadi-Pour, S. Yazdani, M. M. Farsangi and M. Neyestani,A solution to an eco-nomic dispatch problem by a fuzzy adaptive genetic algorithm, Iranian Journal of Fuzzy Systems,8(3)(2011), 1-21.
[28] H. D. Nguyen, I. Yoshihara, K. Yamamori and M. Yasunaga,Implementation of an effective hybrid GA for large scale traveling salesman problem, IEEE Transactions on Systems, Man,and Cybernatics,37(1) 007), 92-99.
[29] I. M. Oliver, D. J. Smith and J. R. C. Holland,A study of permutation crossover operators on the traveling salesman problem, In: Proceedings of the Second International Conference on Genetic Algorithms (ICGA'87), Massachusetts Institute of Technology, Cambridge, MA,(1987), 224-230. 
[30] M. Padberg and G. Rinaldi,Optimization of a 532-city symmetric traveling salesman problem by branch and cut, Operations Research Letters, 6(1) (1987), 1-7.
[31] M. W. Padberg and S. Hong,On the symmetric traveling salesman problem: a computational study, Mathematical Programming Studies, 12 (80), 78-107.
[32] H. L. Petersen. and O. B. G. Madsen,The double travelling salesman problem with multi-ple stack-formulation and heuristic solution approaches, European Journal of Operational Research,198 (2009), 339-347.
[33] A. Vescan and C-M. Pintea,Ant colony component-based system for travelling salesman problem, Applied Mathematical Sciences, 1(28) (2007), 1347-1357.
[34] J. Wang, J. Huang, S. Rao, S. Xue and J. Yin,An adaptive genetic algorithm for solving traveling salesman problem, Springer-Verlag Berlin Heidelberg 2008 , ICIC 2008, LNAI 5227,(2008), 182-189. 
[35] L. Yang, X. Li, Z. Gao and K. Li,A fuzzy minimum risk model for the railway transportation planning problem, Iranian Journal of Fuzzy Systems 8(4) (2011), 39-60.
[36] L. A. Zadeh,Fuzzy sets as a basis for a theory of possibility, Fuzzy Sets and Systems,1(1978), 3-28.
[37] H. J. Zimmermann,Fuzzy set theory and its applications, Allied Publishers Limited, India,1996.  
Iranian Journal of Fuzzy Systems
Volume 10, Issue 1 - Serial Number 1
January and February 2013
Pages 1-28

Files

Share

How to cite

Statistics