Challenge Overview
Prize Distribution
1st place - $3,000
2nd place - $1,500
3rd place - $1,000
4th place - $500
5th place - $500
Bonus: We will give a bonus of $500 to each best score on 7 datasets. These bonus prizes can be added if your solution achieves the best on multiple datasets.
Introduction
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 7 datasets. You will need to come up with a feasible schedule for every dataset and minimize the cost as much as possible.
Background
This challenge is variation derived from the 1st challenge, the 2nd challenge, and the 3rd 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.
Input files
There are 7 datasets (#1, #2, #3, #4, #5, #6, #7). Following are the rules and descriptions of each data. Each dataset has the following items;
1. Depot/Warehouse Name
A depot is a place where all the products are created.
2. Demand
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. Maximum Warehouse Size
Maximum warehouse size you can select. The selected value will be the maximum warehouse capacity of products each warehouse can hold.
4. 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.
Trucks
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.
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.
Warehouses
The warehouse size can be freely selected within the range from 20 to the given maximum warehouse size, in 10 increment. In other words, it is possible to select “20, 30, 40, ... maximum warehouse size”. Please specify these sizes in “warehouse_input”.
Relay warehouse
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.
Output file
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 the floating numbers should be printed in 7 digits after the decimal point, instead of 4 or 5 digits stated in the previous spec.
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.
Submission format
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
dataset1_solution.csv
dataset1_warehouse_input.csv
dataset2_solution.csv
dataset2_warehouse_input.csv
dataset3_solution.csv
dataset3_warehouse_input.csv
dataset4_solution.csv
dataset4_warehouse_input.csv
dataset5_solution.csv
dataset5_warehouse_input.csv
dataset6_solution.csv
dataset6_warehouse_input.csv
dataset7_solution.csv
dataset7_warehouse_input.csv
/code
<your code>
, where
-
/solution/dataset*_solution.csv are the output your algorithm generates on the given 7 datasets. The format of this file is described above in the Output file section.
-
/code contains your solution. You have to provide detailed README about how to deploy and run your solution in a Ubuntu system. We will verify the top submissions by running your solution on our machine.
Samples
We prepared a sample to help you understand: (1) sample dataset, (2) solution.csv, (3) warehouse_input.csv. These (2) and (3) solve the sample dataset.
Cost calculated from Verification tool: 210570.
Report files from Verification tool: action_report.csv, daily_truck_report, daily_warehouse_report.
The mp4 file from Visualization tool: this video visualizes for 30 days.
Scoring
Formula
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 Building Cost>
-
Truck Purchase Cost = 8350.6 * ln(C) - 14542.5
-
C: Maximum load capacity of truck (20 ~ 320, 20 increments)
-
-
Warehouse building cost = 29.725 * T
-
T: Maximum warehouse capacity (20 ~ maximum warehouse size, 10 increments)
-
-
-
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.
-
Benchmarks
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.
-
dataset1: 149572
-
dataset2: 160980
-
dataset3: 152422
-
dataset4: 158243
-
dataset5: 187718
-
dataset6: 216996
-
dataset7: 144434
The bonus prize will also be paid to the top of each data set. In order to get this prize, your solution must achieve a cost reduction more than 0.3% against the given benchmark results. For example, in the case of dataset1, your route’s cost should be lower than 149572 * 0.997.
Final Score
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
The final score for the leaderboard will be the average of the scores per dataset.
Final score = (Σ Independent Score) / 7
Scripts
We have developed a verification tool and a visualization tool and deployed them 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 as well as a link to an mp4 file.
For the visualization tool’s output,
-
Route show 30 days.
-
The truck size is indicated by the size of the circle.
-
The selected warehouse size is indicated by the length of the white bar.
-
Warehouse stock is indicated by the length of the blue bar.- Truck routes are connected by colored lines.
-
Once the warehouse stock falls below the lower limit (<= 0) even once, the circle of the warehouse turns blue.
-
Once the warehouse stock is larger than the upper limit (> selected warehouse size), the circle of the relevant warehouse lights up in red.
Final Submission Guidelines
If you are in the prize pool (including the bonus for the dataset’s best) at the end of the challenge, you are required to submit your report. The report should be written in English, 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.