Traveling salesperson approximation algorithm for real road networks

Ojaswa Sharma, Darka Mioc, François Anton, Girija Dharmaraj

Research output: Chapter in Book/Report/Conference proceedingBook chapterResearchpeer-review

Abstract

Traveling salespersons problem (TSP) is one of the unsolved problems of the day that carry significant value to the transportation networks. The exact solution of a Traveling salespersons problem is not feasible. There are some good approximation algorithms that can provide an approximate solution. Here, we propose a method to extend the conventional Traveling salespersons problem to transportation networks where the travel plan can be optimized within the Geospatial Information System. We also propose an optimized web based implementation scheme that gives a faster response to the route queries. In modern geographic informations systems, such a web accessible route query system can be very useful.
Keyword: Shortest path,Optimal tour,Christofides algorithm,Traveling Salespersons Problem,Transportation network,GIS
Original languageEnglish
Title of host publicationISPRS WG II/1,2,7, VII/6 International Symposium on Spatio-temporal Modeling, Spatial Reasoning, Spatial Analysis, Data Mining and Data Fusion (STM 2005), Beijing, China
PublisherTaylor & Francis
Publication date2006
Publication statusPublished - 2006
Externally publishedYes
SeriesISPRS book series Advances in Spatio-Temporal Analysis

Cite this

Sharma, O., Mioc, D., Anton, F., & Dharmaraj, G. (2006). Traveling salesperson approximation algorithm for real road networks. In ISPRS WG II/1,2,7, VII/6 International Symposium on Spatio-temporal Modeling, Spatial Reasoning, Spatial Analysis, Data Mining and Data Fusion (STM 2005), Beijing, China Taylor & Francis. ISPRS book series Advances in Spatio-Temporal Analysis