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:
- Find a library where document is available. Order URL: http://worldcat.org/oclc/904882633
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

Language

English

Media Info

Media Type: Digital/other
Pagination: 7p
Serial:
- Research Report (University of California, Berkeley. Institute of Transportation Studies)

Subject/Index Terms

TRT Terms: Employment; Mathematical models; Route choice; Travel behavior; Traveling salesman problem; Trip purpose
Uncontrolled Terms: Transport costs
ATRI Terms: Employment; Journey purpose; Modelling; Route choice; Transport costs; Travel behaviour
ITRD Terms: 8122: USA
Subject Areas: Economics;

Filing Info

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