Browse Prior Art Database

THE TRAVELING SALESMAN PROBLEM WITH MANY VISITS TO FEW CITIES

IP.com Disclosure Number: IPCOM000128141D
Original Publication Date: 1981-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 12 page(s) / 45K

Publishing Venue

Software Patent Institute

Related People

Stavros S. Cosmadakis: AUTHOR [+4]

Abstract

We study the version of the traveling salesman problem in which a relatively small number of cities --say, six-- must be visited a huge number of times --e.g., several hundred times each. (It costs to go from one city to itself.) We develop an algorithm for this problem whose running time is exponential in the number of cities, but logarithmic in the number of visits. Our algorithm is a practical approach to the problem for instances of size in the range indicated above. The implementation and analysis of our algorithm give rise to a number of interesting graph-theoretic and counting problems. Keywords, Traveling salesman problem, dynamic programming, assignment problem, transportation problem, minimal Eulerian digraph, feasible sequence, Stirling's formula, Stirling numbers of the second kind, min-cost max-flow problem, Edmonds-Karp scaling method. [Footnote] Work based in part on the author's Batchelor's Thesis at MIT. Work supported in part by NSF Grant IvICS79-08965.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE TRAVELING SALESMAN PROBLEM WITH MANY VISITS TO FEW CITIES

Stavros S. Cosmadakis* and Christos H. Papadirnitriou**

Laboratory for Computer Science M.I.T., Cambridge, U.S.A.

Abstract

We study the version of the traveling salesman problem in which a relatively small number of cities --say, six-- must be visited a huge number of times --e.g., several hundred times each. (It costs to go from one city to itself.) We develop an algorithm for this problem whose running time is exponential in the number of cities, but logarithmic in the number of visits. Our algorithm is a practical approach to the problem for instances of size in the range indicated above. The implementation and analysis of our algorithm give rise to a number of interesting graph-theoretic and counting problems.

Keywords, Traveling salesman problem, dynamic programming, assignment problem, transportation problem, minimal Eulerian digraph, feasible sequence, Stirling's formula, Stirling numbers of the second kind, min-cost max-flow problem, Edmonds-Karp scaling method.

1
1. Introduction

In this paper we study the following version of the, traveling salesman problem (TSP): We are given n cities, an nxn distance matrix d- (not necessarily symmetric or with zero diagonal elements), and n integers kl,...,kn > 0- We are asked to find the. shortest closed walk that visits the first city k, times, the second city k2 times, and so on. (We are allowed to visit city i twice in a row, but this costs us dit)

This problem, which we call the many-visits TSP, is obviously a,generalization of the TSP (the TSP is our problem in the special case in which all ki s are equal to I). It can also be considered as a special case of the TSP (more precisely, a nonstandard representation of the TSP), in which clusters of ki cities with identical rows and columns are treated as a single city to be visited ki times. The many-visits TSP arises in connection to the applications of tile TSP in scheduling. In such applications, the cities are in fact tasks to be executed, and d U reflects the overhead associated with the task j immediately following task i. Now, in certain applications, each task belongs to one of a few types, and tasks of the same type have identical characteristics. For example, in the scheduling of airplane landings, there could only be four types of tasks --e.g., regular, jumbo, private, and military airplanes-- but several dozens of each may be pending at each time for landing. There is a certain delay between the landing of an aircraft and the landing of the next aircraft,_ depending on the types of the tw o airplanes. We

1 Work based in part on the author's Batchelor's Thesis at MIT. Work supported in part by NSF Grant IvICS79- 08965.

Massachusetts Institute of Technology Page 1 Dec 31, 1981

Page 2 of 12

THE TRAVELING SALESMAN PROBLEM WITH MANY VISITS TO FEW CITIES

wish to minimize the total delay. In the many-vis...