source code desktopeditionsample routingextension smartbruteforceroutingfortsp cs 100615.zip

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;
        }
    }
}