An application of the Novel Heuristic Dhouib-Matrix-TSP1
Souhail Dhouib*
Higher Institute of Industrial Management, Sfax University, Tunisia
*Corresponding author: Higher Institute of Industrial Management, Sfax University, Tunisia.
Article History
Received: November 04, 2021 Accepted: November 18, 2021 Published: November 18, 2021
Citation: Dhouib S. An application of the Novel Heuristic Dhouib-Matrix-TSP1. Int J Eng Tech & Inf. 2021;2(5):133‒135. DOI: 10.51626/ijeti.2021.02.00026
Abstract
This paper describes the deterministic column-row heuristic named Dhouib-Matrix- TSP1 (DM-TSP1) and presents a practical stepwise application on a practical example from the literature. The proposed DM-TSP1 is composed by four simple steps: 1) Finding the starting node 2) Selection by rows 3) Removal by columns 4) Generating cycle. The DM-TSP1 can rapidly and robustly generate an initial basic feasible solution just after n iterations (where n is the number of cities).
Keywords: Supply chain engineering; Transport engineering; Dhouib-matrix methods; Computer engineering; Industrial engineering; Information engineering; Software engineering
Background
The Traveling Salesman Problem (TSP) is one of the essential applied engineering problems where the objective is to optimize the shortest cycle between all cities. In this cycle each city is visited only once except the starting city which is visited twice (start from the first city and return to it).
In order to solve the TSP, we designed in [1] a deterministic robust heuristic entitled Dhouib- Matrix-TSP1 (DM-TSP1) which is based on several rules and statistical metric function (in this paper we use the mean function). Then in [2], we intended a stochastic version of the DM-TSP1 named Dhouib-Matrix-TSP2 (DM- TSP2) and we compared the deterministic heuristic DM-TSP1 to the stochastic heuristic DM-TSP2 in [3]. Moreover, we proved the performance of the DM-TSP1 to solve the TSP under uncertain environment: we solved the trapezoidal fuzzy TSP in [4], the octagonal fuzzy TSP in [5], the triangular fuzzy TSP in [6]. Furthermore, we demonstrated the robustness of the heuristic DM-TSP1 under neutrosophic domain: we optimized the case of TSP on single valued triangular neutrosophic numbers [7]. The DM-TSP1 is composed of four steps (Figure 1).
Figure 1: The four steps for the DM-TSP1.
Several other heuristics and metaheuristics are inspired from the concept of DM-TSP1 are under development such as our proposed heuristic in [8] for the Transportation Problem named Dhouib-Matrix-TP1.
Results
In order to explain the novel heuristic DM- TP1, a stepwise application is given on 5×5 distance matrix (Figure 2).
Figure 2: The 5×5 distance matrix for TSP.
Start by computing the average for each row and insert their values at the last column. Next, select the smallest (18.80) at row 3 and then find the minimal element 9 at position d34 (Figure 3).
Figure 3: Select the smallest mean value.
Hence, insert cities 3 and 4 into List-cities {3- 4} and discard columns 3 and 4 (see the red columns in Figure 4).
Figure 4: Discard columns 3 and 4.
Now, select the smallest element between rows 3 and 4 which is 9 at position d45, insert city 5 at the right (because city 5 is generated from city 4 which is at the right of the list) of List-cities {3-4-5} and discard column 5 (Figure 5).
Figure 5: Discard column 5.
Moreover, find the smallest element between rows 3 and 5 which is 25 at position d32, insert city 2 at the left (because city 3 is at the left of the list) of List-cities {2-3-4-5} and discard column 2 (Figure 6).
Figure 6: Discard column 2.
Finally, select the smallest element between rows 2 and 5 which is 37 at position d21, insert city 1 at the left of List-cities {1-2-3-4-5} and discard column 1 (Figure 7).
Figure 7: Discard column 1.
In order to generate a cycle from List-cities {1- 2-3-4-5}, you need to add just city 1 at the end of the list {1-2-3-4-5-1}.
Discussion
The novel DM-TSP1 finds rapidly the optimal solution 125 in just 5 iterations (where 5 represents the number of cities) (Figure 8). Depicts the geographical representation of the generated solution. The DM-TSP1 is a robust heuristic, in this paper we used the mean metric however any other statistical metric can be used.
Figure 8: The generated solution by the DM- TSP1.
Conclusion
This paper describes the novel column-row heuristic entitled Dhouib-Matrix- TSP1. This heuristic is based on several rules in order to generate a good initial basic feasible solution in polynomial computational time. Further directions will be oriented towards the application of the heuristic Dhouib-Matrix-TSP1 multi-start structure to solve Multi-objectives Travelling Salesman Problems.
References
- Dhouib S (2021) A New Column-Row Method for Traveling Salesman Problem: The Dhouib-Matrix-TSP1. International Journal of Recent Engineering Science 8(1): 6-10.
- Dhouib S (2021) Stochastic Column- Row Method for Travelling Salesman Problem: The Dhouib-Matrix-TSP2. International Journal of Engineering Research & Technology 10(3): 524-527.
- Dhouib S (2021) Minimizing the Total Distance for the Supply Chain Problem Using Dhouib-Matrix-TSP2 Method. International Journal of Advanced Research in Engineering and Technology 12(5): 1-12.
- Dhouib Sa, Dhouib S (2021) Optimizing the Trapezoidal Fuzzy Travelling Salesman Problem Through Dhouib-Matrix-TSP1 Method Based on Magnitude Technique. International Journal of Scientific Research in Mathematical and Statistical Sciences 8(4): 01-04.
- Miledi M, Dhouib S, Loukil T (2021) Dhouib-Matrix-TSP1 Method to Optimize Octagonal Fuzzy Travelling Salesman Problem Using α-Cut Technique. International Journal of Computer and Information Technology 10(3): 130-133.
- Dhouib S (2021) Haar Dhouib-Matrix- TSP1 Method to Solve Triangular Fuzzy Travelling Salesman Problem. Research Journal of Recent Sciences 10(5): 18-20.
- Dhouib S (2021) Optimization of Travelling Salesman Problem on Single Valued Triangular Neutrosophic Number using Dhouib-Matrix-TSP1 Heuristic. International Journal of Engineering 34(12): 1-6.
- Dhouib S (2021) A Novel Heuristic for the Transportation Problem: Dhouib-Matrix-TP1. International Journal of Recent Engineering Science 8(4): 1-5.
