گراف مبتنی بر الگوریتم هیوریستیک نظری برای پاسخگویی به زنجیره تامین طراحی شبکه با حمل و نقل مستقیم و غیر مستقیم

The configuration of the supply chain network has a strong influence on the overall performance of the supply chain. A well designed supply chain network provides a proper platform for efficient and effective supply chain management. The supply chain network should be designed in the way that could meet the customer needs with an efficient cost. This paper studies the responsive, multi-stage supply chain network design (SCND) problem under two conditions: (1) when direct shipment is allowed and (2) when direct shipment is prohibited. First, two mixed integer programming models are proposed for multi-stage, responsive SCND problem under two abovementioned conditions. Then, to escape from the complexity of mixed integer mathematical programming models, graph theoretic approach is used to study the structure of the SCND problems and it is proven that both of SCND problems considered in this paper could be modeled by a bipartite graph. Finally, since such network design problems belong to the class of NP-hard problems, a novel heuristic solution method is developed based on a new solution representation method derived from graph theoretic view to the structure of the studied problem. To assess the performance of the proposed heuristic solution method, the associated results are compared to the exact solutions obtained by a commercial.

Today’s competitive business environment leads to many changes in production and distribution systems. One of these important changes goes back to the competition among the supply chains instead of companies. An efficient and responsive supply chain helps firms to satisfy the two polar needs of customers including low delivery time and low price. Supply chain is a network of suppliers, manufacturers, warehouses, and retailers organized to produce and distribute merchandise at the right quantities, to the right locations, and at the right time, in order to minimize total costs while satisfying service level requirements [1]. As a traditional objective, efficiency of the supply chain network is the main objective considered by the researchers and practitioners in supply chain network design. Usually the network efficiency is translated and modeled as cost minimization (e.g. [2] and [3]) or profit maximization (e.g. [4]) in supply chain network design literature. Another aspect that should be considered besides cost efficiency is the customer service level. Chopra [5] mentioned that the performance of supply chain network should be evaluated along two dimensions: (1) customer needs and (2) cost of meeting customers need. “On time delivery” plays an important role in customer satisfaction. The ability of supply chain to satisfy the customer’s expected delivery time called “supply chain responsiveness” and helps firms for being the order winner in their product-markets [6] and [7]. According to this point a number of authors have proposed models for optimizing the supply chain network considering cost efficiency and network responsiveness simultaneously (e.g., [6] and [8]). However, these researches limited themselves to only considering direct shipment or indirect shipment mechanism (see for example [6], [8] and [9]) and no one address both of these shipment mechanisms together and let the model to select the best mechanism as an output decision. Most of supply chain network design problems can be reduced to capacitated facility location problem (CFLP) which is known to be NP-complete [10]; therefore, most of supply chain network design problems are NP-hard. To cope with the complexity of supply chain network design problems many heuristic algorithms (e.g. [3], [11] and [12]) and metaheuristics such as genetic algorithm (e.g. [8] and [13]), simulated annealing (e.g. [14] and [15]), tabu search (e.g. [16] and [17]), memetic algorithm (e.g. [6]) and scatter search (e.g. [9]) are developed and used by authors in the recent decade. However, still this area needs efficient solution approaches, especially, when real-life features are incorporated in the network design model (e.g., the consideration of network responsiveness and/or indirect shipment besides direct shipment) and the complexity of the resulting model increased. The need of more efficient solution approaches overcoming more complex network design models have recently been emphasized by Melo et al. [18] in their comprehensive review article. Based on the aforementioned descriptions, this paper proposes a network design optimization model as well as an efficient solution method for multi-stage, single product, responsive supply chain network design problem considering both direct and indirect shipment. The proposed graph theoretic-based heuristic algorithm can also be used in a number of problems in other domains (see [19]) such as telecommunication network design (see [20]), facility location and transportation network problems (see [21]) and multi-stage process planning in manufacturing systems (see [22]) with some little modifications. The main contributions of this paper that differentiate it from the existing ones in the related literature can be summarized as follows: • Proposing a supply chain network design mathematical model that is able to determine the least cost configuration of the supply chain network considering the network responsiveness as well as both direct and indirect shipment mechanisms. To the best of our knowledge there is no research paper considering both of the abovementioned features in a single model. Also, the proposed model considers penalty cost for non-utilized capacity at opened facilities (i.e., plants and distribution centers) in the objective function. • Applying a graph theoretic approach to study the structure of the concerned SCND problems and proving that both of the studied problems can be converted to a bipartite graph. • Proposing an efficient heuristic solution approach for the concerned problem, based on a new solution representation method derived from graph theoretic view to the structure of the studied problem, which is able to generate high quality solutions in a reasonable time. In the next section the problem is described and possible structures for the studied supply chain networks are classified based on a graph theoretic approach. A novel solution method is proposed to determine the optimal design for the responsive supply chain network in Section 3 and a numerical example and the related results are given in Section 4. Finally a summary of work and some possible future works are given in Section 5.

The design of the supply chain network is the most important strategic decision in supply chain management. This paper studies the responsive SCND problem under two conditions: (1) when direct shipment is allowed and (2) when direct shipment is prohibited. To this aim, first, two mixed integer programming models are developed. The proposed models are multi-stage, capacitated SCND models aimed at making a reasonable balance between fixed opening costs, variable transportation and processing costs and penalty costs for non-utilized capacity at opened facilities to determine the least cost configuration of the concerned supply chains. To escape from the complexity of mixed integer mathematical programming models, graph theoretic approach is used to study the structure of the SCND problem in this paper. Also, it is proven that SCND problems considered in this paper could be modeled by a bipartite graph. A heuristic solution method is proposed based on a new encoding method derived from the bipartite structure of the studied problems to solve the proposed responsive, multi-stage SCND models. The performance of the proposed heuristic solution method is investigated by comparing the associated results with the exact solutions obtained by a commercial solver in a set of problems. To the best of our knowledge, this research is one of the primary works using graph theoretic approach for SCND problem and the literature considering this approach in SCND is still scarce. Therefore, many possible future research avenues can be defined in this context. For example using graph theoretic approach to study the closed-loop or multi-product SCND problems and to analyze the adaptability of the designed supply chain networks or taking into account the uncertainty in SCND problems that may results in stochastic or fuzzy optimization models are attractive future research avenues. Also, providing new efficient heuristic solution approaches based on graph theoretic view or extending the proposed solution method for multi-objective SCND problems is another attractive research line for future. As mentioned in Section 1, the structure of some other problems such as telecommunication network design, facility location and transportation network design and multi-stage process planning problems are somehow similar to the structure of the studied SCND problem. Therefore, the proposed heuristic method in this paper can be modified and extended to solve the abovementioned problems. Moreover, since tripartite graph structure while the time on edges are taken into account is connected with timetabling problems, this problem can also be considered as another potential area for further extensions.