Skip to main content
 首页 » 编程设计

python之使用 PuLP 的 3D 装箱

2024年12月31日8Renyi-Fan

我正在尝试使用线性规划优化器解决 NP 难 (https://en.wikipedia.org/wiki/Bin_packing_problem) 的 3D 装箱问题。我刚开始使用 PuLP 并面临一些问题。我已经详细添加了我的约束、代码、输出和我需要的帮助。

约束:

目标函数是enter image description here我希望模拟以下约束 enter image description here其中 enter image description here

Python 代码:

     from pulp import * 
 
        #Variable Decleration 
        prob = LpProblem('BinPacking', LpMinimize) 
 
        ps = [LpVariable("p{0}{1}".format(i + 1, j + 1), cat="Binary") 
              for i in range(parcel.parcels) for j in range(parcel.containers)] 
        print(ps) 
 
        us = [LpVariable("u{0}".format(j + 1), cat="Binary") for j in range(parcel.containers)] 
        print(us) 
    #location of left bottom (x,y,z) 
        xs = [LpVariable("x{0}".format(i+1), cat="Integer") for i in range(parcel.parcels)]         
 
        ys = [LpVariable("y{0}".format(i+1), cat="Integer") for i in range(parcel.parcels)]     
 
        zs = [LpVariable("z{0}".format(i+1), cat="Integer") for i in range(parcel.parcels)] 
 
        rs = [LpVariable("r{0}".format(i+1), cat="Integer") for i in range(parcel.parcels)]        
 
        ss = [LpVariable("s{0}".format(i+1), cat="Integer") for i in range(parcel.parcels)]    
 
        ts = [LpVariable("t{0}".format(i+1), cat="Integer") for i in range(parcel.parcels)] 
 
    #for the overlapping constraint 
        xik = [LpVariable("xik", cat="Binary")] 
        yik = [LpVariable("yik", cat="Binary")] 
        zik = [LpVariable("zik", cat="Binary")] 
        xki = [LpVariable("xki", cat="Binary")] 
        yki = [LpVariable("yki", cat="Binary")] 
        zki = [LpVariable("zki", cat="Binary")] 
 
    #orientation 
        a = ["1", "2", "3"] 
        b = ["1", "2", "3"] 
        os = [LpVariable("o{0}{1}".format(j, k), cat="Binary")for j in a for k in b] 
    print(os)      
 
 
# Objective function 
 
     t = lpSum([us[i] * parcel.conVolume[i] for i in range(parcel.containers)]) - sum(parcel.parVolume) 
        prob += t 
        print(t) 
 
 
# Dimension Constraint 
     a = [] 
        for j in range(parcel.parcels): 
            b = rs[j] - xs[j] 
            a.append(b) 
            a[j] = parcel.parLength[j] 
        print(a) 
        for j in range(parcel.parcels): 
            u = ps[j * parcel.containers: (j + 1) * parcel.containers] 
            condition1 = sum([u1 * w for u1, w in zip(u, parcel.conLength)]) 
            #print(rs[j]) 
            t = rs[j] <= condition1 
            prob += t 
            print(t) 
 
# Overlapping Constraint 
    for i in range(parcel.parcels): 
        if rs[i - 1] <= xs[i]: 
            xik = 1 
            xki = 0 
        elif xs[i] < rs[i + 1]: 
            xik = 0 
            xki = 1 
    print(xik, xki) 
 
    for i in range(parcel.parcels): 
        # for k in range(parcel.parcels): 
        # u = bs[i * parcel.containers: (i + 1) * parcel.containers] 
        if ss[i - 1] <= ys[i]: 
            yik = 1 
            yki = 0 
        elif ss[i] < ys[i - 1]: 
            yik = 0 
            yki = 1 
    print(yik, yki) 
 
    for i in range(parcel.parcels): 
        # for k in range(parcel.parcels): 
        # u = bs[i * parcel.containers: (i + 1) * parcel.containers] 
        if ts[i - 1] <= zs[i]: 
            zik = 1 
            zki = 0 
        elif ts[i] < zs[i - 1]: 
            zik = 0 
            zki = 1 
    print(zik, zki) 
 
    li = [] 
    for j in range(parcel.parcels): 
        u = ps[j * parcel.containers: (j + 1) * parcel.containers] 
        # print(u) 
        li.append(u) 
    # print(li) 
 
    r = [] 
    for i in range(parcel.containers): 
        z = [x[i] for x in li] 
        r.append(z) 
 
    for i in range(0, len(r)): 
        for j in range(0, len(r[i])): 
            if (j == len(r[i]) - 1): 
                s = r[i][-1] + r[i][0] 
            else: 
                s = r[i][j] + r[i][j + 1] 
            # print(s) 
            t = xik + xki + yik + yki + zik + zki >= s - 1 
            prob += t 
            print(t) 
 
    for i in range(parcel.containers): 
        for j in range(parcel.parcels): 
            a = rs[j - 1] <= xs[j] + (1 - xik) * parcel.conLength[i] 
            b = xs[j] + 1 <= rs[j-1] + (xik * parcel.conLength[i]) 
            c = ss[j - 1] <= ys[j] + (1 - yik) * parcel.conWidth[i] 
            d = ys[j] + 1 <= ss[j-1] + (yik * parcel.conWidth[i]) 
            e = ts[j - 1] <= zs[j] + (1 - zik) * parcel.conHeight[i] 
            f = zs[j] + 1 <= ts[j-1] + (zik * parcel.conHeight[i]) 
 
            prob += a, b 
            prob += c, d 
            prob += e, f 
            print(a, b, c, d, e, f) 
 
 # 
 
    Orientation Constraint   
 
    for i in range(parcel.parcels): 
     p = (rs[i] - xs[i]) == ((os[0] * parcel.parLength[i])+(os[1] * parcel.parWidth[i])+(os[2]*parcel.parHeight[i])) 
          q = (ss[i] - ys[i]) == ((os[3] * parcel.parLength[i]) + (os[4] * parcel.parWidth[i]) + (os[5] * parcel.parHeight[i])) 
                r = (ts[i] - zs[i]) == ((os[6] * parcel.parLength[i])+(os[7] * parcel.parWidth[i])+(os[8]*parcel.parHeight[i])) 
                prob += q 
                prob += p, r 
                print(p) 
                print(q) 
                print(r) 
 
        # Output 
            o11 = 0.0 
            o12 = 0.0 
            o13 = 0.0 
            o21 = 0.0 
            o22 = 0.0 
            o23 = 0.0 
            p11 = 1.0 
            p12 = 0.0 
            p21 = 1.0 
            p22 = 0.0 
            p31 = 1.0 
            p32 = 0.0 
            r1 = 0.0 
            r2 = 0.0 
            r3 = 0.0 
            s1 = 0.0 
            s2 = 0.0 
            s3 = 0.0 
            t1 = 0.0 
            t2 = 0.0 
            t3 = 0.0 
            u1 = 1.0 
            u2 = 0.0 
            x1 = 0.0 
            x2 = 0.0 
            x3 = 0.0 
            y1 = 0.0 
            y2 = 0.0 
            y3 = 0.0 
            z1 = 0.0 
            z2 = 0.0 
            z3 = 0.0 

问题/帮助:

  1. 所有输出值为 0。我不确定我的约束定义是否有问题。有人可以帮助检查我的代码吗?

谢谢!

请您参考如下方法:

欢迎来到SO!我没有检查你的完整问题表述,但我认为你的目标函数至少是错误的。我的理解是,目标应该是使用的容器数量:

# Objective - minimise wasted volume = volume of chosen boxes - volume of parcels 
    prob += lpSum([us[i] * parcel.conVolume[i] for i in range(parcel.containers)]) - sum(parcel.parVolume) 

如果我在上面进行更改,我得到的输出是:

('Status:', 'Optimal') 
('Objective value:', 45.0) 
 
The values of the variables :  
 
('p11', '=', 1.0) 
('p12', '=', 0.0) 
('p21', '=', 1.0) 
('p22', '=', 0.0) 
('p31', '=', 1.0) 
('p32', '=', 0.0) 
('u1', '=', 1.0) 
('u2', '=', 0.0) 

所以至少目标现在正在工作 - 并且它似乎只使用一个容器解决了包装问题,假设所有约束都设置正确(我没有检查它们)。