Route Optimization in Bing Maps powered by OnTerra’s free Stop Optimization Service

OnTerra is a Microsoft Partner specialized on tailored Bing Maps solutions and focussing on but not limited to tracking and fleet management. Recently they launched a free beta version of a Stop Optimization Service. The service allows you to send an unlimited list of stops for your route and receive a string with the order of the stops optimized for the shortest driving distance. Let’s have a quick look at how it works:

Bing Maps supports out-of-the-box Multi-Waypoint Routing for up to 25 stops through the method VEMap.GetDirections. However, the routing algorithm processes the stops always in the order in which they appear in the array of locations. If we want to start for example a trip in the Microsoft Office in Reading and want to visit Swindon, Oxford, Maidenhead and Newbury before we return to the Microsoft office we have to know in which order we want to visit these cities. If we just send the list in the order mentioned above it will guide us from one location to the next in exactly this order and come up with a route that is 185 miles long and takes about 3 hours and 20 minutes of drive time.

image

The free OnTerra Stop Optimization Service figures out in which order we should drive for the shortest distance. In the example above it will suggest that we go to Maidenhead first, then Oxford, Swindon and Newbury. This will save us 45 miles and about 40 minutes of drive time.

image

That’s not bad at all but if you would like to use it for example as a dispatcher in a fleet management application you also need to consider the times when you can make a pickup or a delivery, you may want to optimize for shortest time rather than shortest distance or you may need to consider height and weight restrictions that apply to your trucks. This is not part of the free service but in addition to the free stop optimization, OnTerra also offers such advanced features for a fee. If you are interested in this type of advanced service contact routeopt@onterrasys.com for more details.

To use the free stop optimization service you will need to register and apply for a token. It requires 3 parameters:

  1. the locations which we want to optimize as a string, The string contains a label for the location and the latitude and longitude separated by a comma. Multiple locations are separated by a ‘#’.
  2. a Boolean parameter that indicates weather we do a roundtrip or a one-way trip
  3. our token

You see that we need to geocode the locations before we send them to the stop optimization service. In the sample application above I use the Bing Maps AJAX control and use the callback function for the VEMap.Find-method to concatenate a string with the locations as expected by the stop optimization service, e.g. “txtStop1,51.461179,-0.925943#txtStop2,51.561765,-1.781815#txtStop3,51.522375,-0.727256#txtStop4,51.405876,-1.325891#txtStop5,51.756205,-1.259490”.

Now here is one thing so consider: The optimization service splits the locations-string whenever it finds the character ‘#’. Unfortunately there appears to be a bug(?) which doesn’t process the string correctly when you work with the full number of decimal digits that comes back from the Bing Maps geocoder. In order to work around this bug(?) we can truncate the number of decimal digits to 6. This does actually not have a noticeable impact on the precision of the result but solves our problem.

Once we have our last location we call a JavaScript-function StopOpt which actually creates an AJAX-call

//Build String for Route Optimization
function AppendLocations(layer, resultsArray, places, hasMore, veErrorMessage) {
    i = i + 1;
    if (locations.length > 0) {
        locations=locations+"#"
    }
    locations = locations + "txtStop" + i + "," 
+ places[0].LatLong.Latitude.toFixed(6) + ","
+ places[0].LatLong.Longitude.toFixed(6); if (i == numStops) { StopOpt(); } }

The AJAX-call goes to a web handler which will call the stop optimization service and hands over the locations-string as well as a parameter that indicates if we’re doing a roundtrip or a one-way-trip. The optimized order of the result is received as a string and we process it a bit before we call the VEMap.GetDirections method.

function StopOpt() {
    //Build URL to call the server
    var url = "./06-StopOpt.ashx?";
    url += "locations=" + locations;

    if (document.getElementById("cbRoundtrip").checked == true) {
        url += "&roundtrip=true"
    }
    else {
        url += "&roundtrip=false"
    }

    //Get the appropriate XMLHTTP object for the browser
    var xmlhttp = GetXmlHttp();

    //if we have a valid XMLHTTP object
    if (xmlhttp) {
        xmlhttp.open("GET", url, true); // varAsynx = true

        //set the callback
        xmlhttp.onreadystatechange = function() {
            if (xmlhttp.readyState == 4) //4 is a success
            {
                //web service returns the optimized order of the stops
                var result = xmlhttp.responseText
                var stopArray = result.split(" >> ");
                var stops = new Array();
                var order = "Order (Optimized):<br>";
                for (var i = 0; i < stopArray.length; ++i) {
                    order = order + document.getElementById(stopArray[i]).value + "<br>";
                    stops.push(document.getElementById(stopArray[i]).value);
                }
                if (document.getElementById("cbRoundtrip").checked == true) {
                    order = order + document.getElementById("txtStop1").value;
                    stops.push(document.getElementById("txtStop1").value)
                }

                var options = new VERouteOptions;
                options.RouteCallback = DistTime;

                document.getElementById("pOrder").innerHTML = order;

                map.GetDirections(stops, options);
            }
        }
        xmlhttp.send(null);
    }
}

Finally, here is our web handler that we have been calling with our AJAX-call and which in turn calls the OnTerra stop optimization service:

Imports System.Web
Imports System.Web.Services
Imports BM_Azure_01_WebRole.OnTerra

Public Class _06_StopOpt
    Implements System.Web.IHttpHandler

    Sub ProcessRequest(ByVal context As HttpContext) Implements IHttpHandler.ProcessRequest
        'Get the URL-Parameters
        Dim locations As String = context.Request.Params("locations")
        Dim roundTrip As Boolean = CBool(context.Request.Params("roundtrip"))

        Dim token As String = "YOUR TOKEN"

        Dim svcOT As New OnTerra.OnTerraStopOptClient("basicEndPoint")
        Dim output As String
        output = svcOT.GetStopOpt(locations, roundTrip, token)

        context.Response.ContentType = "text/plain"
        context.Response.Write(output)
    End Sub

    ReadOnly Property IsReusable() As Boolean Implements IHttpHandler.IsReusable
        Get
            Return False
        End Get
    End Property

End Class

Advertisements
This entry was posted in Bing Maps. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s