Abstract
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.
