key: cord-0044822-pgexauuq authors: Almahasneh, Ruba; Tuu-Szabo; Foldesi, Peter; Koczy, Laszlo T. title: Fuzzy Set Based Models Comparative Study for the TD TSP with Rush Hours and Traffic Regions date: 2020-05-15 journal: Information Processing and Management of Uncertainty in Knowledge-Based Systems DOI: 10.1007/978-3-030-50143-3_55 sha: 9e908038c5d57171c8e5155001f5252cbf8a786a doc_id: 44822 cord_uid: pgexauuq 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. The Traveling Salesman Problem (TSP) is one of the extensively studied NP-hard graph search problems [1] . Various approaches are known for finding the optimum or semi optimum solution. The Time Dependent Traveling Salesman Problem (TD TSP) is a more realistic extension of the TSP, where the costs of edges vary in time, depending on the jam regions and rush hours. In the TD TSP, the edges are assigned higher weights if they are traveled within the traffic jam regions during rush hour periods, and lower weights otherwise [2] . The information on the rush hour periods and jam regions is uncertain and vague (fuzzy), hence, representing them by crisp numbers in the classic TD TSP does not quantify the effects of traffic jams accurately [2] . This limitation of simulating real life cases was to the point in constructing three novel fuzzy models capable of addressing the TD TSP with jam regions and rush hours more efficiently. In the Triple Fuzzy (3FTD TSP) model, the costs between the nodes may depend on time and location; and are expressed by fuzzy sets [3] . Here, fuzzy values represent the uncertainties of the costs caused by the fuzzy extensions of the traffic jam areas and rush hour times, which depend on several vague or non-deterministic factors. Rush hour time was represented as a bimodal piecewise linear normal fuzzy set, the jam areas as fuzzy oblongs, and the costs as trapezoidal sets. This model expressed the uncertain costs affected by the jam situations, and calculated the overall tour length quantitatively [3] . Second, the Intuitionistic Fuzzy IFTD TSP approach, involves a hesitation part expressing the effects of membership and non-membership values allowing a higher level of uncertainty [4] . In the IFTD TSP, the use of intuitionistic fuzzy sets ensured an even more realistic cost estimate of the TD TSP problem. By successfully representing simultaneously the higher degrees of association and the lower degrees of nonassociation of the jam factor and rush hours and lower degrees of hesitation to edges cost, resulted in a more accurate cost of the tours [4] . Third, we proposed the intervalvalued intuitionistic fuzzy set model (IVIFTD TSP) [5] . In the IVIFTD TSP, additional uncertainty was modeled, and by using an aggregation of the costs rather than using the max-min composition of the fuzzy factors resulted in an even more adequate model. In this paper, the three models are briefly presented and examined, from the point of view of realistical representation and results. The original TSP was first formulated in 1930 [6] . A salesman starts the journey from the headquarters and visits each city or shop exactly once then returns to the starting point. The task is to find the route with minimum overall travelled distance visiting all destination points. TSP is a graph search problem with edge weights in Eq. 1. In the symmetric case with n nodes c ij = c ji , so, in the graph, there is only one edge between every two nodes. Let x ij = {0, 1} be the decision variable (i, j = 1, 2, …, n), and x ij = 1, if edge e ij between node i and node j is part of the tour. Let x ii ¼ 0 i ¼ 1; 2; . . .; n ð Þ , G TSP ¼ N cities ; E conn ð Þ , C: N cities  N cities ! R; C ¼ C ij À Á nÂn C is called cost matrix, where C ij represent the cost of going from city i to city j. then: The goal is to find the directed Hamiltonian cycle with minimal total length. Despite TD TSP's good results in determining the overall cost for a trip under realistic traffic conditions, yet one major drawback is the crisp values used for the proportional jam factors [2] . The total cost of any trip consists of two main elements: costs proportional to physical distances and costs increased by traffic jams occurring in rush hour periods or in certain areas between the pairs of nodes (such as in city center areas). The first can be looked at as constant; although transit times are subject to external and unexpected environmental factors. Thus, even they should be treated as uncertain variables, in particular, as fuzzy cost coefficients. In the TD TSP, the edges have fixed costs, which may be multiplied by a rush hour factor). This representation of the traffic jam effects is too rigid for real life circumstances. In the 3FTD TSP approach [Put here a citation of our paper] two parameters modify the fuzzy edge costs, the actual jam factor calculated from the membership degree of being in the jam region, and the degree of membership being in the rush hour period in the given moment. We proposed to use a simple Mamdani rule base [7] in the form: If N i is in the traffic jam region J and t j is in the rush hour time R then the cost is C k . Here, membership functions from the unit interval [0, 1] help describe the uncertainty of the jam region and the rush hour period, more efficiently. In this model, the distance between cities is also expressed in terms of the elapsed time. Here, we introduced a velocity (v) as a new parameter of the TSP route. The costs were represented by asymmetrical triangular fuzzy numbers. The total cost of the tour was calculated as follows: where l 1 and l 2 are obtained from the Fuzzy Jam Region (J) and Fuzzy Traffic Rush Hours (R) membership functions. A valid solution for the problem is a permutation of the nodes: where p 1 is the starting and end node of the tour. The time needed for visiting the first city from the start node is: where P 1 is the starting node, P 2 is the first visited one and v is the velocity. The calculation of travel time is necessary as the costs are time dependent, and the actual cost between two cities can be determined by Eq. 3, thus, the time dependency in the cost matrix is represented by virtual distance values. The cost of the trip is calculated from The total cost is: where p n is the location last visited, and t elapsed k is the total time elapsed from the beginning of the tour till the salesman arrives in city p k . In the implementation, the three fuzzy elements used were triangular fuzzy costs between the edges, fuzzy oblong type membership function(s) of the fuzzy jam region(s) J; and bimodal normal piecewise linear membership function(s) for the traffic rush hour time period(s) Rsee next sections. The uncertain costs between the nodes, is expressed by triangular fuzzy numbers. Triangular fuzzy numbers may be expressed by the support C = [C L , C R ], and the peak value C C is, so it is denoted byC = (C L , C C , C R ). To calculate the overall distance of the tour, these fuzzy values are summed up. The calculation of the total length of the tour was done by the defuzzified values of the fuzzy numbers using Center of Gravity (COG) [8] . The fuzzy extensions of the city center areas (the degree of belonging to the jam region J) are expressed by fuzzy borders as in Fig. 1 . Thus, l 1 is simply calculated as , where d1, d2 are the distances from the peak of J. This approach sophisticates Schneider's original model (cf. [2] ), so that the breakpoints are: [0, 1000, 5000, 6000], (see Fig. 1 ). The model uses the bimodal membership function in Fig. 2 for representing the Traffic Rush Hour Time (l 2 ). In this example, the two peak rush hour periods are from 7 to 8 a.m. and from 4 to 6 p.m. Between the two periods the traffic is lower. (We used the traffic data base …). The breakpoints of J are {0, 5, 7, 8, 14, 16, 18, 22, 24}, and its membership value at 14 h is 0.75. For illustration, assuming a jam factor of 5, a sample calculation is run to clarify the approach. The peak point of the fuzzy triangular cost for each edge is the Euclidean distance between the end-points, namely, the left-side and right-side points were determined randomly (0-50% lower and higher than the middle point) in this test. Table 1 was calculated by averaging five times runs for jam factor 5.0 for the three areas of the triangular membership functions (low, medium and high). Table 2 shows the middle values of the supports of the triangular fuzzy numbers for that specific case (for jam factor 5). Depending on Table 1 the average elapsed time is 22.19562. Applying the same approach results in Table 3 , which contains the total time in hours required to visit each location with different jam factors by applying the same concept explained in the previous section With such high jam factors, the tour lengths were longer for the 3FTD TSP problem, because the traffic jam period is longer compared to the classic TD TSP. In this model, we moved one step further and extended the model by using intuitionistic fuzzy set theory. First some related definitions as introduced [4] . Let a universal set E be fixed and 0 The is called the hesitation part, which may cater to either the membership value or to the non-membership value, or to both [9, 10] . The previous formulas hold for all Y. Þbe two IFRs. The max-min-max composition R Q ð Þis the intuitionistic fuzzy relation from X to Z, defined by the membership function and the non-membership function 8 x; z ð Þ 2 X  Z and 8y 2 Y is given by Let A be an IFS of the set J, and R be an IFR from J to C. Then the max-min-max composition B of IFS A with the IFR R (J ! C) denoted by B ¼ A R gives the cost of the edges as an IFS B of C with the membership function given by and the non-membership function given as: 8c 2 C: Here^¼ min and _ max ð Þ If the state of the edge E is described in terms of an IFS A of J; then E is assumed to be the assigned cost in terms of IFSs B of C, through an IFR R from J to C, which is assumed to be given by a knowledge base directory (given by experts) on the destination cities and the extent (membership) to which each one is included in the jam region. This will be translated to the degrees of association and non-association, respectively, between jam and cost. Let there be n edges E i ; i = 1; 2;…, 16 as in Fig. 3 ; in a trip. Thus e i 2 E. Let R be an IFR J ! C ð Þand construct an IFR Q from the set of edges E to the set of jam factors J. Clearly, the composition T of IFRs R and T ¼ R Q ð Þgive the cost for each edge from E to C by the membership function given as: and the non-membership function 8e i 2 E and c 2 C given as: For given R and Q, the relation T ¼ R Q can be computed. From the knowledge of Q and T, an improved version of the IFR R can be computed, for which the following holds valid: Table 4 shows each edge of the tour and the jam factors associated. The ultimate goal is to be able to calculate the total tour jam factor which will be multiplied by the physical distances between two nodes. The intuitionistic fuzzy relations Q E ! J ð Þare given as shown in Table 4 , and R J ! C ð Þas in Table 5 , and the composition ðT ¼ R QÞ as in Table 6 . Then we calculated the jam region cost factors ðc jam Þ (see Table 7 ), where the four cost factors are c 1 ¼ 1:2; c 2 ¼ 1:5; c 3 ¼ 2; c 4 ¼ 5 with weighted average calculations: The rush hour cost factors of each tour edge ðc rush Þ are determined in a similar intuitionistic model. The relations between the tour time and the rush hour periods ( Q) are described with intuitionistic fuzzy functions in Fig. 4 . An IFR ( R) is given between the rush hour periods and the cost factors similarly, as it was done for the jam regions in Table 5 . Then the composition ð T ¼ Q R is calculated. Finally, rush hour cost factors were calculated with weighted averaging. The cost of the edges is calculated taking into account the two cost factors (dist e is the Euclidean distance): IF c jam e [ 0 AND c rush e [ 0 [the edge belongs to at least one of the jam regions and is passed during rush hour periods] THEN c e ¼ c jam e  c rush e  dist e ELSE C e ¼ dist e . Clearly, the improved version of R in the IFTD TSP model is more adequate in translating the higher degrees of association and lower degrees of non-association of the jam factors and rush hours as well as lower degrees of hesitation to any cost C; If almost equal values in T are obtained, then we consider the case for which hesitation is least. From a refined version of R one may infer cost from jam factors in the sense of a paired value, one being the degree of association and other the degree of nonassociation. Ultimately, this model offers more realistic costs calculation for the traveled routes under real traffic conditions. First, some basic definitions are overviewed [11, 12] . In a type-2 fuzzy set, the uncertain values of the membership functionà in Eq. 18 consists of a rounded region called "footprint of uncertainty" (FOU). It is the union of all primary memberships FOUs emphasize the distribution that sits on top of the primary membership function of the type-2 fuzzy set. The shape of this distribution depends on the choice made for the secondary grades. When they are equal between two bounds, it gives an interval type-2 fuzzy set as given in Eq. 19. For discrete universe of discourse X and U, an embedded type-2 setà e has N elements, whereà e contains exactly one element from set J x1;x2.........xN , namely U 1;2...N , with its associated secondary grade f x1 u 1 ð Þ, f x2 u 2 ð Þ. . .. . .f xN u N ð Þ, which equals to Eq. 20.à As we discussed previously, the jam factor costs on the edges in a tour were represented as fuzzy relations between the jam factors and the predicted costs (delays). Let . . .; f E q g denote the sets of jam factors, costs and edges, respectively. Two fuzzy relations (FR) Q and R are defined in Eqs. 21 and 22. where l Q e; j ð Þ and v Q e; j ð Þ indicates jam factors degrees for edges. The degree is the relationship between the edges and the jam factors (rush hours or jam regions). Hence, l Q e; j ð Þ indicates the degree to which jam factor j affects edge E and v Q e; j ð Þ indicates the degree to which jam factor j does not affect the same edge. Similarly, l R j; c ð Þ and v R j; c ð Þ are the relationships between the jam factors and the respective costs. (This is called confirmability degree in the coming sections). j; c ð Þ represents the degree to which jam factor j confirms, and v R j; c ð Þ the degree to which jam factor j does not confirm the presence of cost c, respectively [5] . Since Q is defined on set E  J and R on set J  C; the composition T of R and Q (T ¼ R Q) for the prediction of the cost for a specific edge in terms of the cost can be represented by FR from E to C, given the membership function in Eq. 23 and non membership function in Eq. 24 for all e 2 E and c 2 C l T e; c ð Þ ¼ max j min l Q e; j ð Þ; Þbe a collection of interval-valued intuitionistic fuzzy degrees. Then, an IIFWAA operator is defined in Eq. (25) In the next section, we explain the IVIFTD TSP by simulating a simple real life TD TSP cost problem. The approach consists of four main steps: Step 1. Prediction for the rush hours and jam regions of the edges, in the sense that if the trip between the two cities happens during the rush hours and within the jam regions, both will be taken into consideration and none of the factors will be neglected. Table 8 identifies the cost of each jam factor, which is supposed to be predefined by experts in this domain, according to the rush hours and the jam regions. Step 2. Calculation of the interval-valued intuitionistic fuzzy weighted arithmetic average (IIFWAA) of the edges' confirmability and non-confirmability degrees, respectively with the chosen aggregation [13] . where w 1 ; w 2 . . .. . .:w i ð Þ T are the weight vectors of A. Further, w i [ 0 and P n i¼1 w i ¼ 1. In our model we propose giving equal weights to the factors by w i ¼ 1=n. For finding the final jam factor cost, we first calculate the IIFWAA from the degrees given in Table 8 and then use a measure based on distance between IVIFS. Step 3. Calculating the distance between the IFSs using the IIFWAA obtained in Step 2. To calculate the jam factor cost based on the Park distance model between IVIFS [14] . Particularly, we consider the hesitation part to modify the Park distances. The normalized Hamming distance considering the hesitation part, is defined as below for The normalized Hamming distance considering the hesitation part (where H is the hesitation part) is defined as: Step 4. Determination of the final jam factor affected costs based on the distance (assuming equal weights for all factors). To illustrate how to apply the proposed new model on a TD TSP case study with double uncertain jam regions and rush hours, let us consider that E1 is the first edge of a tour as in Fig. 4 indicate the degrees how a jam factor j affects edge e as in Eq. 23, and the confirmability degree as in Eq. 24 is given by M R j; c ð Þ; N R j; c ð Þ h i . Step 1. Table 9 shows the confirmability and non-confirmability degrees of the jam factors assigned to E1, according to their degree of belonging to the rush hour periods and jam regions Step 2. Based on Tables 9 and 8, calculate the results in Tables 10 and 11 Step 4. The lowest distance points of the traffic costs that affect the edge the most, will cause the most extreme delays In our case, this is 0.16 as shown in Table 12 . Carrying out the same calculations for all the edges, we end up with Table 13 . It contains the jam factor costs for all edges, depending on their confirmabilities ("-" indicates the absence of confirmability). The results indicate that this model effectively simulates the real-life conditions and successfully quantifies the traffic delays without information loss [5] . It gives more tangible conditions for such intangible factors as vagueness and non-determinnistic effects with better accuracy than all previous models. In this paper, we constructed a comparison of three different fuzzy extensions of the Time Dependent Traveling Salesman Problem, namely, the 3FTD TSP, the IFTD TSP, and the IVIFTD TSP. These models offer alternative extensions of the abstract TD TSP with crisp traffic regions and time dependent rush hour periods. The 3FTD TSP represents the jam regions and rush hour costs by fuzzy sets. The IFTD TSP offers higher degrees of association and lower degrees of non-association of the jam factors and rush hours as well as lower degrees of hesitation to any edge cost. Lastly, the IVIFTD TSP decreases the information loss by employing the IIFWAA operator to aggregate interval-valued fuzzy information from the jam factors in order to measure the final cost based on the distance between IVIFS(s) for the TD TSP. The results of the examples indicate that our models effectively simulate real-life conditions and successfully quantify the traffic jam regions and rush hours with minimum information loss. After fuzzification of the jam regions and rush hours each model slightly differs in the optimal solution it suggests, including the best tour and the total cost. Although each one of those proposed approaches uniquely contributes to a more adequate calculation of the jam regions and rush hours under vague and uncertain circumstances, yet it is hard to choose one as the unambiguously best solution. In our future work, we are eager to simulate those approaches on more complicated examples, with larger instances and to compare the results with other models, to test their capability and efficiency. Fuzzy sets The time-dependent traveling salesman problem Modeling of fuzzy rule-base algorithm for the time dependent traveling salesman problem Intuitionistic fuzzy model of traffic jam regions and rush hours for the time dependent traveling salesman problem Optimization of the time dependent traveling salesman problem using interval-valued intuitionistic fuzzy sets The Traveling Salesman Problem: A Computational Study Application of fuzzy algorithms for control of simple dynamic plant Comparison of the COG defuzzification technique and its variations to the GPA index Intuitionistic fuzzy sets On fuzzy sets and intuitionistic fuzzy sets Interval type-2 fuzzy logic systems made simple Type-2 fuzzy sets made simple Methods for aggregating interval-valued intuitionistic fuzzy information and their application to decision making Distances between interval-valued intuitionistic, fuzzy sets