Non-pool-based line planning: a practical analysis of the FPT algorithm tw-lines

Line planning, which is the selection of lines to be operated to meet the demands of a transport network, is a crucial component in public transport optimization. Our line planning algorithm tw-lines for complete line pools (see Heinrich et al. (2023b)) is proven to be fast in theory whenever treewidth, maximum degree, and maximum upper frequency of the input network are bounded. So far, experiments and a detailed analysis of the algorithm’s practical performance were lacking. In this paper we close this gap. For two natural families of line planning instances we show that tw-lines finds (close-to) optimal solutions quickly and markedly reduces the line concept costs compared to traditional line-pool-based solution approaches.