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 the author presents an O (n to the 3rd power) time heuristic for the problem on networks. This heuristic finds a solution whose relative worst-case error equals 3/2 - 3/(2q). The report also shows 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.

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 00607517
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Apr 30 1991 12:00AM