I converted the problem into a maximization problem by giving a profit of 10000 to each train and subtracting the penalty of the schedule. Using this, I made a (randomized) greedy heuristic, which iteratively takes trains, schedules them, and kicks other trains out, when they block the current train. This procedure usually gives feasible solutions for all instances, however with about at least 50 penalty. Thus, I restart this heuristic a few times to generate a bunch of useful routes and put them in a set-covering/partitioning MIP (solved using CPLEX). Finally, I repeatedly solve this MIP and heuristically generate more tours based on the solution of the MIP (e.g., I randomly fix 70% of the trains and look for compatible schedules for the remaining ones). I guess there are still many avenues of improvements for this approach, the biggest issue was the size of the resulting MIP.

I agree with all comments here, especially the ones of @Palstek regarding test instances=evaluation instances, and the prize money.

Regarding the prize money, maybe aside from the Top 3 money, you could also offer some (naturally a smaller amount) of money to people first at the leaderboard at the end of each week (or some criterion in this spirit). This would result in i) people who made a good, but maybe not Top 3 effort maybe getting at least some money, if they had a good idea, which could be quickly implemented (and not just overfitted to the data), as at least from my experience, simple approaches may be more useful in practice as over-engineered approaches (which may be necessary to win a challenge, especially, when test instances=validation instances), and ii) it would also maybe encourage people to submit their results earlier, which could be helpful to other participants to estimate, if it is still worth an effort to continue the competition, and also to see, what the potentially best results for the instances are

I have a solution for instance 8, where the validator-script says

the solution has 2 warnings. It will be accepted as a feasible solution. However, it will incur0.15penalty points in the grader.

Warnings: - Solution with VP-Label “test” and problem_instance_hash “-1187628662” has a wrong Hash! Hash: 42, expected: -402269277 - Entry time 11:22:09 after einMax 11:22 for Train run sections with route_section_id “18239#302” and Section Marker “PF_Halt” in service_intention “18239”

However, the solution uses some route sections with a penalty of 1, e.g., 20539#50075, thus it seems the validator may not be calculating the penalty correctly?

Can you give an indication, what the problem in the validator was? E.g., was it some “systematic” error in reading the data or so? Because since your update this afternoon, solutions which were valid in the previous validator now are infeasible for me due to resource conflicts, so I probably miss the same thing that was wrong in your previous validator in the moment.

@LeoB Thank you, I missed the fractionality of the route penalties

I have a similar issue with instance 3 (and probably others, I did not check all), e.g., when I check with my own validation script, I should not have any penalty, but with your validation script, I have a penalty of 0.7, but your script does not give any output, where this penalty is coming from, so I guess it is a route penalty? However, can route penalties be fractional?