Çoğul depolu tesis yeri belirleme - rotalama probleminin lagrange gevşetme yöntemi ile çözülmesi

The design of a distribution logistics system requires quite a number of decisions of different planning levels. The most important strategic decision is the locations of distribution centers, which are also referred to as depots. The allocation of customers to the depots is a decision of tactical level, while determining vehicle routes to visit those customers belongs to the operational level. Multi-depot Location-Routing Problem (MDLRP) involves the decisions of different levels simultaneously. In the problem, the optimal number and locations of depots are decided while allocating customers to depots and determining vehicle routes to visit all customers. In this thesis, we propose a nested Lagrangian relaxation-based method named [LRTS] for the 2-layer discrete uncapacitated MDLRP. An outer Lagrangian relaxation embedded in subgradient optimization decomposes the parent problem into two subproblems. The first subproblem is a facility location-like problem. It is solved to optimality with Cplex 10.0. The second one resembles a capacitated and degree constrained minimum spanning forest problem, which is tackled with an augmented Lagrangian relaxation. The lower bound to the true optimal solution of the comprehensive problem is obtained by summing the objective function value of the Cplex solution of SubP1 and the lower bound found for SubP2. The solution of the first subproblem reveals a depot location plan. As soon as a new distinct location plan is found in the course of the subgradient iterations, a tabu search algorithm is triggered to solve the multi-depot vehicle routing problem associated with that plan, and a feasible solution to the parent problem is obtained. Its objective value is checked against the current upper bound on the parent problem?s true optimal objective value. The performance of the proposed method is evaluated based on the gap between the best upper bound and the best lower bound achieved. [LR-TS] has been tested on a number of randomly generated test problems as well benchmarking problems from LRP literature, and the results have been tabulated.