×

Worst-case analysis of heuristics for multidepot capacitated vehicle routing problems. (English) Zbl 0752.90018

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.

MSC:

90B06 Transportation, logistics and supply chain management
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI