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 and number of kids.

Name Type Values
Bus String Big, Small
Kid Int [0..300]

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.

Name Type
price of Bus Int
size of Bus Int
Number of Bus Int
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.

Name Type
TotalPrice Int
TotalKids Int

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.

Price and size of Buses
D 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

Minimize TotalPrice

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

Model 1
price_of_Bus := {Big->500, Small->400}.
size_of_Bus := {Big->40, Small->30}.
number_of_Bus := {Big->6, Small->2}.
kids_of_Bus := {Big->240, Small->60}.
TotalPrice := 3800.
TotalKids := 300.

Elapsed Time:

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