The Capacitated Traveling Salesman Location Problem

The capacitated traveling salesmen location problem is the problem of locating one service station with servers, each having a limited capacity, q. The service units must visit each day all the calls that are registered in a service list. Each call is generated with a given probability and the service list contains at most n calls. In the paper we present an O(n³) time heuristic for the problem on networks. This heuristic finds a solution whose relative worst-case error equals 3/2−3/(2q). We also show how one can use this heuristic to solve the problem on the plane with rectilinear or Euclidean distances with the same worst-case error. In the latter case the heuristic is proved to be asymptotically optimal.