ico-arrow-big-left

Vehicle Routing Problem: Relay Warehouse Mini Marathon Challenge

PRIZES

Register
Submit
The challenge is finished.
Show Deadlines

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.


 

Reliability Rating and Bonus

For challenges that have a reliability bonus, the bonus depends on the reliability rating at the moment of registration for that project. A participant with no previous projects is considered to have no reliability rating, and therefore gets no bonus. Reliability bonus does not apply to Digital Run winnings. Since reliability rating is based on the past 15 projects, it can only have 15 discrete values.
Read more.