Solving the multi-depot location-routing problem with lagrangian relaxation
Çoğul depolu tesis yeri belirleme - rotalama probleminin lagrange gevşetme yöntemi ile çözülmesi
- Tez No: 200359
- Danışmanlar: Y.DOÇ.DR. DENİZ AKSEN
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2007
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 127
Özet
Dağıtım sistemlerinin dizayn edilmesi için değisik planlama düzeylerinde bir çok karar alınması gerekir. Kaç adet dağıtım merkezinde faaliyet gösterileceğinin ve bu merkezlerin yerlerinin belirlenmesi stratejik seviyede alınması gereken kararlardır. Hangi deponun hangi müsteriye hizmet vereceği taktik seviyede ele alınırken, teslimat rotaları operasyonel seviyede belirlenir. Çoğul Depolu Tesis Yeri Belirleme - Rotalama Problemi (ÇDTYRP) değisik düzeydeki bu kararları birlikte değerlendirir. Bu problemde, toplam maliyeti enküçülten depo sayısı ve yerleri, her müsteriye hangi deponun 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ğimiz iç 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 ana problemi iki alt probleme ayırmaktadır. ?lk alt problem SubP1, tesis yeri belirleme problemine benzemektedir ve Cplex 10.0 ile en iyi çözümü elde edilmektedir. Kapasite kısıtlı en küçük kapsayan orman problemine benzeyen ve SubP2 olarak adlandırılan diğer alt problem ise ilk Lagrange gevsetmenin içine yerlestirilmis bir çoğalan Lagrange gevsetme 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 alt sınır değeri toplanarak, tüm problemin amaç fonksiyon değeri için bir alt sınır elde edilir. ?lk problemin çözümü sonucunda bir depo yerlesim planı elde edilir. Dıstaki subgradient yönteminin yinelemeleri sırasında, ilk alt problemin sonucu olarak her farklı depo yerlesim planı elde edildiğinde, bir tabu araması algoritması çalısmaya baslar. Tabu araması algoritması ilk alt problem sonucunu temel alarak bir Çok Depolu Araç Rotalama Problemi çözer. Böylece ana problem için olurlu bir sonuç elde edilmis olur. Bulunan en iyi olurlu çözümün toplam maliyeti ana problemin en iyi sonucu için bir üst sınır teskil etmektedir. Önerilen çözüm metodunun performansı bulunan en iyi üst sınır ile en iyi alt sınır arası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.
Özet (Çeviri)
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.
Benzer Tezler
- Multi product inventory location routing problem with shortages
Karşılanamayan talepli çoklu ürün envanter yerleşim rotalama problemi
ÖZGE ŞATIR AKPUNAR
Yüksek Lisans
İngilizce
2019
Endüstri ve Endüstri MühendisliğiDokuz Eylül ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ŞENER AKPINAR
- Karınca kolonisi optimizasyonu ve genetik algoritma tabanlı tramp gemi rotalama ve çizelgeleme
Ant colony optimization and genetic algorithm based tramp ship routing and scheduling
SEHER SUENDAM ARICI
Yüksek Lisans
Türkçe
2021
Denizcilikİstanbul Teknik ÜniversitesiDeniz Ulaştırma Mühendisliği Ana Bilim Dalı
DOÇ. DR. EMRE AKYÜZ
- Modeling static and dynamic dial-a-ride problem
Müşteri rotalama probleminin statik ve dinamik olarak modellenmesi
DİLEK EKİZ
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. SANEM SARIEL
- Çoklu depolu araç rotalama probleminin hibrid algoritmalar yöntemiyle çözülmesi
Solving multi-depot vehicle routing problems via hybrid algorithms
GÜLŞEN APAK
- Belirsizlik altında heterojen filo ve zaman pencereli rotalama problemi: Hızlı tüketim sektöründe bir uygulama
Heterogeneous vehicle routing with time windows under uncertainty: Implementation in fast moving goods industry
ELÇİN ÖZEN KURU
Yüksek Lisans
Türkçe
2018
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesiİşletme Mühendisliği Ana Bilim Dalı
PROF. DR. FERHAN ÇEBİ