1st place - $4,000
2nd place - $2,000
3rd place - $1,000
4th place - $500
5th place - $500
In this challenge, we are looking for solutions for the vehicle routing problem (VRP) to minimize the total cost for 7300 days (20 years). We will give you 8 datasets. You will need to come up with a feasible schedule for some of these dataset and minimize the cost as much as possible. Check the ‘Final Score’ section.
This challenge is variation derived from the 1st challenge, the 2nd challenge, the 3rd challenge, and the 4th challenge we ran previously. The VRP problem in the previous challenge is similar to what you are going to explore in this challenge. You might want to have a look at the previous challenges to understand what the VRP is.
Please note that the goal of this challenge focuses on developing the solver and minimizing the cost. It is your choice to develop your own solver or tailor public Solver for your solution.
1. Depot/Warehouse Name
A depot is a place where all the products are created.
Consumption of products per day at each warehouse
Note that the products are consumed gradually over time and not at the end of each day, meaning for example in 12 hours the products will decrease half the amount of its daily demand
3. Demand Growth Rate (new in this challenge compared to the previous Mini Marathon)
Every warehouse’s demand grows after every 30 days (i.e., on Days 30, 60, 90, …). It follows the compound interest calculation.
4. Possible Truck Size (new in this challenge compared to the previous Mini Marathon)
For each warehouse, there is a maximum size of truck that can be used to load/unload products.
5. Maximum Warehouse Size
Maximum warehouse size you can select. The selected value will be the maximum warehouse capacity of products each warehouse can hold.
6. Travel Time between the depot and/or each warehouses [days]
The minimum travel distance between warehouses in days
Please note that a truck can take more than the days defined to travel between warehouses (e.g., It can take a rest at warehouses) but not less.
Each truck has a size between 20 to 320, in 20 increments. ie. that is 20, 40, 60,…..., 300, 320. You can freely decide the number of trucks and each of its sizes at the beginning.
The size is the maximum capacity that this truck can hold products at any time, thus, the size of the truck can not be changed. Trucks can be added after the simulation begins.
In the beginning, trucks can start at any warehouse or depots loaded with any stock of products. For example, you can start truck #1 from depo, and truck #2 from warehouse #5. The first action must be from “departure”- see Truck Route Pattern below for all the actions.
The warehouse size can be freely selected within the range from 20 to the given maximum warehouse size, in 20 increment. In other words, it is possible to select “20, 40, 60, ... maximum warehouse size”. Please specify these sizes in “warehouse_input”. For every existing warehouse, additional warehouse capacity can be purchased during the simulation period. However, the total of warehouse capacity of each warehouse should not exceed its maximum warehouse size.
Relay warehouse is a special type of warehouse that can hold products to be distributed to other warehouses. Relay warehouse cannot produce products like depots and need to get products brought from the depot in advance. It can not hold more products than the maximum capacity. You are allowed to use zero or more relay warehouses.
Relay warehouse(s) should be chosen from the existing list of warehouses and not newly created. Thus, the demand and the maximum capacity stays the same.
Please note that there could be cases that we do not need any relay warehouse.
In VRP, we should schedule trucks to deliver the product to warehouses and make sure every warehouse has enough product to consume every day. The amount of product at the warehouse increases only after the truck unloaded some product there.
This means that the following formula needs to be accomplished at any time.
warehouse stock > 0
warehouse stock ≤ maximum warehouse capacity
You can freely decide the initial stock of products for each truck and warehouse at the beginning and end of 7300 days.
We will be looking for the initial stock and truck route pattern for the minimum total cost of each dataset in CSV files. For CSV file specifications, see here. Please note that there is no limit on the digits after the decimal point in this challenge. The Verification tool uses “float” in python to read these values, which should be “double” in C/C++.
1. Note on repeating cycles
Your truck route pattern might be made up of the same repeating cycles to become 7300 days.
When we say “repeating cycle”, this means that truck will start at "departure" action at some depot/warehouse and then returns to the same depot/warehouse and performs "departure" action again.
During which the route actions in between is the same.
2. Warehouse stock
Warehouse stock cannot be less than zero at no time.
Note that trucks need 0.25 day to load and unload.
3. Multiple trucks at one location
Multiple trucks can be at the same warehouse at the same time.
This match uses a combination of the "submit data" and "submit code" submission styles. Your submission must be a single ZIP file with the following content:
/solution/dataset*_solution.csv are the output your algorithm generates on the given 8 datasets. The format of this file is described above in the Output file section. You can also make a submission when you only have solutions a part of datasets.
/code contains your solution. You have to provide detailed README about how to deploy and run your solution in an Ubuntu system. We will verify the top submissions by running your solution on our machine.
Cost calculated from Verification tool: 123237.
The total cost we are looking to minimize can be expressed as follows:
Total Cost = <Equipment Cost> + <Normalized Operating Cost>
Equipment Cost = <Truck Purchase Cost> + <Warehouse Purchase Cost>
Truck Purchase Cost = (8350.6 * ln(C) - 14542.5) * <Number of days used> / 7300
C: Maximum load capacity of truck (20 ~ 320, 20 increments)
<Number of days used> is calculated from the truck purchase date till the end of the simulation.
Warehouse Purchase Cost = 29.725 * T * <Number of days used> / 7300
T: Maximum warehouse capacity (20 ~ maximum warehouse size, 20 increments)
<Number of days used> is calculated from the warehouse space purchase date till the end of the simulation. If a warehouse’s capacity has been extended multiple times during the simulation, their costs will be computed separately based on their different purchase dates.
Normalized Operating Cost = <Truck Operating Cost> * <Total Demand consumed in 7300 days> / (<Total Demand consumed in 7300 days > + <total stock of products at the end> - <total stock of products at the beginning>)
Total stock of products: All products aggregated from every trucks and warehouses.
Hint: The more “total stock of products at the end”, the less “total stock of products at the beginning”, the better the cost.
Truck Operating Cost = (1.67012 * ln(C) - 2.9885) * <truck operation days> + <number of truck stops at depot or warehouse> * 2
C: Maximum load capacity of a truck (20 ~ 320, 20 increments)
“truck operation days” is the actual days took that truck was moving. Loading/Unloading and parking time are not included.
note that trucks can spend more than the days between warehouses mentioned in the datasets. Meaning trucks can be parked at the warehouses or depots.
If there are warehouse#1 and warehouse#2 that needs 3 days of travel time, the truck could park at #1 for 2 days or travel slowly to make travel time as 5 days. In both cases, the “total operation days” should be calculated as 3 days.
“a number of truck stops at depot or warehouse” will count all the “arrival” action -- stops the trucks -- made to depot or warehouse. Ex. if truck moved from 1.depot (departure) then to 2.warehouse#1 (arrival), 3. warehouse#3 (arrival), 4.warehouse#6 (arrival), finally to 5.depot (arrival) then, it will be 4.
Here are some benchmark results we have for each dataset. In order to be eligible for prizes, you must achieve costs no more than 1.15x these benchmark results.
On each dataset, we will compute the independent score as follows
Independent Score = (Max((Threshold - Cost) / Threshold), 0)^3 * 100
s.t. Threshold = Benchmark * 1.15
Hint: Since the score is cubed, if you can get a very low cost on a single dataset, you will be able to get a high overall score. Some of the previous Mini Marathon winners have been ranked high in just one data set.
The final score for the leaderboard will be the average of the scores per dataset.
Final score = (Σ Independent Score) / 8
We have developed a verification tool and deployed it in the cloud. To use them, you can make a submission. Then, we will run the tools on the cloud side and send the results back to you via an email. The email will contain the scores on each dataset. If at least one of the submitted solutions passes the verification tool, some feedback will be provided.
Final Submission Guidelines
If you are in the prize pool at the end of the challenge, you are required to submit your report. The report should be written in English or Japanese, more like a technical paper. It will be great to include pseudo codes or formulas that explain why and when should we use a relay warehouse. If you can not logically explain the basis of the submitted data, the prize may not be paid. In that case, the next challenger in the ranking will win the prize.
The report should have a minimum of 2 pages in PDF / Word format to describe your ideas. Please try to leverage charts, diagrams, and tables to explain your ideas is encouraged from a comprehensive perspective.