METAHEURISTICS:TABU SEARCH

TABU SEARCH

Tabu search is a widely used metaheuristic that uses some common-sense ideas to enable the search process to escape from a local optimum. After introducing its basic concepts, we will go through a simple example and then return to the traveling salesman example.

Basic Concepts

Any application of tabu search includes as a subroutine a local search procedure that seems appropriate for the problem being addressed. (A local search procedure operates just like a local improvement procedure except that it may not require that each new trial solution must be better than the preceding trial solution.) The process begins by using this procedure as a local improvement procedure in the usual way (i.e., only accepting an im- proved solution at each iteration) to find a local optimum. A key strategy of tabu search is that it then continues the search by allowing non-improving moves to the best solutions in the neighborhood of the local optimum. Once a point is reached where better solutions can be found in the neighborhood of the current trial solution, the local improvement pro- cedure is reapplied to find a new local optimum.

Using the analogy of hill climbing, this process is sometimes referred to as the steepest ascent/mildest descent approach because each iteration selects the available move that goes furthest up the hill, or, when an upward move is not available, selects a move that drops least down the hill. If all goes well, the process will follow a pattern like that shown in Fig. 14.3, where a local optimum is left behind in order to climb to the global optimum.

The danger with this approach is that after moving away from a local optimum, the process will cycle right back to the same local optimum. To avoid this, a tabu search tem- porarily forbids moves that would return to (or perhaps toward) a solution recently visited. A tabu list records these forbidden moves, which are referred to as tabu moves. (The only exception to forbidding such a move is if it is found that a tabu move actually is better than the best feasible solution found so far.)

This use of memory to guide the search by using tabu lists to record some of the re- cent history of the search is a distinctive feature of tabu search. This feature has roots in the field of artificial intelligence.

Tabu search also can incorporate some more advanced concepts. One is intensifi- cation, which involves exploring a portion of the feasible region more thoroughly than usual after it has been identified as a particularly promising portion for containing very good solutions. Another concept is diversification, which involves forcing the search into previously unexplored areas of the feasible region. (Long-term memory is used to help implement both concepts.) However, we will focus on the basic form of tabu search summarized next without delving into these additional concepts.

An Application Vignette

Founded in 1886, Sears, Roebuck and Company (now commonly referred to as just Sears) grew to become the largest multiline retailer in the United States by the mid-20th century. It continues today to rank among the largest retailers in the world selling merchandise and services. By 2013, it had more than 2,500 full-line and specialty retail stores in the United States and Canada. It also provides the largest home-delivery service of fur- niture and appliances in these countries with approxi- mately 4 million deliveries a year. Sears manages a fleet of over 1,000 delivery vehicles that includes contract carriers and Sears-owned vehicles. It also operates a

fleet of about 12,500 service vehicles and the asso- ciated technicians, who make approximately 14 million on-site service calls annually to repair and install appli- ances and provide home improvement.

The cost of operating this huge home-delivery and home-service business runs in the billions of dollars per year. With many thousands of vehicles being used to make many tens of thousands of calls on customers daily, the efficiency of this operation has a major impact on the company’s profitability.

With so many calls on customers to be made with so many vehicles, a huge number of decisions must be made each day. Which stops should be assigned to each vehicle’s route? What should the order of the stops be (which considerably impacts the total distance and time for the route) for each vehicle? How can all these decisions be made so as to minimize total operational costs while pro- viding satisfactory service to the customers?

It became clear that operations research was needed to address this problem. The natural formulation is as a vehicle-routing problem with time windows (VRPTW), for which both exact and heuristic algorithms have been developed. Unfortunately, the Sears problem is so huge that it is a very difficult combinatorial optimization problem that is beyond the reach of standard algorithms for VRPTW. Therefore, a new algorithm was developed that was based on using tabu search for making both the decisions on which vehicle’s route serves which stops and what the sequence is of stops within a route.

The resulting new vehicle-routing-and-scheduling system, based largely on tabu search, led to over $9 mil- lion in one-time savings and over $42 million in annual savings for Sears. It also provided a number of intangible benefits, including (most importantly) improved service to customers.

Source: D. Weigel, and B. Cao: “Applying GIS and OR Tech- niques to Solve Sears Technician-Dispatching and Home- Delivery Problems,” Interfaces, 29(1): 112–130, Jan.–Feb. 1999. (A link to this article is provided on our website, www.mhhe.com/hillier.)

Outline of a Basic Tabu Search Algorithm

