برنامه ریزی کاربردی اکتشافی DC برای مشکل طراحی شبکه لجستیک

This paper proposes a new heuristic method for the logistics network design and planning problem based on linear relaxation and DC (difference of convex functions) programming. We consider a multi-period, multi-echelon, multi-commodity and multi-product problem defined as a large scale mixed integer linear programming (MILP) model. The method is experimented on data sets of various size. The numerical results validate the efficiency of the heuristic for instances with up to several dozens facilities, 18 products and 270 retailers.

An efficient configuration of a logistics network must enable the production and delivery of goods to customers at the lowest cost while satisfying a required service level. This topic has been the subject of numerous optimisation models and methods in the fields of operations management and operations research. Optimisation of supply chain design and strategic planning problems are often modelled by mixed integer linear programmes (MILPs). In these models, the location issues are often represented by binary variable decisions while the product flows along the logistics network are represented by continuous decision variables. Several reviews have been published in the last 10 years. Beamon (1998) distinguishes models with deterministic data from those with stochastic data. Owen and Daskin (1998) clearly separate the static and dynamic models and list various supply chain performance measures. Sahin and Süral (2007) present a wide range of applications. Finally, Daskin et al. (2005) and Melo et al. (2009) propose an extensive review of location problems in the context of supply chain design and planning. The present paper proposes an enhanced version of an LP-rounding heuristic for the design and planning of complex supply chains. The idea of LP-rounding is to solve the linear relaxation of some MILPs and to round the fractional variables in order to recover integer feasible solutions. Despite its poor formal guarantee of performance, linear relaxation is known to yield good lower bounds for some assignment or location problems (Benders and van Nunen, 1983). LP-rounding methods have been recently applied to the general assignment problem (French and Wilson, 2007) or lot-sizing problems (Hardin et al., 2007). In the field of facility location or logistics network planning, linear relaxation-based heuristics have been used for the single facility location and more complex models (Levi et al., 2004). In a recent paper, Thanh et al. (2010) proposed an LP-rounding method combined with correction procedures for the strategic planning of complex logistics networks. The method relies on successive linear relaxations of the original MILP. At each iteration, some facility location variables are set at 0 or 1, either directly by the linear relaxation or by some rounding procedures. The method produces a sequence of MILPs of decreasing size. After a large enough number of iterations, the resulting MILP can be eventually handled by a solver. The heuristic is able to produce feasible solutions for every tested instance thanks to efficient correction procedures. The observed average reduction in computation time compared to the solver is around 80% while the loss in the objective function is 1.5%. However, for larger instances, the size of the residual MILP at the last step hinders the efficiency of the heuristic. The proposed improvement consists of integrating a DC programming step into this method. At each iteration, the optimisation problem is modelled as a DC (difference of convex functions) problem and solved with the DC algorithm (DCA). This algorithm is used as a local search to improve the current upper bound. The numerical experiments show that introducing this DC formulation to solve the relaxed problem speeds up the heuristic. It also yields solutions that rarely require the use of the correction procedures. The remainder of this paper is organised as follows. Section 2 summarises the underlying mathematical model, which is extensively detailed in Appendix A. Section 3 recalls the main principles of DC programming and the DC algorithm. In Section 4, we introduce the DC-based heuristic and show how to apply it to the logistics network design problem. Numerical results are presented in Section 5.

We have proposed a new heuristic method for the logistics network design and planning problem. This method improves the LP-rounding heuristic method that was proposed in Thanh et al. (2010). For the largest instances, the LP-rounding procedure reached its practical limits and the improvement compared to a commercial solver was not significant enough. Therefore, we have designed a new heuristic to improve the computation performance, especially on large-scale instances. The proposed method is also based on LP-rounding where the problem is reformulated in DC programming and solved with the DCA at each iteration. The method focuses on location variables, which are rounded by using tailored rules. An acceleration procedure is also proposed to enhance the efficiency of the integer variables rounding. We have tested this heuristic on various data sizes of instances. The results show that DC programming is well adapted to the structure of this problem, and that we have proposed an efficient decomposition. Every instance could be solved in less than half an hour. In practice, this enables the potential users to run the algorithm repeatedly to test various economical scenarios. At each iteration, the linear problem is solved very quickly and recovering feasibility does not pose any problem. We show the efficiency of the DC heuristic compared to using a commercial solver, especially for large instances, as the computing time is reduced from 75% to 90% for most of the largest instances. The degradation of the objective function is generally less than 1%. However, for the most difficult instances, we observe a significant optimality gap of about 3%. For further research, we propose to establish a more robust solution method, combining the DC approach with an efficient relaxation technique.