snippetMinor
How to calculate the minimum number of groups, by grouping groups with capacity together?
Viewed 0 times
numberthegroupsgroupingwithcapacityminimumtogethercalculatehow
Problem
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.
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.
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.
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.
- 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.
- 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.
- 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
Solution
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.
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.
Context
StackExchange Computer Science Q#101135, answer score: 2
Revisions (0)
No revisions yet.