ThinkGeo Cloud
ThinkGeo UI Controls
ThinkGeo Open Source
Help and Support
External Resources
ThinkGeo Cloud
ThinkGeo UI Controls
ThinkGeo Open Source
Help and Support
External Resources
using System; using System.Collections.Generic; using System.Collections.ObjectModel; using System.Globalization; using System.Linq; using System.Windows.Forms; using ThinkGeo.MapSuite.Core; using ThinkGeo.MapSuite.DesktopEdition; using ThinkGeo.MapSuite.Routing; namespace SmartBruteForceRoutingForTsp { public partial class Form1 : Form { private readonly MultipointShape RoutePoints = new MultipointShape(new List<PointShape>() { new PointShape(-83.154979000000000,40.009097000000000), new PointShape(-83.152002900000000,40.008476000000000), new PointShape(-83.161758000000000,40.006751000000000), new PointShape(-83.152312000000000,40.007989000000000), new PointShape(-83.155461000000000,40.007945000000000), new PointShape(-83.157128000000000,40.010102000000000), new PointShape(-83.156948700000000,40.004356900000000), new PointShape(-83.157684800000000,40.004400200000000), new PointShape(-83.156563000000000,40.009943000000000), new PointShape(-83.160591000000000,40.007295000000000), new PointShape(-83.156872000000000,40.006665000000000), new PointShape(-83.161495000000000,40.005908000000000), new PointShape(-83.160755500000000,40.004658900000000), new PointShape(-83.156294000000000,40.006924000000000), new PointShape(-83.157663800000000,40.005639500000000), new PointShape(-83.159924999999900,40.008273000000000), new PointShape(-83.161077000000000,40.009275000000000), new PointShape(-83.162287000000000,40.010067000000000), new PointShape(-83.154449000000000,40.009877000000000), new PointShape(-83.156769500000000,40.006212000000000), new PointShape(-83.155544700000000,40.005768900000000), new PointShape(-83.150512000000000,40.008776000000000), new PointShape(-83.156649000000000,40.007936000000000), new PointShape(-83.161035999999900,40.008140000000000), new PointShape(-83.154122000000000,40.008291000000000), new PointShape(-83.158678000000000,40.008052000000000), new PointShape(-83.156238000000000,40.008691000000000), new PointShape(-83.159606000000000,40.008089000000000), new PointShape(-83.149670000000000,40.008865000000000), new PointShape(-83.157407999999900,40.007756000000000), new PointShape(-83.157238000000000,40.008700000000000), new PointShape(-83.154802000000000,40.008125000000000), new PointShape(-83.154122000000000,40.007637000000000), new PointShape(-83.157618000000000,40.008557000000000) }); private BruteForceRoutingEngine routingEngine; public Form1() { InitializeComponent(); } private void Form1_Load(object sender, EventArgs e) { RenderMap(); ShapeFileFeatureSource featureSource = new ShapeFileFeatureSource(@"..\..\App_Data\street.routable.shp"); RoutingSource routingSource = new RtgRoutingSource(@"..\..\App_Data\street.routable.rtg"); routingEngine = new BruteForceRoutingEngine(featureSource, routingSource); } private void btnGetRoute_Click(object sender, EventArgs e) { LayerOverlay overlay = (LayerOverlay)winformsMap1.Overlays["StaticOverlay"]; RoutingLayer routingLayer = (RoutingLayer)overlay.Layers["routingLayer"]; // Calculate the route. RoutingResult routingResult = routingEngine.GetRoute(RoutePoints.Points[0], RoutePoints.Points[RoutePoints.Points.Count - 1], RoutePoints.Points.Skip(1).Take(RoutePoints.Points.Count - 2), Convert.ToInt32(txtInterations.Text)); // Render the route. routingLayer.ShowStopOrder = true; routingLayer.Routes.Clear(); foreach (var segment in routingResult.RouteLines.Lines) { routingLayer.Routes.Add(segment); } routingLayer.StopPoints.Clear(); foreach (PointShape stop in routingResult.OrderedStops) { routingLayer.StopPoints.Add(stop); } winformsMap1.Refresh(overlay); txtTotalDistance.Text = routingResult.Distance.ToString(CultureInfo.InvariantCulture); } private void RenderMap() { winformsMap1.MapUnit = GeographyUnit.DecimalDegree; winformsMap1.BackgroundOverlay.BackgroundBrush = new GeoSolidBrush(GeoColor.FromHtml("#FFFFFF")); LayerOverlay staticOverlay = new LayerOverlay(); winformsMap1.Overlays.Add("StaticOverlay", staticOverlay); // Show street map as background map. ShapeFileFeatureLayer streetLayer = new ShapeFileFeatureLayer(@"..\..\App_Data\street.routable.shp"); streetLayer.ZoomLevelSet.ZoomLevel01.DefaultLineStyle = LineStyles.CreateSimpleLineStyle(GeoColor.SimpleColors.Black, 1, true); streetLayer.ZoomLevelSet.ZoomLevel01.ApplyUntilZoomLevel = ApplyUntilZoomLevel.Level20; staticOverlay.Layers.Add("streetLayer", streetLayer); // Define the routing layer. PointShape startPoint = RoutePoints.Points[0]; PointShape endPoint = RoutePoints.Points[RoutePoints.Points.Count - 1]; Collection<PointShape> stops = new Collection<PointShape>(); foreach (var stop in RoutePoints.Points.Skip(1).Take(RoutePoints.Points.Count - 2)) { stops.Add(stop); } RoutingLayer routingLayer = new RoutingLayer(startPoint, endPoint, stops); staticOverlay.Layers.Add("routingLayer", routingLayer); winformsMap1.CurrentExtent = new RectangleShape(-83.1632526508484, 40.0118482139236, -83.1487472644958, 40.0030076530106); winformsMap1.Refresh(); } } }
using System; using System.Collections.Generic; using System.Collections.ObjectModel; using System.Linq; using System.Threading.Tasks; using ThinkGeo.MapSuite.Core; using ThinkGeo.MapSuite.Routing; namespace SmartBruteForceRoutingForTsp { public class BruteForceRoutingEngine { private FeatureSource featureSource; private RoutingSource routingSource; private RoutingEngine routingEngine; private Dictionary<Tuple<PointShape, PointShape>, RoutingResult> distanceMatrix; private Collection<Collection<Tuple<RoutingResult, PointShape>>> bestRoutes; public BruteForceRoutingEngine() : this(new ShapeFileFeatureSource(), new RtgRoutingSource()) { } public BruteForceRoutingEngine(FeatureSource featureSource, RoutingSource routingSource) { this.featureSource = featureSource; this.routingSource = routingSource; routingEngine = new RoutingEngine(routingSource, new AStarRoutingAlgorithm(), featureSource) { SearchRadiusInMeters = 50 }; distanceMatrix = new Dictionary<Tuple<PointShape, PointShape>, RoutingResult>(); bestRoutes = new Collection<Collection<Tuple<RoutingResult, PointShape>>>(); } public RoutingResult GetRoute(PointShape startPoint, PointShape endPoint, IEnumerable<PointShape> stops) { return GetRouteCore(startPoint, endPoint, stops, 5, GetOptimalNumberOfSplits(stops.Count())); } public RoutingResult GetRoute(PointShape startPoint, PointShape endPoint, IEnumerable<PointShape> stops, int maximumConcurrentThreads) { return GetRouteCore(startPoint, endPoint, stops, maximumConcurrentThreads, GetOptimalNumberOfSplits(stops.Count())); } private RoutingResult GetRouteCore(PointShape startPoint, PointShape endPoint, IEnumerable<PointShape> stops, int maximumConcurrentThreads, int numberOfSplits) { bestRoutes = new Collection<Collection<Tuple<RoutingResult, PointShape>>>(); Collection<PointShape> pointsToVisit = new Collection<PointShape>(); foreach (PointShape pointToVisit in stops) { pointsToVisit.Add(pointToVisit); } Collection<PointShape> allPoints = pointsToVisit.DeepClone(); allPoints.Add(startPoint); allPoints.Add(endPoint); InitializeDistanceMatrix(allPoints); Collection<Collection<PointShape>> intermediatePointSets = GetIntermediatePoints(startPoint, endPoint, pointsToVisit, numberOfSplits); Parallel.ForEach(intermediatePointSets, new ParallelOptions { MaxDegreeOfParallelism = maximumConcurrentThreads }, intermediatePointSet => { Collection<PointShape> pointsToVisitCopy = pointsToVisit.DeepClone(); foreach (PointShape point in intermediatePointSet) { pointsToVisitCopy.Remove(point); } GetBestRoute(startPoint, intermediatePointSet, pointsToVisitCopy); }); double minimumDistance = double.MaxValue; Collection<Tuple<RoutingResult, PointShape>> bestRoute = new Collection<Tuple<RoutingResult, PointShape>>(); foreach (Collection<Tuple<RoutingResult, PointShape>> route in bestRoutes) { double localMinimumDistance = distanceMatrix[Tuple.Create(startPoint, route[0].Item2)].Distance; for (int i = 0; i < route.Count - 1; i++) { localMinimumDistance += distanceMatrix[Tuple.Create(route[i].Item2, route[i + 1].Item2)].Distance; } if (localMinimumDistance < minimumDistance) { minimumDistance = localMinimumDistance; bestRoute = route; } } RoutingResult routingResult = new RoutingResult(); routingResult.Distance = minimumDistance; routingResult.Weight = minimumDistance; for (int i = 0; i < bestRoute.Count; i++) { foreach (var line in bestRoute[i].Item1.RouteLines.Lines) { routingResult.RouteLines.Lines.Add(line); } foreach (var feature in bestRoute[i].Item1.Features) { routingResult.Features.Add(feature); } foreach (var segment in bestRoute[i].Item1.RouteSegments) { routingResult.RouteSegments.Add(segment); } foreach (var vertex in bestRoute[i].Item1.Route.Vertices) { routingResult.Route.Vertices.Add(vertex); } routingResult.OrderedStops.Add(bestRoute[i].Item2); } routingResult.OrderedStops.RemoveAt(routingResult.OrderedStops.Count - 1); return routingResult; } private Collection<Collection<PointShape>> GetIntermediatePoints(PointShape startPoint, PointShape endPoint, Collection<PointShape> pointsToVisit, int numberOfSplits) { Collection<PointShape> intermediatePoints = new Collection<PointShape>(); intermediatePoints.Add(startPoint); intermediatePoints.Add(endPoint); Collection<Collection<PointShape>> intermediatePointSets = new Collection<Collection<PointShape>>(); int possibleIntermediatePointSetSize = (int)(((double)1 / (double)numberOfSplits) * pointsToVisit.Count); Collection<PointShape> possibleIntermediatePoints = new Collection<PointShape>(); pointsToVisit.OrderByDescending(point => (distanceMatrix[Tuple.Create(point, startPoint)].Distance / distanceMatrix[Tuple.Create(endPoint, point)].Distance)).Skip(pointsToVisit.Count / (numberOfSplits * 2)).ToList().ForEach(e => possibleIntermediatePoints.Add(e)); return GetIntermediatePointsRecursively(startPoint, intermediatePoints, possibleIntermediatePoints, intermediatePointSets, possibleIntermediatePointSetSize, numberOfSplits - 1); } private Collection<Collection<PointShape>> GetIntermediatePointsRecursively(PointShape startPoint, Collection<PointShape> intermediatePoints, Collection<PointShape> possibleIntermediatePoints, Collection<Collection<PointShape>> intermediatePointSets, int intermediatePointSetSize, int numberOfSplitsLeft) { if (numberOfSplitsLeft <= 0) { intermediatePointSets.Add(intermediatePoints); } else { foreach (PointShape intermediatePoint in possibleIntermediatePoints.Skip(intermediatePointSetSize * (numberOfSplitsLeft - 1)).Take(intermediatePointSetSize)) { Collection<PointShape> possibleIntermediatePointsCopy = possibleIntermediatePoints.DeepClone(); Collection<PointShape> intermediatePointsCopy = intermediatePoints.DeepClone(); possibleIntermediatePointsCopy.Remove(intermediatePoint); intermediatePointsCopy.Insert(intermediatePoints.Count - 1, intermediatePoint); intermediatePointSets = GetIntermediatePointsRecursively(startPoint, intermediatePointsCopy, possibleIntermediatePointsCopy, intermediatePointSets, intermediatePointSetSize, numberOfSplitsLeft - 1); } } return intermediatePointSets; } private void GetBestRoute(PointShape startPoint, Collection<PointShape> intermediatePoints, Collection<PointShape> pointsToVisit) { double minimumDistance = double.MaxValue; Collection<Tuple<RoutingResult, PointShape>> bestRoute = new Collection<Tuple<RoutingResult, PointShape>>(); Collection<PointShape> points = pointsToVisit.DeepClone(); for (int i = 0; i < intermediatePoints.Count - 1; i++) { Collection<PointShape> nextSetOfPoints = new Collection<PointShape>(); if (i == intermediatePoints.Count - 2) { nextSetOfPoints = points.DeepClone(); } else { points.OrderByDescending(point => (distanceMatrix[Tuple.Create(point, intermediatePoints.Last())].Distance / distanceMatrix[Tuple.Create(startPoint, point)].Distance)).Take(points.Count / (intermediatePoints.Count - i - 1)).ToList().ForEach(e => { nextSetOfPoints.Add(e); points.Remove(e); }); } Tuple<Collection<Tuple<RoutingResult, PointShape>>, double> result = FindBestRoute(intermediatePoints[i], intermediatePoints[i + 1], nextSetOfPoints); foreach (Tuple<RoutingResult, PointShape> routeResult in result.Item1) { bestRoute.Add(routeResult); } minimumDistance += result.Item2; } if (!(bestRoute == null)) { bestRoutes.Add(bestRoute); } } private Tuple<Collection<Tuple<RoutingResult, PointShape>>, double> FindBestRoute(PointShape startPoint, PointShape endPoint, Collection<PointShape> pointsToTraverse) { return FindBestRouteRecursively(startPoint, endPoint, pointsToTraverse, new Collection<Tuple<RoutingResult, PointShape>>(), 0, new Collection<Tuple<RoutingResult, PointShape>>(), double.MaxValue); } private Tuple<Collection<Tuple<RoutingResult, PointShape>>, double> FindBestRouteRecursively( PointShape currentPoint, PointShape endPoint, Collection<PointShape> pointsToTraverse, Collection<Tuple<RoutingResult, PointShape>> currentRoute, double currentDistance, Collection<Tuple<RoutingResult, PointShape>> localBestRoute, double localMinDistance) { Collection<PointShape> closestPoints = new Collection<PointShape>(); if (pointsToTraverse.Count == 0) { currentDistance += distanceMatrix[Tuple.Create(currentPoint, endPoint)].Distance; if (currentDistance >= localMinDistance) { return Tuple.Create(localBestRoute, localMinDistance); } else if (currentDistance < localMinDistance) { currentRoute.Add(Tuple.Create(distanceMatrix[Tuple.Create(currentPoint, endPoint)], endPoint)); return Tuple.Create(currentRoute, currentDistance); } } else if (pointsToTraverse.Count < 3) { closestPoints = pointsToTraverse.DeepClone(); } else { closestPoints = new Collection<PointShape>(); pointsToTraverse.OrderByDescending(i => distanceMatrix[Tuple.Create(currentPoint, i)].Distance).Reverse().Take(3).ToList().ForEach(e => closestPoints.Add(e)); } foreach (PointShape point in closestPoints) { double currentDistanceCopy = currentDistance; currentDistanceCopy += distanceMatrix[Tuple.Create(currentPoint, point)].Distance; if (currentDistanceCopy > localMinDistance) { return Tuple.Create(localBestRoute, localMinDistance); } Collection<PointShape> pointsToTraverseCopy = pointsToTraverse.DeepClone(); pointsToTraverseCopy.Remove(point); Collection<Tuple<RoutingResult, PointShape>> currentRouteCopy = currentRoute.DeepClone(); currentRouteCopy.Add(Tuple.Create(distanceMatrix[Tuple.Create(currentPoint, point)], point)); Tuple<Collection<Tuple<RoutingResult, PointShape>>, double> results = FindBestRouteRecursively(point, endPoint, pointsToTraverseCopy, currentRouteCopy, currentDistanceCopy, localBestRoute, localMinDistance); localBestRoute = results.Item1; localMinDistance = results.Item2; } return Tuple.Create(localBestRoute, localMinDistance); } private void InitializeDistanceMatrix(IEnumerable<PointShape> stops) { distanceMatrix = new Dictionary<Tuple<PointShape, PointShape>, RoutingResult>(); foreach (PointShape fromPoint in stops) { foreach (PointShape toPoint in stops) { if (!fromPoint.Equals(toPoint)) { if (distanceMatrix.ContainsKey(Tuple.Create(toPoint, fromPoint))) { distanceMatrix.Add(Tuple.Create(fromPoint, toPoint), distanceMatrix[Tuple.Create(toPoint, fromPoint)]); } else { RoutingResult tempResult = routingEngine.GetRoute(fromPoint, toPoint); distanceMatrix.Add(Tuple.Create(fromPoint, toPoint), tempResult); } } } } } private int GetOptimalNumberOfSplits(int stops) { int numberOfSplits = 1; long total = stops * (long)Math.Pow(3, stops); long nextSplitTotal = stops * (long)Math.Pow(3, stops); while (total >= nextSplitTotal) { numberOfSplits++; total = nextSplitTotal; nextSplitTotal = stops * (long)Math.Pow(3, stops / numberOfSplits); for (int i = 0; i < numberOfSplits; i++) { nextSplitTotal = nextSplitTotal * (stops - i + 2); } } return numberOfSplits - 1; } } static class Extensions { public static Collection<T> DeepClone<T>(this Collection<T> collectionToCopy) { Collection<T> copy = new Collection<T>(); foreach (T item in collectionToCopy) { copy.Add(item); } return copy; } } }