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

DOI10.1016/J.ORL.2023.03.013MaRDI QIDQ6106544zbMATH OpenWikidataFDO

Authors Tinghan Ye, David B. Shmoys

Publication date 3 July 2023

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2211.11173

zbMATH Keywords

bipartite matchingmin-max theoremminimum fleet-size problem

Mathematics Subject Classification ID

Inventory, storage, reservoirs (90B05) Transportation, logistics and supply chain management (90B06) Programming involving graphs or networks (90C35) Minimax problems in mathematical programming (90C47)

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.

Recommendations

• Improving vehicle scheduling support by efficient algorithms
• The basic problem of vehicle scheduling can be solved by maximum bipartite matching
• On some matching problems arising in vehicle scheduling models
• Some properties of the fleet assignment problem
• An efficient algorithm for the bipartite matching problem

Cites work

• Optimization for dynamic ride-sharing: a review

Cited in

(2)

• scientific article; zbMATH DE number 5150856 (Why is no real title available?)
• Optimal fleet composition via dynamic programming and golden section search

This page was built for publication: A min-max theorem for the minimum fleet-size problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6106544)