Bin packing (1D, 2D, 2D and a bit more constraints?

Started by Noisy Cricket, June 09, 2015, 06:38:51 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Noisy Cricket

Hi All,

I've been hooked on Visio for the last 2.5 years, spending a lot of my free time fiddling about and trying to promote Visio at work.
We're a pretty big dredging/offshore shipping company but it seems that most people still/only associate Visio with Org. charts.
Coincidentally (but i guess that's with most people), everyone seems to make those the wrong way.

Anyway, I'm now turning my attention toward "bin packing" or "knapsack problem" which is essentially an algorithm to try and optimise a certain amount of items/cost/whatever in a given amount of space/time/cost/whatever.

Typical field applications would be: 1D steel bar cutting, 2D nesting. I was thinking more along the line of trying to optimise the amount of modules (part of factories) on a given amount of vessel deck space, depending on a given schedule that modules become available at a given fabrication yard. (yes this is also going towards the travelling salesmen conundrum). The information would typically be stored/taken from an excel sheet and consists of Module ID, Length, Width, Height, Weight. and the vessel's deck space, width, length and carrying capacity, ready for shipment and required on site as constraints.

Although I've found multiple Excel examples, the issue hasn't seemed to find its way to Visio yet. This surprised me in a sense given that Visio, being able to draw simple or complex shapes.

I was wondering whether anyone ventured into this and if so, what the experience was doing this in Visio.

If nobody has "boldly gone where no one has gone before", consider it a challenge :)

I've not started work just yet apart from creating a separate macro to import the module shapes and corresponding information as shape data and vessel library but looking forward to anything the forum could add here.


Next up would be network optimisation attempting to find an optimal solution to ship the modules with a certain amount of vessels etc. etc.

P.S. I'm aware that commercial packages are available to model this but..... there's no fun in that is there.

Thanks in advance for any and everything,

Gijs (if you're english/american, don't bother trying to pronounce this)







Yacine

Hi Gijs,
I agree with you that this a very interesting project. A CAD software would certainly by less ergonomic.
And having the possibility to attach all the data you want to the shapes, is a definite advantage.
I now you want to some clever advice ... sorry, I don't know enough about the matter.
If you come with a precise question, I'd be pleased to try to help.
Met vriendelijke groeten,
Yacine
Yacine

Noisy Cricket

Well,

I suppose the actual precise question isn't necessarily related to Visio but rather to the optimisation algorithm behind it.
Getting the data on paper isn't really the problem as this is probably the easiest thing in Visio.

I'll give it some more thought.

Noisy Cricket

So! I gave it some more thought but haven't been able to get my head around it.

What I did come by is a post by Yacine helping someone out with the "shortest path"-problem, which supposedly is a disquised bin packing problem. :) Both are trying to minimise distance / number of boxes (aka bins) while still accommodating a certain amount of volume (whatever needs to be transported).

So how do I get from Yacine's shortest path.vsd to something that can work with multiple smaller boxes and multiple larger boxes (bins) &  unit cost.

Care to give it another try Yacine?!


Gijs



Yacine

#4
Sure, but I'd need more infos, drawings, etc.
Yacine

Noisy Cricket

#5
Ok, here goes & this is what I have so far:

1) Visio imports a list of vessels (HTV) and cargoes (cargo) from an xlsx sheet and drops these on the page.
Both shapes are pre-defined in the LMT.VSS with the appropriate shape and user data readily available.

2) A macro will update the HTV cargo summary and cargo-vessel relationship and report same in the respective shape texts
Note: Removing a cargo from the vessel deck does not update the cargo-vessel relationship (as I want to know where the cargo came from in the first place.

The obvious goal is to attempt to optimally store the cargoes on the respective vessel decks.

The definition of optimal:

1) High deck utilisation
2) Lowest vessel cost (relates to deck spacing)

General guideline:
1) Cargo may be rotated freely (although a restricting per cargo would be nice as this is a real-life restriction sometimes)
2) Vessel's have unlimited weight capacity (not really, but that's for later)
3) Vessel deck space is linearly related to vessel cost (not really, it's related to vessel age, fuel consumption and transit distance)
4) 2 smaller vessels will generally be more expensive than 1 larger vessel (due to mobilisation cost (think of cab fare in the Netherlands, as soon as you close the door you pay a minimum fee)

There's plenty to be found on the subject as it translates to all kinds of practical issues:
http://codeincomplete.com/posts/2011/5/7/bin_packing/

My thoughts on the algorithm:
Quick assessments:
1) Add all lower values of width/length and divide this by the deck length the cheapest vessel. Alternatively this could be done by area too.
2) Sort modules by width/length (whichever is smaller) and try and make a first categorisation by required vessel width.

