### 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

Keyword: Shortest path,Optimal tour,Christofides algorithm,Traveling Salespersons Problem,Transportation network,GIS

Original language | English |
---|---|

Title of host publication | 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 |

Publisher | Taylor & Francis |

Publication date | 2006 |

Publication status | Published - 2006 |

Externally published | Yes |

Series | ISPRS 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