On some matching problems arising in vehicle scheduling models

Two bipartite matching problems arising in Vehicle Scheduling are considered: the capacitated matching and the multicommodity matching. For the former, given a reasonable cost structure, we can exhibit a polynomial time algorithm, while the general case is conjectured to be NP‐hard. The latter problem is shown to be NP‐hard. A heuristic algorithm based on Lagrangean relaxation for the capacitated version of the multicommodity matching is also presented together with experimental results.