ClearPath

A new smart phone app helps navigate driving with an accurate travel time estimation.

Time and energy are the most important commodities of the 21st century – and traffic congestion wastes both. Our mission is to help drivers find the best path to their destination and avoid unnecessary delays and expenses. We accomplish this by using "predicted traffic patterns" computed based on 3 years of historical traffic sensor data. Cleaparth also adjusts the predicted traffic patterns in real-time by taking into account the travel-delays caused by weather and accidents.

Clearpath is a spin-off company from University of Southern California. The technology behind ClearPath is a result of more than 10 years of research and protected by 3 patents.

Experimental results show that Clearpath yields 18% travel-time savings over Google Map's paths, and travel - time accuracy is 92%. ClearPath received more than $2 million research funding in the last 3 years from variety of industry and federal agencies.

Navteq

Demo:

This is the pattern I created from the data of sensors I matched, I filled the missing data from near related sensor or history data.

• Blue: speed < 10
• Red: speed >= 10 && speed < 25
• Yellow: speed >= 25 && speed < 50
• Green: speed >= 50

Manual:

1) CA GNDEMO Process:

In PatternGeneration Project:

• input/CAInputFileGeneration
• (Optional) output/CAOutputKMLGeneration to generate kml
• pattern/CAAdjListPattern

2) Clean Data Process:

In PatternGeneration Project:

• input/InputFileGeneration

    writeAverageCube
    readAverageCube(i, 0);
    changeInterval();
    writeAverage15Cube(i, 0);
    renameAverageFile(i, 0);
  

• process/DataClean

• output/OutputDatabaseGeneration

3) AdjList Create Process:

In ArterialPatternGeneration_shireesh Project:

• GetAverageSpeedForArterials1to5New
• GetAverageSpeedForHighways
• CreateListForArterials1to5New
• CreateListForHighways1to5New
• CreateAdjList1to5New

OpenStreetMap

Demo:

This is map near our campus I fetched from OSM Project and converted it to our project's format. And I cleaned all the shape, building, barrier,etc which cannot be used for routing.

Bidirectional Hierarchy Searching:

1) Introduction:

1. From source and destination to perform forward searching and reverse searching simultaneously.
2. Forward searching is based on time dependent A* searching, but when it enter the highway, it will keep on highway.
3. Reverse searching is based on lower bound A* searching, it will also keep on highway when it hit the highway entrance.
4. When forward searching and reverse searching encounter on the highway, we will find a path.
5. The mechanism of hierarchy(keep on highway) will reduce the searching space and lead to less response time.
6. By the mechanism of bidirectional search, we do not worry about finding highway entrance and highway exit.

2) A* searching vs BH searching

Chose two long distance nodes in Los Angeles and perform A* routing, Bidirectional Hierarchy routing and compare.

3) Reference

• [1] Sebastian Knopp, Peter Sanders, Dominik Schultes and Frank SchulzFast. Computation of Distance Tables using Highway Hierarchies, 2006.

Manual:

1) put your "map.osm" in the "file" folder of the project

2) osm2wkt/Osm2wkt

this step will get rid of the none-routable path, and please press "N" when it asked for fixCompleteness.

• read the data from OSM file
• get rid of unroutable data
• generate xxx.wkts file

3) controller/OSMInputFileGeneration

• read the data from OSM file
• generate xxx_node.csv and xxx_way.csv from data

4) controller/OSMOutputFileGeneration

• read the data from xxx_node.csv and xxx_way.csv
• according xxx.wkts, overwrite xxx_node.csv and xxx_way.csv

5) controller/OSMDivideWayToEdge

• divide the long way to seperate edges based on intersect

6) controller/OSMGenerateKML(Optional)

• generate edge kml
• generate node kml

7) controller/OSMGenerateAdjList

• generate xxx_adjlist.csv file

All the preprocessing steps (1~7) can be done in the controller/OSMGenerateAll.

8) controller/OSMRouting

• using A* algorithm for path routing
• using A* algorithm with fibonacci heap for path routing
• using bidirectional hierarchy routing algorithm for path routing
• show turn by turn information

9) test/CompareTdspTdspHTimeCost

• compare the response time and cost time between A* algorithm and hierarchy routing algorithm

10) test/AnalyzeTravelTimeMatrix

• calculate the travel time based on matrix data