Li, Chung-Lun; Simchi-Levi, David Worst-case analysis of heuristics for multidepot capacitated vehicle routing problems. (English) Zbl 0752.90018 ORSA J. Comput. 2, No. 1, 64-73 (1990). Summary: We consider the multidepot capacitated vehicle routing problems and analyze the tour partitioning heuristics for different versions of the model. We prove that the worst-case ratios of the heuristics are bounded by some fixed numbers. Examples are provided to show that the worst-case bounds are tight or asymptotically tight for almost all versions. Cited in 21 Documents MSC: 90B06 Transportation, logistics and supply chain management 90-08 Computational methods for problems pertaining to operations research and mathematical programming Keywords:multidepot capacitated vehicle routing; tour partitioning heuristics; worst-case bounds PDFBibTeX XMLCite \textit{C.-L. Li} and \textit{D. Simchi-Levi}, ORSA J. Comput. 2, No. 1, 64--73 (1990; Zbl 0752.90018) Full Text: DOI