All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Related Documents

Share

Description

Direct flow between distribution centers for multi-objective supply chain design Hertwin Minor Popocatl Universidad Politécnica de Tulancingo Tulancingo, Hidalgo, México Elías

Transcript

Direct flow between distribution centers for multi-objective supply chain design Hertwin Minor Popocatl Universidad Politécnica de Tulancingo Tulancingo, Hidalgo, México Elías Olivares Benítez CIP UPAEP Centro Interdisciplinario de Posgrados Investigación y Consultoría Universidad Popular Autónoma del Estado de Puebla Puebla, Puebla, México Enrique González Gutiérrez Universidad Politécnica de Tulancingo Tulancingo, Hidalgo, México Rubén Tapia Olvera Universidad Politécnica de Tulancingo Tulancingo, Hidalgo, México Abstract This paper reviews the problem of designing a multi-objective supply chain called Capacitated Fixed Cost Facility Location Problem with Transportation Choices (CFCLP-TC). We solve this multi-objective problem using the epsilon-constraint approach. The models with and without this transshipment feature are implemented in GAMS and solved with CPLEX. Keywords: Multi-objective Optimization, ε-constraint, Facility Location, Pareto Front 1. Introduction Supply Chain Management (SCM) is the process of planning, implementing and controlling the operation of the supply chain efficiently (Chopra 2010). SCM spans all movements and storage of raw materials, work-in-process inventory, and finished goods from the point of origin to the point of consumption (Melo et al. 2009). Part of the planning processes in SCM aim at finding the best possible supply chain configuration so that all operation can be performed in an efficient way. The Capacitated Fixed Cost Facility Location Problem with Transportation Choices (CFCLP-TC) proposed by (Olivares 2007) is a combinatorial optimization problem for supply chain design. It is an extension of the FCLP (Fixed-Cost Facility Location Problem) as a biobjective mixed-integer program. It is based in a two-echelon system for the distribution of one product in a single time period with two objectives: to minimize cost and to minimize the transportation time from plants to customers. This approach considers several alternatives to transport the product from one facility to the other in each echelon of the network. The criterion of cost is an aggregate function of variable cost and fixed cost. The function of time represents the longest time it may take to transport a product from any plant to any customer. Differently from similar works in the literature, the aim here is to provide to the decision maker with a set of non-dominated alternatives to allow her to decide. Some qualitative information only known by the decision maker may motivate the selection of one of these alternatives. This paper reviews the design of the supply chain by modifying the original model to allow direct flow between distributions centers. For the study of this problem and the proposed variation, instances of different sizes were used. We compare the results on the basis of two types of metrics, the first one is the R pos (set of no dominated solutions) used by (Altiparmark et al. 2006), and the second are called D avg and D min (metric of the mean and minimal difference) proposed by (Olivares 2007), to compare two bi-objective Pareto fronts. The models were implemented in GAMS and solved with CPLEX 12. Additionally, the run times for both models, the original and the variation, are compared. This paper is divided into five sections as follows: the first section presents a general introduction to the work. The second section shows the literature review of the subject in order to identify the gap that this work fills. The third section presents an overview of the problem. The fourth section shows details of the computational experiment, explains the metrics used to evaluate the Pareto fronts, and presents the results of the computational implementation. Finally, the fifth section presents the conclusions and proposals to carry out further work Literature review Historically, researchers have focused on the design of distribution systems (Geoffrion and Powers 1995) without considering as a whole supply chain. Typically discrete location models were proposed to include additional features. (Aikens 1985) reviews some important integerlinear mixed formulations for production-distribution systems. However, these models had limited scope and could not cope with realistic supply chain structures. (Geoffrion and Powers 1995) proposes the inclusion of relevant features for Supply Chain Management (SCM) in the facility location models that gradually began to be considered. (ReVelle and Laporte 1996) suggested the inclusion of additional features in facility location models such as the inclusion of new objectives (maximum investment return) and decisions regarding the selection of equipment for new installations. The capacitated facility location problem (CFLP) is a wellknown combinatorial optimization problem. It consists in deciding which facilities to open from a given set a potential facility locations and how to assign customers to those facilities. The objective is minimizing total fixed and shipping cost. Applications of the CFLP include location and distribution planning, lot sizing in production planning and telecommunication network design as mentioned in (Klose and Gortz 2006). Numerous heuristics and exact algorithms for the CFLP have been proposed in the literature. Heuristic solution methods as well as approximation algorithms were proposed by (Kuehn and Hamburger 1963, Khumawala 1974, Korupolu et al. 1998). Tabu Search methods for the related p-median problem and the CFLP with single source were developed by (Rolland et al. 1996, Delmaire et al. 1999). Exact solution methods based on the Benders decomposition algorithm are considered in (Magnanti and Wong 1981, Wetges 1996). Polyhedral results for the CFLP have been obtained by (Leung and Magnanti 1989). (Aardal 1998) uses these results in a branch-and-cut algorithm for the CFLP. A variety of heuristic and exact solution approaches for the CFLP, however, use Lagrangean Relaxation. Moreover, several variants of the CFLP have been investigated. (Laporte et al. 1994) formulated a stochastic integer linear programming model for the CFLP with stochastic demands. A branchand-cut approach was applied to find the optimal solution of the problem. (Tragantalerngsak et al. 1997) formulated the mathematical model of the two-echelon SSCFLP and considered six Lagrangian relaxation-based approaches for the solution. In recent years, many meta-heuristic approaches have been applied to combinatorial optimization problems successfully, such as Simulated Annealing (SA), Genetic Algorithms (GAs), Tabu Search (TS), Ant Colony Optimization (ACO). Some recent works in this field include those presented by (Moncayo- Martinez and Zhang 2011), in which they use an ant colony approach for the design of a supply chain. (Wei-Chang et al. 2011) proposed a memetic algorithm for a problem in a multi-stage supply chain. (Rajesh et al. 2011) proposed a simulated annealing algorithm for an allocation problem. The bi-objective location problems are an extension of classic locations problems. These problems are bi-objective median, knapsack, quadratic, covering, unconstrained, locationallocation, hub, hierarchical, competitive, network, obnoxious and semi-obnoxious location problems. Considering capacities in location problems, there are capacitated and uncapacitated problems in the literature For instance, (Myung et al. 1997) have considered an uncapacitated facility location problem with two maxisum objectives net profit and return on investment and modeled it as parametric integer program with fractional and linear objectives. (Villegas et al. 2006) modeled a supply network as a bi-objective uncapacitated facility location problem, with minisum and maxisum objectives (cost and coverage). In contrast, (Galvao et al. 2006) developed an extension of the capacitated model to deal with locating maternity facilities with minisum objectives (distance traveled and load imbalance). (Costa et al. 2008) utilized a different bicriteria approach to the single allocation hub location problem. This approach has two objectives, the first is a minisum form (cost), while the second objective (process time) has two alternative forms. The Capacitated Fixed Cost Facility Location Problem with Transportation Choices (CFCLP-TC) proposed by (Olivares 2007) is an extension of the CFLP with a bi-objective mixed-integer program approach (cost and time). It is based in a two-echelon system for the distribution of one product in a single time period. This approach considers several alternatives to transport the product from one facility to the other in each echelon of the network. Differently from similar works in the literature the aim here is to provide the decision maker with a set of non-dominated alternatives to allow her deciding. Some qualitative information only known by the decision maker may motivate the selection of one of these alternatives. In combinatorial optimization, the consideration of multiple objectives has received wide attention; in specific the multi-objective combinatorial optimization (MOCO) has become a very active area of research (Ehrgott and Gandibleux 2004). This approach has been extensively studied in the literature, (Bornstain et al. 2012) develops an algorithm with re-optimization for one problem with a cost and several bottleneck objective functions, (Bérubé et al. 2009) propose an exact epsilonconstraint method for a especial case of MOCO called bi-objective combinatorial optimization (BOCO) for the traveling salesman problem with profits. The ε-constraint method is a MOCO solution method based on a scalarization where one of the objective functions is optimized while all the other objective functions are bounded in the form of additional constraints (Ehrgott 2005). The ε-constraint method guarantees to find weakly efficient solutions. However when we have an optimal solution, it is not easy to verify if this solution is either an efficient solution or it is not. (Cardona-Valdés et al. 2011) propose an algorithm based on the fusion of the ε-constraint and the L-shaped method for a bi-objective supply chain design problem with uncertainty. Likewise (Salazar-Aguilar et al. 2011) uses the ε-constraint approach for a bi-objective programming model for designing compact and balanced territories in commercial districting. In our implementation of the ε-constraint method we select one objective function as the main objective function and another objective function is transformed to another constraint. For variations in the direct flow to plants (i) to customer (k) compared with the original model, the same approach to generate the Pareto Front is used. (Mula et al. 2010) established that one of the main contributions that remain to be done in the field of mathematical models for designing supply chains is the consideration of the different distribution channels in these models and considering the different types of configurations for product flow. The study of the variations of the problem (CFCLP-TC) will establish the importance of the choice of distribution channels under the assumptions described above so that this problem is closer to real situations that are demanded in the supply chain process and location of modern facilities. Thus, the investigation in this paper contributes the development of state of art in an area that has not been sufficiently explored Problem Description The Capacitated Fixed Cost Facility Location Problem with Transportation Choices (CFCLP-TC) proposed by (Olivares 2007), is based on a two-echelon system for the distribution of one product in a single time period. In the first echelon, the product is sent from manufacturing plants (i) to distribution centers (j). The second echelon corresponds to the flow of product from distribution centers (j) to customers (k). ). The outline of the distribution network is shown in Figure 1. Figure 1 Schematic of the original Capacitated Fixed Cost Facility Location Problem with Transportation Choices (CFCLP-TC) In this problem, the number and location of plants (i) and customers (k) are known a priori. This problem includes a further decision on the selection of transportation channels between facilities, using a bi-objective approach that simultaneously minimizes the time for transporting the product from plants to customers and the combined costs of locating facilities and transportation. This solution approach builds a set of alternative non-dominated solutions for the decision maker. This problem has a set of possible locations for the opening of distribution centers (j) and their number is not defined. Each candidate site has a fixed cost for opening a facility, and each site has limited capacity. Manufacturing plants have limited capacity. This paper proposes to compare the original model (CFCLP-TC) with our proposal, which allows the exchange of product between the distributions centers (j) (p). For some alternatives in this variation the path of plants (i)-distribution centers (j)-customers (k) would compete directly with the alternative flow of plants (i)-distribution centers (j)-distribution centers (p)- customers (k). The main idea is that for some cases it is cheaper and faster to send a product from one distribution center (j) to another distribution center (p) and then send it to the customers (k). The outline of the distribution network is shown in Figure 2. The proposal explores a configuration of the new supply chain that has not been considered in the literature. Cij1, tij1 Cjk1, tjk1 Cij2, tij2 Cjk2, tjk2 Cjp1, tjp1 Cjp2, tjp2 Cpj1, tpj1 Cpj2, tpj2 Plants (i) Distributions Centers (j) Customers (k) Model: min(f 1, f 2 ) Figure 2 Schematic of the Capacitated Fixed Cost Facility Location Problem with Transportation Choices (CFCLP-CT) with flow between distribution centers f 1 = CP ijl X ijl + CW jkl Y jkl + C jpl R jpl + C pjl l LP ij k K i I j J j J l LW jk j J p P l LS jp R pjl + j J p P l LS pj F j Z j f 2 = T (2) Subject to 1 2 T - E j - E j 0 j J (3) T - E3 0 j J (4) E 1 j TP ijl A ijl 0 i I, j J, l LPij (5) E 2 j TW jkl B jkl 0 j J, k K, l LWjk (6) C jpl M 1 δ jp j J, p P (7) l LS jp C pjl l LS pj M 1 δ pj j J, p P (8) E3 A ijl TP ijl + C jpl TS jpl + B pkl TW pkl Mδ jp i I, j J, p P, k K (9) l LP ij l LS jp l LW pk E3 A ipl l LP ij C jpl + C pjl j J l LS jp TP ipl + C pjl TS pjl + B jkl TW jkl Mδ pj i I, j J, p P, k K (10) l LS pj l LW pk p P l LS jp C jpl + C pjl 1 j J, p P (11) 1 p P, (12) j J (1) p P l LS jp Y jkl = D k j J I LW jk p P l LS jp k K (13) X ijl = MP i j J I LP ij i I (14) MW j Z j Y jkl + R jpl R pjl 0 j J (15) j J l LW jk j LS jp j LS pj X ijl + R pjl Y jkl R jpl = 0 j J (16) i I l LP ij B jkl = 1 j J I LW jk p P l LS jp k K l LW jk p P l LS jp k K (17) A ijl 1 i I, j J (18) l LP ij B jkl 1 j J, k K (19) l LW jk C jpl 1 j J (20) l LS jp C pjl 1 j J (21) l LS pj X ijl A ijl 0 i I, j J, l LP ij (22) Y jkl B jkl 0 j J, k K, l LW jk (23) R jpl C jpl 0 j J, l LS jp (24) R pjl C pjl 0 j J, l LS pj (25) MP i A ijl X ijl 0 i I, j J, l LP ij (26) MW j B jkl Y jkl 0 j J, k K, l LW jk (27) MW j C jpl R jpl 0 j J, l LS jp (28) MW j C pjl R pjl 0 j J, l LS pj (29) T, E 1 j, E 2 j, E3, X ijl, Y jkl, R jpl 0 i I, j J, k K, l LP ij, l LW jk, l LS jp (30) Z j, A ijl, B jkl, C jpl, δ jp {0, 1} i I, j J, k K, l LP ij, l LW jk l LS jp (31) Equations (1) and (2) are the objective functions that look for the best possible cost and shortest time. The constraints (3) calculate the longest total time from any (i) to any (k). The constraints (4) calculate the longest total time. The constraints (5) and (6) calculate the transportation time in each echelon respectively. The constraints (7) and (8) establish a condition if - then to determine the longest time in the flow of product from (i) to (k). The constraints (9) and (10) complete the if-then condition to calculate the longest time in the flow of product from (i) to (k). Table 1: Instances Sizes Instances sizes Integer variables in the original approach Integer variables in the approach that allows flow between distribution centers (j)-(p) Constraints (11) restrict multiple product flows through distribution centers (j) so that it can only be done once. Constraints (12) state that the exchange of product between (j) - (p) do not make a cycle. Constraints (13) allow the satisfaction of the needs for each customer. Constraints (14) mean we cannot exceed the capacity of each plant (i). Constraints (15) make that the capacity of distributions centers (j) cannot be exceed. Constraint (16) provides a balance between the quantities transported in each echelon. The constraints in (17) state that customers (k) can only be provided by a single source. The constraints (18), (19), (20) and (21) provide that the transportation of the product can only be done through a single arc. The constraints (22), (23), (24) and (25) establish that an arc is inactive if there is no flow through it. The constraints (26) and (27), (28) and (29) provide that the product shipment will be made only through active arcs. The constraints (30) and (31) set the domain of the variables in the model Computational Experiment For the process of computational experiments five sets of instances of the following sizes were used as shown in Table 1. The encoding of the instance is as follows: The first index indicates the number of plants (i), the second index indicates the number of distribution centers (j), the third index indicates the number of customers (k), and finally the fourth index indicates the number of arcs between nodes in each echelon. In each size 5 instances were tested. The experiments were performed on a workstation machine with a Core 2 Duo T8300 CPU at 2.40 GHz with 12 GB of RAM, all under an operating system of 64 bits windows (seven) Metrics for evaluations To make the comparison of the Pareto fronts with the original approach and with flow between distribution centers, the metric R pos (P i ) proposed by (Altiparmark et al. 2006) was used. Additionally, we registered the average number of Pareto-optimal solutions in each front. To calculate the R pos (P i ) consider P 1 and P 2 be the sets of Pareto-optimal solutions obtained from each model, and P be the union of the sets of Pareto-optimal solutions (i.e P = P 1 P 2 ) such that it includes only non-dominated solutions Y s. The ratio of Pareto-optimal solutions in P i that are not dominated by any other solutions in P is calculated as follows: R pos (P i ) = P i {X P i T P: Y X} P i (33) Where Y X means that the solution X is dominated by solution Y. The higher the ratio R pos (P i ) is, the better the solution set P i is. Similarly, we used the metrics proposed by (Olivares-Benitez et al. 2012) called D avg and D min. These were developed to give practical meaning to the comparison of sets point by point. Then D avg computes an average rate deviation of the objective function f 1 for each value of f 2, which is in the set T. f 1 (s): f 2 (s) = t t T f1(s ): f D avg = 2 (s ) = t T D min = min t T f 1 (s): f 2 (s) = t f 1 (s ): f 2 (s ) = t T s S 1, s S 2 (34) s S 1, s S 2 (35) The metric D avg indicates the quality of a set compared to another. The following relationship can be established: If D avg 1 S 1 is better than S 2 1 S 1 is worse than S 2 = 1 S 1 is similar to S 2 Results Table 2 shows the results of the variation that allows the flow between distribution centers (j) (p). D avg is greater than 1 in all cases; this indicates a lower quality of the Pareto fronts of this variation compared with the original model. D min in all cases indicates the smallest difference comparing both fronts and gives us an indication of the difference of the fronts compared. With respect to R pos shows that the variation to the model presents values lower than 1 in all cases compared with the original model. The R pos values in the original model are on average of 1 with respect to the variatio

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks