This thesis addresses a timetabling problem known as Strategic Passenger-Oriented Timetabling (SPOT). SPOT is a timetabling problem that involves assigning departure and arrival times to train services. Unlike classical timetabling, which typically emphasizes infrastructural feasibility, SPOT shifts the focus toward enhancing the passenger experience without infrastructural constraints. The timetables generated by SPOT provide information regarding important connections for passengers and can later be adjusted to accommodate infrastructural constraints. SPOT evaluates a timetable based on the perceived travel time consisting of drive, dwell and transfer times, along with additional penalties for inconveniences by transfers and initial waiting times of passengers.

An initial research focused on using a Mixed-Integer Linear Programming (MILP) approach to solve the SPOT problem. However, this MILP formulation has multiple problems. The MILP tends to perform slow for small problem instances and becomes significantly worse as the problem size increases. Additionally, the effectiveness of the timetables generated by the MILP are often unreliable, because there is a substantial gap between the perceived travel time of the best-found timetable and the best-found lower bound.

This thesis explores a heuristic approach to solving SPOT. Specifically, two heuristics are employed: Local Search and Simulated Annealing. Both operate by exploring a neighborhood of possible timetables around a current timetable to identify better alternatives. The absence of infrastructural constraints in SPOT simplifies the creation of these neighborhoods, as different train services do not influence each other. Additionally, multiple lower bounds are calculated for the perceived travel time, providing benchmarks to evaluate the quality of the solutions. Overall, these heuristics are effective in finding good timetables within a short period, with the lower bounds being reasonably close to the perceived travel time of the generated timetables.