A Comparison Between Optimization Heuristics of the Best Path Problem Applied to S-Route

摘要

The paper contextualizes the traveling salesman problem applied to S-Route, a system developed based upon the ant colony approach and used by the Analysis and Research in Petroleum Analytical Chemistry Laboratory - UFMA in order to generate routes in the process of fuel collection. Some heuristic approaches (constructive and improvement), such as Nearest Neighbor, Clarke and Wright, Mole and Jameson, 2-Opt, 3-Opt and Opt-K, are conceptualized and compared to the Ant Colony. Comparisons between the heuristics, and in some cases the combination of the constructive and improvement occurred through the S-TSP system. Like S-Route, the application was developed in a web environment and integrated with Google Maps API in order to facilitate visualization of the results from georeferenced data. Thus, the essay aims at identifying amongst the listed and/or combined heuristics, the best one regarding cost/benefit to be utilized by S-Route.