matlab 使用算法确定运输箱的理想尺寸

我在一家公司的物流部门工作，最近我们一直在努力缩小我们使用的不同 Package 选择的数量。
我有所有必要的产品数据，如长度，宽度，高度，体积和销售数据。
因此，我在想，是否有可能使用一种算法来聚类不同数量的产品，也许还可以考虑哪些尺寸的销售最多，以确定，哪些盒子尺寸将是理想的。（考虑多久一个产品的销售是次要的，所以这不是绝对必要的）
我想要的是，我可以给予算法多少不同的盒子大小我想要的数量，算法应该确定在哪里放置限制，这样就有一个解决方案，我们有每一个产品。优化的目标是最小的体积浪费，同时也不使用超过不同的盒子设置数量。
同样重要的是要注意，产品的方向和每盒的数量是固定的，所以没有必要确定如何 Package 产品和有多少进入一个盒子理想或类似的东西。
什么样的算法可以用来解决这样的问题，我有什么选择来编写它们？我在考虑使用Matlab，但也会考虑其他可能的选择。我想编写它，而不是简单地使用现有的程序，如SPSS。
提前感谢，如果我的英语不是最好的，请原谅，我不是一个母语。

下面的C++程序将为小示例找到最佳解决方案。对于10个输入框大小，每个大小的维度在1..100范围内随机选择，并且对于1..10个任意数量的框大小可供选择，它在我的计算机上几秒钟内计算出答案。对于15个输入框大小，它需要大约10秒。对于20个输入框大小，我可以在大约3分钟内计算出4个选择的盒子大小，内存成为一个问题（它使用了大约3GB），我不得不增加链接器的默认堆栈大小以避免堆栈溢出。

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

输入示例：

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

输出示例：

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)

如果大家感兴趣的话，我会解释一下这背后的算法，这比考虑k个候选框大小的所有可能组合要好，但效率不是很高。

matlab 使用算法确定运输箱的理想尺寸

1条答案

相关问题

热门标签

最新问答