Trying to resolve the Travelling Salesman Problem in Salesforce

Below is a screen showing one attempt at finding the best route to visit several accounts using the Artificial Bee Colony algorithm. The best route is defined as the route with minimal total sum of the distances between accounts. In other words, the route to spent the least amount of time and gas.

I am not sure anyone has ever had that problem to resolve in a Salesforce application but I found it was a good way to test my implementation of the Artificial Bee Colony (ABC) optimization algorithm, which could be used in many other optimization problems.

This implementation offers a fairly good approximation of the best route – definitely not the best route as you can see below:  you would go from Plano to Richardson before Garland and then from Garland to Mesquite to save a few miles/gallons.

Travelling Salesman Problem in the DFW

Travelling Salesman Problem in the DFW

The implementation is split into 2 main classes:  the Hive, which implements the ABC algorithm, and the TravellingSalesmanProblem class, which is in charge of storing the accounts latitude/longitude, calculate the distances between accounts and getting the next best route.

Another interesting part is the Javascript code that uses the Google Map API to plot the route.

Plotting using the Google Map API

Plotting using the Google Map API

Other potential applications of the Travelling Salesman Problem could be:

  • deciding the different routes each truck should follow in a delivery/courier company fleet
  • wiring together memory elements in digital circuits in a sequence to minimize length of wire
  • finding a sequence of advertising spots where ads from one company would not be shown immediately after its competitor (say, keep a Coke ad away from an Pepsi ad)
  • in robotic welding, find a good sequence of tasks and path for the robot arm to weld the seams faster
  • likewise, find the optimum path for a CNC machine to drill multiple holes
Advertisements

Posted on 02/08/2015, in No category and tagged , , . Bookmark the permalink. Leave a comment.

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

%d bloggers like this: