A TSP Optimization using the Random Keys Technique
Updated 2019-03-27
The Travelling Salesman Problem (TSP) is an archetypical example of a class of optimization applications dealing with structuring a sequence. In it, the salesman starts at the home city, must visit each of N other cities once, then return home. The DV is the city sequence. A simple OF is to minimize the total distance traveled as measured by straight lines between points (cities). However, the OF could involve travel time, tolls, risk, and other metrics associated with the path between cities. There could be constraints related to maximum travel time, or the need to visit one city prior to another to pick up material and deliver it. There could be issues related to arrival and departure times, and penalties for expensive overnights. But, in this introductory example, the OF is simply the straight line distance between points.
Although the concept is about a person travelling, the application could be to optimize a sequence for a cargo truck or ship, or the route for trash pickup, or mail delivery. Optimizing airplane flight segments, or shipping itineraries, or design of roads or one-way streets for traffic, are all examples of the TSP. Although the TSP is structured to be a sequence for travelling between points in space, the application could be how to sequence tasks in time. For instance, in a batch reaction should the sequence be: Add A, Heat, Stir, Add B, hold, then dump? Or Add A and B, Stir, dump, heat, then hold? It is common in scheduling and logistics.
If the locations to visit are labeled A, B, C, D, and H is home, then possible TSP sequences could be H-A-B-C-D-H, or H-B-D-A-C-H. One starts and ends at “Home”. The DV is the sequence; and here, the DV is a sequence of text (category or class) variables. Making it difficult for an optimizer based on numerical DV values to set a sequence.
The random keys approach is a clever trick, perhaps first published by J. C. Bean (“Genetic algorithms and random keys for sequencing and optimization”, ORSA Journal on Computing, 1994, 6,154-160), and suitable for multi-player optimizers. There seem to be many examples of the random key approach with Particle Swarm Optimization and Genetic Algorithms. I use it with the Leapfrogging optimization algorithm.
If the locations are home plus N cities, there are a total of N+1 cities. But there are N-1 DVs. One must start and end at H. After N-2 cities have been visited there is a last choice between the 2 remaining cities. When one of those two is chosen, there is no choice left for the last. So, there are N-1 decisions to be made. However, in the random keys method, each city is assigned a random numerical value, and each of the M LF players has N DVs, a numerical value for each city. In the random keys method, initially assign a random number to each player’s DVs. Then for any particular player the city sequence is that obtained by ordering the cities by random key. For instance in a N=4 city search, Player 7 might have these DV values (0.529, 0.117, 0.983, and 0.636). Sorted in ascending order it would indicate a sequence of H-B-A-D-C-H. For each player, sort the cities by the random key values, then calculate the OF for that city sequence.
File r3eda Generic LF Function Optimizer Realtor Tour TSP 2017-04-23 has LF solve the TSP with 12 locations. My wife is a realtor, and each Thursday morning all of the local realtors travel as a group and visit the new listings. The 12 points on this file represent one particular week’s locations of houses. Brief user directions are at r3eda site Realtor Tour File Directions.