Using an algorithm to determine the ideal size for shipping boxes

Question

I work in a logistic department for a company, recently we have been trying to narrow down the amount of different packaging options that we use.

I have all the necessary product data like length, width, height, volume and also sales data.

So I was thinking if it is possible to use an algorithm to cluster the different volumes of the products and maybe also take into account which sizes are selling the most, to determine, which box sizes would be ideal. (Taking into account how often a product sells is secondary so that is not absolutely necessary)

What I want is that I can give the Algorithm an amount of how many different boxsizes I want and the algorithm should determine where to put the limits, so that there is a solution for every product that we have. With the goal of the optimization being minimum volume wasted while also not using more than the set amount of different boxes.

Also important to note, the orientation of the products and the amount per box is set, so there is no need to determine how to pack the products and how many go into one box idealy or something like that.

What kind of algorithms could be used for a problem like this and what are my options to program them? I was thinking of using Matlab, but would also be open for other possible options. I want to program it, not simply use an existing program like SPSS.

Thanks in advance and forgive me if my english is not the best, I'm not a native speaker.

Answer 1

The following C++ program will find optimal solutions for small instances. For 10 input box sizes, each having dimensions randomly chosen in the range 1..100, and for any number 1..10 of box sizes to choose, it computes the answer in a couple of seconds on my computer. For 15 input box sizes, it takes around 10s. For 20 input box sizes, I could compute up to 4 chosen box sizes in about 3 minutes, with memory becoming an issue (it used around 3GB). I had to increase the linker's default stack size to avoid stack overflows.

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <functional>
#include <climits>

using namespace std;

ostream& operator<<(ostream& os, array<int, 3> a) {
    return os << '(' << a[0] << ", " << a[1] << ", " << a[2] << ')';
}

template <int N>
long long vol(array<int, N> b) {
    return static_cast<long long>(b[0]) * b[1] * b[2];
}

template <int N, int M>
bool fits(array<int, N> a, array<int, M> b) {
    return a[0] <= b[0] && a[1] <= b[1] && a[2] <= b[2];
}

// Compares first by volume, then lexicographically.
struct CompareByVolumeDesc {
    bool operator()(array<int, 3> a, array<int, 3> b) const {
        return vol(a) > vol(b) || vol(a) == vol(b) && a < b;
    }
};

vector<array<int, 3>> candSizes;

struct State {
    vector<array<int, 4>> req;
    int n;
    int k;

    // Needed for map<>
    bool operator<(State const& other) const {
        return make_tuple(n, k, req) < make_tuple(other.n, other.k, other.req);
    }
} dummy = { {}, -1, -1 };

map<State, pair<int, State>> memo;

// Compute the minimum volume required for the given list of box sizes if we use exactly k of the first n candidate box sizes.
pair<long long, State> solve(State const& s) {
    if (empty(s.req)) return { 0, dummy };
    if (s.k == 0 || s.k > s.n) return { LLONG_MAX / 4, dummy };
    auto previousAnswer = memo.find(s);
    if (previousAnswer != end(memo)) return (*previousAnswer).second;

    // Try using the nth candidate box size.
    int nFitting = 0;
    vector<array<int, 4>> notFitting;
    for (auto r : s.req) {
        if (fits(r, candSizes[s.n - 1])) {
            nFitting += r[3];
        } else {
            notFitting.push_back(r);
        }
    }

    pair<long long, State> solution;
    solution.second = { s.req, s.n - 1, s.k };
    solution.first = solve(solution.second).first;
    if (nFitting > 0) {
        State useNth = { notFitting, s.n - 1, s.k - 1 };
        long long useNthVol = nFitting * vol(candSizes[s.n - 1]) + solve(useNth).first;
        if (useNthVol < solution.first) solution = { useNthVol, useNth };
    }
    memo[s] = solution;
    return solution;
}

void printOptimalSolution(State s) {
    while (!empty(s.req)) {
        State next = solve(s).second;
        if (next.k < s.k) cout << candSizes[s.n - 1] << endl;
        s = next;
    }
}

int main(int argc, char** argv) {
    int n, k;
    cin >> n >> k;
    vector<array<int, 4>> requestedBoxSizes;
    set<int> lengths, widths, heights;
    for (int i = 0; i < n; ++i) {
        array<int, 4> d;        // d[3] is actually the number of requests for this box size
        cin >> d[0] >> d[1] >> d[2] >> d[3];
        sort(begin(d), begin(d) + 3, std::greater<int>());
        requestedBoxSizes.push_back(d);

        lengths.insert(d[0]);
        widths.insert(d[1]);
        heights.insert(d[2]);
    }

    // Generate all candidate box sizes
    for (int l : lengths) {
        for (int w : widths) {
            for (int h : heights) {
                array<int, 3> cand = { l, w, h };
                sort(begin(cand), end(cand), std::greater<int>());
                candSizes.push_back(cand);
            }
        }
    }

    sort(begin(candSizes), end(candSizes), CompareByVolumeDesc());
    candSizes.erase(unique(begin(candSizes), end(candSizes)), end(candSizes));
    cout << "Number of candidate box sizes: " << size(candSizes) << endl;
    State startState = { requestedBoxSizes, static_cast<int>(size(candSizes)), k };
    long long minVolume = solve(startState).first;
    cout << "Minimum achievable volume using " << k << " box sizes: " << minVolume << endl;
    cout << "Optimal set of " << k << " box sizes:" << endl;
    printOptimalSolution(startState);
    return 0;
}

Example input:

15 5
100 61 35 27
17 89 96 47
31 69 30 55
37 23 39 9
94 11 48 19
38 17 29 36
63 79 80 36
59 52 37 51
86 63 54 7
32 30 11 26
50 88 51 5
74 70 33 14
67 46 4 79
83 94 89 58
65 42 37 69

Example output:

Number of candidate box sizes: 2310
Minimum achievable volume using 5 box sizes: 124069460
Optimal set of 5 box sizes:
(94, 48, 11)
(69, 52, 37)
(100, 89, 35)
(88, 79, 63)
(94, 89, 83)

I'll explain the algorithm behind this if there's interest. It's better than considering all possible combinations of k candidate box sizes, but not terribly efficient.