Tabu search heuristic for the network design model with lead time and safety stock considerations. (October 2020) - Lee, Kyoungsun; Ozsen, Leyla
Highlights: A tabu search heuristic with a novel indirect-cost analysis concept is introduced. The indirect-cost concept is tested on instances of a location-inventory model. The heuristic outperforms a published Lagrangian-based heuristic for that model. The heuristic outperforms also a published genetic algorithm for the same model. The heuristic outperforms three different classical implementations of tabu search. The model the heuristic is tested on, is a non-linear mixed integer program with terms that are neither concave nor convex. Abstract: This research proposes an effective and efficient tabu search heuristic for an integrated location-inventory problem. Integrated location-inventory models extend classical facility location problems by incorporating operational and tactical aspects such as lead times and safety stock. Owing to these additional considerations, integrated problems are not only NP-hard but also include non-linear terms, unlike classical facility location problems. To address this added complexity, we develop a tabu search by introducing a novel concept, the indirect cost, a ratio used to evaluate candidate facilities, along with direct cost, changes in the objective function value. For an integrated non-linear problem, the proposed tabu search heuristic with indirect cost yields near-optimal solutions. It outperforms an existing Lagrangian-based heuristic and a genetic algorithm in computational efficiency and classical tabu search heuristics without indirect costs, in terms of solution quality and robustness. We conclude that indirect costs play a key role in identifying good candidate facilities, and that the proposed tabu search is an effective and efficient solution methodology for integrated location-inventory models with non-linear terms that are neither convex nor concave.