Ruba Almahasneh
57205404463
Publications - 7
The Extension of the Triple Fuzzy Time Dependent Travelling Salesman Problem Model, with a Discrete Bacterial Memetic Optimization Algorithm
Publication Name: Acta Polytechnica Hungarica
Publication Date: 2025-01-01
Volume: 22
Issue: 5
Page Range: 71-91
Description:
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.
Open Access: Yes
Optimization of the time-dependent traveling salesman problem using interval-valued intuitionistic fuzzy sets
Publication Name: Axioms
Publication Date: 2020-06-01
Volume: 9
Issue: 2
Page Range: Unknown
Description:
This study proposes a new model and approach for solving a realistic extension of the Time-Dependent Traveling Salesman Problem, by using the concept of distance between interval-valued intuitionistic fuzzy sets. For this purpose, we developed an interval-valued fuzzy degree repository based on the relations between rush hour periods and traffic regions in the "city center areas", and then we utilized the interval-valued intuitionistic fuzzy weighted arithmetic average to aggregate fuzzy information to be able to quantify the delay in any given trip between two nodes (cities). The proposed method is illustrated by a simple numerical example.
Open Access: Yes
Extension of the Time Dependent Travelling Salesman Problem with Interval Valued Intuitionistic Fuzzy Model Applying Memetic Optimization Algorithm
Publication Name: ACM International Conference Proceeding Series
Publication Date: 2020-03-21
Volume: Unknown
Issue: Unknown
Page Range: 111-118
Description:
The Time Dependent Traveling Salesman Problem (TD TSP) is an extension of the classic Traveling Salesman Problem towards more realistic conditions. TSP is one of the most extensively studied NP-complete graph search problems. In TD TSP, the edges are assigned different weights, depending on whether they are traveled in the traffic jam regions (such as busy city centers) and during rush hour periods, or not. In such circumstances, edges are assigned higher costs, expressed by a multiplying factor. In this paper, we introduce a novel and even more realistic approach, the Interval Intuitionistic Fuzzy Time Dependent Traveling Salesman Problem (IVIFTD TSP); which is a further extension of the classic TD TSP, with the additional notion of deploying interval valued intuitionistic fuzzy for describing uncertainties. The core concept employs interval valued intuitionistic fuzzy sets for quantifying the traffic jam regions, and the rush hour periods loss (those are additional costs of the travel between nodes), which are always uncertain in real life. Since type-2 (such as inter valued) fuzzy sets have the potential to provide better performance in modeling problems with higher uncertainties than the traditional fuzzy set, the new approach it may be considered as an extended, practically more applicable, extended version of the original abstract problem. The optimization of such a complex model is obviously very difficult; it is a mathematically intractable problem. However, the Discrete Bacterial Memetic Evolutionary Algorithm proposed earlier by the authors' team has shown sufficient efficiency, general applicability for similar type problems and good predictability in terms of problem size, thus it is applied for the optimization of the concrete instances.
Open Access: Yes
Fuzzy set based models comparative study for the td tsp with rush hours and traffic regions
Publication Name: Communications in Computer and Information Science
Publication Date: 2020-01-01
Volume: 1238 CCIS
Issue: Unknown
Page Range: 699-714
Description:
This study compares three fuzzy based model approaches for solving a realistic extension of the Time Dependent Traveling Salesman Problem. First, the triple Fuzzy (3FTD TSP) model, where the uncertain costs between the nodes depend on time are expressed by fuzzy sets. Second, the intuitionistic fuzzy (IFTD TSP) approach, where including hesitation was suitable for quantifying the jam regions and the bimodal rush hour periods during the day. Third, the interval-valued intuitionistic fuzzy sets model, that calculates the interval-valued intuitionistic fuzzy weighted arithmetic average (IIFWAA) of the edges’ confirmability degrees and non-confirmability degrees, was contributing in minimizing the information loss in cost (delay) calculation between nodes.
Open Access: Yes
Quasi-Optimization of the Time Dependent Traveling Salesman Problem by Intuitionistic Fuzzy Model and Memetic Algorithm
Publication Name: Studies in Computational Intelligence
Publication Date: 2020-01-01
Volume: 872
Issue: Unknown
Page Range: 239-253
Description:
The Traveling Salesman Problem (TSP) is an NP-hard graph search problem. Despite having numerous modifications of the original abstract problem, Time Dependent Traveling Salesman Problem (TD TSP) was one of the most realistic extensions under real traffic conditions. In TD TSP the edges between nodes are assigned higher costs (weights), if they were traveled during the rush hour periods, or crossed the traffic jam regions, such as the city center(s). In this paper we introduce an even more real-life motivated approach, the Intuitionistic Fuzzy Time Dependent Traveling Salesman Problem (IFTD TSP), which is a further extension of the TSP, and also of the classic TD TSP, with the additional notion of using intuitionistic fuzzy sets for the definition of uncertain costs, time, and space of the rush hour—traffic jam region affecting graph sections. In IFTD TSP we use fuzzy memberships and non-memberships sets for estimating the vague costs between nodes in order to quantify the behavior of traffic jam regions, and the rush hour periods. Since intuitionistic fuzzy sets are generalizations of classic fuzzy sets, our approach may be considered an extension and substitution of the original abstract TD TSP problem, even, of the (classic) Fuzzy TD TSP. Lastly, DBMEA (Discrete Bacterial Memetic Evolutionary Algorithm) was applied on the IFTD TSP model, the results of the simulation runs based on some extensions of the benchmarks generated from the original TD TSP data set showed quite good and promising preliminary results.
Open Access: Yes
Modeling of Fuzzy Rule-base Algorithm for the Time Dependent Traveling Salesman Problem
Publication Name: IEEE International Conference on Fuzzy Systems
Publication Date: 2019-06-01
Volume: 2019-June
Issue: Unknown
Page Range: Unknown
Description:
The Traveling Salesman Problem (TSP) is one of the most extensively studied NP-hard graph search problems. In the literature, there have been numerous published attempts, applying various approaches in order to find the optimum (least cost) or semi optimum solution. Time Dependent Traveling Salesman Problem (TD TSP) is one of the most sufficient extensions and modifications of the original TSP problem. In TD TSP the costs of edges between nodes varies, they are assigned higher cost in the traffic jam region, such as city center or during the rush hour periods. In this paper, we introduce an even more realistic approach, the 3FTD TSP (Triple Fuzzy Time Dependent Traveling Salesman Problem); a fuzzified model of the original TD TSP. The 3FTD TSP presents a variation of the TD TSP utilizing fuzzy values in the cost between two nodes (shops, cities, etc.), the geographical areas of the traffic jam region, and also the rush hour period. The goal is to give a practically useful and realistic alternative of the basic TD TSP problem. In order to calculate the (quasi-) optimum solution, the Discrete Bacterial Memetic Evolutionary Algorithm was used, since it has been proven to be rather efficient (and predictably) in a wide range of NP-hard problems, including the original TSP and the TD TSP as well. The results from the runs based on the extensions of the family of benchmarks generated from the original TD TSP benchmark data set showed rather good and credible initial results.
Open Access: Yes
Intuitionistic Fuzzy Model of Traffic Jam Regions and Rush Hours for the Time Dependent Traveling Salesman Problem
Publication Name: Advances in Intelligent Systems and Computing
Publication Date: 2019-01-01
Volume: 1000
Issue: Unknown
Page Range: 123-134
Description:
The Traveling Salesman Problem (TSP) is one of the most extensively studied NP-hard graph search problems. Many researchers published numerous approaches for quality solutions, applying various techniques in order to find the optimum (least cost) or semi optimum solution. Moreover, there are many different extensions and modifications of the original problem, The Time Dependent Traveling Salesman Problem (TD TSP) is a prime example. TD TSP indeed was one of the most realistic extensions of the original TSP towards assessment of traffic conditions [1]. Where the edges between nodes are assigned different cost (weight), considering whether they are traveled during the rush hour periods or they cross the traffic jam regions. In such conditions edges are assigned higher costs [1]. In this paper we introduce an even more realistic approach, the IFTD TSP (Intuitionistic Fuzzy Time Dependent Traveling Salesman Problem); which is an extension of the classic TD TSP with the additional notion of intuitionistic fuzzy sets. Our core concept is to employ intuitionistic fuzzy sets of the cost between nodes to quantify traffic jam regions, and the rush hour periods. Since the intuitionistic fuzzy sets are generalizations of the original fuzzy sets [2], then our approach is a usefully extended, alternative model of the original abstract problem. By demonstrating the addition of intuitionistic fuzzy elements to quantify the intangible jam factors and rush hours, and creating an inference system that approximates the tour cost in a more realistic way [3]. Since our motivation is to give a useful and practical alternative (extension) of the basic TD TSP problem, the DBMEA (Discrete Bacterial Memetic Evolutionary Algorithm) was used in order to calculate the (quasi-)optimum or semi optimum solution. DBMEA has been proven to be effective and efficient in a wide segment of NP-hard problems, including the original TSP and the TD TSP as well [4]. The results from the runs based on the extensions of the family of benchmarks generated from the original TD TSP benchmark data set showed rather good and credible initial results.
Open Access: Yes
