Grouping orders by similarity (cluster) of their items

Question

My task is to write an algorithm for grouping list of orders into batches, each batch consisting of 4 orders. Orders are grouped by similarity of their items, which means the more items from Order X sharing the same location as Order Y's items, the bigger the similarity ratio between both. Note that one order is compared only against equally sized or bigger orders. A similarity ratio of 0 would mean no items match, whereas 1 means 100% match. Also, the biggest order in a batch has ratio of 1 because it's compared only against itself.

The idea behind all this is to optimize the path for a warehouse worker who visit a location and pick the ordered items. In the best case they should pick all identical items with a single visit, then proceed to the next location.

The code below represents a custom class I created for this purpose, but something says me it's not very optimized or could be written better. I'd be very happy if you can help me out and give some advice on what could be improved.

public static class SimilarityCalculator
{
    private static double CalcSimilarityRatio(Order minOrder, Order maxOrder)
    {
        var similarities = 0;

        foreach (var item1 in minOrder.Items)
        {
            foreach (var item2 in maxOrder.Items)
            {
                if (string.Equals(item1.Cluster, item2.Cluster))
                {
                    similarities++;
                    break;
                }
            }
        }

        var ratio = (double)similarities / minOrder.Items.Count;
        ratio = Math.Round(ratio, 3);
        return ratio;
    }

    private static void CheckSimilarities(List<Order> ordersList)
    {
        foreach (var order in ordersList)
        {
            order.MatchingList.Clear();

            var equalOrGreaterOrders = ordersList
                                       .Where(o => o.Items.Count >= order.Items.Count)
                                       .ToList();

            foreach (var equalOrGreater in equalOrGreaterOrders)
            {
                var ratio = CalcSimilarityRatio(order, equalOrGreater);
                var match = new KeyValuePair<Order, double>(equalOrGreater, ratio);
                order.MatchingList.Add(match);
            }
        }
    }

    private static List<KeyValuePair<Order, double>> GetTop4Matches(Order order)
    {
        var top = (from m in order.MatchingList
                   orderby m.Value descending
                   select m)
                   .Take(4)
                   .ToList();

        return top;
    }

    /// <summary>
    /// This method is called for creating the batches. Can be used from another app.
    /// </summary>
    /// <param name="ordersList">All the orders that should be grouped into batches.</param>
    /// <returns>Generated batches consisting of 4 orders each.</returns>
    public static List<List<Order>> GenerateBatches(List<Order> ordersList)
    {
        var batches = new List<List<Order>>();
        while (ordersList.Any())
        {
            CheckSimilarities(ordersList);

            var currentOrder = ordersList.First();
            var top4Matches = GetTop4Matches(currentOrder);
            var batch = new List<Order>();

            foreach (var match in top4Matches)
            {
                batch.Add(match.Key);
                ordersList.Remove(match.Key);
            }

            batches.Add(batch);
        }

        return batches;
    }
}

Answer 1

Faulty algorithm. Any order would be 100% to an order of all items.

I real life a warehouse worker can only pick up so many items in a pass.

Take an order less than pass size and find the order or orders fully contained that get up to pass size.

After you cannot get up to pass size contained then normalize similarity with match / (size1 + size2).

A better measure of similarity is:

var ratio = 2 * (double)similarities / (minOrder.Items.Count + maxOrder.Items.Count);