VRP Problem / Solver Characteristics Analysis

This purpose of this challenge is to analyze obstacles we may encounter when trying to solve the VRP problem using general solvers, and provide detailed analysis on these obstacles (top priority) and propose potential solutions (lower priority). 

We are awarding 10 checkpoint prizes at $200 for each chosen winner and the checkpoint deadline is 2018/09/16 17:15 (EDT), and keep in mind we do NOT need working code!

Task Details

The goal of the task is somewhat special and unlike normal challenges in that we don’t really need to solve the presented VRP problem in this challenge, instead we want to understand in detail what makes VRP problem hard to solve by general solvers.
 
We are assuming that when solving the VRP problem with a general solver, we’d define the VRP problem formulation and its problem configuration (you can also think of configuration as conditions applied to the VRP problem to make it harder or easier to solve) very well. We want to collect information from experienced members to understand what kind of configuration would make the problem:

1. Reasonable to solve
2. Not possible to solve
3. Solvable but performance degrades rapidly

 
We have provided a sample VRP problem with some specific configuration, and we’d like you to try to solve that. You can find the details of it from this slide:
https://docs.google.com/presentation/d/1iJpTT_6gRmtAqD57KSxBktOX82O_cndVJ2OKVZBq7Hg
 
First, you will need to pick one of general solvers (such as Gurobi, CPLEX, OR-Tools, SCIP, or GLPK) and try to solve using as much of its functionality. You can try to solve using “higher” API of solvers or using “lower” API as much as possible. We are assuming that this sample VRP problem is not solvable using just the functions of general solvers.
 
We need you to provide good reasoning and background of list of issues that you encounter, which will make the client understand what the limitation of known Solver(s) are. Also give detailed ideas or pseudo-code to  approach those limitations to solve.
 
For example, general solvers might not have straight forward way to handle changes of capacities. In this case you might need to pass some static capacities and try to call the solver method multiple times from external script. These are the places you would need to give detailed analysis on.
Please note we do NOT need working code, some kind of pseudo-code that helps explain your analysis is good enough.
 
Basically we are trying to understand the limitations of known Solver(s) by trying to solve the sample VRP problem.
 
We want competitors to gather the following information and report on them based on past research and experiences:

• Parts of the problem that might be obstacles in solving the problem:
  • Example: problem configurations, a range of parameter values, the characteristic of the parameter (e.g. continuous value vs a discrete value, etc)
• Tips on the use of certain Solver
• Limitations of the certain Solver
• Guidelines for the certain Solver
  • Here are some sample solvers: Gurobi, CPLEX, OR-Tools, SCIP, and GLPK.

 
As part of your submission, we expect you to clearly identify the configuration parameters and issues that greatly affect the performance of the solution:

• We don’t need to know some obvious conditions such as extremely increasing the number of trucks to make the optimization time longer to go over the limit of certain Solver. Rather, the client is looking for conditions and explanation to non-obvious conditions as following bullet.
• The kind of parameters we are looking for are these that are harder to think of. For example: depending on the relationships between the daily consumption of each warehouse, the total volume of warehouse, and the total volume of truck, there can be various cases to be considered and it is necessary to optimize the solution that takes care of these cases:
  • The case in which the track may only reach each warehouse once per week (or some fixed period)
  • The case where there is a need to visit each warehouse more than one route
  • The case that same route has to be followed every time
  • The case that there is a need to change the route regularly                                    
• In the cases, we want to know the relationship between the parameters that generate the large difference of the processing time and the optimized value.

 
When carrying out the task, the following approaches should be considered by difficulty of the problem:

• If you have difficulty to solve the sample VRP problem with the existing solver
  • You may delete or modify one (or more) of problem configuration parameters that’s the blocker. For example, removing the maintenance window of trucks, etc.
  • In this case you should update the problem into a solvable one and include the following details in your submission
    • The parameters causing the trouble and how to change the problem into a solvable one
    • Detailed explanation / analysis why the parameters are a blocker
• If it is simple to solve the sample VRP problem using the existing solvers
  • You should add or modify one (or more) of problem configuration parameters and turn the problem into an unsolvable one. The parameters you should add on to sample VRP problem is written in “Advanced” column in the slide.
  • In this case, you should update the problem into an unsolvable one and include the following details in your submission:
    • The parameters that need to be changed to make the problem into an unsolvable one
    • Detailed explanation / analysis why the changes would cause the problem to become unsolvable

                                               
Here is a sample description of such kind of changes:

• When the state "Σai <Σbi" isn't established between the parameters ai and bi, processing time increases rapidly.
• The reason for this is that if this state isn't established ... a kind a of something occurs.

Submission

Contents

• Title
  • Title of your analysis
• Description
  • High level overview / important points and results
• Details
  • In general we need the submission to be as detailed as possible, to cover all the requirements stated in the Task Details section. For example:
    • Problem configuration parameters that generate the performance obstacles
    • Analysis on the obstacles and limitations of the existing solvers
    • Scenarios in which the phenomenon occurs
    • The pseudo-code that reproduces the phenomenon

Format

• It should be written in English.
• Using charts, diagrams and tables to explain your analysis is encouraged.
• Submission can be in PDF or Word format.

Judging Criteria

The winners will be picked by the customers in a relatively subjective way, but we’ll take the following into consideration while evaluating submissions:

• Clarity (50%)
  • Whether the submission clearly describes the obstacles and limitations, and whether the reason of them are clearly and logically explained.
• Utility (30%)
  • In terms of performance and optimal values, whether the proposed solution / changes would yield good results
• Feasibility (20%)
  • Evaluate how feasible the proposed changes / solution are 

Checkpoint

We are awarding 10 checkpoint prizes at $200 for each chosen winner. You do not have to submit for checkpoint to earn final prizes. But in order to qualify for the checkpoint prizes you must submit to the final round.
 
Checkpoint due 2018/09/16 17:15(EDT) which is the same as registration deadline.

Final Submission Guidelines

Please check the requirements above.