How to sort collection based on next property?

Question

I am trying to calculate the best route to take between all stops w/ GeoCoordinates in C#.

I have some methods which get the next closest location in a list, but I need to be able to sort my original list by:

start -> next stop -> next stop -> next stop -> finish

This is what I'm currently working with:

Models

public class DispatchStopModel
{
    public long OrderDispatchID { get; set; }
    public long? NextDispatchID { get; set; }
    public PhysicalAddress PhysicalAddress { get; set; }
    public double Distance { get; set; }
}

Methods

    private static double DistanceTo(double lat1, double lon1, double lat2, double lon2, char unit = 'M')
    {
        double rlat1 = Math.PI * lat1 / 180;
        double rlat2 = Math.PI * lat2 / 180;
        double theta = lon1 - lon2;
        double rtheta = Math.PI * theta / 180;
        double dist =
            Math.Sin(rlat1) * Math.Sin(rlat2) + Math.Cos(rlat1) *
            Math.Cos(rlat2) * Math.Cos(rtheta);
        dist = Math.Acos(dist);
        dist = dist * 180 / Math.PI;
        dist = dist * 60 * 1.1515;

        switch (unit)
        {
            case 'K': //Kilometers -> default
                return dist * 1.609344;
            case 'N': //Nautical Miles 
                return dist * 0.8684;
            case 'M': //Miles
                return dist;
        }

        return dist;
    }

    private void FindClosestStop(DispatchStopModel start, ICollection<DispatchStopModel> stops)
    {
        if(start.PhysicalAddress?.HasGeocode ?? false)
        {
            foreach(var stop in stops.Where(s => s.OrderDispatchID != start.OrderDispatchID))
            {
                if(stop.PhysicalAddress?.HasGeocode ?? false)
                {
                    double distanceTo = DistanceTo((double)start.PhysicalAddress.Latitude, (double)start.PhysicalAddress.Longitude, (double)stop.PhysicalAddress.Latitude, (double)stop.PhysicalAddress.Longitude);

                    if (distanceTo < start.Distance)
                    {
                        start.Distance = distanceTo;
                        start.NextDispatchID = stop.OrderDispatchID;
                    }
                }
            }
        }
    }

Now here is my controller action:

public IActionResult GetDeliveries()
{
    var deliveries = deliveryService.GetYourDeliveries();

    var Stops = Deliveries.Select(d => new DispatchStopModel
    {
        OrderDispatchID = d.OrderDispatchID,
        NextDispatchID = null,
        PhysicalAddress = d.Order.OrderAddress?.PhysicalAddress,
        Distance = double.MaxValue
    })
    .ToArray();


    foreach(var stop in Stops)
    {
        FindClosestStop(stop, Stops);
    }

    //How can I sort on deliveries using the "NextDispatchID" from the collection I just generated?
}

What I was thinking is that I could setup a new list, and manually insert each delivery where the OrderDispatchID equals the OrderDispatchID of the stop. I feel like this would be inefficient though.

Thoughts on the proper way to do this?

Thanks in advance,

