This project is about creating a train routing system for intercity trains between specific stations within the Netherlands. This means that within a given time frame, we can establish a number of routes. A route consists of tracks and stations where trains travel back and forth. A route must not exceed the specified time frame. Our objective is to maximize the total score of a route. The score is calculated based on the number of connections completed, the number of routes, and the total time. The equation to obtain the score is given by K = p * 10000 - (T * 100 + Min), where K is the quality of the route, p is the fraction of connections traverse (thus, between 0 and 1), T is the number of trajectories, and Min is the total number of minutes it took to traverse the route.
To find a solution for the route several algorithms are possible:
- Random: From a (random) starting station, selects a random connection until all connections have been used.
- Normal: runs the random algorithm for a given amount of runs.
- Max: runs the random algorithm for a given amount of runs with a number of heuristics.
- Postman: From a (random) starting station, the postman tour problem is used to find a route.
- Seven bridges: Uses the seven bridges problem to find a route.
- Greedy: From a (random) starting station, always selects the connection of least time until all connections have been used.
This codebase is entirely written in Python 3.8.10. The requirements.txt file contains all the necessary packages to successfully run the code. These can be easily installed using pip with the following instruction:
pip install -r requirements.txt
Or via conda:
conda install --file requirements.txt
An example can be generated by using the following command line prompt:
python main.py
The user will be prompted to select the case. The Holland case contains 22 stations, the The Netherlands case contains 61 stations. Once selected, the user is prompted again to select an algorithm from the list. Note: Most algorithms will require at least an hour to complete 1,000,000 runs or more. The results of the runs will be saved in a text file located at /Results even if the program is stopped prematurely.
The following list describes the most important folders and where to find them.
- /Cases: Contains .csv files with information about the two cases: Holland and The Netherlands
- /Code: Contains all code used in this project.
- /Algorithms: Contains a number of algorithms to look for the best route.
- /Classes: Contains classes used to run the algorithms.
- /Results: Contains the results of the algorithms written to either a .txt or .csv file.
- /Visualisation: Contains files visualisation the network and the results of the algorithms.
We randomly drew 1.000 observations from each of the algorithms. Based on the Shapiro-Wilk test, the data did not meet the assumption of normality, W = 0.9558, p < .001. Based on the Levene test, the data also did not meet the assumption of homogeneity of variance, F(2, 2997) = 361.43, p < .001. Therefore, a Kruskal-Wallis test was performed. The algorithms differed significantly in score, H(2) = 1993.2, p < .001. Post-hoc Tukey tests showed that the greedy algorithm performed superior to both the normal algorithm (p < .001) and the maximum algorithm (p< .001). Thus, we conclude the greedy algorithm to be the most effective.
- Sten Bakker
- Nidanu O'Shea
- Berend Peeters