SOLVING THE MULTI-DEPOT LOCATIONROUTING
PROBLEM WITH LAGRANGIAN
RELAXATION
Zeynep Özyurt1 and Deniz Aksen2
1Industrial Engineering Deparment, Koç University; 2College of Administrative Sciences
and Economics, Koç University, Rumelifeneri yolu 34450 Sariyer, İstanbul, Türkiye
Abstract: Multi-depot Location-Routing Problem (MDLRP) is about finding the optimal
number and locations of depots while allocating customers to depots and
determining vehicle routes to visit all customers. In this study we propose a
nested Lagrangian relaxation-based method for the 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 9.0. The second one resembles a capacitated and degree constrained
minimum spanning forest problem, which is tackled with an augmented
Lagrangian relaxation. 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 has been observed on a
number of test problems, and the results have been tabulated.
Key words: location routing; Lagrangian relaxation; heuristics; tabu search.
Oleh: mirarahayu | Juni 29, 2009
SOLVING THE MULTI-DEPOT LOCATION-ROUTING
Ditulis dalam Info Manajemen Rantai Pasok
Industrial Engineering Blog 
AM Tires: EVALUASI PENAWARAN RANTAI DESAIN KEPUTUSAN DALAM KETIDAKPASTIAN
Sebuah keputusan desain rantai pasokan di AM Tires (perusahaan produsen ban), digunakan untuk menggambarkan kekuatan metodologi analisis pohon keputusan untuk membuat keputusan di bawah ketidakpastian. AM Tires menghadapi lokasi pabrik dalam jaringan global dengan fluktuasi nilai tukar dan permintaan yang tidak pasti.
AM Tires menjual produk-produknya di Meksiko dan Amerika Serikat. Permintaan di Amerika Serikat saat ini 100.000 ban per tahun, dan di Meksiko adalah 50.000 ban per tahun. Dari satu tahun ke depan, permintaan di kedua negara dapat meningkatkan sebesar 20% dengan probabilitas 0,5 atau penurunan sebesar 20% dengan probabilitas 0.5. Fluktuasi permintaan di kedua negara independen.
Harga satu ban sebesar $ 30 di Amerika Serikat dan 240 peso di Meksiko. Kurs saat ini adalah $ 1 US = 9 peso. Dari satu tahun ke depan, peso akan naik 25% atau turun 25%, masing-masing dengan probabilitas 0.5. Fluktuasi nilai tukar yang independen terhadap fluktuasi permintaan.
Perusahaan berencana untuk membangun 100.000 unit pabrik di Amerika Serikat dan 50.000 unit pabrik di Meksiko. Plant dapat berdedikasi, dalam hal ini mereka hanya dapat memasok pasar lokal, atau fleksibel, dalam hal ini mereka dapat pasokan pasar baik.
Biaya transportasi antara Amerika Serikat dan Meksiko adalah $ 1 per ban. Keputusan pabrik harus tinggal di tempat selama 2 tahun dan tingkat diskonto yang digunakan oleh AM Tires adalah k = 0,1.
Vice President membuat pohon keputusan. Setiap simpul dalam periode tertentu mengarah ke delapan periode berikutnya karena permintaan di setiap negara dan kurs bisa naik atau turun.
Permintaan dalam ribuan dan diwakili oleh DU untuk Amerika Serikat dan DM untuk Meksiko. Kurs diwakili oleh E, di mana E adalah jumlah peso ke US $.
Ada empat kemungkinan kapasitas dan fleksibilitas kombinasi antara plant di Meksiko dan Amerika Serikat. Vice President di AM Tires mengevaluasi kasus pertama di mana yang berdedikasi kapasitas 100.000 terinstal di Amerika Serikat dan kapasitas yang berdedikasi 50.000 terinstal di Meksiko.
• BERDEDIKASI KAPASITAS 100.000 DI AMERIKA SERIKAT DAN 50.000 DI MEXICO
Vice President memulai dengan mengevaluasi keuntungan di setiap node dalam Periode 2. Setiap negara di Periode 2 adalah diwakili oleh nilai yang sesuai DU, DM, dan E. Jumlah yang diproduksi dalam setiap plant adalah minimum kapasitas pabrik dan permintaan lokal karena kedua plant diasumsikan berdedikasi.
Dalam periode 1 terdapat delapan hasil node harus dianalisis.
Dalam periode 0, permintaan dan nilai tukar yang diberikan oleh DU = 100, DM = 50, E = 9. Di samping pendapatan dan biaya pada simpul ini, juga perlu mempertimbangkan keuntungan yang diharapkan dari delapan node dalam periode 1.
Keuntungan yang diharapkan untuk PM Ban dari menginstal 100.000 unit dari kapasitas yang didedikasikan di Amerika Serikat dan 50.000 unit kapasitas berdedikasi di Meksiko adalah: $ 1.758.656
The Vice President of PM Tires sehingga memperoleh
NPV = $ 1, 758.656
• FLEKSIBEL KAPASITAS 100.000 DI AMERIKA SERIKAT DAN 50.000 DI MEXICO
Vice President mengevaluasi berikutnya NPV menginstal kapasitas fleksibel baik di Amerika Serikat dan Meksiko. Kapasitas fleksibel dapat digunakan untuk memproduksi ban untuk kedua negara, tergantung pada keuntungan dari melakukannya. Vice President mengevaluasi pertama keuntungan di setiap node dalam periode 2.
Vice President yang pertama mengevaluasi kontribusi margin menghasilkan ban di satu tempat dan penjualan di masing-masing dari 2 pasar.
Bandingkan keuntungan simpul ini dengan dan tanpa fleksibilitas. Kapasitas yang fleksibel memberikan keuntungan sebesar $ 1.089.280, sedangkan kapasitas berdedikasi menghasilkan laba sebesar $ 677.809, memungkinkan fleksibilitas produksi AM Tires untuk mengeksploitasi fluktuasi nilai tukar dan meningkatkan keuntungan dengan menyesuaikan pasar dilayani oleh masing-masing plant.
Dalam periode 1 terdapat delapan hasil node harus dianalisis. Di samping pendapatan dan biaya pada simpul ini, juga perlu mempertimbangkan nilai sekarang dari keuntungan yang diharapkan dari delapan bening di periode 2 yang mungkin disebabkan dari node ini. Transisi probabilitas untuk masing-masing dari delapan simpul adalah 0,125.
Langkah selanjutnya adalah mengevaluasi kontribusi margin menghasilkan ban di satu tempat dan penjualan di masing-masing dari dua pasar dengan nilai tukar E = 11,25. Langkah selanjutnya adalah mengevaluasi kontribusi keuntungan dari masing-masing plant dengan memecahkan masalah alokasi permintaan.
Dalam periode 0, permintaan dan nilai tukar yang diberikan oleh DU = 100, DM = 50, E = 9. Di samping pendapatan dan biaya pada simpul ini, juga perlu mempertimbangkan nilai sekarang dari keuntungan yang diharapkan dari semua node dalam periode 1. Diberi transisi probabilitas 0,125 untuk setiap node.
Langkah selanjutnya adalah mengevaluasi kontribusi margin menghasilkan ban di satu tempat dan penjualan di masing-masing dari dua pasar dalam periode 0. Yang dilakukan Vice President berikutnya adalah mengevaluasi kontribusi keuntungan dari setiap pabrik.
Vice President yang dengan demikian memperoleh berikut:
NPV = $ 1.594.427
Pilihan untuk memiliki kedua plant menjadi fleksibel diharapkan menghasilkan NPV yang lebih rendah dibandingkan dengan kedua plant yang berdedikasi. Hal ini karena biaya membangun fleksibilitas lebih tinggi daripada nilai yang menyediakan berbagai kemungkinan di bawah nilai tukar dan permintaan hasil. Analisis yang serupa dapat digunakan untuk mengevaluasi kasus-kasus di mana salah satu dari dua plant yang fleksibel.
CEO AM Tires memutuskan untuk membangun pabrik khusus di Amerika Serikat dan plant yang fleksibel di Meksiko karena konfigurasi ini memiliki keuntungan yang diharapkan tertinggi.
Dalam pohon keputusan yang kompleks, ribuan atau bahkan jutaan mungkin jalan mungkin timbul dari periode pertama sampai akhir. Transisi probabilitas digunakan untuk menghasilkan tertimbang acak probabilitas-jalan di dalam pohon keputusan.
Model simulasi memerlukan biaya setup yang lebih tinggi untuk memulai dan menjalankan dibandingkan dengan diagram pohon keputusan. Namun, keuntungan utama mereka adalah bahwa mereka dapat memberikan penilaian kualitas tinggi dari situasi yang kompleks.
By: Riska Aprilina (112060158) on September 6, 2009
at 8:45 am
Nama : Gilang Cakra D.
NIM : 112060025
Kelas : TI 30 03
(Hal 217)
7.6 Ukuran Kesalahan Peramalan
Kesalahan peramalan berisikan informasi penting dan harus dianalisa dengan dua alasan sebagai berikut:
1) Manager menggunakan analisis error untuk menentukan apakah metode peramalan yang digunakan memprediksikan kompenen yang sistematis dari permintaan secara tepat.
2) Semua perencanaan darurat harus meliputi kesalahan peramalan.
Kesalahan peramalan untuk periode waktu t didefinisikan oleh Et,berdasarkan persamaan sebagai berikut:
Et = Ft – Dt
Satu ukuran kesalahan peramalan dikenal sebagai MSE (mean square error), persamaannya sebagai berikut:
MSEn = 1/n.∑ (1n).Et2
MSE disebut juga variansi dari kesalahan peramalan.
Dalam hal ini, kita memperkirakan bahwa komponen acak dari permintaan mempunyai rataan 0 dan variansi MSE.
Untuk menggambarkan nilai dari deviasi absolute dalam periode t, At, sehingga menjadi nilai absolut dari kesalahan dalam periode t adalah:
At = │Et│
Untuk menggambarkan MAD (mean absolute deviation) menjadi nilai rataan dari nilai deviasi absolut keseluruhan periode waktu, adalah:
MADn = 1/n ∑ (1n).At
MAD dapat digunakan untuk menghitung standar deviasi, yaitu:
σ = 1.25 MAD
MAPE (mean absolute percentage error) adalah rata-rata kesalahan absolut yaitu:
MAPEn = {∑ (1n). │Et/Dt│.100} / n
Untuk menentukan apakah metode peramalan secara konsisten over atau under estimates, kita dapat menggunakan jumlah dari kesalahan peramalan untuk mengevaluasi Biasn, dari persamaan:
Biasn = ∑ (1n).Et
TS (Tracking signal), adalah rasio antara bias dengan MAD:
TSt = biast/MADt
By: GILANG CAKRA D on September 6, 2009
at 2:40 pm
(Hal 217)
7.6 Ukuran Kesalahan Peramalan
Kesalahan peramalan berisikan informasi penting dan harus dianalisa dengan dua alasan sebagai berikut:
1) Manager menggunakan analisis error untuk menentukan apakah metode peramalan yang digunakan memprediksikan kompenen yang sistematis dari permintaan secara tepat.
2) Semua perencanaan darurat harus meliputi kesalahan peramalan.
Kesalahan peramalan untuk periode waktu t didefinisikan oleh Et,berdasarkan persamaan sebagai berikut:
Et = Ft – Dt
Satu ukuran kesalahan peramalan dikenal sebagai MSE (mean square error), persamaannya sebagai berikut:
MSEn = 1/n.∑ (1n).Et2
MSE disebut juga variansi dari kesalahan peramalan.
Dalam hal ini, kita memperkirakan bahwa komponen acak dari permintaan mempunyai rataan 0 dan variansi MSE.
Untuk menggambarkan nilai dari deviasi absolute dalam periode t, At, sehingga menjadi nilai absolut dari kesalahan dalam periode t adalah:
At = │Et│
Untuk menggambarkan MAD (mean absolute deviation) menjadi nilai rataan dari nilai deviasi absolut keseluruhan periode waktu, adalah:
MADn = 1/n ∑ (1n).At
MAD dapat digunakan untuk menghitung standar deviasi, yaitu:
σ = 1.25 MAD
MAPE (mean absolute percentage error) adalah rata-rata kesalahan absolut yaitu:
MAPEn = {∑ (1n). │Et/Dt│.100} / n
Untuk menentukan apakah metode peramalan secara konsisten over atau under estimates, kita dapat menggunakan jumlah dari kesalahan peramalan untuk mengevaluasi Biasn, dari persamaan:
Biasn = ∑ (1n).Et
TS (Tracking signal), adalah rasio antara bias dengan MAD:
TSt = biast/MADt
Nama : Gilang Cakra D.
NIM : 112060025
Kelas : TI 30 03
By: GILANG CAKRA D on September 6, 2009
at 2:43 pm
Pentingnya Aliran Supply Chain
Ada keterkaitan antara design dan manajemen aliran supply chain (product, information, and cash) dengan kesuksesan sebuah supply chain. Seperti perusahaan Dell computer yang sukses menggunakan supply chain yang bagus untuk mensupport strategi kompetisinya.
Dell membutuhkan relatif sedikit waktu untuk menjadi PC Manufaktur terbesar di dunia. Mereka mendapatkan margin, profit, dll yang lebih besar dari kompetitornya. Hal tersebut dikarenakan oleh beberapa faktor, diantaranya model bisnis perusahaan Dell adalah direct sales to customers sehingga Dell dapat melakukan segmentasi yang tepat, menganalisis kebutuhan, dan keuntungan masing-masing segmen. Sedangkan untuk menyeimbangkan antara supply dan demand, Dell membuat strategi-strategi khusus.
Selain itu, kesuksesan supply chain Dell adalah dapat melakukan kegiatan operasional kurang dari sepuluh hari, difasilitasi oleh sophisticated information exchange, menjanjikan real time data kepada supplier, memanage cash flownya dengan sangat efektif. Jadi, design dan management supply chain Dell (product, information, dan cash flow) mengantarkannya menjadi perusahaan yang sukses.
Contoh perusahaan yang tidak dapat memanage aliran supply chainnya dengan efektif adalah Quaker Oats dan e-businesses (seperti Webvan dan Kozmo).
By: PUSPITA SISWI PRATIWI/ 112060045 on September 8, 2009
at 4:57 am