Freight train scheduling on a single line network

The problem of scheduling the transportation of goods from one location to another is one that arises in quite a few industries. Real world examples of these type of scheduling problems include milk tanker scheduling, distribution of ready-mixed concrete, and refuse collection.In this thesis, we study the problem of scheduling the transportation of goods from one location to another using freight trains on a single line track network. We first consider the train scheduling problem, which involves determining the departure and arrival times for all trains at all stations on their respective routes while ensuring that all safety and operational constraints are not violated. We adapt an existing formulation that schedules trains on a single line corridor to one that schedules multi-tripped trains on a track network. We add constraints, which exploit the precedence relationships between trains, with the purpose of tightening the formulation. We also adapt a greedy heuristic that schedules trains on a single line corridor to one that schedules multi-tripped trains on a track network, and use the solution obtained both as a warm start when solving the problem and as a primal bound for the objective function. We test the performance of our additions against the original formulation in 862 instances and find that results obtained from solving formulations that contain the added constraints and use the heuristic solution as a warm start improve upon results obtained from solving the adapted formulation on its own.We then consider the demand fulfilment problem, which involves the movement of goods on the track network from supplier to customer while avoiding congestion at all endstations on the network. We present an original formulation which combines features present in different studies in the literature. We use column generation as our solution method by first rewriting our formulation as a restricted master problem and two subproblems using the Dantzig-Wolfe decomposition. We solve both subproblems using labelling algorithms. As our problem contains binary variables, we perform branch-and-bound where we solve the problems at each node by column generation. We use Ryan-Foster-based branching rules to make the branching decisions at each node. We test the performance of our formulation and solution method in 72 instances. The results show good performance in areas including solve time and optimality gap