A tree-based model for setting optimal train fare zones (Q1718240)

Summary: Given a railway line with \(n\) stops and the number of travelers between each pair of stops, we show how to split these stops into \(k\) different fare zones in order to maximize the benefit obtained from the sale of tickets to the travelers. We present a method to obtain this solution that is based on finding the longest path in a weighted root tree. This method improves in terms of efficiency the combinatorial method, where all the possible distributions have to be considered for deciding which is the optimal one.