ico-arrow-big-left

Vehicle Routing Problem -- Relay Warehouse Challenge

Key Information

Register
Submit
The challenge is finished.
Show Deadlines

Challenge Overview

Prize

1st place - $2000
2nd place - $1000
3rd place - $500

Challenge Overview

In this challenge, we are looking for reports discussing when using “relay warehouse” will lead to a better solution in the vehicle routing problem (VRP) to minimize the total operating cost of trucks for 10 days. You are asked to conduct an analysis based on a small dataset and derive your rules and conclusions.

Background

This challenge is variation derived from the previous challenge we ran. 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 challenge to understand what the VRP is.

Please note that the goal of this challenge is no longer about analyzing public Solvers. It is your choice to develop your own solver or tailor public Solver for your report.

Task Details

We have 5 datasets. Each dataset expresses a number of warehouses and the distance between them. The goal of this task is to create accurate, intuitive mathematical formulae to determine when and how to choose relay warehouse(s), in order to minimize the total operation cost minimum in these 5 datasets. You are asked to submit a report about how you have analyzed data and derived the rules and conclusions.
Please note that there could be cases that we do not need any relay warehouse. Also, in your analysis and conclusion, it is NOT necessary to think of a case beyond the given 5 datasets -- you can “overfit” your conclusions just for these 5 datasets.

The data can be found in these spreadsheets (#1, #2, #3, #4, #5). There are

  • The depot has an infinite amount of the product;
  • The “demand” column describes the daily consumption at each warehouse;
  • Each warehouse has a capacity of 1,000 units of the product. Warehouses cannot store more than its capacity;
  • Each warehouse has a specific size of trucks (small or medium) that it can use. “Use” means that the truck can initially depart from here and finally return here to load and unload;
  • The distance matrix describes the number of days that are required for the truck to travel between each warehouse/depot. Truck needs to spend 6 hours while loading/unloading product at depot/warehouse.
Relay Warehouse is a special type of warehouse where it can serve as temporary depots for other warehouses. You are allowed to use zero or more relay warehouses.
In VRP, we should schedule trucks to deliver the product to warehouses and make sure every warehouse has enough product to consume every day. There are no product at all warehouses initially. The amount of product at warehouse increases only after the truck unloaded some product there. Of course, in the first a few days, there might be some warehouses lack of the product, but the schedule should meet a long-term needs.
There are 2 small-size trucks and 1 medium-size truck. Total of 3 trucks for all cases.
  • A small-size truck can carry up to 160 units of products
  • A medium-size truck can carry up to 320 units of products
The Operating Cost consists the following 3 parts:
  • For small truck
    • Cost = 5.4876 * <truck operation days> + (<number of truck stops at depot or warehouse> * 2)
  • For medium truck
    • Cost = 6.6452 * <truck operation days> + (<number of truck stops at depot or warehouse> * 2)

 

Final Submission Guidelines

Submissions

Contents

A document with details for the proposed algorithm and/or a proof of concept solution, pseudo-code or any documentation/ previous research papers that helps illustrate a proposal.

The final submission should be a report, more like a technical paper. It should include, but not limited to, the following contents. The client will judge the feasibility and the quality of your proposed conditions of how relay warehouses should be chosen, and/or the conditions when relay warehouse are not needed.

The client is specifically looking for some mathematical expression to describe these conditions.

  • Abstract / Description:
    • Outline your findings and conclusions.
  • Details :
    • Any assumptions you have made if there is any.
    • Your proposed way to choose and leverage the relay warehouse.
    • What are the parameters that may affect the use of relay warehouse? What are their effects?
      • Figures and charts are highly recommended.
  • Appendix(optional) :
    • Bibliography, A reference to the paper, etc.

Format

  • A document should be minimum of 2 pages in PDF / Word format to describe your ideas.
  • It should be written in English.
  • Leveraging charts, diagrams, and tables to explain your ideas is encouraged from a comprehensive perspective.

Judging Criteria

The client will score and announce winners based on the following criteria:

Quality of your Mathematical Formulae for Choosing Relay Warehouse(s) (50%)

  • Can your formulae accurately describe when and how relay warehouse(s) should be chosen from the given data sets?
  • Are your formulae intuitive and easy-to-follow? Please see below for example on what kind of formulae we are looking for.
  • Please use specific numbers and draw your conclusions in a few sentences.
  • Is your formulae meaningful if there're more trucks? The range of a total number of trucks is 3 to 6.
  • Is your formulae meaningful if truck size changes? the capacity of the trucks can change in a range of 20 to 320.
    Cost = (1.67012*ln(capacity)-2.9885) * <truck operation days> + (<number of truck stops at depot or warehouse> * 2)

Clarity of the report (50%)

  • Please thoroughly document your solution with the analysis and your thinking process.
  • Please structure your report in a good shape with a clear logic flow.
  • Please make sure your report is easy to understand.

Example of the Mathematical Formulae we are looking for - Note this is only for illustration without any specific meaning.

Let’s say you have analyzed and concluded that relay warehouses should be chosen by the density of the warehouses and the distance between the warehouse and the depot.

The formulae to choose might look something like below, where the closer the distance between each warehouse and the farther the distance between the warehouse from the depot will make the cost smaller.

 

: the distance between warehouses i and j

 : the distance between depot and warehouse i

 

Submission Guideline

You can submit at most TWO solutions but we encourage you to include your great solution and details as much as possible in a single submission.

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.

ELIGIBLE EVENTS:

Topcoder Open 2019

REVIEW STYLE:

Final Review:

Community Review Board
?

Approval:

User Sign-Off
?

CHALLENGE LINKS:

Review Scorecard

?