Home // GEOProcessing 2013, The Fifth International Conference on Advanced Geographic Information Systems, Applications, and Services // View article

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

Authors:
Adriano dos Santos Rêgo
Alex Barradas
Sofiani Labidi
Nilson Costa

Keywords: Traveling salesman problem; S-Route; Fuel Quality Monitoring; ANP.

Abstract:
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.

Pages: 172 to 177

Copyright: Copyright (c) IARIA, 2013

Publication date: February 24, 2013

Published in: conference

ISSN: 2308-393X

ISBN: 978-1-61208-251-6

Location: Nice, France

Dates: from February 24, 2013 to March 1, 2013