Similar Topics...
 |
The Traveling Salesman - Greedy Solution in Javascript for Mapping
Scenario: You have many pushpins on Bing Maps (or any javascript API), and you want to quickly re-order them to reduce total trip length. You either want a straight line (do not care which stop is first and which is last) or a round trip (use first stop as the start and end).
Solution:
The javascript code is a function called resortStops() (as in re-sort)
This uses a very simple greedy algorithm to sort a series of Bing Maps Pushpins by location to optimize the stop order for route planning.
You will need to adapt to your own data. If you want a specific start/end point, that'd be trivial to implement as a variation.
Includes support for round trip, one way, or both (keep round trip only if already was round trip)
Assumes:
Array of string Ids named globalItineraryShapeIdArray represent your stops (in random order, that should be sorted)
Function getShapeByID(shapeId) to fetch a Bing Maps Pushpin Object for any given shapeId in the array
Each pushpin already has been preset with a variable pinid that stores its shapeId.
Function writeItineraryItemsToDiv() exists which will tell Bing to render the updated route when done.
Pushpin object has getLocation() method that returns a point; this is already done for you if you are using a Bing PushPin object.
Duplicate stops will be removed.
RoundTrip option: if true, it will keep stop 1 as both stop 1 and the last stop (even if wasn't set as last stop). If false, it will build a straight line trip. If null, it will build a straight line trip UNLESS the trip was already a round trip (same start/stop), in which case it will retain that same start/stop, only reordering mid-trip points.
There are several alerts commented out you can add for debugging, and one that will only fire if it detects an infinite loop and manually breaks (shouldn't happen)
// sort itinerary using a greedy sort to set order of stops somewhat reasonably. User can manually clean up. This just gets a reasonable starting point.
// if roundTrip is true, keeps 1st point as 'start' and builds a round trip, adding start point to the end.
// if roundTrip is null, but it WAS a roundtrip (same start/end pt), it will be kept a round trip.
function resortStops(roundTrip) {
if (globalItineraryShapeIdArray.length <= 1)
return;
if (roundTrip == null) {
if (globalItineraryShapeIdArray[0] == globalItineraryShapeIdArray[globalItineraryShapeIdArray.length - 1]) {
roundTrip = true; // it already was a RT, so keep it that way
}
}
// clear cached connections
for (var i = 0; i < globalItineraryShapeIdArray.length; i++) {
var shapeId = globalItineraryShapeIdArray[i];
var pushpin = getShapeByID(shapeId);
pushpin.connectedFrom = null;
pushpin.connectedTo = null;
}
if (roundTrip) { // keep current start
//alert('keeping ' + getShapeByID(globalItineraryShapeIdArray[0]));
getShapeByID(globalItineraryShapeIdArray[0]).connectedFrom = 'start'; // use this as start
}
// connect all points until none are left unconnected
var minDistance = -1;
while (minDistance != null) {
minDistance = setMinConnection();
}
// get starting point
var startPin = null;
if (roundTrip) { // keep current start
//alert('starting with ' + globalItineraryShapeIdArray[0]);
startPin = getShapeByID(globalItineraryShapeIdArray[0])
}
else { // choose any end point as start
for (var i = 0; i < globalItineraryShapeIdArray.length; i++) {
var shapeId = globalItineraryShapeIdArray[i];
var pushpin = getShapeByID(shapeId);
if (pushpin.connectedTo == null || pushpin.connectedFrom == null)
startPin = pushpin; // a start or end
}
}
// now resort output
globalItineraryShapeIdArray = new Array();
var currentPin = startPin;
while (currentPin != null) {
// check for bad data/infinite loop. Sanity check, not really needed.
var isDuplicate = false;
for (var i = 0; i < globalItineraryShapeIdArray.length; i++) {
var shapeId = globalItineraryShapeIdArray[i];
var pushpin = getShapeByID(shapeId);
if (shapeId == currentPin.pinid) {
alert('ERROR - inserting duplicate pin: ' + getPushpinAlert(currentPin)); // better never happen!
isDuplicate = true;
currentPin = null;
break;
}
}
// passed check
if (!isDuplicate) {
globalItineraryShapeIdArray.push(currentPin.pinid);
// alert(currentPin.pinid);
if (currentPin.connectedTo != null && currentPin.connectedTo != startPin) {
startPin = currentPin;
currentPin = currentPin.connectedTo;
}
else if (currentPin.connectedFrom != null && currentPin.connectedFrom != startPin) {
startPin = currentPin;
currentPin = currentPin.connectedFrom;
}
else
currentPin = null;
}
}
// loop back if RT
if (roundTrip) {
startPin = getShapeByID(globalItineraryShapeIdArray[0]);
//alert('looping to ' + startPin.pinid);
globalItineraryShapeIdArray.push(startPin.pinid);
}
writeItineraryItemsToDiv();
}
// find all unconnected points and connect the 2 that are nearest to eachother
function setMinConnection() {
var minDistance = 99999999;
var minStartPushpin = null;
var minEndPushpin = null;
for (var i = 0; i < globalItineraryShapeIdArray.length; i++) {
var shapeId = globalItineraryShapeIdArray[i];
var pushpin = getShapeByID(shapeId);
for (var j = 0; j < globalItineraryShapeIdArray.length; j++) {
var otherShapeId = globalItineraryShapeIdArray[j];
if (otherShapeId != shapeId) {
var otherPushpin = getShapeByID(otherShapeId);
var dist = distanceKm(pushpin.getLocation().latitude, pushpin.getLocation().longitude, otherPushpin.getLocation().latitude, otherPushpin.getLocation().longitude);
// if this is smallest distance and pin has at least one open connection and they're not already connected
if (dist < minDistance
&& !areConnected(pushpin, otherPushpin, null)
&& (pushpin.connectedTo == null || pushpin.connectedFrom == null) // must have room for a connection
&& (otherPushpin.connectedTo == null || otherPushpin.connectedFrom == null)
)
{
minDistance = dist;
//alert('foudn min ' + dist);
minStartPushpin = pushpin;
minEndPushpin = otherPushpin;
}
}
}
}
if (minStartPushpin != null && minEndPushpin != null) { // found 2 points to connect
if (minStartPushpin.connectedTo == null) {
minStartPushpin.connectedTo = minEndPushpin;
}
else {
minStartPushpin.connectedFrom = minEndPushpin;
}
if (minEndPushpin.connectedFrom == null) {
minEndPushpin.connectedFrom = minStartPushpin;
}
else {
minEndPushpin.connectedTo = minStartPushpin;
}
return minDistance; // something connected
}
return null;
}
function areConnected(pin1, pin2, pinParent) {
if (pin1 == pin2)
return true; // same pin
if (pin1.connectedFrom == pin2 || pin1.connectedTo == pin2)
return true; // directly connected
if (pin1.connectedFrom != null && pin1.connectedFrom != pinParent && areConnected(pin1.connectedFrom, pin2, pin1))
return true; // from pin is connected (and not to parent)
if (pin1.connectedTo != null && pin1.connectedTo != pinParent && areConnected(pin1.connectedTo, pin2, pin1))
return true; // from pin is connected (and not to parent)
return false;
}
// function getPushpinAlert(pushpin) {
// return pushpin.pinid + ", t " + (pushpin.connectedTo == null ? "" : pushpin.connectedTo.pinid) + ", f " + (pushpin.connectedFrom == null ? "" : pushpin.connectedFrom.pinid)
// }
function distanceKm(lat1, lon1, lat2, lon2) {
var R = 6371;
var a =
0.5 - Math.cos((lat2 - lat1) * Math.PI / 180) / 2 +
Math.cos(lat1 * Math.PI / 180) * Math.cos(lat2 * Math.PI / 180) *
(1 - Math.cos((lon2 - lon1) * Math.PI / 180)) / 2;
return R * 2 * Math.asin(Math.sqrt(a));
}
>>>>>>
How does it work?
Loop over the N stops N times, each time linking the two closest stops that are not yet linked to each other (even through other stops) to create a linked chain.
Pick an end of the chain at random.
Re-sort your array by running through the chain in order.
If it should be a round trip, adds the start back to the end.
Call getDirections API.
Note: distanceKm is a useful function that gets straight-line distance in km from one point to another. This is another shortcut vs. getting full driving distance which would take a long time.
Created By: amos 2/27/2014 4:57:33 PM
Updated: 3/31/2014 12:56:31 PM
|
|
|
|
|
|