From Analytical Perspective to Heuristic Approach: Travelling Salesman Problem with Discrete Fuzzy Travel Times

Year 2009, Volume: 22 Issue: 4, 267 - 276, 27.03.2010

Selçuk İşleyen Saadettin Kesen Ömer Baykoç

Abstract

In today’s business, travelling times are affected by many factors such as traffic, weather, road etc. So deterministic approaches can not find any solution for problems where such an ambiguity happens. This paper deals with the Travelling Salesman Problem (TSP) in which travelling times are inaccurate. We use discrete fuzzy numbers to represent the uncertainty. Discrete fuzzy numbers are then converted to the triangular fuzzy numbers (TFNs). TFNs enforce the TSP model to have a non-linear objective function. Then we make an approximation and obtain linear model (LM) by inserting lower, medium, and lower values of the TFNs into one since non-linear model (NLM) can trap local optima. Finally, we develop Iterated Local Search (ILS) technique to get good solutions in a shorter time in the case that objective function is non-linear. NLM, LM and ILS are compared on a wide range of test problems that randomly generated. Results show that ILS technique is very promising and finds much better solutions in a very shorter computational time. Hence, it can be substituted in the place of NLM.

 

Key Words: Travelling Salesman Problem(TSP),Discrete Fuzzy Numbers, Heuristic

Keywords

-

Discrete Fuzzy Travel Times

Abstract

References

• Laporte, G., Osman I.H., “Routing problems: A bibliography”, Annals of Operations Research, 61: 227-262 (1995).
• Gendreau, M., Laporte, G., Seguin, R., “Stochastic vehicle Operational Research, 88: 3-12 (1996). Journal of
• Bektas, T., “The multiple traveling salesman problem: an overview of formulations and solution procedures”, Omega, 34: 209-219 (2006).
• Jaillet, P., “A Priori solution of a traveling salesman problem in which a random subset of the customers are visited”, Operations Research, 36: 929-936 (1988).
• Dumas, Y., Desrosiers, J., Gelinas, E.; Solomon, M., “Optimal algorithm for the traveling salesman problem Research, 43: 367-371 (1995). Operations
• Voxman, W., “Canonical representations of discrete fuzzy numbers”, Fuzzy Sets and Systems, 118: 457-466 (2001).
• Wang, G., Wu, C., Chunhui, Z., Representation and operations of discrete fuzzy numbers, Southeast Asian Bulletin of Mathematics, 28: 1003-1010 (2005).
• Kung, J.Y., Chuang, T.N., “The shortest path problem with discrete fuzzy arc lengths”, Computers and Mathematics with Applications, 49: 263-270 (2005).
• Martin, O., Otto, S.W., Felten, E.W., “Large-step Markov chains for the TSP incorporating local search heuristics”, Operations Research Letter, 11: 219-224 (1992).
• Lourenço, H.R., Martin, O.C., Stützle, T., “A beginner’s introduction to iterated local search”, In: International Conference, (2001). 4th Metaheuristics
• Congram, R.K., Potts, C.N., Van de Velde, S.L., “An Iterated Dynasearch Algorithm for the Single- Machine Total Weighted Tardiness Scheduling Problem”, Informs Journal on Compuiıng, 14(1): 52-67 (2002).
• Stützle, T., “Applying iterated local search to the permutation flow shop problem”, Technical Report Darmstadt, 23 (1998). Intellektik, TU
• Yang, Y., Kreipl, S., Pinedo, M., “Heuristics for minimizing total weighted tardiness in flexible flow shops”, Journal of Scheduling, 3(2):89-108 (2000).
• Balas, E., Vazaconoulos, A., “Guided Local Search with Shifting Bottleneck for Job Shop Scheduling”, Management Science, 44(2): 262- 275 (1998).
• Stützle, T., “Iterated local search for the quadratic assignment problem”, European Journal of Operational Research, 174(3): 1519-1539 (2006).
• Lourenço, H.R., Martin, O.C., Stützle, T., “Handbooks of Metaheuristics”, Editor: Fred Glover, Kluwer Academic Publishers, 321-353 (2002).
• Bianchi, L., Knowles, J., Bowler, N., “Local search for the probabilistic traveling salesman problem: Correction to the 2-p-opt and 1-shift algorithms”, European Journal of Operational Research, 162(1): 206-219 (2005).