Consider the Vehicle Routing Problem with Distance Constraints.

Formally, a set of customers has to be served by vehicles that are all located at a common depot. The customers and the depot are presented as the nodes of an undirected graph G  (N,E). Each customer has to be visited by a vehicle.

The j th vehicle starts from the depot and returns to the depot after visiting a subset Nj ⊆ N. The total distance traveled by the j th vehicle is denoted by Tj . Each vehicle has a distance constraint λ: no vehicle can travel more than λ

units of distance (i.e., Tj ≤ λ). We assume that the distance matrix satisfies the triangle inequality assumption. Also, assume that the length of the optimal traveling salesman tour through all the customers and the depot is greater than λ.

(a) Suppose the objective function is to minimize the total distance traveled.
Let K ∗ be the number of vehicles in an optimal solution to this problem.
Showthat there always exists an optimal solution with total distance traveled > 1 2K ∗
λ. Does this lower bound hold for any optimal solution?

(b) Consider the following greedy heuristic: start with the optimal traveling salesman tour through all the customers and the depot. In an arbitrary orientation of this tour, the nodes are numbered (i0, i1, . . . , in) ≡ S in order of appearance, where n  the number of customers, i0 is the depot and i1, i2, . . . , in are the customers. We break the tour into KH segments and connect the end-points of each segment to the depot. This is done in the following way. Each vehicle j, 1 ≤ j Show that KH ≤ min{n, T−2dm λ−2dm } where T is the length of the optimal traveling salesman tour and dm is the distance from the depot to the farthest customer.