Initialization. Start with a feasible initial trial solution.

Iteration. Use an appropriate local search procedure to define the feasible moves into the local neighborhood of the current trial solution. Eliminate from consideration any move on the current tabu list unless that move would result in a better solution than the best trial solution found so far. Determine which of the remaining moves provides the best solution. Adopt this solution as the next trial solution, regardless of whether it is better or worse than the current trial solution. Update the tabu list to forbid cycling back to what had been the current trial solution. If the tabu list already had been full, delete the oldest member of the tabu list to provide more flexibility for future moves.

Stopping rule. Use some stopping criterion, such as a fixed number of iterations, a fixed amount of CPU time, or a fixed number of consecutive iterations without an im- provement in the best objective function value. (The latter criterion is a particularly pop- ular one.) Also stop at any iteration where there are no feasible moves into the local neighborhood of the current trial solution. Accept the best trial solution found on any iteration as the final solution.

This outline leaves a number of questions unanswered:

1. Which local search procedure should be used?

2. How should that procedure define the neighborhood structure that specifies which solutions are immediate neighbors (reachable in a single iteration) of any current trial solution?

3. What is the form in which tabu moves should be represented on the tabu list?

4. Which tabu move should be added to the tabu list in each iteration?

5. How long should a tabu move be retained on the tabu list?

6. Which stopping rule should be used?

These all are important details that need to be worked out to fit the specific type of prob- lem being addressed, as illustrated by the following examples. Tabu search only provides a general structure and strategy guidelines for developing a specific heuristic method to fit a specific situation. The selection of its parameters is a key part of developing a suc- cessful heuristic method.

The following examples illustrate the use of tabu search.

A Minimum Spanning Tree Problem with Constraints

Section 10.4 describes the minimum spanning tree problem. In brief, starting with a net- work that has its nodes but no links between the nodes yet, the problem is to determine which links should be inserted into the network. The objective is to minimize the total cost (or length) of the inserted links that will provide a path between every pair of nodes. For a network with n nodes, (n - 1) links (with no cycles) are needed to provide a path between every pair of nodes. Such a network is referred to as a spanning tree.

The left-hand side of Fig. 14.7 shows a network with five nodes, where the dashed lines represent the potential links that could be inserted into the network and the number next to each dashed line represents the cost associated with inserting that particular link. Thus, the problem is to determine which four of these links (with no cycles) should be in- serted into the network to minimize the total cost of these links. The right-hand side of the figure shows the desired minimum spanning tree, where the dark lines represent the links

that have been inserted into the network with a total cost of 50. This optimal solution is obtained easily by applying the “greedy” algorithm presented in Sec. 10.4.

To illustrate the use of tabu search, let us now add a couple complications to this example by supposing that the following constraints also must be observed when choos- ing the links to include in the network.

Constraint 1: Link AD can be included only if link DE also is included.

Constraint 2: At most one of the three links—AD, CD, and AB—can be included.

Note that the previously optimal solution on the right-hand side of Fig. 14.7 violates both of these constraints because (1) link AD is included even though DE is not and (2) both AD and AB are included.

By imposing such constraints, the greedy algorithm presented in Sec. 10.4 can no longer be used to find the new optimal solution. For such a small problem, this solution probably could be found rather quickly by inspection. However, let us see how tabu search could be used on either this problem or much larger problems to search for an optimal solution.

The easiest way to take the constraints into account is to charge a huge penalty, such as the following, for violating them:

1. Charge a penalty of 100 if constraint 1 is violated.

2. Charge a penalty of 100 if two of the three links specified in constraint 2 are included.

Increase this penalty to 200 if all three of the links are included.

A penalty of 100 is large enough to ensure that the constraints will not be violated for a spanning tree that minimizes the total cost, including the penalty, provided only that there exist some feasible solutions. Doubling this penalty if constraint 2 is badly violated pro- vides an incentive for at least reducing how many of the three links are included during an iteration of the tabu search.

There are a variety of ways to answer the six questions that are needed to specify how the tabu search will be conducted. (See the list of questions that follows the out- line of a basic tabu search algorithm.) Here is one straightforward way of answering the questions.

1. Local search procedure: At each iteration, choose the best immediate neighbor of the current trial solution that is not ruled out by its tabu status.

2. Neighborhood structure: An immediate neighbor of the current trial solution is one that is reached by adding a single link and then deleting one of the other links in the cycle that is formed by the addition of this link. (The deleted link must come from this cycle in order to still have a spanning tree.)

