The Multicommodity Multilevel Bottleneck Assignment Problem

The Multilevel Bottleneck Assignment Problem is defined on a weighted graph of L levels and consists in finding L − 1 complete matchings between contiguous levels, such that the heaviest path formed by the arcs in the matchings has a minimum weight. The problem, introduced by Carraresi and Gallo (1984) to model the rostering of bus drivers in order to achieve an even balance of the workload among the workers, though frequently cited, seems to have never been applied or extended to more general cases. In this paper, we discuss one possible extension, that is the introduction of multicommodity aspects to model different classes of workers.