From timin@netcom.com Sun Jun 19 21:37:31 EDT 1994
Article: 22576 of comp.ai
Xref: glinda.oz.cs.cmu.edu comp.ai:22576
Newsgroups: comp.ai
Path: honeydew.srv.cs.cmu.edu!rochester!udel!gatech!howland.reston.ans.net!agate!library.ucla.edu!csulb.edu!csus.edu!netcom.com!timin
From: timin@netcom.com (Mitchell E. Timin)
Subject: Contest Announcement (TSP software)
Message-ID:
Summary: TSP Software Contest
Keywords: TSP contest
Organization: NETCOM On-line Communication Services (408 261-4700 guest)
Date: Sat, 11 Jun 1994 17:25:43 GMT
Lines: 130
Software Competition
for
"Traveling Salesman" Programs
Announcing a competition for the best computer programs that find
solutions to the Traveling Salesman Problem (TSP). Programs will
be judged both on execution speed and on the quality of their solutions.
Problem Description:
There are N points, plus a starting point, plus an ending point. The
N points are identified as 0, 1, 2, 3,.... N-1. A "route" is any
permutation of these N point numbers. A cost function exists such
that the cost to move from the starting point to any of the N points,
or between any of the N points, or from any point to the ending
point, is known. Each route has an associated total cost, which is
the sum of the N+1 costs to move to each point. (Starting point to
first point on route, first to second point, etc., and finally last
point on route to ending point.) Also, the point-to-point cost has
two values, depending on the direction of travel. The problem is to
find a route such that the total cost is not far from a global minimum,
and to do so as fast (minimum computer execution time) as possible.
Program Requirements:
Programs must run on typical IBM PC compatibles, under DOS or
Windows. Programs must be supplied as a .exe file, ready to execute.
They must be able to handle up to 140 points, plus the start and stop
points. Each program must begin by waiting for some keyboard input
prior to reading the input file (described below). Timing, with a
stopwatch, will begin when the keyboard input is satisfied and the
program begins to read the input file. The program must announce, by
a tone, that it has found a solution, and immediately output the
solution to a file, as well as show it on the screen. The solution
consists of the total cost, plus the route followed. Here is a sample
output, for N = 12, corresponding to the sample input given below:
----------------------------------------------------------------------
A good route is:
4 1 7 0 10 6 8 11 5 3 9 2
The total cost is:
6696
----------------------------------------------------------------------
Programs must read an ASCII text input file containing a problem
definition. The problem is defined by giving all of the
individual point-to-point costs. This file will have a value for N,
the number of points, on the first line. The second line will have
all of the cost values to move from the starting point to each of the
N points. The third line will have all costs to go from each point
to the ending point. The following lines will have all of the other
costs given as an N X N matrix. The number in row i and column j
of this matrix is the cost to move directly from point i to point j.
(i and j both range from 0 to N-1.) Note that the diagnol elements
are zero, since the routes don't specify moving from a point to itself.
All costs will be positive integers < 10,000. Here is a sample input
file for N = 12:
----------------------------------------------------------------------
12
1079 583 890 1235 223 2255 1412 955 1787 1111 1222 1459
1915 1450 167 1034 1036 2234 2110 1731 2363 984 2110 1947
0 556 1887 1835 857 2255 649 308 1136 1683 237 1098
550 0 1461 1627 383 2372 1074 574 1534 1481 755 1339
1901 1456 0 824 1077 2127 2014 1675 2242 809 1968 1812
1800 1630 844 0 1298 1309 1682 1543 1737 151 1814 1284
844 390 1100 1350 0 2201 1210 739 1607 1161 1000 1312
2209 2350 2133 1321 2187 0 1730 1964 1414 1322 2097 1178
638 1043 2101 1697 1225 1731 0 501 487 1542 424 558
(5 more lines not shown)
----------------------------------------------------------------------
Problem Details:
Please note that the lengths of the lines in the input file may reach
several hundreds of characters when N is large. The input file is
best read simply as a sequence of integers, and line lengths ignored.
Problem cases will not be simple Euclidean distances on the plane.
Problem cases will not be pathological nor especially contrived to
have peculiar characteristics. Problems will be generated by computer
beginning with random points in 2 or 3 dimensional space, computing
some cost metric (not Euclidean distance), and then further modifying
each cost by adding a function of x and y, plus a random component.
Judging:
Programs will all be run on the same PC, and with the same setup and
software configuration. Each will be run several times using different
input files, and also with repeated runs of the same input file.
Values of N near 40, and near 100 will be used. The judges will look
for a program that consistently finds a solution with total cost
within 5% of of the lowest cost found by any program, and
that does it faster than the other competitors. However, if program
A is only very slightly faster than program B, while program B
consistently finds lower cost solutions, then the judges may choose
program B over program A. In all cases the decision of the judges
will be based on their human judgement, and will be final. There is
no claim here that judges will be restricted to purely objective
criteria for decision making. In case of difficulty in choosing
among competing programs, the judges may decide that two or more
programs have a tie or draw in the competition.
Prizes:
Adept Computer Solutions, publishers of Street Wizard software, has
promised to donate $1000 worth of their city and county street mapping
programs, as long as there are at least five competitors to share the
prizes. Map data will be supplied for the geographical regions of
interest to each winner. If there are less than five competitors,
then the total donation will be reduced proportionately. The prizes
will be distributed according to the merit of the competitors, as
judged by the judges. Neither employees of Adept Computer Solutions
or Mitchell Timin Software, nor their relatives and close personal
friends and associates are eligible to compete in this contest.
The names of the winners, and brief biographical information, will
be announced in several internet newsgroups. This may include, at
the winner's option, a description of the algorithms used.
When:
Programs will be accepted until Sep. 15, 1994. Testing will be
completed prior to October 31, 1994 and the winners announced
on or before that date.
Programs may be submitted immediately or at any time. Any programs
received prior to July 10 will be tested promptly and results will be
e-mailed to their authors.
How to Enter the competition:
Prior to July 10, mail a diskette to:
Mitchell Timin
2201 Ardemore Drive
Fullerton, CA 92633
In addition to your TSP program, be sure to include your name,
address, phone no., and e-mail address. After that date, e-mail to
timin@netcom.com requesting the current address.