Consider a set of trips where each trip is specified a priori by a place of origin, a destination, a duration, a cost and a time interval within which the trip must begin. The trips may include visits to one or more specific points. Our problem is to determine the number of vehicles required together with their routes and schedules, so that each trip begins within its given time interval, while the fixed costs related to the number of vehicles, and the travel costs between trips are minimized. The problem is a generalization of the m-travelling salesman problem.

We use column generation on a set partitioning problem solved by simplex and branch-and-bound; columns are generated by a shortest path algorithm with time windows on the nodes. Numerical results for several school bus transportation problems with up to 151 trips are discussed.