What *ordering* is implied by `start -> next stop -> next stop -> next stop -> finish`? If this is a singular path, *distance from start node*? — user2864740, Sep 19 '19 at 19:53
@user2864740 we'll say start is any address, and then next closest stop is the item in Stops with NextDispatchID — IntricateJake, Sep 19 '19 at 19:54
Can there be more than one start .. -> .. finish route? ( ie. assume that multiple routes have the same [best] cost when *first applying* an algorithm like the [A-star search algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm) ) — user2864740, Sep 19 '19 at 19:57
This is called the Traveling Salesman Problem and if you really need the best route this can't be solved by quickly sorting some list. The problem lies in the fact that in the optimal route it might be better to prefer a slightly further stop over a closer one because it works better for the rest of the route. — , Sep 19 '19 at 19:58
@user2864740 Start Address will always be the same, the stops + destination address will change though. — IntricateJake, Sep 19 '19 at 19:58
@Knoop not necessarily, in my scenario it's mainly flat ground in the city. This method would be significantly better than going to random dots placed on a map (ie: driving across town and then back, when could have made the closer delivery sooner) — IntricateJake, Sep 19 '19 at 20:01
"Flat ground" doesn't have much to do with it. What I'm hearing, though, is that you're okay with a "good enough" approach rather than "the best route" that you asked for originally? In that case you should probably look into [other people's approximate solutions](https://stackoverflow.com/a/2933435/120955) for the Travelling Salesman Problem. Unless the number of stops is limited to an extremely small number (like 3 or 4), in which case a brute force approach would probably suffice. — StriplingWarrior, Sep 19 '19 at 20:09
@IntricateJake There are loads of algorithms giving a very good solution to the traveling salesman problem, but just keep in mind they might not give the optimal solution. If just keep picking the next closest unvisited point is good enough that's perfectly fine, that would fall into the category of greedy algorithms. — , Sep 19 '19 at 20:14
@StriplingWarrior I understand where you're coming from. I would be only making maybe tops 7 stops per drive. Would my usage be efficient or is there better algorithms out there? I took a look at Striplings link. — IntricateJake, Sep 19 '19 at 20:22
Since [a brute force algorithm's complexity would be `O(n!)`](https://en.wikipedia.org/wiki/Travelling_salesman_problem#Exact_algorithms), 7 stops would only require you to check through about 5000 possibilities, which might take a few milliseconds. What it sounds like you're suggesting you want to try is the Nearest Neighbor Solution. That's probably simplest to accomplish with simple imperative code following [this algorithm](https://en.wikipedia.org/wiki/Nearest_neighbour_algorithm), but it's [not impossible to do with LINQ](https://stackoverflow.com/q/7538622/120955). — StriplingWarrior, Sep 19 '19 at 21:09

Rufus L · Accepted Answer · 2019-09-19T21:26:35.870

Looking at your question from a high level, it seems to me you're really dealing with a linked list, where each item points to a next item.

If this is the case, one way to set the "next" item for each item is: make a copy of all the stops, loop through the original list of stops, assign the closest one in the list copy on each iteration, and then remove that item from the list copy so it doesn't get assigned again:

List<DispatchStopModel> deliveries = deliveryService.GetYourDeliveries();
List<DispatchStopModel> temp = deliveries.ToList();

// Assuming you have a start location
DispatchStopModel start = GetStartingPoint();

// Assign the closest stop to it
FindClosestStop(start, deliveries);

// Now assign the closest delivery for each of the rest
// of the items, removing the closest item on each
// iteration, so it doesn't get assigned more than once.
foreach (var delivery in deliveries)
{
    var closest = FindClosestStop(delivery, temp);
    temp.Remove(closest);
}

After this, all the items should be assigned with a NextDispatchID that points to the next closest delivery point. If you still want to "sort" the list, there are many answers on this site on how to sort a linked list (like this, for example).

Note that I made a slight change to FindClosestStop so that it returns the closest stop found:

private DispatchStopModel FindClosestStop(DispatchStopModel start, 
    ICollection<DispatchStopModel> stops)
{
    DispatchStopModel closest = null;

    // other code ommitted for brevity

    if (distanceTo < start.Distance)
    {
        start.Distance = distanceTo;
        start.NextDispatchID = stop.OrderDispatchID;
        closest = stop;
    }

    // other code ommitted for brevity

    return closest;
}

Also note that Equals and GetHashCode should be overridden on the DispatchStopModel class for the Remove method to work. If you don't want to do that, then you'd need to search for the item with a matching OrderDispatchID and remove it that way.

this is exactly what I was looking for. Thanks – IntricateJake Sep 20 '19 at 06:32 — IntricateJake, Sep 20 '19 at 06:32

How to sort collection based on next property?

1 Answers1