Traveling salesperson approximation algorithm for real road networks

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

Traveling salesperson approximation algorithm for real road networks

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

University of Calgary

Research output: Chapter in Book/Report/Conference proceeding › Book chapter › Research › peer-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 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

OpenUrl availability

Full text

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

Sharma, Ojaswa ; Mioc, Darka ; Anton, François et al. / Traveling salesperson approximation algorithm for real road networks. 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, 2006. (ISPRS book series Advances in Spatio-Temporal Analysis).

@inbook{08e7e8106aa845e89f2353efef7ffe2d,

title = "Traveling salesperson approximation algorithm for real road networks",

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",

author = "Ojaswa Sharma and Darka Mioc and Fran{\c c}ois Anton and Girija Dharmaraj",

year = "2006",

language = "English",

series = "ISPRS book series Advances in Spatio-Temporal Analysis",

booktitle = "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",

}

Traveling salesperson approximation algorithm for real road networks. / Sharma, Ojaswa; Mioc, Darka; Anton, François et al.

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, 2006. (ISPRS book series Advances in Spatio-Temporal Analysis).

Research output: Chapter in Book/Report/Conference proceeding › Book chapter › Research › peer-review

TY - CHAP

T1 - Traveling salesperson approximation algorithm for real road networks

AU - Sharma, Ojaswa

AU - Mioc, Darka

AU - Anton, François

AU - Dharmaraj, Girija

PY - 2006

Y1 - 2006

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

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

M3 - Book chapter

T3 - ISPRS book series Advances in Spatio-Temporal Analysis

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

PB - Taylor & Francis

ER -

Traveling salesperson approximation algorithm for real road networks

Abstract

OpenUrl availability

Fingerprint

Cite this