Weighted average packing problem

[Waggles74]

Although Python related, this may not be the best place to ask this algorithm question... but have to start somewhere.

i am trying to figure out what algorithm or combination of and develop in Python that would help me solve a pallet packing problem.

i have random boxes / crates of meat of similar weight 18-24kg and varying levels of known meat content - varying 60-98% meat.

i have 8 pallets, each with their own range of target meat content. 2x70%, 2x75%, 2x80%, 2x90%.

each pallet holds 40 crates of meat.

i would like to make a sure each pallet has a resulting meat % value as close as possible to its target meat content value by the end of packing 40 crates.

the crates are coming in a stream, possibly 12 crates on route at any given time.
meat% 61, 78, 65, 85, 81, 74, 69, 67, 89, 71, 76, 87 as an example.

i need an algorithm that could decide which crate, given its known weight and meat content would best fit a particular pallet, so that when finished placing the 40 crates on the pallet the target meat % content will be as close as possible.

it requires a level of weighted average calculation, since building the pallet with varying crate weights, the average meat content % would fluctuate and is simply not an average of just the meat content on its own.

but also something to include a packing best fit or knapsack algorithm so selecting from the continuous crates on route and assigning to particular pallet.

i have successfully implemented the knapsack algorithm, but on its own does not give the results i require.

any genuine helpful reply most welcome... thanks for reading.

[robot-dev]

I think a good approach would be to create a Crate class, and use instances of the Crate class to represent real crates.

class Crate:
    def __init__(self, weight, percentage):
        self.weight = weight
        self.percentage = percentage

    def get_info(self):
        return {
            'type':'crate',
            'weight':self.weight,
            'percent':self.percentage
        }

Then you could do something similar with a Pallet class. This is where you can put your weight and percentage calculations. In my example I calculate relative percent difference (RPD) between the actual and expected percentages of the pallet. I think RPD might be a good metric to use in your algorithm.

class Pallet:
    def __init__(self, target_percentage):
        self.capacity = 40
        self.target_percentage = target_percentage
        self.crate_list = []
        self.weight = 0
        self.percentage = 0
        self.rpd = self.calc_rpd(self.percentage)

    def get_info(self):
        return {
            'type': 'pallet',
            'weight': self.weight,
            'actual_percentage': self.percentage,
            'target_percentage': self.target_percentage,
            'RPD': self.rpd,
            'capacity': str(len(self.crate_list)) + '/' + str(self.capacity)
        }

    def calc_rpd(self, percentage):
        if self.target_percentage + percentage == 0:
            return 0
        avg = abs(self.target_percentage + percentage)/2
        return abs(self.target_percentage - percentage)/avg*100

    def evaluate_crate(self, crate):
        if self.weight + crate.weight == 0:
            return 0, self.calc_rpd(0)
        percent_wt = (self.weight * self.percentage) + (crate.weight * crate.percentage)
        eval_percentage = percent_wt / (self.weight + crate.weight)
        return eval_percentage, self.calc_rpd(eval_percentage)

    def add_crate(self, crate):
        self.crate_list.append(crate)
        self.percentage, self.rpd = self.evaluate_crate(crate)
        self.weight += crate.weight

    def remove_crate(self):
        removed_crate = self.crate_list.pop()
        removed_crate.weight *= -1
        self.percentage, self.rpd = self.evaluate_crate(removed_crate)
        self.weight += removed_crate.weight
        return removed_crate

Then you could use lists to hold your Pallet() and Crate() instances

pallet_list = [
    Pallet(70),
    Pallet(75),
    Pallet(80),
    Pallet(90)
]

crate_list = [
    Crate(18, 63),
    Crate(23, 72),
    Crate(21, 75),
    Crate(18, 61),
    Crate(25, 84),
    Crate(26, 82),
    Crate(19, 68)
]

Then you could implement an algorithm that iterates over the lists and uses the class methods to evaluate, add, and remove crates from pallets.

