Solving the multi-depot location-routing problem with lagrangian relaxation

Abstract

Dağıtım sistemlerinin dizayn edilmesi için değisik planlama düzeylerinde bir çokkarar alınması gerekir. Kaç adet dağıtım merkezinde faaliyet gösterileceğinin ve bumerkezlerin yerlerinin belirlenmesi stratejik seviyede alınması gereken kararlardır.Hangi deponun hangi müsteriye hizmet vereceği taktik seviyede ele alınırken, teslimatrotaları operasyonel seviyede belirlenir. Çoğul Depolu Tesis Yeri Belirleme - RotalamaProblemi (ÇDTYRP) değisik düzeydeki bu kararları birlikte değerlendirir. Buproblemde, toplam maliyeti enküçülten depo sayısı ve yerleri, her müsteriye hangideponun hizmet verdiği ve teslimat rotaları eszamanlı olarak belirlenir.Bu tez, 2 seviyeli ayrık ve kapasite kısıtsız ÇDTYRP için [LR-TS] adını verdiğimiziç içe geçmis iki Lagrange gevsetmeye dayanan bir çözüm yöntemi önermektedir.Subgradient eniyileme yöntemi içerisine oturtulmus olan dıstaki Lagrange gevsetme anaproblemi iki alt probleme ayırmaktadır. ?lk alt problem SubP1, tesis yeri belirlemeproblemine benzemektedir ve Cplex 10.0 ile en iyi çözümü elde edilmektedir. Kapasitekısıtlı en küçük kapsayan orman problemine benzeyen ve SubP2 olarak adlandırılandiğer alt problem ise ilk Lagrange gevsetmenin içine yerlestirilmis bir çoğalan Lagrangegevsetme yöntemiyle çözülmektedir. SubP1'in Cplex çözümünden elde edilen amaçfonksiyon değeri ve çoğalan Lagrange gevsetme yöntemiyle SubP2 için bulunan altsınır değeri toplanarak, tüm problemin amaç fonksiyon değeri için bir alt sınır eldeedilir.?lk problemin çözümü sonucunda bir depo yerlesim planı elde edilir. Dıstakisubgradient yönteminin yinelemeleri sırasında, ilk alt problemin sonucu olarak herfarklı depo yerlesim planı elde edildiğinde, bir tabu araması algoritması çalısmayabaslar. Tabu araması algoritması ilk alt problem sonucunu temel alarak bir Çok DepoluAraç Rotalama Problemi çözer. Böylece ana problem için olurlu bir sonuç elde edilmisolur. Bulunan en iyi olurlu çözümün toplam maliyeti ana problemin en iyi sonucu içinbir üst sınır teskil etmektedir.Önerilen çözüm metodunun performansı bulunan en iyi üst sınır ile en iyi alt sınırarasındaki aralık temel alınarak değerlendirilmektedir. [LR-TS] bir kısmı rasgeleüretilmis ve bir kısmı da literatürdeki kıyas problemlerinden alınmıs test problemleriüzerinde denenmis ve sonuçlar sunulmustur.

The design of a distribution logistics system requires quite a number of decisions ofdifferent planning levels. The most important strategic decision is the locations ofdistribution centers, which are also referred to as depots. The allocation of customers tothe depots is a decision of tactical level, while determining vehicle routes to visit thosecustomers belongs to the operational level. Multi-depot Location-Routing Problem(MDLRP) involves the decisions of different levels simultaneously. In the problem, theoptimal number and locations of depots are decided while allocating customers todepots 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 relaxationembedded in subgradient optimization decomposes the parent problem into twosubproblems. The first subproblem is a facility location-like problem. It is solved tooptimality with Cplex 10.0.The second one resembles a capacitated and degree constrained minimum spanningforest problem, which is tackled with an augmented Lagrangian relaxation. The lowerbound to the true optimal solution of the comprehensive problem is obtained bysumming the objective function value of the Cplex solution of SubP1 and the lowerbound found for SubP2.The solution of the first subproblem reveals a depot location plan. As soon as a newdistinct location plan is found in the course of the subgradient iterations, a tabu searchalgorithm is triggered to solve the multi-depot vehicle routing problem associated withthat plan, and a feasible solution to the parent problem is obtained. Its objective value ischecked against the current upper bound on the parent problem?s true optimal objectivevalue.The performance of the proposed method is evaluated based on the gap between thebest upper bound and the best lower bound achieved. [LR-TS] has been tested on anumber of randomly generated test problems as well benchmarking problems from LRPliterature, and the results have been tabulated.