Google directions route optimization

3
votes

Google as an API to calculate the route between some origin and destination and there's an additional parameter called waypoints (middle route stops) and you can specify you want the route to be optimized, so the final directions will be an optimizing route passing by all the waypoints.

API: https://developers.google.com/maps/documentation/directions/#Waypoints

Is there any way to optimize a route so it optimizes not only the passage through the waypoints but also the origin and destination? Google only optimizes the waypoints, the origin and destination remain static but what if it also said something like "you should start your route here and go through these locations in order and this will be the optimized route"

1
apigoogle-mapsoptimizationdirections
Do you mean like an optimal route for delivering post; no matter where you start of finish? What do you call optimal? Are you talking about the minimum distance, or anything else? – Emmanuel Delay
@EmmanuelDelay, exactly, no start/finish and it returns the shortest path (optimal) – andrepcg

1 Answers

0
votes

This is not really an answer to the question, but it might help you. I put the locations in sortable boxes (jQuery-UI). So you can easily change the order (also the start and end) and check again.

Optimizing routing is not easy. I don't see any obvious solution. You might have to use algorithms like Dijkstra.

If anyone has suggestion; they are welcome.

<!DOCTYPE html>
<html>
  <head>
    <title></title>
    <meta name="viewport" content="initial-scale=1.0, user-scalable=no">
    <meta charset="utf-8">
    <link rel="stylesheet" href="//ajax.googleapis.com/ajax/libs/jqueryui/1.11.2/themes/smoothness/jquery-ui.css" />
    <style>
      #map-canvas {
        height: 500px;
        width: 48%;
        float: left;
        margin: 0px;
        padding: 0px
      }
      ul.sortable {
        height: 500px;
        width: 48%;
        float: left;
        overflow-y: auto;
      }
      ul.sortable li {
        border: 1px solid #eee;
        margin: 2px;
        cursor: pointer;
      }
    </style>
    <script src="https://maps.googleapis.com/maps/api/js?v=3.exp"></script>
    <script src="http://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
    <script src="//ajax.googleapis.com/ajax/libs/jqueryui/1.11.2/jquery-ui.min.js"></script>
    <script>

    // list of some locations in Brussels
    var locations = [
      {lat: 50.8949444353626, lng: 4.34153383970260, title: 'Atomium'},
      {lat: 50.8224796094648, lng: 4.39153021574020, title: 'VUB'},
      {lat: 50.8348811096048, lng: 4.29784601926803, title: 'RSCA stadion'},
      {lat: 50.8471595652635, lng: 4.34852904081344, title: 'AB'},
      {lat: 50.8390463848631, lng: 4.37321072816848, title: 'European parliament'},
    ];
    var locationsOrdered = [];

    // generates the <li> items
    function generateListItems(items) {
      var content='';
      for(var i=0; i<items.length; i++) {
        content += '<li data-id="' + i + '">' + items[i].title + '</li>';
      }
      return content;
    }

    var map;
    function initialize() {
      directionsDisplay = new google.maps.DirectionsRenderer();
      // generates the <li> items, add them to ul.sortable
      var ul = generateListItems(locations);
      $('ul.sortable').html(ul);
      // make the <ul> sortable with jQuery-UI
      locationsOrdered = locations;
      $('ul.sortable').sortable({
        stop: function(event, ui) {
          // update the order of the items
          locationsOrdered = [];
          $('ul.sortable li').each(function( key, value ) {
            var index = $(value).data('id');  // reads the data-id="X"; this value is the original order
            locationsOrdered.push(locations[index]);
          });
        }
      });


      var my_position = new google.maps.LatLng(50.84715956, 4.3485290);
      map = new google.maps.Map(document.getElementById('map-canvas'), {
        center: my_position,
        zoom: 12
      });
      directionsDisplay.setMap(map);
    }
    google.maps.event.addDomListener(window, 'load', initialize);

      var directionsDisplay;
      var directionsService = new google.maps.DirectionsService();

      // based on https://developers.google.com/maps/documentation/javascript/examples/directions-waypoints
      function calcRoute(locationsOrdered) {
        // optimize?  read the checkbox 
        var optimize = $('#optimize').prop('checked');
        // clear all previous overlays, and distance display
        directionsDisplay.setMap(null);
        $('#log').empty();

        // 
        var length = locationsOrdered.length;
        var start = new google.maps.LatLng(locationsOrdered[0].lat, locationsOrdered[0].lng);
        var end = new google.maps.LatLng(locationsOrdered[length - 1].lat, locationsOrdered[length - 1].lng);
        var waypts = [];
        var checkboxArray = document.getElementById('waypoints');
        for (var i=1; i < locationsOrdered.length - 1; i++) {
          waypts.push({
              location: new google.maps.LatLng(locationsOrdered[i].lat, locationsOrdered[i].lng),
              stopover: true
          });
        }

        var request = {
            origin: start,
            destination: end,
            waypoints: waypts,
            optimizeWaypoints: optimize,    // depends on the checkbox
            travelMode: google.maps.TravelMode.DRIVING
        };
        directionsService.route(request, function(response, status) {
          if (status == google.maps.DirectionsStatus.OK) {
            // as Google changes the order of the waypoints, we will update the order of the <li> items
            var waypoint_order = response.routes[0].waypoint_order;
            for (var i=0; i<waypoint_order.length; i++) {
              swapLiItem(i + 1, waypoint_order[i] + 1);  // the + 1 is because the start point is not a waypoint, but it is an <li>
            }
            // route display
            directionsDisplay.setDirections(response);
            var route = response.routes[0];
            // display the distances
            var totalDistance = 0;
            log('Waypoint distances: <br>');
            for (var i = 0; i < route.legs.length; i++) {
              totalDistance += route.legs[i].distance.value;
              log(i +': ' + route.legs[i].distance.text + '<br>');
            }
            log('Total distance: ' + (totalDistance / 1000) + 'km');
            directionsDisplay.setMap(map);
          }
        });
      }
      // How to set sortable items manually.
      // @see http://stackoverflow.com/questions/9981563/jquery-ui-sortable-set-manually-a-position
      function swapLiItem(from, to) {
        $('ul.sortable li:eq(' + from + ')').insertAfter($('ul.sortable li:eq(' + to + ')'));
      }

      // writes a message in <div id=log"></div>
      function log(message) {
        $('#log').append(message);
      }
    </script>
  </head>
  <body>
    <div id="map-canvas"></div>
    <ul class="sortable"></ul>
    <input type="button" id="go" value="Go" onclick="calcRoute(locationsOrdered)"><br>
    <input type="checkbox" id="optimize" checked="checked"> auto optimize waypoints
    <hr>
    <div id="log"></div>
  </body>
</html>