3. Form of tabu moves: List the links that should not be deleted.

4. Addition of a tabu move: At each iteration, after choosing the link to be added to the network, also add this link to the tabu list.

5. Maximum size of tabu list: Two. Whenever a tabu move is added to a full list, delete the older of the two tabu moves that already were on the list. (Since a spanning tree for the problem being considered only includes four links, the tabu list must be kept very small to provide some flexibility in choosing the link to be deleted at each iteration.)

6. Stopping rule: Stop after three consecutive iterations without an improvement in the best objective function value. (Also stop at any iteration where the current trial solu- tion has no immediate neighbors that are not ruled out by their tabu status.)

Having specified these details, we now can proceed to apply the tabu search algorithm to the example. To get started, a reasonable choice for the initial trial solution is the optimal solution for the unconstrained version of the problem that is shown in Fig. 14.7(b).

Because this solution violates both of the constraints (but with the inclusion of only two of the three links specified in constraint 2), penalties of 100 need to be imposed twice. Therefore, the total cost of this solution is

Cost = 20 + 10 + 5 + 15 + 200 (constraint penalties) = 250.

Iteration 1. The three options for adding a link to the network in Fig. 14.7(b) are BE, CD, and DE. If BE were to be chosen, the cycle formed would be BE-CE-AC-AB, so the three options for deleting a link would be CE, AC, and AB. (At this point, no links have yet been added to the tabu list.) If CE were to be deleted, the change in the cost would be 30 - 5 = 25 with no change in the constraint penalties, so the total cost would in- crease from 250 to 275. Similarly, if AC were to be deleted instead, the total cost would increase from 250 to 250 + (30 - 10) = 270. However, if link AB were to be the one deleted, the link costs would change by 30 - 20 = 10 and the constraint penalties would decrease from 200 to 100 because constraint 2 would no longer be violated, so the total cost would become 50 + 10 + 100 = 160. These results are summarized in the first three rows of Table 14.1.

The next two rows summarize the calculations if CD were to be the link that is added to the network. In this case, the cycle created is CD-AD-AC, so AD and AC are the only options for deleting a link. AC would be a particularly bad choice because constraint 1 would still be violated (a penalty of 100), and a penalty of 200 now would need to be charged for violating constraint 2 since all three of the links specified in the constraint would be included in the network. Deleting AD instead would have the virtue of satisfying constraint 1 and not increasing the extent to which constraint 2 is violated.

The last three rows of the table show the options if DE were the added link. The cy- cle created by adding this link would be DE-CE-AC-AD, so CE, AC, and AD would be the options for deletion. All three would satisfy constraint 1, but deleting AD would satisfy constraint 2 as well. By completely eliminating constraint penalties, the total cost for this option would become only 50 + (40 - 15) = 75. Since this is the smallest cost for all eight available options for moving to an immediate neighbor of the current trial solution, we choose this particular move by adding DE and deleting AD. This choice is indicated in the iteration 1 portion of Fig. 14.8 and the resulting spanning tree for beginning itera- tion 2 is shown to the right.

To complete the iteration, since DE was added to the network, it becomes the first link placed on the tabu list. This will prevent deleting DE next and cycling back to the trial solution that began this iteration.

To summarize, the following decisions have been made during this first iteration:

Add link DE to the network. Delete link AD from the network. Add link DE to the tabu list.

Iteration 2. The upper right-hand portion of Fig. 14.8 indicates that the corresponding decisions made during iteration 2 are the following:

Add link BE to the network.

Automatically place this added link on the tabu list. Delete link AB from the network.

Table 14.2 summarizes the calculations that led to these decisions by finding that the move in the sixth row provides the smallest cost.

The moves listed in the first and seventh rows of the table involve deleting DE, which is on the tabu list. Therefore, these moves would have been considered only if they would result in a better solution than the best trial solution found so far, which has a cost of 75. The calculation in the seventh row shows that this move would not provide a better solu- tion. A calculation is not even needed for the first row because this move would cycle back to the preceding trial solution.

Note that the move in the sixth row is made even though it results in a new trial so- lution that has a larger cost (85) than for the preceding trial solution (75) that initiated iteration 2. What this means is that the preceding trial solution was a local optimum because all of its immediate neighbors (those that can be reached by making one of the moves listed in Table 14.2) have a larger cost. However, moving to the best of the immediate neighbors allows us to escape the local optimum and continue the search for the global optimum.

