Vehicle Routing Problem -- Relay Warehouse Challenge Part2

Register
Submit a solution
The challenge is finished.

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 cost for 7300 days (20 years). You are asked to conduct an analysis based on a small dataset and derive your rules and conclusions. In addition, we will be looking for the truck route pattern in CSV format of your proposed solution.
 
We are awarding 10 checkpoint prizes at $200 for each chosen winner and the checkpoint deadline is 2019/02/20 19:00 (EST), and keep in mind we do NOT need a working code!
Also, we are handing out a program to verify your truck route pattern matches the given rules correctly. So please make sure to submit whatever you have at the checkpoint.
 
 
Background
 
This challenge is variation derived from the 1st challenge and the 2nd 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 is no longer about analyzing public Solvers as seen in the 1st challenge. It is your choice to develop your own solver or tailor public Solver for your report. Also, the rules and datasets have been changed from the 2nd challenge.
 
 
 
Task Details
 
There are 2 goals in this task.
  1. [Mathematical Formulae] Create accurate and intuitive mathematical formulae to determine when and how to choose relay warehouse(s), in order to minimize the total cost for given 5 datasets (#1, #2, #3, #4, #5). You are asked to submit a report about how you have analyzed data and derived the rules and conclusions. As mentioned in the scoring criteria, the small number of mathematical formulae, the better your solution will be scored.
  2. [Truck Route Pattern] Provide a truck route pattern for the given 7300 days implementing the above 1. Mathematical Formulae model. The route pattern format is explained below. 

 
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.
 
 
Datasets
 
There are 5 datasets. 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 12hours the products will decrease half the amount of its daily demand
    3. Possible Truck Size
        A maximum size of truck that each warehouse can use to load/unload products
    4. Maximum Warehouse Capacity
        Maximum warehouse capacity of products each warehouse can hold
    5. 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 (ex. It can take rest at warehouses) but not less.
 
 
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.
 
 
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.
 
 
Total Cost Calculation
 
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
  • 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.
  • 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.
 
 
Truck Route Pattern
 
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.
    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 6 hours to load and unload.
    3. Multiple trucks at one location
        Multiple trucks can be at the same warehouse at the same time.
 


Final Submission Guidelines

Submissions

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 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.
If your solution has several Mathematical Formulae for different conditions, please be clear to mention them.

        (1) Report on Mathematical Formulae when to use relay warehouse
  • 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 its effects?
      • Figures and charts are highly recommended.
    • Please write the cost calculation formula.
    • Please also show examples of calculations with the program to verify consistency. Especially when it achieves the minimum cost, it becomes a high score.
      • Program to verify consistency is provided after the checkpoint.
    • Appendix(optional) : 
      • Bibliography, A reference to the paper, etc.
          (2) Truck Route Pattern of 7300 days implementing your Mathematical Formulae model in CSV format for 5 dataset

Report Format
  • A document should be a 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%)
  • Please use specific numbers and draw your final conclusions should be able to be described in a few sentences
  • 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.
  • Is the truck route pattern created from your model matches the rules correctly?

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

Checkpoint

We are awarding 10 checkpoint prizes at $200 for each chosen winner. 
For this challenge, you should submit to the checkpoint of whatever you have done until then. We will be sending the program to verify your truck routing patterns matches the rules correctly only to those who have submitted to the checkpoint.

Checkpoint due 2019/02/20 19:00 (EST) which is the same as registration deadline.

ELIGIBLE EVENTS:

Topcoder Open 2019

Review style

Final Review

Community Review Board

Approval

User Sign-Off

ID: 30083697