Zoo, Buses and Kids

Zoo, Buses and Kids is a small optimization problem taken from the DMCommunity challenges.

Zoo, Buses and Kids

300 kids need to travel to the London zoo. The school may rent 40 seats and 30 seats buses for 500 and 400 £. How many buses of each to minimize cost?

You can probably solve this problem without the use of a computer, but it’s still a nice showcase of optimization within cDMN.

We start by creating a glossary. We need a type to represent buses, sizes, price ranges, number of kids and the number of buses.

Type
Name Type Values
Bus String Big, Small
Size Int [30..40]
Price Int [0..4000]
Kid Int [0..300]
Number Int [0..10]

For every bus, we need to express exactly one price, and exactly one size. Furthermore, we need a way to express how many buses of each type we will have, and how many children will be on each bus type. Since all of these concepts map one type on exactly one type, we use functions for this purpose.

Function
Name Type
price of Bus Price
size of Bus Size
Number of Bus Number
Kids of Bus Kid

To represent our total number of kids which need seating and the total price of all the buses, we use constants.

Constant
Name Type
TotalPrice Price
TotalKids Kid

The next step is inputting the data in our model. We know for each bus type their size and their price, and we represent this in a data table.

Data Table: Price and size of Buses
Bus size of Bus price of Bus
1 Big 40 500
2 Small 30 400

We also already know the total number of kids.

Total Kids
U TotalKids
1 300

We now express two things in order to complete the logic:

  1. Every kid needs a bus.
  2. Buses cannot have a number of children exceeding their size.

This first rule is state by the following table. It checks that the sum of the number of kids assigned to each bus type equals the total number of kids.

Every kid needs a bus.
C+ Bus TotalKids
1 - Kids of Bus

The second rule is expressed by a constraint. For every type of bus, there cannot be more children than the size of the type multiplied by the number of the type.

Limit number of kids per bus.
E* Bus size of Bus * Number of Bus
1 - ≥ Kids of Bus

After implementing these two rules, we still need to add the formula for calculating the total price, and then tell the solver to minimize it by adding a Goal table.

Calc TotalPrice.
C+ Bus TotalPrice
1 - Number of Bus * price of Bus

Goal
Minimize TotalPrice

We can now run our model using the cDMN solver. This results in the following output:

Number of models: 1
Model 1
=======
structure  : V {
  Kids = { Big->240; Small->60 }
  Number = { Big->6; Small->2 }
  Price = { Big->500; Small->400 }
  Size = { Big->40; Small->30 }
  TotalKids = 300
  TotalPrice = 3800
}

Elapsed Time:
0.091493

The optimal solution is to get 6 big buses, and 2 small ones for a total cost of 3800 pounds.