Before moving to iteration 3, we should interject an observation about what more ad- vanced forms of tabu search might do here when selecting the best immediate neighbor. More general tabu search methods can change the meaning of a “best neighbor,” depending on history, by using additional forms of memory to support intensification and diversifi- cation processes. As mentioned earlier, intensification focuses the search in a particularly promising region of solutions identified previously and diversification drives the search into promising new regions.

Iteration 3. The lower left-hand portion of Fig. 14.8 summarizes the decisions made during iteration 3.

Add link CD to the network.

Automatically place this added link on the tabu list. Delete link DE from the network.

Table 14.3 shows that this move leads to the best immediate neighbor of the trial solution that initiated this iteration.

An interesting feature of this move is that it is made even though it is a tabu move. The reason it is made is that, in addition to being the best immediate neighbor, it also results in a solution that is better (a cost of 70) than the best trial solution found previously (a cost of 75). This enables the tabu status of the move to be overridden. (Tabu search also can incorporate a variety of more advanced criteria for overriding tabu status.)

One more adjustment needs to be made in the tabu list before beginning the next iteration:

Delete link DE from the tabu list.

This is done for two reasons. First, the tabu list consists of links that normally should not be deleted from the network during the current iteration (with the exception noted above), but DE is no longer in the network. Second, since the size of the tabu list has been set at two and two other links (BE and CD) have been added to the list more recently, DE au- tomatically would have been deleted from the list at this point anyway.

Continuation. The current trial solution shown in the lower right-hand portion of Fig. 14.8 is, in fact, the optimal solution (the global optimum) for the problem. However, the tabu search algorithm has no way of knowing this, so it would continue on for a while. Iteration 4 would begin with this trial solution and with links BE and CD on the tabu list. After completing this iteration and two more, the algorithm would terminate because three consecutive iterations did not improve on the best previous objective func- tion value (a cost of 70).

With a well-designed tabu search algorithm, the best trial solution found after the algorithm has run a modest number of iterations is likely to be a good feasible solution. It might even be an optimal solution, but no such guarantee can be given. Selecting a stopping rule that provides a relatively long run of the algorithm increases the chance of reaching the global optimum.

Having gotten our feet wet by designing and applying a tabu search algorithm to this small example, let us now apply a similar tabu search algorithm to the example of a traveling salesman problem presented in Sec. 14.1.

The Traveling Salesman Problem Example

There are some close parallels between a minimum spanning tree problem and a travel- ing salesman problem. In both cases, the problem is to choose which links to include in the solution. (Recall that a solution for a traveling salesman problem can be described as the sequence of links that the salesman traverses in the tour of the cities.) In both cases, the objective is to minimize the total cost or distance associated with the fixed number of links that are included in the solution. And in both cases, there is an intuitive local search procedure available that involves adding and deleting links in the current trial solution to obtain the new trial solution.

For minimum spanning tree problems, the local search procedure described in the preceding subsection involves adding and deleting only a single link at each iteration. The corresponding procedure described in Sec. 14.1 for traveling salesman problems involves using sub-tour reversals to add and delete a pair of links at each iteration.

Because of the close parallels between these two types of problems, the design of a tabu search algorithm for traveling salesman problems can be quite similar to the one just described for the minimum spanning problem example. In particular, using the outline of a basic tabu search algorithm presented earlier, the six questions following the outline can be answered in a similar way below.

1. Local search algorithm: At each iteration, choose the best immediate neighbor of the current trial solution that is not ruled out by its tabu status.

2. Neighborhood structure: An immediate neighbor of the current trial solution is one that is reached by making a sub-tour reversal, as described in Sec. 14.1 and illustrated in Fig. 14.5. Such a reversal requires adding two links and deleting two other links from the current trial solution. (We rule out a sub-tour reversal that simply reverses the direction of the tour provided by the current trial solution.)

3. Form of tabu moves: List the links such that a particular sub-tour reversal would be tabu if both links to be deleted in this reversal are on the list. (This will prevent quickly cycling back to a previous trial solution.)

4. Addition of a tabu move: At each iteration, after choosing the two links to be added to the current trial solution, also add these two links to the tabu list.

5. Maximum size of tabu list: Four (two from each of the two most recent iterations).

Whenever a pair of links is added to a full list, delete the two links that already have been on the list the longest.

6. Stopping rule: Stop after three consecutive iterations without an improvement in the best objective function value. (Also stop at any iteration where the current trial solution has no immediate neighbors that are not ruled out by their tabu status.)

