1D multiple sized bin packing algorithm with least waste

Question

I am trying to apply a 1D bin packing with unlimited number of bins.

list = [1000, 1200, 2400, 1700, 3000, 500, 2800] # N number of data
bin = [3100, 2700, 2400] # N number of bins with all sizes available

I have already used the https://pypi.org/project/binpacking/ library but it does not apply for multiple sized bins. I want the exact library or code or algorithm which can accurately calculate the answer by using the lowest bins and with the lowest waste. I tried to use this 2D bin packing library https://github.com/secnot/rectpack by converting it to 1D but it has a loophole of not calculating the lowest waste. for ex. if there are only two values left, 400 and 500, then the algorithm should only use a 2400 sized bin, instead, it takes whatever the next bin comes in the line or list.

did you find solution? I think your problem is so similar to mine https://stackoverflow.com/questions/64614071/algorithm-for-distribute-products-to-boxes — sipdorus, Oct 30 '20 at 20:51
I managed to design my own version of logic after failing to find a perfect answer using binpacking library. — Shripal, Nov 01 '20 at 11:41

score 0 · Accepted Answer · answered Dec 10 '20 at 06:56

I managed to create my own logic for this question. As you can see, I have put many comments in my code that will help you understand different segments of the code.

import random
import binpacking

# DISTRIBUTES A DICTIONARY OF LENGTHS (KEY-VALUE = ID-LENGTH PAIR) TO A MINIMAL NUMBER IF BINS WHICH CAN HAVE DIFFERENT VOLUME.
def packing2dOptimizer(b, bin_bucket):

    # OPTIMIZED BINS WILL BE STORED HERE
    bin_list = []

    bin_bucket.append(0)
    bin_bucket.sort(reverse=True)

    # LIST OF DIFFERENCES BETWEEN BIN SIZES
    difference = [0]
    if len(bin_bucket) > 1:
        for index in range(1, len(bin_bucket)):
            difference.append(bin_bucket[0] - bin_bucket[index])

    # FIND THE EXACT BIN WIDTH AS PER USAGE OF PACKINGS
    def checkFinalSize(total):
        bin_width = 0
        for i in bin_bucket: 
            if total <= i: bin_width = i
            else: break
        return bin_width

    # PACK ALL THE VALUES IN BINS WITH MAXIMUM SIZE
    packer_list = binpacking.to_constant_volume(b,bin_bucket[0])

    # CREATE A DETAILED DATA OF BINPACKING
    counter = 0
    for packer in packer_list:
        bin_usage = sum(packer.values())
        bin_width = checkFinalSize(bin_usage)
        bin_waste = bin_width - bin_usage
        bin_data = {
            'bin_id': counter,
            'bin_width': bin_width,
            'bin_usage': bin_usage,
            'bin_waste': bin_waste,
            'pack_data': packer
        }
        counter += 1
        bin_list.append(bin_data)

    # PRINT THE LIST
    area_used = 0
    area_covered = 0
    area_waste = 0
    for i in bin_list: 
        print("Bin", i['bin_width'],":",i['pack_data'], i['bin_waste'])
        area_used += i['bin_width']
        area_covered += sum(i['pack_data'].values())
        area_waste +=  i['bin_waste']
    print()
    print("Area Used:", area_used)
    print("Area Covered:",  area_covered)
    print("Area Waste:",  area_waste)
    print()

    # TAKES TWO PACKED BINS AND THE AVAILABLE SIZES OF ALL BINS AS ARGUMENT
    def optimizer(small_bin, big_bin):
        dict1 = small_bin['pack_data']
        dict2 = big_bin['pack_data']

        # CREATE A NEW DICTIONARY OF DATA OF THE BOTH PACKED BINS
        new_dict = dict1.copy()
        new_dict.update(dict2)
        max_val = max(list(new_dict.values()))

        # FIND A SUITABLE BIN WITH LOWEST SIZE AND WASTAGE
        for size in bin_bucket:
            if size >= max_val:
                new_bins = binpacking.to_constant_volume(new_dict,size)    
                if len(new_bins) <= 2:
                    final_bins = new_bins

        # UPDATE BOTH PACKED BIN VALUES AND RETURNS
        big_bin['pack_data'] = final_bins[0]
        small_bin['pack_data'] = final_bins[1]
        return small_bin, big_bin

    # OPTIMIZE THE BINS TO MINIMIZE THE WASTE
    bin_bucket.sort(reverse=True)
    for small_bin in bin_list:
        if small_bin['bin_width'] == bin_bucket[-2] and small_bin['bin_waste'] > 0:
            for big_bin in bin_list:
                if big_bin['bin_width'] > small_bin['bin_width']:
                    pack_data = list(big_bin['pack_data'].values())
                    for length in pack_data:
                        if length <= small_bin['bin_waste']:
                            # CALL THE OPTIMIZER
                            small_bin, big_bin = optimizer(small_bin, big_bin)
                            
                            # UPDATE THE BIN DATA
                            bin_usage = sum(small_bin['pack_data'].values())
                            bin_width = checkFinalSize(bin_usage)
                            small_bin['bin_width'] = bin_width
                            small_bin['bin_usage'] = bin_usage
                            small_bin['bin_waste'] = bin_width - bin_usage

                            bin_usage = sum(big_bin['pack_data'].values())
                            bin_width = checkFinalSize(bin_usage)
                            big_bin['bin_width'] = bin_width
                            big_bin['bin_usage'] = bin_usage
                            big_bin['bin_waste'] = bin_width - bin_usage

                            break

    # SORT THE OPTIMIZED BINS BY BIN SIZE
    bin_list = sorted(bin_list, key = lambda i: i['bin_width'], reverse = True)

    # PRINT THE LIST
    area_used = 0
    area_covered = 0
    area_waste = 0
    for i in bin_list: 
        print("Bin", i['bin_width'],":",i['pack_data'], i['bin_waste'])
        area_used += i['bin_width']
        area_covered += sum(i['pack_data'].values())
        area_waste +=  i['bin_waste']
    print()
    print("Area Used:", area_used)
    print("Area Covered:",  area_covered)
    print("Area Waste:",  area_waste)

    return bin_list

def main():
    
    # LIST OF DATA THAT WILL BE SELECTED RANDOMLY
    random_data = [ i for i in range(100, 3200,100) ]

    # DIFFERENT SIZE OF VALUES WITH UNIQUE ID ASSOCIATED WITH IT
    b = {
        'a': random.choice(random_data), 
        'b': random.choice(random_data), 
        'c': random.choice(random_data), 
        'd': random.choice(random_data),
        'e': random.choice(random_data),
        'f': random.choice(random_data),
        'g': random.choice(random_data),
        'h': random.choice(random_data),
        'i': random.choice(random_data),
        'j': random.choice(random_data),
        'k': random.choice(random_data),
        'l': random.choice(random_data),
        'm': random.choice(random_data),
        'n': random.choice(random_data),
        'o': random.choice(random_data),
        'p': random.choice(random_data),
        'q': random.choice(random_data),
        'r': random.choice(random_data),
        's': random.choice(random_data),
        't': random.choice(random_data),
        'u': random.choice(random_data),
        'v': random.choice(random_data),
        'w': random.choice(random_data),
        'x': random.choice(random_data),
        'y': random.choice(random_data),
        'z': random.choice(random_data),
    }

    # LIST OF DIFFERENT SIZES OF BINS
    bin_bucket = [2400, 2700, 3100]

    bin_list = packing2dOptimizer(b, bin_bucket)

main()

1D multiple sized bin packing algorithm with least waste

1 Answers1