We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
An n-Constraint Formulation of the (Time Dependent) Traveling Salesman Problem.
- Authors
Fox, Kenneth R.; Gavish, Bezalel; Graves, Stephen C.
- Abstract
This article discusses the travelling salesman problem which minimizes the total intercity travel cost while visiting each of it cities exactly once. The Time-Dependent Traveling Salesman Problem (TDTSP) is a generalization of the TSP in which the cost of traveling between city i and city j depends on the time period and is given by Cyt for time period t. It is assumed that the travel time between any two cities is one time period. In this note the article presents a new formulation of the TDTSP which requires on the order of 4n linear constraints. This is used as a basis for a formulation that requires only n linear constraints.
- Subjects
MATHEMATICAL formulas; TRAVEL costs; GRAPHIC methods; OPERATING costs; PROBLEM solving; OPERATIONS research; RESOURCE allocation; PER diem allowances
- Publication
Operations Research, 1980, Vol 28, Issue 4, p1018
- ISSN
0030-364X
- Publication type
Article
- DOI
10.1287/opre.28.4.1018