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 his 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 compare numerical results for 3 algorithms developed by our research team:
1) column generation on a set partitioning problem solved by simplex and branch-and-bound; columns are generated by a shortest path algorithm with time constraints on the nodes.
2) adaptation of the Carpaneto-Toth algorithm for the asymmetric travelling salesman problem: solution of network problems by relaxing scheduling constraints, and branch-and-bound on flow variables.
3) solution of network problems by relaxing scheduling constraints and branch-and-bound based on dividing the time windows.