At the DIMACS Implementation Challenge on Vehicle Routing you find the description of eight variants of the vehicle routing problem. You have to choose one and focus on that one. The higher the number of the problem chosen the more challenging the solution is but also the more rewarding could be the grade.
Choose some test instances with the following criterion: there should be some instances that you can solve to optimality and some that you cannot. In other terms, you should aim at finding a threshold between solvable and not solvable instances.
You have submit a report and a source code that address the following tasks:
Determine an easy-to-calculate lower bound $K_{LB}$ to the number of vehicles needed to satisfy the demand of all customers. Report in a table of your final text document the lower bounds thus found for each given instance. (Another way to obtain a lower bound, which is a bit harder to calculate, is by solving a problem addressed in one of the examples treated in the course [MPG, part C] – you will need this to address point 3 below.)
Model the problem in constraint programming terms and describe the model in the report. Ignore initially the objective and focus on feasibility only.
Implement the model at point 2. above in MiniZinc. Let $K^*$ be the minimum number of vehicles needed cover the demand of all customers of an instance. Determine this number for the instances chosen and compare it with $K_{LB}$. Report in a table the comparison with the lower bounds found in point 1.
Modify your model to include an objective function. Report the results in a table. Indicate whether the instance is solved to optimality or not and report meaningful measures to describe the effort needed to find the solutions. If the solution found is not optimal within a given time limit, report the best solution found so far.
Improve your model by fine tuning some parameters of your choice and present the analysis with numerical results and discussion. The parameters can be: branching rules, level of consistency enforced, redundant constraints, alternative models, symmetry breaking.
Study the use of random restarts. Describe the restart strategy and the configuration you chose and find out whether random restarts improve or not the performance of the solver. Start your implementation from the best model found so far, but make sure that a restart is worth by ensuring that at each restart a modified problem is solved. Consider using no-goods, shared heuristics or random choices or different heuristics at each restart.
There is no predefined time limit. You can choose to run your experiments with the time limit that best fit with your computation resources (eg, time left from deadline, number of cores and machines, etc). Performance can be assessed in several ways (max size of the instances solved, computation time, solution quality, etc.) It is up to you to identify meaningful measures and comment on the performance.