Part of the planning process in supply chain management consists of finding the best possible configuration, including the definition of product flow from plants to clients (markets) via a set of warehouses. Defining the location of such warehouses is also part of the decision-making problem. This problem is known in the literature as the two-echelon uncapacitated facility location problem (TUFLP) and is known to be NP-hard. This chapter aims at solving this problem using optimization methods baesd on approximate algorithms. Their performance is analyzed using well-known date sets from the academic literature.
TopIntroduction
This chapter studies the strategic decision making problem regarding the design of a distribution network and the definition of material flows. In particular, we consider the Two-Echelon Uncapacitated Facility Location Problem (TUFLP). In a general case, the problem is defined as follows. A firm may have relatively few products and a number of plants. Products are shipped from plants to markets via a set of warehouses. The key issues we are concerned with are: how many warehouses to have, where to locate them, and how the products should flow through the system. Implicit in the product flow decision are other decisions about which products should be produced at which plants for which markets. Figure 1 is a schematic of such a system.
Figure 1. Representation of the TUFLP
This problem is known to NP-hard (Cornuejols, Nemhauser, & Wolsey, 1990), which means that approximate algorithms are required in order to find good solutions in a reasonable amount of time for big data sets. Various solution approaches have been considered in the literature, including heuristics (e.g., Pirkul and Jayaraman, 1998; Cohen and Lee, 1989; Zuo, Kuo, & McRoberts, 1991; Chen and Wang, 1997), and meta-heuristics to solve similar, but not identical, problems (Klose, 2000; Syarif, Yun, & Gen, 2002; Syarif and Gen, 2003; Zhou, Min, & Gen, 2003; Gen, Kumar, & Kim, 2005; Gen and Syarif, 2005; Gen, Altiparmak, & Lin, 2006; Amiri, 2006; Adlakha and Kowalski, 2003; Kowalski and Lev, 2008; Adlakha, Kowalski, & Lev, 2010; Jawahar and Balaji, 2009; Zegordi, Kamal Abadi, & Beheshti Nia, 2010).
The same problem studied here is considered by Montoya-Torres, Aponte, Rosas, & Caballero-Villalobos (2010) and Montoya-Torres, Aponte, & Rosas (2011). These authors propose the use of the meta-heuristic Greedy Randomized Adaptive Search Procedure (GRASP). This chapter is an extension of their work. We present a greedy heuristic, as well as a Tabu Search meta-heuristic algorithm in order to solve the TUFLP. Our goal is to propose more effective and easy to implement algorithms. We also aim to provide the readers a rigorous experimental analysis of both deterministic and probabilistic algorithms to handle this complex problem.
TopSolutions Using Approximate Algorithms
Using approximate algorithms is usually the main alternative to solve large number of real-life optimization problems in economics and business. Talbi (2009) classifies these approaches in two classes:
- •
Dedicated Heuristics: These are problem-dependent and are designed and applicable to a particular problem, and
- •
Meta-Heuristics: More general approximate algorithms applicable to a large variety of optimization problems.