Busca Tabu Aplicada ao Problema de Localização de Facilidades com Restrições de Capacidade

A Tabu Search Heuristic Procedure for the Capacitated Facility Location Problem

Minghe Sun, Department of Management Science and Statistics, College of Business

The University of Texas at San Antonio, San Antonio, TX 78249-0634
A TS procedure is developed, implemented and computationally tested for the capacitated facility location problem (CFLP) [Sun, 2010a]. Many researchers have worked on the CFLP and many heuristic and exact solution methods have been developed to solve it in the past. Some of the earlier heuristic methods are very effective and efficient. Therefore, it is not easy to develop a TS procedure that is more effective and efficient than these earlier heuristics. The TS procedure performs search cycles. In a search cycle, a diversification process (except in the first), the main search process and an intensification process are performed in that order.

The TS procedure uses different memory structures. Visited solutions are stored in a primogenitary linked quad tree (PLQT). The PLQT is very efficient in storing and retrieving visited solutions both in computation time and memory space [Sun, 2010b]. The binary vector representing the facility statuses is encoded into an integer vector. The encoded integer vector is used as the composite key to access the PLQT. Before a trial solution is evaluated, the PLQT is searched. The solution is retrieved and is prohibited from being visited again if it is in the PLQT already. Hence, no solution is allowed to be visited the second time. For each facility, the recent move at which the facility changed its status and the frequency it has been open are also stored. These memory structures are used to guide the main search process as well as the diversification and intensification processes.

A move is made by changing the status of one facility. Lower bounds on the decreases of total cost are used to measure the attractiveness of the moves and to select moves in the search process. To find a lower bound, a continuous knapsack problem is solved when a facility opens and an initial feasible solution for a transportation problem is found when a facility closes. Using lower bounds saves substantial computation time because finding these lower bounds is much easier than finding the exact decreases by solving transportation problems.

At each move, a transportation problem is solved. A specialized network algorithm is developed and used to exploit the problem structure in solving these transportation problems. All facilities, whether closed or open, are kept in the transportation problem. A facility is closed by adding a large number to the unit transportation cost of each arc originating from the facility. A facility is opened by removing this added large number from the unit transportation cost. In this way, the optimal solution of the previous transportation problem is primally feasible in the current one. The optimization process then starts from this solution. When selecting an arc to enter the spanning tree, this algorithm skips all arcs originating from any closed facilities. Tremendous computation time is saved by doing so especially when the number of closed facilities is large relatively to that of open facilities.

In the main search process, the facility with the maximum lower bound in the decrease of the total cost is selected to change status. The tabu condition is implemented through the recency based memory. Each closed facility is required to stay closed for at least moves and each open facility is required to stay open for at least moves, unless its aspiration criterion is satisfied. After a facility is selected, its tabu condition is checked. If not tabu, a move is made to change the status of the facility. Otherwise, its aspiration criterion is checked. The aspiration criterion is that the upper bound of total cost of the resulting solution is lower than that of the best solution found in the current search cycle. If the aspiration criterion is satisfied, the move is made even if it is tabu. Otherwise, the move is not made and another facility is selected to change status.

Three phases, called criterion altering, solution reconciling and path relinking, are used to perform the intensification process. In criterion altering, facilities that are frequently open but currently closed are more likely to be selected to open and facilities that are frequently closed but currently open are more likely to be selected to close. This is done by altering the criterion to select a facility to change status. In solution reconciling, facilities that are more promising to open are selected to open and those that are less promising are selected to close. Promising is measured by the criteria proposed by Domschke and Drexl [1985] used to select facilities to open in the ADD procedure. Path relinking is performed by moving from the current solution to the best solution found since the search started and then to the best solution found in the current search cycle.

The diversification process is conducted by changing the status of those facilities that have not changed status for the longest time. Facilities are selected by using the recency based memory.

The performance of the TS procedure is tested through computational experiments using test problems from the OR-Library and new test problems randomly generated. It found optimal solutions for almost all test problems from the OR-Library. As compared to the heuristic method of Lagrangean relaxation with improved subgradient scheme [Lorena and Senne, 1999], the TS procedure found much better solutions using much less CPU time. The computational results also show that solution reconciling is the most effective and efficient phase among the three intensification phases.

References:

Lorena, L. A. N. and Senne, E. L. F. (1999). “Improving traditional subgradient scheme for Lagrangean relaxation: an application to location problems,” International Journal of Mathematical Algorithms, 1, 133–151.

Sun, M. (2010a). “A Tabu Search Heuristic Procedure for the Capacitated Facility Location Problem,” under review in Journal of Heuristics.

Sun, M. (2010b), “A Primogenitary Linked Quad Tree Approach for Solution Storage and Retrieval in Heuristic Binary Optimization,” under review in European Journal of Operational Research.