Bin packing:
1) Decreasing fit: sorting by size from largest to smallest and start filling the smallest vessel that can accommodate the largest piece of cargo
2) then either fill the remaining space with the largest cargo that fits this remaining space OR attempt to gain a higher deck utilisation by decreasing the vessel size (Or both?)

Looking forward to everyone's thoughts!


Gijs





Yacine

I'm missing the destination of the cargos.
Or did I misunderstand the task and all the vessels are heading for the same destination? ie pack as much cargos on all vessels?
Yacine

Noisy Cricket

#7
Well, technically there could be several fabrication locations, muster points, and even multiple destinations but wanted to take it step by step. But you're right, no destinations provided at this moment and yes, they'd generally be the same location.

The basic question would be how to A) meet the schedule (maybe with some slack), B) have highest deck utilisation with C) likely lowest cost.

Generally a piece of cargo would have a "RFS" (ready for shipment) date and a "ROS" (required on site) date driving the schedule.
In between you'd have a load-out, transit, discharge and potentially even two more phases in-between. After discharging the cargo, a vessel will either A) demobilise or B) transit to the nearest/high priority yard to pick up more cargoes. (provided size/weight of the cargo is possible on the respective vessel).


Having said that, it's a bit of a chicken and egg story since the shipping schedule depends on vessel capacity, speed and RFS/ROS dates but it could very well be that by dispatching a larger vessel and allowing some slack on the ROS dates of cargoes, an overall better solution is found.

But first things first: slapping cargoes on multiple ships
In case there would be several pick-up and drop-off points and maybe the possibility to have a single vessel pass by several of each.... then I get lost in the "logistic"-spaghetti.....


Noisy Cricket

Yacine,

I came across this page which supposedly has an vb algorithm for an exhaustive bin packing solution.

http://www.devx.com/dotnet/Article/36005/0/page/5

Any idea how this would/could be translated to visio across multiple shapes (bins?)

Yacine

Hi Gijs,
Yes, your link looks very promising. I had a first look at the code and understood so far, that a structure needs to be built up front of the shown function.
I was not able yet to set up something.

Ideally, I'd see for this kind of problem, a solution based on functional (https://en.wikipedia.org/wiki/Functional_programming). The problem is, that every time I tried to dig in it, I had to resign after a while and got frustrated.
The search "prolog bin packing" gives quite some links. But this is beyond my capabilities.

I don't want to promise, but if I find some time, I'll think some more about your problem.

Cheers,
Yacine
Yacine

Noisy Cricket

Hey Yacine,

Thanks for the effort so far.... I've been able to do most of my work of getting shapes on the page from the excel file and populating it with shape data but couldn't get much further in actually placing "cargoes" than putting one in front of the other. :)

I'm hoping to write a piece of procedure that keeps track of the length/width that's taken up on deck and the size of remaining space(s) for modules to fit.

The frustrating part sounds surprisingly familiar (especially since other people were able to solve the issue :))

Let's keep our hopes up!

Yacine

Hi Gijs,
sorry but I am blocked at finding out the residual free space.
One could use some visio function (spatial neighborhood), but this certainly very slow - considering the thousands of necessary iterations.
Yacine

Noisy Cricket

That would be the exhaustive approach :) (which supposedly takes ages)

I'd be happy with reversed first fit (trying to fit big modules first and fill up the space afterwards.

or even a procedure that tries it's best at getting a limited amount of modules onboard and stowing them in such a way that they don't overlap.



Noisy Cricket

#13
Hi all,

The 2d bin packing seems to keep haunting me.
Now aiming a bit lower. I'm resorting to do the first selection of shapes/containers manually which then leaves the "placement issue".

Basically boils down to this:
1) Set of rectangle shapes (say 10 shapes with varying length (between 10 and 30m) and width (between 5 and 15m)
Rectangles can be sorted by size, length and width (in excel)
2) Container with fixed size (say 100x36m)

Goal:
Fit the rectangle shapes in the container at a given spacing (say 2m).
The idea is not getting the container completely full but to automate placement of the shapes.

I was wondering whether the bounding box / shape overlap / spatial could prove useful in incrementally moving shapes from the bottom left corner of the container until it doesn't overlap any of the other shapes in the container. Maybe a variation on the space shapes function?!

Any thoughts are welcome!

for inspiration:
http://codeincomplete.com/posts/bin-packing/
http://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu