The 3rd Vehicle Routing Problem Mini Marathon Challenge

Marathon MatchPythonTest CaseUbuntuCAlgorithmsExcel Solver
Register
Submit a solution
The challenge is finished.

Challenge Overview

Prize Distribution

1st place - $4,000

2nd place - $2,000

3rd place - $1,000

4th place - $500

5th place - $500

 

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

Background

This challenge is variation derived from the 1st challenge, the 2nd challenge, the 3rd challenge, the 4th challenge, and the 5th 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 9 datasets (#1, #2, #3, #4, #5, #6, #7, #8, #9). 

The datasets has the following features:

  1. “Expansion of delivery facilities by investment” (#1, #2, #3, #4)

  2. “Expansion of delivery facilities by investment” and “Departure and arrival time limit” (#5, #6, #7, #8)

  3. “Expansion of delivery facilities by investment” and “Departure and arrival time limit” and “Demand Growth Rate” (#9)

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. Demand Growth Rate

        Every warehouse’s demand grows after every 30 days (i.e., on Days 30, 60, 90, …). It follows the compound interest calculation.

    4. L:

        Warehouse-specific parameter.

    5. Initial Possible Truck Size 

       There is an initial possible truck size for each warehouse. 

    6. Possible Truck Size 

        This is the maximum size of truck that can be used to load/unload products. At the very beginning, for each warehouse, there is an initial possible truck size for each warehouse. You can choose to invest more into each warehouses. The investment cost can be calculated by the formula L * log(your_proposed_possible_truck_size / initial_possible_truck_size), where L is a warehouse-specific parameter.

 

    7. Maximum Warehouse Size

        Maximum warehouse size you can select. The selected value will be the maximum warehouse capacity of products each warehouse can hold.

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

    9. Departure and Arrival Time Limit

        Every warehouse is open only in a fixed time interval, either 0-24 (i.e., all day) or 0-12 (i.e., only the former half day). This will be specified in each test case. You can load / unload warehouse even after it is closed.

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

Warehouses

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

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

 
 

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

    dataset8_solution.csv

    dataset8_warehouse_input.csv

    dataset9_solution.csv

    dataset9_warehouse_input.csv

 

/code

    <your code>

 

, where

  • /solution/dataset*_solution.csv are the output your algorithm generates on the given 9 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.

Samples

We prepared two samples to help you understand.

 

This is the first example without “Demand Growth Rate”: (1) sample dataset, (2) solution.csv, (3) warehouse_input.csv. Cost calculated from Verification tool: 183381. Report files from Verification tool: action_report.csv, daily_truck_report, daily_warehouse_report.

 

This is the second example with “Demand Growth Rate”: (1) sample_dataset, (2) solution.csv,  (3) warehouse_input.csv. Cost calculated from Verification tool: 156645. Report files from Verification tool: action_report.csv, daily_truck_report, daily_warehouse_report.

Scoring

Formula

 

The total cost we are looking to minimize can be expressed as follows:

  • Total Cost = <Equipment Cost> + <Normalized Operating Cost> + <Investment Cost>

  • Investment Cost = \sum_{each warehouse} L * log(your_proposed_possible_truck_size / initial_possible_truck_size)

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

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

  • dataset2: 127746

  • dataset3: 166638

  • dataset4: 181548

  • dataset5: 245795

  • dataset6: 132676

  • dataset7: 198550

  • dataset8: 198065

  • dataset9: 213698

Final Score

On each dataset, we will compute the independent score as follows

 

Independent Score = (Max((Threshold - Cost) / Threshold), 0)^2 * 100 

+ Min(0.1, Max(0, (2 - Cost / Threshold) / 10))

s.t. Threshold = Benchmark * 1.1 

 

Hint: Since the score is squared, 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) / 9

 

Scripts

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. Applicants will receive notification of submission by email. 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.

ID: 30096611