Improved bounds for vehicle routing solutions

We present lower bounds for the vehicle routing problem (VRP) with and without split deliveries, improving the well known bound of Haimovich and Rinnooy Kan. These bounds are then utilized in a design of best-to-date approximation algorithms.