Feifei Li, Dihan Cheng, Marios Hadjieleftheriou, George Kollios and Shang-Hua Teng

In *Proceedings of the 9th International Symposium on Spatial
and Temporal Databases (SSTD '05) * Angra dos Reis, Brazil, August 2005.

In this paper we discuss a new type of query in Spatial Databases,
called the Trip Planning Query (TPQ). Given a set of points of interest *P*
in space, where each point belongs to a specific category, a starting point *S*
and a destination point *E*, TPQ retrieves the best trip that starts at
*S*, passes through at least one point from each category, and ends at
*E*. For example, a driver traveling from Boston to Providence might want to stop
to a gas station, a bank and a post office on his way, and the goal is to provide him
with the best possible route (in terms of distance, traffic, road conditions, etc.).
The difficulty of this query lies in the existence of multiple choices per category.
In this paper, we study fast approximation algorithms for TPQ in a metric space.
We provide a number of approximation algorithms with approximation ratios that depend
on either the number of categories, the maximum number of points per category or both.
Therefore, for different instances of the problem, we can choose the algorithm with the best
approximation ratio, since they all run in polynomial time. Furthermore, we use
some of the proposed algorithms to derive efficient heuristics for large datasets
stored in external memory. Finally, we give an experimental evaluation of the
proposed algorithms using both synthetic and real datasets.

**1. California Road Network and Category Points**

California Road Network's Nodes (Node ID, Longitude, Latitude)

California Road Network's Edges (Edge ID, Start Node ID, End Node ID, L2 Distance)

California's Points of Interest With Original Category Name (Category Name,
Longitude, Latitude)

California's Points of Interest (Longitude, Latitude, Category ID)

Merge Points of Interest with Road Network--Map Format

Map Format in Detail:

For each edge:

Start Node ID, End Node ID, Edge Length, Number of Points on This Edge

For each point on this edge:

Category ID, Distance of This Point to the Start Node of This Edge

**
Note: ** A. The road network is obtained from: Digital Chart of the World Server (http://www.maproom.psu.edu/dcw/)

B. The category points are obtained from: U.S. Geological
Survey (http://www.usgs.gov/)

**2. San Francisco Road Network**

San Francisco Road Network's Nodes (Node ID, Normalized X Coordinate, Normalized Y Coordinate)

San Francisco Road Network's Edges (Edge ID, Start Node ID, End Node ID, L2 Distance)

**
Note: **Road network is from T. Brinkhoff: A framework for generating network-based moving objects.

**3. Road Network of North America (NA)**

North America Road Network's Nodes (Node ID, Normalized X Coordinate, Normalized Y Coordinate)

North America Road Network's Edges (Edge ID, Start Node ID, End Node ID, L2 Distance)

**Note: ** The road network is obtained from: Digital Chart of the World Server (http://www.maproom.psu.edu/dcw/)

**4. City of San Joaquin County (TG) Road Network**

TG Road Network's Nodes (Node ID, Normalized X Coordinate, Normalized Y Coordinate)

TG Road Network's Edges (Edge ID, Start Node ID, End Node ID, L2 Distance)

**
Note: ** Data is from T. Brinkhoff: A framework for generating network-based moving objects.

**5. City of Oldenburg (OL) Road Network**

OL Road Network's Nodes (Node ID, Normalized X Coordinate, Normalized Y Coordinate)

OL Road Network's Edges (Edge ID, Start Node ID, End Node ID, L2 Distance)

**
Note: **Road network is from T. Brinkhoff: A framework for generating network-based moving objects.

Example of Uniformly Generated Data on OL's Network