A taxi routing problem can be solved via bipartite matching, where a maximum cardinality matching corresponds to the minimum number of taxis needed to cover all trips. We prove a min-max theorem: the maximum number of pairwise incompatible trips equals the minimum number of taxis needed. We also demonstrate the problem on an NYC taxi dataset and obtain a 35% reduction in the total number of taxis needed.
Part of the work is integrated into a lab for ENGRI 1101: Engineering Applications of OR.