A further enhancement of the ashay dharwadker's algorithm in finding hamiltonian cycle with application for food delivery service

ABSTRACT: Hamiltonian Cycle came from the idea and invention of Icosian Game by William Rowan Hamilton. The aim of the game to visit every vertex once on a Dodecahedron graph and the ending point must be starting point forming a cycle. This problem is considered as NP-complete that is known to be theoretically and computationally difficult to be solve. Studying different graphs, and analysing the original and existing algorithm, the researchers found three problems on the existing algorithm in terms of finding Halmitonian cycles. The researchers formulated the three specific objectives based on the problems observed: 1. To improve the existing process in evaluating the nearest vertex connected to Vi in order to produce better and more effective Hamiltonian cycle; 2. To modify and improve the process and condition on the existing algorithm for cases of having exactly equal vertices to produce more optimal and better results and; 3. To eliminate the chances of not visiting all the vertices which are not connected to each other. This study applied the descriptive type of research and used surveying and interviewing as methods of gathering data from the delivery boy from different food establishments, The data gathered help and support the idea and theory formed on the study. The researchers analyse ad conducted intensive research in formulating the enhanced algorithm in order to solve the stated problems and meet the objectives. For the first problem and objective, the researchers improved the evaluation process by adding searching the nearest two pints (Vi and Vj). The researchers also added another category called “load” wherein the user will specify the load on a given vertex for the purpose of choosing the better cycle among the cycle with same distance. For the second problem and objective, the enhanced algorithm was modified that it will apply the nearest neighbour algorithm to the vertices to create path from each vertex to a particular vertex where it was equal. Alternative routes are also displayed for those cycle with equal distance on the result that was shown by the enhanced algorithm. For the third problem and objective, the researchers added a “verification process” on the last 2 parts of the algorithm wherein it will try all vertices as the starting vertex and apply the whole algorithm again until it tries all vertices as starting vertex. In the end, the algorithm will choose the path with least weight and produce the solution starting on the original home vertex. Existing and enhanced algorithm was compared using the simulator and a food delivery route finder application were developed by using the formulated enhanced algorithm. Researchers recommendations were to include time relations or running time for enhancing the algorithm, improve the implementation of the food delivery application and consider more areas on the application.

5

Filipiniana

5