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.