THE CAPACITATED TRAVELING SALESMEN 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 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.

• Availability:
  • Find a library where document is available. Order URL: https://www.library.northwestern.edu/find-borrow-request/requests-interlibrary-loan/lending-institutions.html
• Authors:
  • SIMCHI-LEVI, D
• Publication Date: 1991-2

Media Info

• Features: Appendices; Figures; References; Tables;
• Pagination: p. 9-18
• Serial:
  • Transportation Science
  • Volume: 25
  • Issue Number: 1
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Heuristic methods; Instruments for measuring time; Mathematical models; Service stations; Travel time
• Uncontrolled Terms: Capacity
• Old TRIS Terms: Time measurement
• Subject Areas: Highways; Planning and Forecasting;

Filing Info

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