箱装包装问题的一个特例 [英] A special case of bin packing problem
问题描述
亲爱的专家，
我有一个真实的生活场景，我需要解决一个与装箱问题有点类似的建筑相关问题。情况如下：
我有大量的电缆卷筒/鼓（大概是20,000个数字），每个都有不同的长度（随机长度在200米到3,000米之间）其中的电缆。
我必须切割大量不同长度的电缆（随机变化从1米到1000米）。
我想把电缆分配给这些鼓，有两个目标即。 （a）尽量减少浪费或尽量减少用于整个分配的总电缆（b）最大化废电缆的长度（例如，在绝对必要时，我会尽量浪费一条20米的电缆而不是浪费两条10米电缆）以增加机会可重复使用。
我使用动态算法（类似于解决子集求和问题）来找到最适合特定电缆卷轴/鼓并得到一个相当好的解决方案
但是，由于以下原因，这不是最佳解决方案：
（1）I不知道在开始时哪个鼓首先进行分配。我开始分配的顺序极大地影响了整体的浪费。
（2）当有多个完美组合可能为特定鼓的零浪费时，选择正确的组合对于整体优化来说，这是我的挑战。
（3）我最后为鼓所造成零浪费，我实际上应该保留一些故意浪费用完一些特定的电缆，这将导致我最大限度地减少浪费。这意味着，为滚筒零浪费不一定是最好的解决方案，（特别是当电缆长度在300到800米之间时）
寻求你的帮助！
问候
我的尝试：
尝试使用动态算法解决子集和问题
Dear Experts ,
I have a real life scenario, where I need to solve a construction related problem somewhat similar to bin packing problem.The situation is as follows :
I have large number of cable reels/drums (lets say in the order of 20,000 numbers) each having varying lengths (random lengths between 200 meter to 3,000 meter) of cable in it.
I have to cut a large number of cables of different lengths (that randomly varies from 1 meter to 1000 meter).
I want to allocate the cables to these drums with two objectives viz. (a) minimize wastage or minimize total cable used for the whole allocation (b) Maximize the length of waste cables (e.g. instead of wasting two 10 meter cable, when absolutely necessary, I would try to waste one 20 meter) to increase the chance of re-usability.
I have used a dynamic algorithm (similar to solving a subset sum problem) to find the best fit for a specific cable reel/drum and get a fairly good solution.
However, this is not the most optimum solution for the following reasons :
(1) I don't know at the beginning which drum to take first for the allocation. The sequence at which I start allocation vastly affects the overall wastage.
(2) When there are multiple perfect combinations possible for zero wastage for a particular drum, choosing right combination from that for a overall optimization is my challenge.
(3) I end up making zero wastage for a drum, where I should actually keep some deliberate wastage to use up some specific cable, that will lead me to a over all minimized wastage. That means, making zero wastage for a drum is not necessarily the best solution, (especially when the cable lengths are in the order between 300 to 800 meter)
Seek your help !
Regards
What I have tried:
Tried with dynamic algorithm for subset sum problem
推荐答案
此问题适合名为使用整数进行线性编程的域数字。
需要书籍才能解释算法的有效性。问题是如此困难，以至于公司只是出售程序来解决这个问题。
整数编程 - 维基百科 [ ^ ]
减少库存问题 - 维基百科 [ ^ ]
1解决方案是生成适合每个鼓长度的所有可能的电缆组合。然后选择一个以减少浪费。
This problem fit in a domain named "Linear Programming with Integer Numbers".
It takes books to explain how efficient algorithms are working. The problem is so difficult that companies are selling programs just to solve this problem.
Integer programming - Wikipedia[^]
Cutting stock problem - Wikipedia[^]
1 solution is to generate all possible combination of cable that fit in each drum length. Then pick ones to minimize waste.
我有大量的电缆卷筒/鼓（大概是20,000个数字），每个都有不同长度（随机长度在200米到3,000米之间）的电缆。
I have large number of cable reels/drums (lets say in the order of 20,000 numbers) each having varying lengths (random lengths between 200 meter to 3,000 meter) of cable in it.
鼓的数量非常重要，它是重要的鼓长度数。
The number of drums do nit matters, it is the number of drum length which matters.
我要削减一大堆不同长度的电缆（随机变化范围从1米到1000米）。
I have to cut a large number of cables of different lengths (that randomly varies from 1 meter to 1000 meter).
如果最小电缆长度为1米，则废弃物是鼓状，剩余电缆较短。
If minimum cable length is 1 meter, waste is drum with shorter cable remaining.
这篇关于箱装包装问题的一个特例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
