Traveling Salesperson Problem (TSP)

The traveling salesperson problem (TSP) is a classic combinatorial problem where a salesperson is asked to visit a certain number of cities and would like to find the shortest route while visiting each. The atom array in this case is a single resource row (the salesperson) and a time column for each step of the route. The atom state is the city that is to be visited at time t, so it is obvious that each atom state must be unique - the salesperson doesn't want to visit the same place twice.

This is accomplished by setting the following problem definition (tsp.json) parameters as shown below:

  {
    "params": {
      "initializeType": "Unique",
      "mutatorType": "Swap"
    }
  }

Thus, all atom states are initialized randomly, but each is required to be a unique state - implying that the number of states must match the number of atoms. And, the only mutator type allows is "Swap" which means the states will remain unique.

In the samples directory:

• tspProb contains the problem definition (tsp.json) and a subdirectory called dyndata which contains a random cost array that contains the distances between each city.
• In the Python sample tester (azopytest), the tsp directory contains the python code that generates the random cost array.

Next is a sample run via azopytest.

Python sample tester (azopytest) command line parameters:

--run debug --itest tsp --tc 5 --st 20

Output:

** Problem Results **
---------------------

** Solver Results **
--------------------

Score  : 	6.789317607879639
Stop   : 	2
Time   : 	20.376

R Count: 	1
T Count: 	100
S Count: 	100

Atoms: 
[ 
	[46, 59, 83, 53, 11, 17, 64, 75, 26, 39, 15, 51, 66, 36, 23, 47, 14, 85, 87, 44, 5, 25, 69, 16, 29, 3, 81, 35, 63, 28, 93, 88, 65, 55, 90, 31, 61, 1, 57, 73, 32, 10, 0, 4, 22, 21, 80, 89, 95, 99, 40, 24, 84, 30, 67, 96, 37, 92, 74, 72, 86, 98, 34, 54, 91, 76, 94, 27, 58, 60, 71, 62, 70, 50, 8, 19, 52, 49, 42, 41, 7, 20, 82, 77, 38, 12, 13, 18, 79, 2, 48, 45, 68, 56, 97, 9, 6, 33, 43, 78]
] 

Constraints: 
O1: 6.789317607879639 (19732 ms)