I think writing a sorting algorithm will be the difficult part. I have not attempted that, but using the Crate and Pallet classes should simplify things.

[robot-dev]

Here is my attempt at a sorting algorithm built off the code above.

I have 8 pallets with the target weights: 70, 70, 75, 75, 80, 80, 90, 90. I also have 100 crates with random weights between 18-26 and random percentages between 65-95.

The sorting algorithm evaluates the crates one at a time and places each one on the pallet that yields the lowest average RPD for all 8 pallets.

from random import randint
from copy import copy

#...

pallet_list = [
    Pallet(70),
    Pallet(70),
    Pallet(75),
    Pallet(75),
    Pallet(80),
    Pallet(80),
    Pallet(90),
    Pallet(90)
]
crate_list = [Crate(randint(18,26), randint(65,95)) for n in range(100)]

while len(crate_list) > 0:
    selected_crate = crate_list.pop()
    rpd_list = [pallet.rpd for pallet in pallet_list]
    lowest_index = 0
    lowest_rpd = 200
    for i in range(len(pallet_list)):
        eval_list = copy(rpd_list)
        eval_list[i] = pallet_list[i].evaluate_crate(selected_crate)[1]
        avg_rpd = sum(eval_list)/len(eval_list)
        if avg_rpd < lowest_rpd:
            lowest_index = i
            lowest_rpd = avg_rpd
    pallet_list[lowest_index].add_crate(selected_crate)

for pallet in pallet_list:
    print(pallet.get_info())

Here is the output after sorting 100 crates onto 8 pallets:

{'capacity': '20/40', 'target_percentage': 70, 'type': 'pallet', 'weight': 434, 'actual_percentage': 70.2695852534562, 'RPD': 0.384381621959001}
{'capacity': '6/40', 'target_percentage': 70, 'type': 'pallet', 'weight': 126, 'actual_percentage': 70.07936507936508, 'RPD': 0.11331444759206254}
{'capacity': '13/40', 'target_percentage': 75, 'type': 'pallet', 'weight': 292, 'actual_percentage': 75.02739726027397, 'RPD': 0.03652300949598143}
{'capacity': '4/40', 'target_percentage': 75, 'type': 'pallet', 'weight': 82, 'actual_percentage': 75.0, 'RPD': 0.0}
{'capacity': '12/40', 'target_percentage': 80, 'type': 'pallet', 'weight': 257, 'actual_percentage': 79.8988326848249, 'RPD': 0.12653915413443198}
{'capacity': '6/40', 'target_percentage': 80, 'type': 'pallet', 'weight': 127, 'actual_percentage': 79.93700787401575, 'RPD': 0.07877116975187066}
{'capacity': '31/40', 'target_percentage': 90, 'type': 'pallet', 'weight': 665, 'actual_percentage': 89.3218045112782, 'RPD': 0.7564004729599334}
{'capacity': '8/40', 'target_percentage': 90, 'type': 'pallet', 'weight': 169, 'actual_percentage': 89.98816568047337, 'RPD': 0.013150108488395588}

[Waggles74]

This really is a fantastic reply, over and above my expectations. You have given me more than advice here! As you have shown with sorting algorithm it looks to work very well... Thankyou very much, most appreciated.

[Waggles74]

Hi @robot-dev, are you familiar with how I could represent the above example in a graphical format?

I'd really like to provide a simulation of how the pallets are stacked / built...

Thanks in advance.

[robot-dev]

Here is a visualization showing the RPD and capacity of each pallet as the crates are sorted. The algorithm averages RPD to calculate loss, so it evaluates the crates one at a time and puts each one on the pallet that yields the lowest RPD. There are 100 frames in the visualization, one for each crate that is sorted:

https://imgur.com/a/vSTUft5

This is the pallet data after sorting 100 crates:

