Worst-Case Analysis of Heuristics for Multidepot Capacitated Vehicle Routing Problems
Published Online:1 Feb 1990https://doi.org/10.1287/ijoc.2.1.64
Abstract
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.
INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
