Improving the approximation ratio for capacitated vehicle routing
Jannis Blauth, Vera Traub, Jens Vygen
Abstract
Abstract We devise a new approximation algorithm for capacitated vehicle routing. Our algorithm yields a better approximation ratio for general capacitated vehicle routing as well as for the unit-demand case and the splittable variant. Our results hold in arbitrary metric spaces. This is the first improvement upon the classical tour partitioning algorithm by Haimovich and Rinnooy Kan (Math Oper Res 10:527–542, 1985) and Altinkemer and Gavish (Oper Res Lett 6:149–158, 1987).
Topics & Concepts
MathematicsVehicle routing problemApproximation algorithmRouting (electronic design automation)Mathematical optimizationMetric (unit)Metric spaceCombinatoricsComputer scienceDiscrete mathematicsEngineeringComputer networkOperations managementVehicle Routing Optimization MethodsData Management and AlgorithmsTransportation Planning and Optimization