The Time-Dependent Traveling Salesman Problem is a generalization of the well-known Traveling Salesman Problem, where the cost for travel between two nodes is dependent on the nodes and their position in the tour. Inequalities for the Asymmetric TSP can be easily extended to the TDTSP, but the added time information can be used to strengthen these inequalities. We look at extending the Lifted Cycle Inequalities, a large family of inequalities for the ATSP. We define a new inequality, the Extended Cycle (X-cycle) Inequality, based on cycles in the graph. We extend the results of Balas and Fischetti for Lifted Cycle Inequalities to define Lifted X-cycle Inequalities. We show that the Lifted X-cycle Inequalities include some inequalities which define facets of the submissive of the TDTS Polytope.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/5543 |
| Date | January 2010 |
| Creators | White, John Lincoln |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0024 seconds