Realtor Tour – a TSP Optimization using the Random Keys Technique

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. The 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 example, the OF is simply the straight line distance between points.

Optimizing delivery routes for mail delivery, or pickup routes for trash collection, or 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, 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. The DV is the sequence; and here, the DV is a sequence of text (category or class) variables. Making it difficult for an optimizer 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 Leapfrogging.

If there are home plus N cities, then there are N DVs. Each of the M LF players has N DVs. 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.