Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

This is something I did for a bus travel company a long time ago, and I was never happy with the results. I was thinking about that old project recently and thought I'd revisit that problem.

Problem:

Bus travel company has several buses with different passenger capacities (e.g. 15 50-passenger buses, 25 30-passenger buses ... etc). They specialized in offering transportation to very large groups (300+ passengers per group). Since each group needs to travel together they needed to manage their fleet efficiently to reduce waste.

For instance, 88 passengers are better served by three 30-passenger buses (2 empty seats) than by two 50-passenger buses (12 empty seats). Another example, 75 passengers would be better served by one 50-passenger bus and one 30-passenger bus, a mix of types.

What's a good algorithm to do this?

share|improve this question
3  
Not to be picky, but I would suspect from the bus company point of view, 2 50 passenger buses would be more efficient since the gas costs are only going towards 2 buses instead of 3. So is this actually how you did it? –  Dunk May 31 '12 at 19:04
8  
This sounds like the knapsack problem, which is NP-hard. In practice, your search space for a given route should be pretty small. –  chrisaycock May 31 '12 at 19:08
    
@Dunk - I will be the first to admit that I have no idea about bus and tour logistics, but that was their requirement. They even had a highly paid consultant who did it manually. –  System Down May 31 '12 at 19:12
    
Empty seats are irrelevant, what counts are operating costs. Thus look at philosodad's answer. –  Loren Pechtel Jun 1 '12 at 0:52
    
@LorenPechtel - Like I said before, I don't dictate the business rules, I just implement them. –  System Down Jun 2 '12 at 0:52

3 Answers 3

up vote 7 down vote accepted

This is (sort of) an example of the bin packing problem, which is frequently confused with the knapsack problem. In bin packing, you have bins of a certain capacity, and you are trying to distribute objects of various sizes into the bins. The idea is to use the least possible number of bins.

You aren't exactly trying to minimize the number of bins, though, you are trying to minimize the number of empty seats. And it is possible that you are trying to minimize the number of empty seats across the fleet, that is, you have four tour groups of various sizes, and you want to accomodate all of them with the fewest number of empty seats. I can't think of an instance right off the bat, but I imagine it might be possible to construct a fleet and a set of tour groups such that you would be better off with a substandard solution for some group because it allowed you to avoid using an even worse solution for some other group.

It gets worse. What if you have 20,30, and 50 passenger busses. Each one uses different amounts of fuel, but it is more efficient to run one 50 than it is to run a 20 and a 30. But from our single measure (least number of empty seats), it makes sense to run either for a 50 passenger tour.

Also, buses with weird numbers, like 28 or 39, would skew a lot of our shortcuts.

So, depending on the complexity of the situation, you could do one of two things:

First, and exhaustive search tree: use every possible combination of buses. If you only have 3 or 4 bus sizes, this is probably a reasonable solution. Otherwise, something like Best fit decreasing would yield reasonable, but not optimal, results.

share|improve this answer
    
I can't imagine why this answer got downvoted. Upvoting to compensate. Well done. –  David Conrad Jun 1 '12 at 0:31

I'm going to answer this from the customer perspective. I would not want a hard coded algorithm for this application. There are too many variables that can change over time. Although nothing about your buses may change the weights of the factors could change or new factors could be discovered that I never thought of (e.g. over-time, laws, and other driver costs).

Because of this, I would want to be able to create my own lookup table based on a range of the number of passengers requested and I would create my own settings for the best bus combinations. Example: 31-50 = 1 X 50, 51-60 = 2 X 30. Does this really need to be calculated? Easier to change settings than a bunch of formulas factoring seats, gas and drivers. Figure out the best combination and be done with it and have plenty of room for the user to change these settings as they see fit.

New factors could be discovered. Do larger buses pay an exponentially higher rate on tolls? Can I get less expensive drivers for small buses when a new law for extra certification and licensing goes up on drivers of buses over 30 passengers?

They hire a new consultant with a different logic to their formula and your app may need to be rewritten. You mean you have to factor cost of parking?

share|improve this answer
    
This doesn't work: 31-50 = 50 seat bus, unless they're already used for other groups, or out of service, or unavailable for other reasons. The bus company from the question, with 15 50-passenger buses is very likely going to have multiple customers at a time. –  MSalters Jun 1 '12 at 11:15

Here's a quick-and-dirty solution in Python:

def add50(passengers, buses):
    proposed = buses + [50]
    if sum(proposed) < passengers:
        return add50(passengers, proposed)
    return proposed

def add30(passengers, buses):
    proposed = buses + [30]
    if sum(proposed) < passengers:
        proposed30 = add30(passengers, proposed)
        proposed50 = add50(passengers, proposed)
        return proposed30 if sum(proposed30) < sum(proposed50) else proposed50
    return proposed

print add30(88, [])
print add30(75, [])
print add30(105, [])

When I run it, I get:

[30, 30, 30]
[30, 50]
[30, 30, 50]

The code is doing a depth-first search through the possible scenarios. Since order doesn't matter ([30, 50] is the same as [50, 30]), we can make the search space a lot smaller by only adding buses of the same size or larger. That's why add30() can call add50(), but not the other way around.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.