To apply this tabu search algorithm to our example (see Fig. 14.4), let us begin with the same initial trial solution, 1-2-3-4-5-6-7-1, as in Sec. 14.1. Recall how starting the sub-tour reversal algorithm (a local improvement algorithm) with this initial trial solution led in two iterations (see Figs. 14.5 and 14.6) to a local optimum at 1-2-4-6-5-3-7-1, at which point that algorithm stopped. Except for adding a tabu list, the tabu search algo- rithm starts off in exactly the same way, as summarized below:

However, rather than terminating, the tabu search algorithm now escapes from this local optimum (shown on the right side of Fig. 14.6 and the left side of Fig. 14.9) by moving next to the best immediate neighbor of the current trial solution even though its distance is longer. Considering the limited availability of links between pairs of nodes (cities) in Fig. 14.4, the current trial solution has only the two immediate neighbors listed below:

Reverse 6-5-3: 1-2-4-3-5-6-7-1 Distance = 65

Reverse 3-7: 1-2-4-6-5-7-3-1 Distance = 66

(We are ruling out reversing 2-4-6-5-3-7 to obtain 1-7-3-5-6-4-2-1 because this is simply the same tour in the opposite direction.) However, we must rule out the first of these im- mediate neighbors because it would require deleting links 4-6 and 3-7, which is tabu since both of these links are on the tabu list. (This move could still be allowed if it would im- prove upon the best trial solution found so far, but it does not.) Ruling out this immediate neighbor prevents us from simply cycling back to the preceding trial solution. Therefore, by default, the second of these immediate neighbors is chosen to be the next trial solution, as summarized below:

Iteration 3: Choose to reverse 3-7 (see Fig. 14.9).

Deleted links: 5-3 and 7-1

Added links: 5-7 and 3-1

Tabu list: 4-6, 3-7, 5-7, and 3-1

(2-4 and 3-5 are now deleted from the list.)

New trial solution: 1-2-4-6-5-7-3-1 Distance = 66

The sub-tour reversal for this iteration can be seen in Fig. 14.9, where the dashed lines show the links being deleted (on the left) and added (on the right) to obtain the new trial solution. Note that one of the deleted links is 5-3 even though it was on the tabu list at the end of iteration 2. This is OK since a sub-tour reversal is tabu only if both of the deleted links are on the tabu list. Also note that the updated tabu list at the end of iteration 3 has

However, the second of these immediate neighbors is tabu because both of the deleted links (4-6 and 5-7) are on the tabu list. The fourth immediate neighbor (which is the pre- ceding trial solution) also is tabu for the same reason. Thus, the only viable options are the first and third immediate neighbors. Since the latter neighbor has the shorter distance, it becomes the next trial solution, as summarized below:

Figure 14.10 shows this sub-tour reversal. The tour for the new trial solution on the right has a distance of only 63, which is less than for any of the preceding trial solutions. In fact, this new solution happens to be the optimal solution.

Not knowing this, the tabu search algorithm would attempt to execute more iterations. However, the only immediate neighbor of the current trial solution is the trial solution that was obtained at the preceding iteration. This would require deleting links 6-7 and 5-3, both of which are on the tabu list, so we are prevented from cycling back to the preceding trial solution. Since no other immediate neighbors are available, the stopping rule terminates the algorithm at this point with 1-2-4-6-7-5-3-1 (the best of the trial solutions) as the final solution. Although there is no guarantee that the algo- rithm’s final solution is an optimal solution, we are fortunate that it turned out to be optimal in this case.

The metaheuristics area in your IOR Tutorial includes a procedure for applying this particular tabu search algorithm to other small traveling salesman problems.

This particular algorithm is just one example of a possible tabu search algorithm for traveling salesman problems. Various details of the algorithm could be modified in a number of reasonable ways. For example, the method typically doesn’t stop when all avail- able moves are forbidden by their tabu status, but instead just selects a “least tabu” move. Also, an important feature of general tabu search methods includes the use of multiple neighborhoods, relying on basic neighborhoods as long as they bring progress, and then including more advanced neighborhoods when the rate of finding improved solutions di- minishes. The most significant additional element of tabu search is its use of intensifica- tion and diversification strategies, as mentioned earlier. But the general outline of a basic “short-term memory” tabu search approach would remain roughly the same as we have illustrated.

Both examples considered in this section fall into the category of combinatorial op- timization problems involving networks. This is a particularly common area of applica- tion for tabu search algorithms. The general outline of these algorithms incorporates the principles presented in this section, but the details are worked out to fit the structure of the specific problems being considered.