A tabu search heuristic procedure for the capacitated facility location problem |
| |
Authors: | Minghe Sun |
| |
Institution: | (1) MicroStrategy, Inc, McLean, VA, USA;(2) The University of Texas at Austin, Austin, TX, USA |
| |
Abstract: | A tabu search heuristic procedure is developed, implemented and computationally tested for the capacitated facility location
problem. The procedure uses different memory structures. Visited solutions are stored in a primogenitary linked quad tree.
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.
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. A specialized network algorithm is developed to exploit the problem structure in solving transportation problems.
Criterion altering, solution reconciling and path relinking are used to perform intensification functions. The performance
of the procedure is tested through computational experiments using test problems from the literature and new test problems
randomly generated. It found optimal solutions for almost all test problems from the literature. As compared to the heuristic
method of Lagrangean relaxation with improved subgradient scheme, the tabu search heuristic procedure found much better solutions
using much less CPU time. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|