A min-max theorem for the minimum fleet-size problem

Tinghan Ye; David Shmoys

doi:10.1016/j.orl.2023.03.013

paper

A min-max theorem for the minimum fleet-size problem

arXiv:2211.11173 · doi:10.1016/j.orl.2023.03.013

Abstract

A retrospective fleet-sizing problem can be solved via bipartite matching, where a maximum cardinality matching corresponds to the minimum number of vehicles needed to cover all trips. We prove a min-max theorem on this minimum fleet-size problem: the maximum number of pairwise incompatible trips is equal to the minimum fleet size needed.