The Extension of the Triple Fuzzy Time Dependent Travelling Salesman Problem Model, with a Discrete Bacterial Memetic Optimization Algorithm

Abstract

The Traveling Salesman Problem (TSP) is one of the most often studied NP-hard graph search problems. There have been numerous publications in the literature that applied various approaches to find the optimum or semi optimum solution. Although the problem is computationally intractable, but the Time Dependent Traveling Salesman Problem (TD TSP) is one of the most realistic extensions of the original TSP problem. In the TD TSP, the costs of edges between nodes vary, namely, they are assigned higher costs if they crossed a predefined oblong shaped area (to represent the jam region in the city center). Realizing that the jam regions and the rush hours costs on a tour are uncertain and can never be accurately represented by concrete numbers, we introduced the novel 3FTD TSP (Triple Fuzzy Time Dependent Traveling Salesman Problem); a fully fuzzified model of the original TD TSP. The 3FTD TSP utilizes fuzzy values for determining the costs between any two nodes within the traffic jam regions and during the rush hours periods more precisely. In this paper, we extend the 3FTD TSP further and apply it on the biggest universal instances in the literature in pursuit of testing the generality and applicability of the 3FTD TSP on real-life scenarios. To support the claim of the model’s efficiency, we propose the application of the DBMEA (Discrete Bacterial Memetic Evolutionary Algorithm), as a meta-heuristic and the classic GA (Genetic Algorithm) enabling the reader to compare the accuracy and the speed of (quasi-) optimum solutions convergence.