A Class of Train-Scheduling Problems

We relate the question of determining stop-schedules for trains that deliver traffic on a line of stations to the maximization of submodular set functions. We prove that a greedy algorithm is optimal under certain assumptions and report computational experience on the performance of the greedy heuristic as compared to the exact algorithm when the optimality of the greedy heuristic cannot be guaranteed.