Bounding the VRP Distance Before Knowing the Location of Points

This note presents upper bounds for the minimum distance needed to visit n points in a unit circle, with a vehicle fleet based at its center and allowed to visit a maximum of q points per vehicle tour. The paper shows that the minimum distance can never exceed: [2n/q]+ + pi q. If points are randomly and uniformly distributed, and travel can only take place on a ring-radial network, the paper also proves that for q = 0(n**beta), 0 less than beta less than 1/2, the average minimum distance does not exceed: [4n/3q] + 0.82(pi n)**1/2 + 0(q). For the Euclidean metric, it is claimed that a tighter bound, [4n/3q] + 0.64(pi n)**1/2 + 0(q), holds even if beta = 0. Simulation tests seem to confirm this claim, even for relatively small n. For the conditions specified, the new bounds are lower than those obtained by partitioning traveling salesman problem tours.