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


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


Dive into the research topics of 'Traveling salesperson approximation algorithm for real road networks'. Together they form a unique fingerprint.

Cite this