OptiRoute for Windows Phone 7

Last week my latest Windows Phone 7 app got certified and became available for download on the Windows Phone App Store.

OptiRoute is a route optimization application, that “attempts” to come up with the shortest route around a set of locations that you enter. The reason that I say “attempts” is that OptiRoute uses a heuristic that allows it run very fast, but in doing so, there are cases where it may not find the most optimal route (more on that later – Check the technical background section). (The way I deal with the cases, is that I provide you with functionality that allows you to customize the route after it has been optimized)

Background:

When I was searching for a home to buy, I always found it hard to come up with an optimal route to visit all the homes in my list. I knew about computer algorithms like the travelling sales man problem, but could not find any implementations for use on a mobile platform (at that time I had an iPhone). One of the biggest problems with finding an optimal route around a set of locations is that its computationally intensive. And when you take into account that you are working on a mobile platform, every resource becomes that much more expensive to use.

When Microsoft launched its “30 to launch” initiative, I decided to port some early work I had done as a web-app with routing to the Windows Phone platform – OptiRoute is the result of that initiative.

The OptiRoute UI:

Welcome screen:

The first time you load up OptiRoute you will be presented with a welcome screen, that gives you a brief overview of the functions available within OptiRoute.

In addition to giving you a quick introduction to the main UI, this screen also allows you to load sample locations to check out the route optimization software (you need to scroll to the bottom of the page to view the load button):

Once you tap the “Load Sample Data” button, you can close out of the “welcome screen” and you will be presented the list of locations. (Tip: the welcome screen is only shown the first time you open OptiRoute. If you want to see it again, you can do so via the help screen). The screen showing you the list of locations is your “Home Screen”. You manage your route via this page.

Home Page (location list) and viewing your route:

Lets take a look at the route, without performing optimization. Click on the “Map Route” button . This will take you to the “Route Viewer” screen with a map of the route as well as detailed information on the route that you need to take.

By tapping “”, you can change the map type from “road” to “aerial”, as well as hide or show the detailed route information. Rotating your phone will show the map in full-screen:

Click the “back button” to return to the home screen.

Optimizing your route:

Lets optimize the route by clicking the “Optimize Route” button . Now when you click on the “Map Route” button, you will find that the route has been optimized:

Route before optimization	Route after optimization!

Customizing your Route:

Now what if you want to change the starting location? Go back to the home-screen and tap and hold the location you wish to make the start of your route until a context menu is displayed:

Tapping on the “Set as Start” button will make that location the starting point in your route. As you can see from the image above, this same context menu also provides you a way to delete locations from your route.

What if you want to manually change the route? You can do this using the “Reorder handles” that appear to the right of the location (highlighted in red in the image below):

Simply tap, hold and drag that location to the correct place in the route list.

Tip: “Map Route” button displays the route and performs the route based on the order of the locations on the home screen. So if you don’t “optimize” your route, you will be presented the route that reflects the order of the locations shown on the home page. This makes OptiRoute a handy tool for viewing your routes without even using the route optimizer.

Searching for locations:

You can add locations to your route via the “Search” screen. Version 1.0 of Optiroute only supports searching for addresses and points of interest (I plan on adding POIs in a later release).

Tap the “Add” button to visit the “Search” page.

Type in an address and tap the go button to find that location:

To add the location to your route, tap on the pushpin that represents the address you wish to visit and then tap the “Select” button. This will add the selected location to your route and take you back to the “home” screen.

Tip: If you wish to add your current location, tap the “Current Location” button .

Screen shots:

Here are some screenshots taken of the different screens within the application:

Technical background:

Route optimization has many different names (eg: Travelling Sales Man problem, etc.). If you have studied computer algorithms then you may know that the travelling sales man problem (TSP) is NP-Complete. OptiRoute uses a heuristic where it lays out all the locations on a grid, divides the grid into 4 quadrants and attempts to visit all the locations within a quadrant before moving on to the next quadrant. At the same time that its trying to visit each location, it attempts to not criss-cross the lines. The algorithm that I use is based on Sierpinski’s space filling curve (check out the video below to see how it fills 4 separate sections of the rectangle, filling each section before moving on to the next)

Sierpinski Space Filling Curve Animation (I created this video many years back and the routing algorithm is based off of this fractal)

Why is the heuristic important?

Determining the actual travelling route (the driving directions) between any 2 locations is an expensive operation. This is especially true on a phone, where bandwidth is limited (and you typically need to use a web-service to determine the driving directions between any pair of locations). In addition, if you had 10 locations to visit and you attempted to brute force find the optimal route, you would need to find out the distance between all 10 locations (which amounts to 45 separate route calculations: n(n-1)/2 ). 

It is generally better to come up with a general idea of your route and then determine the driving directions between each pair of locations in that route (in which case you would need only 10 route calculations – a far cry from the 45 separate routes needed by the brute force implementation). Using the Sierpinski curve, I am able to determine the general route to visit the different locations (this is done on the phone itself) and then I use Bing’s mapping service to find out the actual route between each pair of locations as determined by my algorithm.

The idea of using a space filling curve to determine routing is not something that I invented and I have read about it in papers earlier. Mine is probably the first implementation of such a routing algorithm on the Windows phone platform and maybe any mobile platform.

Note: I had created a silverlight based app a long time ago based on a similar idea. That site has been down for a long time. But if you are interested in reading about it, check out: http://blog.aggregatedintelligence.com/2009/06/optiroute.html

When you may not get the optimal route:

The reason that you may not always get an optimal route is that while performing route optimization the algorithm is not looking at the “travelling distance”, but just the straight line distance between the different locations. This results in sometimes less than optimal routes when one-way streets are involved, or any other impediments are added to the actual route. In addition, the algorithm does not take into account traffic conditions and hence may not be able to find the route with the shortest travel time. But these problems typically occur only when all the locations to visit are concentrated in a small area (eg: downtown city center) and normally do not affect the route when routing on a larger scale.