search

iquadrat / sbb-train-scheduler

Solver that schedules train time tables according for SBB according to given constraints
MIT License
10 stars 7 forks source link

understanding your algorithm #1

Open DanielLSM opened 5 years ago

DanielLSM commented 5 years ago

as i've understood, you create an occupancy map and then resolve greedily this conflicts, but what were the heuristics used? when do you backtrack? could you tell me what theoretical background you used?

iquadrat commented 5 years ago

Well, there is a heuristic for choosing which conflict to address next. See the code for details. And then, the conflict resolution that (locally) causes the least conflicts is chosen. Backtracking is done if I see that no solution is possible anymore (e.g., when there is a resource with a time range where two trains each need 2 minutes occupation but the time range is only 3 minutes).