Optimisation Algorithms for Compiling Travel Salesman Problem

Artificial intelligence is becoming a part of daily life as technology rapidly grows. So, how do people instruct the computer to finish the tasks assigned? As we know, computers cannot understand human languages. Algorithms are generally used for mathematical calculations, data processing and other operations related to computing.

In the case of airlines, the airline industry wishes they could navigate the shortest path to travel from one country to another and minimise the cost of petrol and time. They can optimise the fuel efficiently by carrying the fuel required for the shortest route. Air navigation is the way to get accurate navigation for the airline industry. Air navigation is proficient with several approaches. The technique or structure used for navigating an airspace system depends on the flight category, including Visual Flight Rules or Instrument Flight Rules (VFR or IFR), in which navigation structures are connected to the planes and navigation structures are accessible in a firm zone. It is similar to the Travelling Salesman Problem (TSP), where a salesman has to visit some cities without repeating visiting the same cities, hoping it can reduce the time required for his trip. It is frequently used in primary vehicles directing resolution issues. Throughout the study, the authors can know by reflecting on TSP to solve the airline’s navigation due to the precise requirements.

There are many types of searching and optimisation algorithms. In this study, the authors are going to compare Ant Colony Optimization (ACO), Hill Climbing Algorithm (HCA), Nearest Neighbor Algorithm (NNA), Recursive Brute Force Algorithm (RBFA) as well as Simulated Annealing (SAA) to generate the results which algorithm will be the best optimisation algorithm to solve the TSP.

Tools & Technique

The authors conduct the research using five algorithms: ACA, HCA, NNA, BFA and SSA. The study’s objective is to find the best results between these five algorithms, which one can see as the shortest route for solving the TSP. The authors used Java programming to run the algorithms to solve TSP. Instead of using Python and MATLAB, the authors used Java to solve TSP, and the results generated by Java are the fastest compared between these three languages. The IDE, the authors, used is IntelliJ. The benefits of IntelliJ provided the authors with the ability to conduct the research appropriately. The authors derived the five algorithms from online tutorials solving the TSP by combining several algorithms with coding in Java, inserting the latitude and longitude of various cities, and generating it with the platform IntelliJ. The authors investigate and research the TSP and then get the idea and make decisions on implementing the five algorithms using Java to generate the result of the best route to solve the TSP. Other researchers primarily compared only two or three algorithms at once, but the authors managed to work on five algorithms for the best results.

Hardware Configuration

The hardware the authors used to conduct this research is two PCs to run the algorithms in Java on TSP as five algorithms were used: ACO, HCA, NNA, BFA and SAA. A PC had been used with the operating system as the latest Windows 10, CPU third generation of Intel i7, 8GB RAM, 1TB Hard Disk Drive with intel graphic card 630 to run the five algorithms in the platform IntelliJ. Besides that, the authors also used another PC with the latest operating system as Windows 10, CPU eighth generation of Intel i7, 16GB RAM, 1 TB Solid-state Drive with graphic card GTX 1070 to run the algorithms on the same platform to test for the time on generating the result. The authors found that the time to create the result is identical no matter which PC used the same Java platform.

Implementation of ACO

ACO is a meta-heuristic method to solve combinatorial issues like the travel salesman problem, which Darigo introduced. The advantage of ACO is getting a confident response for fast finding the best result. In the results of ACO, no matter what data from TSP is inserted in it, it always shows the shortest route in a short time. ACO is a very effective algorithm to solve the Traveling Salesman Problem and the similar problem. It can be utilised in the airline’s navigation that figure out the shortest route travel from this country to another. It also can be utilised in dynamic applications such as Global Positioning System (GPS) or any application required to navigate the routes. Some disadvantages are that the orders of ACO make a spontaneous decision and the probability distribution changes by repetition. It will get the shortest route for the result but will not generate the same route every time.

Implementation of HCA

For the HCA, it is simple and effective to generate the result. HCA endlessly travels the route of cumulative value. For the advantages, HCA is helpful in work scheduling, programmed programming, circuit planning, vehicle directing and the portfolio of the executives. It is likewise beneficial to take care of unadulterated improvement issues where the goal is to locate the best state as indicated by the goal work. It requires considerably fewer conditions than other pursuit systems. The disadvantage of HCA is an inquiry that remaining parts on HCA are whether this hill is the peak hill conceivable. Tragically, moving along without any broader investigation, this inquiry cannot be replied to. This method works as it utilises nearby data; that is the reason it tends to be tricked. The calculation does not keep up a search tree, so the present hub information structure needs to record the state and its target work esteem. It expects that nearby improvement will prompt worldwide improvement.

Implementation of NNA

NNA is a non-parametric algorithm meaning that there are expectations to meet for the implementation in NNA. NNA was developed to recognise a pattern and apply it to organisational responsibilities. The advantage of NNA is that it is simple and easy to understand the way to implement it in the problem-solving procedure. The disadvantage of NNA is that it may be simple to apply but if the dataset raises competence or speed of algorithm failures rapidly. Another matter with NNA is to select the optimum number of neighbours to reflect through categorising the new information entry. NNA performs better with a small number of input variables, but as the numbers of variables rise, NNA struggles to expect the output of new information argument.

Implementation of BFA

BFA is known as naïve and the most straightforward algorithm usually used in pattern searching. The advantage of the BFA is that it has extensive applicability and is simple, which can solve optimisation problems such as Travel Salesman Problem. At the same time, BFA represents a practical algorithm for several significant issues like searching, matching, and matrix development. BFA is a typical algorithm developed for solving simple computational issues like product and amount of n numbers and getting the result of maximum or minimum in the list. When it comes to the disadvantages, BFA represents a seldom effective algorithm. Sometimes, the BFA is unsatisfactorily slow in generating the result. It is known as applicable or inventive as other strategy methods.

Implementation of SAA

SAA is a stochastic search technique that emulates the physical annealing of compact form, discovering resolution to syndicate optimise issues. Its significant advantages over additional local search methods are flexibility, and it can approach worldwide optimality. The algorithm is practical because it does not depend on any obstructive properties of the model. For the disadvantages, there is precise adjustment among the quality of the resolutions and the time compulsory to figure them. The modifying work required to explain different modules of restrictions and fine-tune the algorithm’s constraints can be moderately delicate. The accuracy of the information applied for the operation of SAA can take an actual result upon the value of the result.

Results

The distance between each city is identified by its latitude and longitude coordinates. It is crucial for use in navigation. The Haversine formula is used to calculate distances between cities. The Haversine formula calculates the shortest distance between two points on a sphere using their latitudes and longitudes measured along the surface. The authors implemented the ACA, HCA, NNA, BFA and SSA into the Java Platform. Of all the algorithms, ACO is the most efficient algorithm for TSP. The author used the same number of US-based cities to make the trials fair.

Conclusion

In conclusion, the authors found that ACO is the most optimized algorithm for TSP as it achieves the shortest distance in the shortest time compared to all other algorithms. ACO, with the artificial ant, found the shortest route by travelling cities by cities in only one way without repeating travel to the same cities. The reason for conducting this research is because this will help future researchers to utilize the algorithm. In this journal, the author compared five algorithms, and researchers will know which one to choose for solving TSP and which one not to choose based on the situation and resources. Also, based on the results that the authors found by using Java for comparing algorithms above, it is helpful for the researchers for the relevant research about the comparison algorithms with Java. Thus, it saves time on research based on comparing the algorithms with Java to solve the TSP.