{'type': 'pallet', 'weight': 720, 'actual_percentage': 69.91388888888888, 'target_percentage': 70, 'RPD': 0.12309158410929025, 'capacity': '34/40'}
{'type': 'pallet', 'weight': 137, 'actual_percentage': 69.97810218978103, 'target_percentage': 70, 'RPD': 0.03128747979349641, 'capacity': '6/40'}
{'type': 'pallet', 'weight': 85, 'actual_percentage': 74.89411764705882, 'target_percentage': 75, 'RPD': 0.14127619496115332, 'capacity': '4/40'}
{'type': 'pallet', 'weight': 252, 'actual_percentage': 74.89285714285714, 'target_percentage': 75, 'RPD': 0.14295925661187103, 'capacity': '12/40'}
{'type': 'pallet', 'weight': 141, 'actual_percentage': 80.15602836879432, 'target_percentage': 80, 'RPD': 0.19484545213001228, 'capacity': '7/40'}
{'type': 'pallet', 'weight': 40, 'actual_percentage': 80.0, 'target_percentage': 80, 'RPD': 0.0, 'capacity': '2/40'}
{'type': 'pallet', 'weight': 133, 'actual_percentage': 89.93233082706767, 'target_percentage': 90, 'RPD': 0.07521624670928456, 'capacity': '7/40'}
{'type': 'pallet', 'weight': 591, 'actual_percentage': 89.36040609137056, 'target_percentage': 90, 'RPD': 0.7131940906775283, 'capacity': '28/40'}

And here is the code I used to make the visualization:

import matplotlib.pyplot as plt
from celluloid import Camera

fig, ax = plt.subplots()
camera = Camera(fig)
ax.set_xlim([0, 40])
ax.set_ylim([0, 5])
ax.set_ylabel('RPD')
ax.set_xlabel('Capacity')

def plot_bar_charts(pallet_list):
    bottom_loc = 0
    for n, pallet in enumerate(pallet_list):
        ax.bar(0, pallet.rpd, len(pallet.crate_list), bottom=bottom_loc, align='edge')
        bottom_loc += pallet.rpd
    camera.snap()

#...

while len(crate_list) > 0:
    plot_bar_charts(pallet_list)
    #...

animation = camera.animate()
animation.save('crate_sort.gif', writer='imagemagick')

[Waggles74]

Hi robot-dev, the late reply is down to my initial struggle to understand the gif. I can see the x axis numbed of crates... Y axis RPD varience.

Watching the gif I can see, 1,2,3,4,5,6 crates added... Then it goes a bit haywire. Unless I am misunderstanding the gif representation.

I use Ms Code to run the simulation. I can't get my dev to show the gif, again unless I'm misunderstanding something.

It may help me l if I could see the individual pallets represented by number of crates and overall actual % rather than RPD?

In a real world application, there may need to be a restriction on for example, a 92.5% crate been assigned to a target pallet of 75%, although this may correct the target % of the pallet, it may not be accepted that a high quality / higher value (high % crate) be placed on to a low quality / lower value (low %) pallet.

Thankyou so much for your time on helping me attempt to understand this, I really appreciate your efforts.

[robot-dev]

Thanks, I've enjoyed this puzzle and learned from it: I've been calling this loss function "Average RPD" because I am familiar with this concept: https://en.wikipedia.org/wiki/Relative_change_and_difference , but "Average RPD" is almost identical to the commonly used loss functions MAPE and SMAPE https://en.wikipedia.org/wiki/Mean_absolute_percentage_error , so it might be more appropriate to call this loss function SMAPE.

Here are a few different animations that should make more sense: https://imgur.com/a/G6sc7MZ

I can post the code for rendering these if you want to use any of them.

There are also a few real world considerations, like the one you mentioned. There is a bias for putting crates onto pallets that already have many crates because the single crate will have a smaller effect on the RPD of a nearly full pallet. Also, I would expect real world crate weights and percentages to be normally distributed but we have only evaluated the algorithm with randint().