2D Bin Packing with Multiple Constraints — Finding the Optimal Layout for The Ramen Sensei

Preface

A while ago, out of boredom, I picked up The Ramen Sensei again. It's a small business-simulation game, and both the art style and the gameplay are right up my alley.

One of the mechanics is laying out the ramen shop: you're given a plot of land and several shops, and you can place them however you like. Naturally, the more shops you place, the better.

When I first started playing I didn't think much of it and just placed things casually. But later on, when my popularity wouldn't go up, I suddenly wondered: could I fit all the shops in? Or could I fill as much of this land as possible?

I looked around for information, then found a post that had placed 11 shops (there are 12 in total). Link: https://tieba.baidu.com/p/3583521915?red_tag=2365356271

The OP had simply been playing a Klotski-style puzzle in Excel, shuffling things around until they came up with this layout. But this layout is definitely not optimal, because the plot is 19 cells * 19 cells, i.e. 361 cells, while the 12 shops add up to only 274 cells. The margin for error is huge, which means the chance that all 12 shops can fit is very high. So how do we find such a layout?

I first tried playing Klotski the same way the OP did, then realized it was terribly inefficient, because there are far too many layouts. Trying them one by one won't find it, and there's no pattern to follow either. I then recalled the 2D bin-packing problem I'd tinkered with before, and on closer thought I went, wait, isn't this just 2D bin packing with extra constraints??!!!!

So I treated this as an algorithm problem.

Stating the Problem

If we're going to treat it as an algorithm problem, we definitely need to describe the problem clearly. The problem statement is as follows:

Given a rectangular grid region and several ramen shops of different sizes, each shop being a rectangular block of grid cells and each having an entrance, place these ramen shops into the given region subject to the following constraints.

Constraints:

1. When placing a shop, the angle between its long/short sides and the region's long/short sides must be either 0° or 90° (i.e. we don't consider shoving them in diagonally ♂);
2. Shops cannot overlap with each other;
3. Shops cannot extend beyond the rectangular region;
4. Each shop's entrance has a path leading to the boundary of the rectangular region;
5. Shops are placed strictly on the grid, i.e. all four vertices of a shop lie on grid points;
6. A shop's entrance is adjacent to the shop's boundary and occupies only one cell, as in the example below:

7. Shops can be rotated, but rotation can only be around y=x (with left defined as the positive x-axis and down as the positive y-axis), as shown:

Let me emphasize again: this entire problem is discussed in terms of grid cells. From here on, a point means a cell, and relative positions are counted in numbers of cells—a few cells up, a few cells right; moving down or left is also in cell counts; and so on.

2D Bin Packing

With the problem clearly stated, next comes the related 2D bin-packing problem. The paper I mainly referred to is: https://www.docin.com/p-902429329.html

This paper mainly studies packing on a rectangular region of finite width and infinite height. That said, the underlying ideas are the same, so the methods can be borrowed (freeloaded). I mainly looked at the BL algorithm and an enhanced BL algorithm, first because both are easy to implement and relatively simple, and second because this problem has quite a few constraints: if you use a greedy heuristic or a recursive algorithm, checking constraint 4 is especially hard. In my view, constraint 4 is the most critical of all, and it's also the one that stumped me the longest.

Let me briefly explain the BL algorithm. Imagine you're playing Tetris, except all your pieces are rectangles. Each time you start from the top-right corner, and your placement strategy is: keep pressing the down key; when you can't go down any further, press left; keep pressing left; when you can't go left any further, press down… Cycle like this until you can no longer move both down and left, at which point this piece is placed and you can place the next one.

Then there's the improved BL algorithm. Still Tetris, still starting from the top-right. You first mash the down key; when you can't go down any further, press the left key a little at a time, and whenever you can go down again, press down. It's a bit like going down stairs, until you can no longer move down or left.

These two algorithms satisfy constraints 1, 2, 3, and 5. To make them also satisfy constraints 4, 6, and 7, further modifications and improvements are needed. After several weeks of struggling, I finally found an improved algorithm that works reasonably well.

Algorithm Improvements

The first problem to consider is: how to ensure constraint 4 is satisfied during movement, i.e. how to guarantee that every shop's entrance has a path to the region's boundary. At first I considered checking whether a shop was directly blocking a door, i.e. covering an entrance, as shown:

That definitely doesn't work. I could back up a step when this happens to make sure my ramen shop doesn't cover someone else's entrance, but I still couldn't guarantee that every shop's entrance has a path, for example in a case like this:

How on earth would you determine whether this entrance has a path in such a complicated situation? So trying to analyze it from the blocked-entrance angle doesn't work.

Given the rotation properties in constraint 7, a shop's entrance can only lie on two of its sides:

So I only need to expand each shop by one cell—4x4 becomes 5x5—and then pack them. No matter how you pack, every shop's entrance is guaranteed to have a path! And this is simple to do, and you can still use those two algorithms to place shops without changing them much. Pretty clever, if I do say so myself!

