The basic problem of vehicle scheduling can be solved by maximum bipartite matching

In the operative planning of public transport, the vehicle scheduling problem (VSP) is one of the most important tasks. In the single depot vehicle scheduling problem (SDVSP) there is only one depot, each vehicle being in the same depot; and the task is to construct a valid set of vehicle schedules in such a way that each timetabled trip is covered by a vehicle schedule (vehicle shift). The objective to be minimized is the sum of the cost of the timetabled trips and the cost of the trips without passengers, where the latter trips are the deadhead trips and the pull-in and pull-out trips. (The vehicles have to return to the depot at the end of the day.) This optimization problem can be solved by solving a minimum perfect matching problem of a weighted bipartite graph (Bertossi et al., Networks, Vol. 17, 1987). Here, we consider the basic problem of vehicle scheduling (BVSP), which is a special (fleet minimization) case of SDVSP, where the cost to be minimized is just the number of vehicles used (vehicle schedules) and we do not consider any other possible costs. We show that BVSP can be solved by using the maximum matching of a non-complete, unweighted bipartite graph.