Background: JAVA Interactive Routing for Minneapolis

This sheet contains background information regarding the WebRoute project at the University of Minnesota's Spatial Database Laboratory.

What Is Java?

Java is an object-oriented interpreted programming language allowing the execution of interactive software across computer networks, allowing a single program to be run different platforms. Using Java, computation may be distributed across many machines, lowering the load on a single machine.

Experiences with Java

Java was chosen to develop our WebRoute software since it add interactivity to web pages, unlike HTML and cgi. The major findings related to route computation using Java are that for a single route request, the server performs the computation faster than the client. However, route computation on the client computer may be attractive if the number of route requests is very large.

After programming in Java, we feel that the interactivity that Java brings to the Internet make it a key component for the continued growth and usefulness of digital information. Java allowed us to bring our routing work to a large audience on the Web. However, improvements are possible in the areas of GUI-building and security.

What are Advanced Traveler Information Systems and Route Planning?

Estimates made by government agencies show that approximately 6 percent of all driving time in the U.S. is due to an incorrect choice of routes. Advanced Traveler Information Systems (ATIS) assist travelers with planning, perception, analysis and decision making to improve the convenience, safety and efficiency of travel. Route planning is an essential component of ATIS, aiding travelers in choosing the optimal path to their destinations in terms of travel distance, travel time and other criteria.

A critical component of routing service is a complete and accurate road-map suited for navigation. Unfortunately, navigation quality road-maps are not available for most of Minnesota. We plan to use WebRoute to evaluate the available road-map for the Twin-Cities metro-area with the help of commuters. WebRoute allows commuters to select their source and destination and computes a route based on that information. Commuters will then provide comments about the quality of the computed route to help evaluate the underlying road-map.

The system currently features an interactive routing environment where the user enters a source and destination and a shortest travel distance path is computed. Only major roads in Minneapolis are considered (one-in-three roads) and not all road names are accurate (entered by hand). Future work will involve accounting for current incidents, congestions and routing based on historical travel times. We will also investigate how routing algorithms scale on a large road-map since the metro area map has 250,000 road segments while the Minneapolis map has 3000 road segments.

Publications Related to ATIS

  1. Proceedings of the National Conference on Intelligent Transportation Systems, April 14-18, 1996, Houston.
  2. IEEE International Conference on Data Engineering, 1993
These works are a comparison of main-memory and database routing algorithms
  1. IEEE Conference on Data Engineering, 1995
This work deals with the efficient storage and retrieval of very large road maps

Authors

This software was developed by Andrew Fetterer, Brajesh Goyal, and Nisha Agarwal, who are graduate researchers in the Spatial Database Laboratory at the Computer Science Department in the University of Minnesota under the supervision of Professor Shashi Shekhar. The road-map evaluation project is sponsored by the Intelligent Transportation Institute and the Guidestar Project at the Minnesota Department of Transportation.