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.

Type
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.

Function
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.

Constant
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:

Every kid needs a bus.
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:

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:
0.822

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