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

Selçuk Kürsat İŞLEYEN, Saadettin Erhan KESEN, Ömer Faruk BAYKOÇ
1.459 422

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

Full Text:

PDF