Name: Computation of optimal railway schedules
Name of the student: Fedir Kovalov
E-mail: kovalov3@uniba.sk
Supervisor: Jozef Rajník
E-mail: jozef.rajnik@fmph.uniba.sk
Goal: Develop and implement a program for computation of optimal railway schedules, more in the winter report
"Legacy" code:Simple c++ program that recieves the description of railroad network and routes of all trains, and 1. - find out, if these routes are valid within the given railroad network. 2. find out, if starting these trains all at the same time will produce any conflicts, a try to add delay to one train such that the conflit dissapears (the same as the "naive approach" in the winter report): kod
Latest code: github
The project was... messy. It's not a success story, but it wasn't disaster by almost any measure.
This is a brief overview about how the program came about, and a glance over how it works. For a detailed specification of how it all works or how to use it, look into summer report or github page.
The idea was concieved way before I ever knew I would have to make a yearly project in the university. Probably it dates all the way back to the time I made the automated lego railway, and never left my mind since.
Nevertheless, when the time came, I had to do the yearly project in my uni, and after some hesitation, I finally decided to pick this idea.
Exactly what idea you ask? Well, I wish someone asked me to clarify this at the time: not only did I not understand the complexity of the matter, nor had any idea what I was doing. I completely underestimated the complexity of the schduling problem. My thought at the time was: "hey, since everyone schedules trains by hand now, I would be the first!".
I think that by now you can guess I was completely wrong with my assumption. As I would learn pretty soon, not only the solutions already exist, not everyone schedules trains by hand anymore either.
At first, I decided that the naive FIFO solution would be good enough, and oh boy, was I wrong... Already halway trough the semester, when most code was already written, I started noticing that even I could come up with solutions that are far better than FIFO, and that's when I started reading the research on the topic... And discovered my solution was complete garbage.
The hope wasn't lost however. While doing the research I have found a fantastic youtube channel called scheduling seminar, where in one video the "job-shop" approach to the scheduling problem was described. Basically, the idea was to reduce the train scheduling problem to the job-shop scheduling problem, where trains would become jobs, and the track sections would be shops.
So, the winter semester concluded by me presenting the "naive" solution, and promising to improve to to the job-shop next time.
Needless to say, the supervisor was not happy. Still, he took it on me pretty easy, but promised this won't work next time.
This time, I had an actual plan: to use a linear solver that would solve the job-shop problem, that I transformed from the train scheduling problem. So, I started doing exactly that. I downloaded the google's CP-SAT, and started baking up code... or did I?
Well, not really. Since I decided to write the program in C++, I needed to link the library. But no matter how hard I tried, CP-SAT refused to link to my code. I think I have tried everythnig, even writing my own Makefile(s) for the entire thing, but... It eventuially worked.
The happiness was short-lived though, as the semester almost over, and considering all of the midterms, I had no time at all. Still, I tried my best at making the program work as well, as possible.
In the end, I did make a functional product: according to my (very limited) testing, it did generate correct schedules, and definetly was far more efficient than whatever FIFO algorithm could ever even dream of. The program wasn't very fast, nor easy to use. By far the biggest issue is that to make up new routes (yes, the program not only can schedule, but also plan routes from scratch) it just finds ALL of them, and forces the poor CP-SAT to choose from potentially thousands of different routes.
This time, supervisor was not happy either. The biggest complaint was that I basically recreated software someone already came up with loooong time ago, and pretty poor communication.
I don't think he is wrong on either one of these. I guess I didn't mention it much in the rest of the story, but I almost didn't talk to my supervisor, which, looking back, was the biggest reason all of the above mentioned issues happened in the first place. If I talked to him more, I could have avoided not understanding the problem. If I talked to him, he probably could suggest a better solution before I started wasting my time on the FIFO implementation. It all comes down to talking to the person, that is there to help you in the first place.
I can confidently say that the created program indeed can accurately compute train schedules. It recieves desired train routes (or instruction for creating one) and your track network graph in the input and outputs a schedule for each train route.
This, however, comes at expense of convinience, as there is no practical way to create the descriptions for the railway layout, and overall, it's not easy to use by any means.
I stronly believe, that given enough time I would be able to evolve the program to a more usable state.
For now, I don't have plans for evolving this much further. I don't have time, nor desire to continue any of this for now.
However, if I did, I would probably:
