How to calculate the minimum number of groups, by grouping groups with capacity together?

Question

I need to group cars (and their passengers) with other cars, and I don't know how to approach this problem.

If I have, for example, 3 cars. Car A with 7 seats and 2 passengers (3/7 because of the driver). Car B, 2/2. Car C, 1/3. The most wasteful clustering would be [A, B, C]. But car C has room to pick up the driver and passenger of B, but no room for A, leaving us with [A, C]. Obviously, the best cluster would be one with only A because it has room to pick-up the other 2 cars. Now, this is a simple and small example, but how can I search for the minimum number of cars in samples with an arbitrary number of cars and passengers?

I tried to approach this problem in 3 different ways, but all fell short.

1. I thought about a maximum flow problem (image 1). But the maximum flow problem deals with capacities in edges of a graph. This specific problem has limitations on capacities of nodes/cars (not in its edges).

Maybe there's an adaptation of this method that I can use, but I couldn't think of any that would give me the list of groups that minimize the number of cars.

2. I also thought about the longest path problem (image 2). Every edge of my graph would be weighted by the number of people (driver + passenger) that would be picked-up if traversing to that node. And I could adapt the algorithm to decreased the capacity of the origin node accordingly with each node visited and stop that iteration if the max capacity was reached.

But to my understanding, I need to calculate the longest simple path (and not repeat any nodes) and that requires an acyclic graph. Given the context of my problem, most of the times there would be no way to turn my graph acyclic given that all the nodes would be strongly connected.

3. Lastly, I considered creating a list of trees (image 3). Where each root would be the origin car, and each child node would be a car that the root could pick-up. For each level of depth the available seats of the root would decrease until no more combinations existed. Then I would group trees' levels together and try to achieve the best combination and minimum of cars.

But at what level do I start. Does starting at the tree with the greatest depth and then grouping with other trees guarantee the minimum number of cars? Or is there a counterexample where grouping trees in their respective mid levels achieve better clustering? Do I just need to try every possible combination? That seems like an exhausting comparison and awfully inefficient.

I may be overlooking some characteristics of my problem, or maybe I'm just not comprehending the solutions I described. Is there a known solution to my problem, or maybe an adaptation I could implement? Any help or guidance is appreciated.

Thank you.

---

Edit:

u/gnasher729 mentioned the Bin packing problem in the answers which is indeed very similar to my problem.

Bin packing is calculated with bins of the same size. Given the context of my problem, my bins (cars) have different capacities.

With u/gnasher729 suggestions, the adaptation I came up with was:

1. Sort cars by remaining capacity first. Items weights are the size of the different groups of passengers.
2. Run the bin packing algorithm with bins of capacity equal to that of the car with more available seats.
3. Of the bin allocations produced by the algorithm, choose the bin with more items in it (meaning more groups of passengers were able to fit inside).
4. Remove the grouped cars (the bin + the items) from the sorted list and from the unplaced items.
5. Re-run the bin packing algorithm with the next emptiest car and with the remaining passenger groups.
6. Repeat until no more packing is possible.

It seems like it'll be an intense computation when given a large enough number of cars. If I have 20 cars with unknown passengers and unknown seats, and if I group 2/3 of those cars together with each iteration of the bin packing algorithm, then it'll be costly.

Is my adaptation wrong? Can i optimize it further?

Answer 1

The problem is NP-complete, because in the special case that all cars have the same capacity, it is just the bin-packing problem.

If car A has a higher capacity than car B, and you get an optimal solution (smallest number of cars) containing B but not A, then you can swap cars A and B, you won't need more cars, and because A has more empty capacity, you may fit the passengers from another car. So which cars you use in an optimal solution is obvious. You use cars sorted by capacity in decending order. So no matter what the numbers of passengers are, you would use the car with 7 seats, then the car with 3 seats, then the one with 2 seats. I assume you have groups of passengers you want to keep together, otherwise it is trivial.

You should be able to adapt any bin-packing algorithm to your situation. I can't see graphs being useful in any way.