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.