3/2-Approximation Algorithm for a Generalized, Multiple Depot, Hamiltonian Path Problem

In this study, the authors consider a Generalized, Multiple Depot Hamiltonian Path Problem (GMDHPP) and show that it has an algorithm with an approximation ratio of 3/2 if the costs are symmetric and satisfy the triangle inequality. This improves on the 2-approximation algorithm that is already available for the same Traveling Salesman Problem (TSP) or Hamiltonian Path Problem (HPP).

• Record URL:
  https://escholarship.org/uc/item/06p2815q
• 
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/183900287
• Corporate Authors:

  University of California, Berkeley

  Department of Civil and Environmental Engineering
  Davis Hall
  Berkeley, CA  United States  94720-1710

  University of California, Berkeley

  Institute of Transportation Studies
  McLaughlin Hall
  Berkeley, CA  United States  94720

  California Department of Transportation

  Office of Research, P.O. Box 942873
  Sacramento, CA  United States  94273-0001
• Authors:
  • Rathinam, Sivakumar
  • 0000-0002-9223-7456
  • Sengupta, Raja
• Publication Date: 2007-10

Language

• English

Media Info

• Media Type: Digital/other
• Features: Appendices; Figures; References;
• Pagination: 14p
• Serial:
  • Research Report (University of California, Berkeley. Institute of Transportation Studies)

Subject/Index Terms

• TRT Terms: Algorithms; Logistics; Mathematical models; Routing; Traveling salesman problem
• Subject Areas: Freight Transportation; Highways; Operations and Traffic Management; Research; I71: Traffic Theory;

Filing Info

• Accession Number: 01095838
• Record Type: Publication
• Source Agency: UC Berkeley Transportation Library
• Report/Paper Numbers: UCB-ITS-RR-2007-2
• Files: CALTRANS, TRIS, ATRI
• Created Date: Apr 30 2008 7:32AM