Matroid Intersection and Its Application to a Multiple Depot, Multiple TSP

This paper extends the Held-Karp's lower bound available for a single Travelling Salesman Problem to the following symmetric Multiple Depot, Multiple Travelling Salesman Problem (MDMTSP): Given k salesman that start at different depots, k terminals and n destinations, the problem is to choose paths for each of the salesmen so that (1) each vehicle starts at its respective depot, visits at least one destination and reaches any one of the terminals not visited by other vehicles, (2) each destination is visited by exactly one vehicle, and (3) the cost of the paths is a minimum among all possible paths for the salesmen. The criteria for the cost of paths considered is the total cost of the edges travelled by the entire collection.

  • Record URL:
  • Availability:
  • Corporate Authors:

    University of California, Berkeley

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

    University of California, Berkeley

    Department of Civil and Environmental Engineering
    Davis Hall
    Berkeley, CA  United States  94720-1710
  • Authors:
    • Rathinam, S
    • Sengupta, R
  • Publication Date: 2006-5


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01386671
  • Record Type: Publication
  • Source Agency: ARRB
  • Report/Paper Numbers: UCB-ITS-RR-2006-3
  • Created Date: Aug 22 2012 9:37PM