/gmaps-bigrouteoptimizer

Javascript object for find optimal routes for Big Distance matrix for Google Maps

Primary LanguageJavaScriptMIT LicenseMIT

Route Optimizer for Big Distance Matrix for Google Maps

Javascript object for find optimal routes for Big Distance Matrices for Google Maps.

It takes a distance matrix between given locations obtained using Google Maps API using the Big Distance Matrix for Google Maps and computes the shortest route to travel through all the locations.

This object implements the Ant Colony Algorithm to get the shortest path using distance, time or speed (distance/time) as optimization variables.

It can display the optimal route on a HTML div or export it as an array in JSON format.

Known issue: When It's executed on a webbrowser, It blocks the screen until the optimization ends. It's highly recommended to use it in server-side with NodeJS.

Links

Requirements:

  1. jQuery 1.8+ http://jquery.com/
  2. JSON3 http://bestiejs.github.io/json3/
  3. Big Distance Matrix for Google Maps https://github.com/davcs86/gmaps-bigdistancematrix

Instructions:

  1. Use "Big Distance Matrix for Google Maps" to generate a object with the distance and time between locations.

    //from example.js
var Route_Points = {
	"Times Square": [40.758673, -73.985281],
	"St Patrick's Cathedral": [40.758196, -73.975347],
	"Grand Central Terminal": [40.752105, -73.977686],
	//...
	"Bronx Zoo": [40.848611, -73.882631],
	"New York Botanical Garden": [40.861748, -73.880145],
	"Washington Square Park": [40.731371, -73.996997]
};
Route_DistanceMatrix.init(Route_Points);
Route_DistanceMatrix.displayTable("table_route_matrix");
Route_DistanceMatrix.startRouting(3000);

  2. Initialize the object.

    Route_Optimizer.init(distanceMatrix, optimizeBy, consoleDivId);
//from example.js
Route_Optimizer.init(Route_DistanceMatrix.exportResults(), 1, "console_route_matrix"); // 1 for use time as optimization variable
Route_Optimizer.init(Route_DistanceMatrix.exportResults(), 2, "console_route_matrix"); // 2 for use distance as optimization variable
Route_Optimizer.init(Route_DistanceMatrix.exportResults(), 3, "console_route_matrix"); // 3 for use speed as optimization variable
    Parameter Description
    distanceMatrix Object returned by the "Big Distance Matrix for Google Maps".
    Mandatory.
    optimizeBy Select variable to optimize.
    Mandatory.
    Possible Values:
    1, distance.
    2, time.
    3, speed (correlation: distance/time)
    consoleDivId DOM id of the container where the log information will be written.
    Optional. Default value: false.

  3. Do Route Optimization.

    Route_Optimizer.doOptimize(maxIterations, numAnts, decayFactor, heuristicCoeff, greedinessFactor);
//from example.js
var OptimalRoute = Route_Optimizer.doOptimize();
    Parameter Description
    maxIterations Number of iterations for find the solution.
    Optional. Typically a value between 200 and 500 times the numAnts value.
    numAnts Number of ants (cars) that run the trials.
    Optional. A typical value is the half of locations plus one.
    decayFactor Rate at which historic information is lost.
    Optional. Recommended values: 0.1-0.5, Default value: Random number between 0.1 and 0.5
    heuristicCoeff Controls the amount of contribution problem-specific heuristic information plays in a components probability of selection.
    Optional. Recommended values: 2-5, Default value: Random number between 2 and 5
    greedinessFactor Controls the amount of contribution problem-specific heuristic information plays in a components probability of selection.
    Optional. Recommended values: 0.8-1.3, Default value: Random number between 0.8 and 1.3

    Returns an JSON object with the optimal route.

  4. You can convert the JSON object to something more readable with convertToHuman method.

    var optimalRouteStr = Route_Optimizer.convertToHuman(optimalRoute);
    Parameter Description
    optimalRoute Optimal route returned in the previous step
    Mandatory.

Support

Drop me line on: http://d-castillo.info/contactme/ or to: davcs86@gmail.com

Donations

Did this project help you to save (or earn) some money?
Please, support to the author by making a small donation.

Buy Me A Coffee :) @ PayPal