But there's a problem: this wastes a lot of space, and you're still a bit far from the optimum. To get as close as possible to the optimum, I improved both algorithms. After moving a shop according to the original algorithm, I then check that shop: move it up one cell and see if the constraints are still satisfied; move it right one cell and see if the constraints are still satisfied; move it in both directions at once and see if the constraints are still satisfied. That gives five cases:

1. Can move up, but not right

In this case, move up.

2. Can move right, but not up

In this case, move right.

3. Can move in both directions at once

In this case, move in both directions at once.

4. Can move up and can move right, but not both at once

In this case pick one direction; I chose to move up.

5. Can move neither up nor right

In this case, don't move.

I have these shops loop indefinitely, checking and moving, until case 5 occurs and we exit the loop. At that point the shop's placement should be one where it can no longer move.

Genetic Algorithm

With these two improved algorithms, I can generate a reasonably good feasible solution, i.e. one fairly close to the optimum. Next I only need to find the order in which to place the shops, and which shops need to be rotated. How to find that? Random search? Brute force? That would take forever! My attention went back to the paper I mainly referred to, which used a heuristic plus a genetic algorithm. So I thought: if 2D bin packing can be tackled with a genetic algorithm, can I use a genetic algorithm to find this optimum?

So I started learning about genetic algorithms, and after a long stretch of exploring I concluded—it's feasible!

There are plenty of explanations of genetic algorithms online, so I'll just briefly share my understanding of the algorithm.

A genetic algorithm is an algorithm for finding an optimal solution or approximating one. It mainly draws on natural laws such as survival of the fittest to randomly approach the optimum and thereby find it.

Because of its randomness, a genetic algorithm won't get stuck in a local optimum; you only need to add some simple strategies to escape local optima. But also because of its randomness, its convergence speed is fairly random: you might get a pretty good solution right away in one run, and a terrible one after a long time in the next. You also can't guarantee that every run's result is reasonably good. It's a bit like gacha: the solution you randomly get this time might be close, and the next time it might be a bit far.

So I was still pretty nervous when implementing this algorithm. I had no idea whether I could find the optimum; I could only hope to get as close as possible. (Luckily I got lucky in the end—first pull, jackpot. The first run found the optimum after only a little over a hundred iterations. Happy.)

A genetic algorithm has several key pieces: gene encoding, selection, crossover, mutation, and fitness.

Genes determine traits; it's a one-to-one mapping. Relating this to our problem, the trait is the shop layout, and the genes are the order of the shops plus each shop's rotation (rotated or not). With the improved algorithm above, given the shop order and rotation, a unique layout is determined—clearly one-to-one—so we can take shop order and rotation as the genes, and the layout as the trait.

Selection should follow survival of the fittest: better individuals should be more likely to be selected. Common methods include roulette wheel, stochastic universal sampling, tournament, etc. I used roulette wheel here.

Link: https://blog.csdn.net/xinbolai1993/article/details/79458929

Two individuals crossover to produce a new individual; applied to the algorithm, that means two encodings produce one encoding (or a pair of encodings). This process is called a crossover operator. Common crossover operators include PMX, OX, PBX, OBX, CX, SEC, etc. I implemented all six. I originally planned to try them one by one for parameter tuning, but the first one, PMX, already produced a result, hahahaha~

Link: https://blog.csdn.net/ztf312/article/details/82793295

Mutation is simpler. A mutation operator takes one encoding and produces one encoding, i.e. it changes some segments of the encoding, for example changing the order, or changing false to true, and so on. As for how to pick the segments, I referred to OX and PBX among the crossover operators; I won't go into more detail.

An individual's fitness is used to judge how good it is, and it affects the probability of being selected. In this problem, being good can have several metrics, such as high space utilization, or the number of shops placed. Here I chose the sum of the areas of the placed shops as the individual's fitness.

The overall flow of a genetic algorithm is as follows: first generate an initial population, then start looping: compute each individual's fitness, check whether a termination condition is met; if yes, break out and output the best solution; if no, perform selection, crossover, and mutation on individuals in the population to generate a new generation for the next iteration.

On top of this overall flow, I borrowed (freeloaded) from that paper ideas such as using two populations for comparison, an elitist preservation strategy, comparative preferential assignment, a crossover probability formula, a mutation probability formula, circular crossover, circular mutation, and so on. As for the selection, crossover, and mutation operations (which that paper didn't provide), my flow is: given a number of crossovers, each time select two individuals, compute the crossover probability, and if they can crossover, crossover to produce a new individual; compute the mutation probability for the new individual, and if it can mutate, mutate; then put it into the new population; then select individuals from the original population and copy them into the new population until the population size is filled.

Finally

At this point, all the preliminary work I needed to do is done. Next up: just write the code!

PS: The actual code implementation is in the next post. Stay tuned!