csp材料切割问题

csp(cutting-stock problem)材料切割问题是最优化问题中的一个子问题,定义如下:从一种(或几种)指定长度的材料,要求切割出不同长度的材料(不同长度材料的数量不同),如何最节省。这个问题在工程领域应用广泛,比如说切割钢筋、管材(往多个车上装货物问题也是这一类)。csp问题属于NP-hard问题,其编程解法可以归为整数线性程序。

1.公式与计算流程

标准的csp问题可描述如下:需要得到m种不同长度的材料,每种长度的材料又需要q.j个(j=1,…,m),然后我们把所有可能的用料组合方式列出来(比如一共有n种组合方式),每种用料组合方式我们标记为x.i,然后,整数线性方程可以表示如下:
image
a.ij是在i种组合方式中第j种材料的用量,c.i是第i种组合方式中的材料使用数量(如果m种材料长度一样,那么问题就变为了bin packing problem)。

例子:一维csp问题

我们现在有很多5600mm长的管子,需要切割出下面要求的小管子:
image
计算过程:
根据上面的要求,进行材料组合,一共有308种组合方式,最优的情况下,需要使用73根管材,同时浪费率为0.401%(这样的组合一共有19种),其中一种组合的配置如下:
image

2.csp问题的进一步描述

上面的例子是一个一维的csp问题,相应的,还有二维、三维csp问题。一维问题对应的实际例子有比如切割管材、电线、钢筋,二维问题对应的实际例子有比如切割木板、衣服、草坪。在二维问题中,如果需要切割出来的是不规则的形状,则又可以延伸为嵌入问题。三维的csp问题常见的例子是向容器(集装箱、仓库)里放东西。

更多阅读:
1. R包:gbp-vignette
2. Bin Packing Problem using GA, PSO, FA, and IWO

发表评论