Pendekatan Metode Column Generation pada Vehicle Routing Problem dengan Soft Time Windows

Pendekatan Metode Column Generation pada Vehicle Routing Problem dengan Soft Time Windows Nurul Nafartsani1, Yudi Satria2, Helen Burhan3 1

Departemen Matematika, FMIPA UI, Kampus UI Depok, 16424, Indonesia Departemen Matematika, FMIPA UI, Kampus UI Depok, 16424, Indonesia 3 Departemen Matematika, FMIPA UI, Kampus UI Depok, 16424, Indonesia 2

1

[email protected], [email protected], [email protected]

Abstrak Optimisasi rute kendaraan untuk pengantaran barang merupakan salah satu cara untuk mengatasi masalah transportasi logistik di daerah perkotaan. Bentuk optimisasi rute pengantaran barang yang mempertimbangkan waktu pelayanan yang dapat berada diluar interval waktu yang sudah ditentukan dengan dikenakan biaya penalty disebut sebagai Vehicle Routing Problem with Soft Time Windows (VRPSTW). VRPSTW merupakan masalah optimisasi kombinatorik yang bertujuan untuk mencari rute dengan biaya minimum. Pencarian solusi dari VRPSTW disini menggunakan metode column generation yang dikombinasikan dengan labeling algorithm. Metode column generation mendekomposisi masalah menjadi master problem dan subroplem. Bentuk master problem dari VRPSTW berupa set partitioning problem dan subproblem yaitu Elementary Shortest Path Problem with Resource Constraint and Late Arrival Penalties (ESPPRCLAP).

A Column Generation Approach to Vehicle Routing Problem with Soft Time Windows Abstract Route optimization is one of city logistics measures to optimize logistics and the transportation systems. This type of route optimization problem where deliveries are possible outside the time windows with some penalty cost uses the form of Vehicle Routing Problem with Soft Time Windows (VRPSTW). VRPSTW is a combinatorial problem which aims to find a set of routes with minimum delivery cost. Column generation method is used to obtain solution for VRPSTW. To use column generation method to solve VRPSTW, the model formulation of VRPSTW is decomposed into master problem and subproblem. The master problem of the VRPSTW forms a set partitioning problem and Elementary Shortest Path Problem with Resource Constraint and Late Arrival Penalties (ESPPRCLAP) as a subproblem. Keywords: route optimization, vehicle routing problem, column generation

Pendahuluan Kegiatan manusia yang sering terpusat di daerah perkotaan mengakibatkan meningkatnya permintaan terhadap jasa transportasi, baik untuk manusia maupun untuk barang. Untuk memenuhi kebutuhan manusia terhadap barang, dilakukan pendistribusian barang yang seringkali menggunakan truk atau kendaraan besar. Pengangkutan barang yang dilakukan dengan kendaraan

Pendekatan metode…, Nurul Nafartsani, FMIPA UI, 2014

besar termasuk dalam masalah sistem transportasi logistik. Beberapa masalah yang dihadapi sistem transportasi logistik adalah perannya yang cukup tinggi dalam peningkatan kepadatan lalu lintas, dampak buruk bagi lingkungan, keselamatan lalu lintas dan konsumsi energi yang digunakan. Masalah yang dihadapi oleh sistem transportasi logistik tersebut termasuk dalam masalah city logistics. Masalah city logistics merupakan suatu proses untuk mengoptimalkan logistik dan kegiatan transportasi dalam area perkotaan dengan mempertimbangkan biaya yang dikeluarkan dan manfaat bagi setiap pihak yang memiliki kepentingan, tidak hanya dalam konteks biaya tetapi juga dalam lingkungan lalu lintas, kepadatan lalu lintas, dan konsumsi energi yang digunakan. (Taniguchi, 2008). Berdasarkan Taniguchi (2008), pihak yang memiliki kepentingan dalam masalah city logistics diantaranya adalah produsen, penyedia layanan logistik atau distributor, masyarakat, dan pemerintah. Masing-masing pihak pemangku kepentingan memiliki tujuan yang berbeda-beda dalam masalah city logistics. Masyarakat terdiri dari masyarakat yang merupakan pelanggan layanan logistik dan yang bukan merupakan pelanggan. Masyarakat yang merupakan pelanggan berharap agar mendapatkan barang sesuai dengan permintaan dalam waktu yang sudah ditentukan, sedangkan masyarakat yang bukan pelanggan menginginkan agar mendapat seminimum mungkin dampak dari pengangkutan barang dengan kendaraan besar. Pihak pemerintah mengatur dampak kendaraan besar bagi lingkungan dan masyarakat. Penyedia layanan logistik dan distributor yang terlibat dalam pendistribusian barang diharapkan dapat mengurangi dampak dari penggunaan truk besar bagi lingkungan dan mengurangi biaya operasional pengangkutan barang. Salah satu upaya yang dapat dilakukan oleh penyedia layanan logistik adalah melakukan optimisasi rute pengantaran barang sehingga tercapai keoptimalan dalam sistem transportasi logistik. Masalah optimisasi rute pengantaran barang dapat dibentuk menjadi Vehicle Routing Problem (VRP). VRP merupakan masalah optimisasi rute yang bertujuan untuk mencari rute optimal untuk sejumlah kendaraan dalam melayani sejumlah pelanggan dengan jumlah permintaan tertentu. Permasalahan optimisasi rute yang menambahkan kendala waktu pelayanan yang berada dalam suatu interval waktu tertentu dikenal dengan Vehicle Routing Problem with Time Windows (VRPTW). Salah satu bentuk variasi dari VRPTW adalah adanya keringanan dari time windows yang berlaku, yaitu Vehicle Routing Problem with Soft Time Windows (VRPSTW).


Berdasarkan Qureshi (2010), masalah transportasi logistik sebagian besar menggunakan interval waktu pelayanan yang diberi keringanan, yaitu jika kendaraan sampai lebih awal dari waktu pelayanan pelanggan, kendaraan tersebut diperbolehkan menunggu sampai masuk waktu awal pelayanan, tetapi apabila kendaraan tersebut terlambat maka ada biaya penalty yang harus dibayarkan. Pada model matematis VRPSTW, variabel yang digunakan mereprentasikan rute pengantaran barang yang mungkin dilalui oleh kendaraan. Semakin banyak rute yang mungkin dilalui, semakin banyak pula variabel yang digunakan dalam model masalah tersebut. Setiap variabel bersesuaian dengan kolom pada model matematis pada VRPSTW, sehingga variabel yang sangat banyak mengakibatkan jumlah kolom yang banyak. Salah satu metode yang dapat digunakan untuk menyelesaikan masalah program linier dengan jumlah kolom yang banyak adalah metode column generation (Desrosiers, J., Lubbecke, M.E., 2003). Pada skripsi ini akan dibahas mengenai pendekatan metode column generation untuk VRPSTW. Tinjauan Teoritis Pada bagian ini akan diberikan beberapa teori dasar mengenai masalah program linier dan metode column generation. Masalah program linier didefinisikan sebagai masalah mengoptimalkan suatu fungsi linier dengan variabel !! , ! = 1,2, … , ! yang disebut sebagai fungsi tujuan terhadap sejumlah berhingga kendala yang berbentuk linier. Kendala disini dapat berupa persamaan atau pertidaksamaan. Masalah program linier juga dapat diinterpretasikan sebagai pencarian sehimpunan rancangan aktivitas untuk mengalokasikan sumber daya terhadap aktivitas tertentu (F. Hillier, G. Lieberman, 2001). Bentuk umum masalah program linier untuk masalah meminimumkan adalah sebagai berikut: min ! =

!! !! !∈!

dengan syarat (d.s.) !!" !! ≥ !! , ! = 1,2, … , ! !∈!

!! ≥ 0, ! ∈ !


Karena masalah program linier melibatkan fungsi tujuan dan kendala yang berbentuk linier, bentuk umum dari masalah program linier dapat dinyatakan dalam matriks sebagai berikut: min ! = ! ! ! d.s. !! ≥ ! !≥! !! !! dengan c ! = [!! !! … !! ], x = ⋮ , ! = !!" !!

!! ! , dan b = ! . !×! ⋮ !!

Pada masalah program linier, suatu himpunan dari nilai-nilai !! yang memenuhi semua persamaan kendala disebut sebagai daerah layak (feasible), sedangkan solusi layak merupakan nilai-nilai dari !! yang memenuhi semua persamaan kendala. Solusi layak yang meminimumkan fungsi tujuan ! disebut sebagai solusi optimal dari masalah program linier tersebut. Solusi optimal dari masalah program linier terletak pada batas daerah layak, sehingga untuk penyelesaian masalah program linier kendala pertidaksamaan diubah menjadi persamaan. Hasil dari perubahan kendala pertidaksamaan menjadi persamaan disebut sebagai bentuk baku dari masalah program linier. Cara perubahan bentuk umum masalah program linier menjadi bentuk baku adalah sebagai berikut: 1. Apabila bentuk umum masalah program linier dengan kendala pertidaksamaan yang memiliki tanda ′ ≤ ′, pada kendala ke-! ditambahkan variabel slack !! di ruas kiri, dengan !! ≥ 0. Kemudian pada fungsi tujuan ditambahkan 0!! . 2. Apabila bentuk umum masalah program linier dengan kendala pertidaksamaan yang memiliki tanda ′ ≥ ′, pada kendala ke-! ditambahkan variabel surplus −!! di ruas kiri, dengan !! ≥ 0. Kemudian pada fungsi tujuan ditambahkan 0!! . Bentuk baku dari masalah program linier 2.4 − (2.6) adalah sebagai berikut: min ! = ! ! ! d.s. !! = ! ! ≥ 0.


Selanjutnya akan dijelaskan mengenai metode column generation yang dikutip dari (Desrosiers, J., Lubbecke, M.E., 2003). Pada masalah program linier, setiap variabel bersesuaian dengan kolom pada matriks koefisien kendala. Sehingga, masalah program linier dengan jumlah variabel yang banyak mengakibatkan kolom yang besar. Metode column generation merupakan salah satu metode yang efisien untuk digunakan dalam menyelesaikan masalah program linier dengan kolom yang besar. Ide dari metode column generation adalah menggunakan subhimpunan dari himpunan semua kolom yang ada untuk menyelesaikan masalah dan menambahkan kolom baru apabila kolom tersebut berpotensi memperbaiki nilai fungsi tujuan. Pada penyelesaian dari masalah program linier dengan menggunakan metode column generation, masalah dibagi menjadi master problem dan subproblem. Berikut adalah bentuk dari master problem pada masalah program linier dengan himpunan kolom !. min ! =

!! !! !∈!

d.s. a! !! ≥ b !∈!

!! ≥ 0, ! ∈ ! Penyelesaian dari master problem dilakukan dengan hanya menggunakan sejumlah kolom dari himpunan semua kolom yang ada yaitu !′ ⊆ !, dan masalah kemudian menjadi restricted master problem (RMP). Himpunan kolom yang dipilih mebentuk basis di ruang kolom matriks koefisien kendala pada masalah program linier tersebut. Sehingga, bentuk umum dari RMP adalah sebagai berikut: min ! =

!! !! !∈!!

d.s. a! !! ≥ b !∈!!

!! ≥ 0, ! ∈ !!


Pada setiap iterasi dari metode simpleks, dicari variabel nonbasis yang akan masuk ke basis, yaitu dengan mencari variabel dengan nilai reduced cost yang minimum. Hal tersebut juga dilakukan untuk mencari kolom yang dapat memperbaiki nilai dari fungsi tujuan. Masalah tersebut menjadi tujuan dari subproblem pada masalah program linier tersebut. Solusi dari subproblem merupakan kolom yang akan masuk pada RMP yang baru. Iterasi yang dilakukan dalam metode column generation adalah sebagai berikut: 1. Lakukan inisialisasi dengan melakukan dekomposisi masalah awal menjadi master problem dan subproblem. 2. Pilih sejumlah kolom untuk masuk kedalam RMP, kemudian selesaikan RMP. Dari penyelesaian RMP didapat solusi RMP !∗ dan nilai variabel dual y. 3. Selesaikan subproblem, apabila nilai reduced cost !! = !! −

! ! !!! y !!"

dari setiap kolom

tidak ada yang negatif, maka solusi optimal dari RMP merupakan solusi optimal dari keseluruhan masalah. 4. Apabila masih ada kolom dengan reduced cost yang negatif, tambahkan kolom tersebut kedalam RMP. 5. Ulangi langkah 2 sampai ditemukan solusi optimal untuk keseluruhan masalah. Metode Penelitian Metode yang digunakan dalam penelitian ini adalah studi literatur. Pembahasan Untuk memodelkan masalah optimisasi rute pengantaran barang, suatu VRPSTW dapat digambarkan dalam sebuah graf !(!, !) dengan mendefinisikan beberapa himpunan sebagai berikut: ! = {1,2, … , !} sebagai himpunan pelanggan, ! = ! ∪ {0} sebagai himpunan simpul pada graf, dimana setiap pelanggan direpresentasikan sebagai satu simpul dan depot direprentasikan sebagai simpul 0, !: himpunan busur layak yang menghubungkan dua buah simpul pada graf, dan !: himpunan kendaraan yang identik dan berkapasitas sama, dimana setiap kendaraan terletak di depot.


Pada graf tersebut, didefinisikan beberapa notasi yang akan menjadi bobot dari graf sebagai berikut. !!" : Biaya pengantaran barang dari simpul ! ke simpul !. Biaya pengantaran terdiri dari fixed utilization cost dan variable cost, yaitu sebagai berikut. •

Fixed utilization cost merupakan biaya penggunaan dan pemeliharaan kendaraan, nilai fixed utilization cost ditambahkan pada setiap nilai !!! , ! ∈ ! yaitu sebagai biaya dari setiap kendaraan yang berangkat dari depot.

•

Variable cost merupakan biaya perjalanan pengantaran barang dari simpul ! ke simpul !. Nilai dari variable cost bergantung pada jarak tiap simpul dan biaya yang dikeluarkan pada perjalanan, seperti biaya tol dan biaya bensin.

!!" : Lama waktu perjalanan dari simpul ! ke simpul ! dan lama waktu pelayanan pada simpul !. ! : Kapasitas kendaraan. !! : Permintaan dari pelanggan !. Didefinisikan juga pada simpul depot !! = 0. [!! , !! ]: time windows dari pelanggan !. Time windows ini merepresentasikan interval waktu mulai pelayanan yang mungkin pada pelanggan !. !! : biaya penalty keterlambatan per unit waktu. Nilai dari !!" dan !!" berasosiasi dengan setiap busur layak !" ∈ !, dan nilai !! dan [!! , !! ] terletak pada tiap simpul ! ∈ !. Pada VRPSTW, dipertimbangkan waktu mulai pelayanan yang berada di luar time windows dari suatu pelanggan. Apabila kendaraan datang lebih awal, kendaraan diperbolehkan menunggu sampai batas bawah time windows pelanggan. Tetapi apabila kendaraan datang terlambat, yaitu setelah batas dari pelayanan terhadap pelanggan tersebut, pelayanan masih dapat dilakukan sampai batas atas keterlambatan, dengan dikenakan biaya penalty. Oleh karena itu, ditentukan batas maksimal keterlambatan waktu mulai pelayanan pada tiap pelanggan. Batas maksimal tersebut merupakan maksimum dari selisih waktu pelayanan pada pelanggan ! terhadap batas atas dari time windows dari depot, yaitu !! − !!! , dan perbandingan antara biaya untuk melayani pelanggan ! dengan hanya menggunakan satu kendaraan yang khusus untuk melayani pelanggan tersebut dengan biaya penalty, yaitu !! +

!!! !!!! !!

. Sehingga batas keterlambatan pada

simpul ! didefinisikan sebagai berikut !!! = min !! − !!! , !! +

!!! + !!! !!


(Qureshi, A., 2010). Setiap busur pada graf dari VRPSTW disebut sebagai busur layak apabila pada busur tersebut berlaku pertidaksamaan !! + !!" ≤ !!! , yaitu apabila akan digunakan busur !", batas bawah waktu pelayanan di simpul ! ditambah dengan waktu perjalanan dari simpul ! ke simpul ! dan waktu pelayanan pada simpul ! masih dibawah batas keterlambatan waktu pelayanan dari simpul !. Hal ini menjamin bahwa apabila busur tersebut merupakan busur layak, pelayanan pada simpul ! masih mungkin untuk dilakukan. Hal-hal yang harus dipenuhi pada masalah optimisasi rute pengantaran barang adalah sebagai berikut. 1. Pada setiap rute pengantaran barang yang dilalui kendaraan, barang yang diangkut oleh kendaraan tidak boleh melebihi kapasitas yang ada. Rute pengantaran barang dengan jumlah barang yang diangkut melebihi kapasitas yang ada merupakan rute yang tidak layak. 2. Setiap pelanggan harus dilayani oleh satu kendaraan tepat satu kali dengan waktu awal mulai pelayanan ada dalam time windows yang diberi keringanan pada pelanggan tersebut, yaitu time windows dengan mempertimbangkan batas atas keterlambatan pada suatu pelanggan. 3. Setiap kendaraan memulai dan mengakhiri perjalanan di depot yaitu simpul 0, dan hanya melewati depot saat berangkat dan kembali. Waktu keberangkatan dan waktu kembali dari suatu kendaraan harus ada dalam time windows dari depot. Time windows dari depot merepresentasikan waktu operasional dari depot. Untuk memodelkan masalah optimisasi rute pengantaran barang sebagai VRPSTW, didefinisikan variabel keputusan yang digunakan bersesuaian dengan rute dari pengantaran barang yang mungkin dilewati, dimana nilai dari variabel tersebut menentukan apakah rute tersebut akan dipilih dalam solusi. Didefinisikan variabel keputusan pada VRPSTW adalah !!"# dan !!" dimana !!"# bernilai 1 apabila busur !" bagian dari solusi dan digunakan oleh kendaraan !, dan bernilai 0 apabila sebaliknya. Variabel !!" merupakan waktu mulai pelayanan pada simpul ! ∈ ! menggunakan kendaraan ! ∈ !. Biaya pengantaran barang bergantung dengan waktu awal mulai pelayanan pada suatu ′ pelanggan, sehingga didefinisikan !!"# yaitu biaya perjalanan yang mempertimbangkan


keterlambatan pelayanan, sehingga merupakan fungsi dari waktu awal mulai pelayanan, yaitu sebagai berikut: ′ !!"# =

!!" , jika !! ≤ !!" ≤ !! !!" + !! !!" − !! , jika !! ≤ !!" ≤ !!′

Sehingga, model matematis untuk VRPSTW secara lengkap adalah sebagai berikut ′ !!"# !!"#

min !∈! (!,!)∈!

Dengan syarat !!"# = 1 ∀! ∈ ! !∈!

!! !∈!

!!"# ≤ ! ∀! ∈ ! !∈!

!!!" = 1 ∀! ∈ ! !∈!

!!!! − !"#

!!!" = 0

∀ℎ ∈ !, ∀! ∈ !

!"#

!!!! = 1 ∀! ∈ ! !∈!

!!" + !!" − !!" ≤ 1 − !!"# ! !! ≤ !!" ≤ !!′

∀(!, !) ∈ !, ! ∈ !

∀! ∈ !, ∀! ∈ !

!!"# ∈ 0,1 , ∀!" ∈ !, ∀! ∈ ! Untuk mengaplikasikan metode column generation pada VRPSTW, bentuk masalah dari VRPSTW dibagi menjadi master problem dan subproblem. Master problem dalam VRPSTW adalah masalah awal, yaitu pencarian rute dengan biaya pengantaran minimum. Fungsi tujuan dari master problem memiliki bentuk yang sama dengan fungsi tujuan dari VRPSTW dan kendala yang digunakan hanya kendala pada persamaan pertama, yaitu setiap pelanggan harus dilayani tepat satu kali oleh satu kendaraan. Bentuk master problem dari VRPSTW kemudian disederhanakan dengan membuat suatu himpunan ! yang berisi rute layak yang dapat digunakan untuk pengantaran barang, dimana setiap rute terdiri dari busur-busur (!, !). Rute pengantaran barang pada VRPSTW berupa suatu


lintasan pada graf dari VRPSTW dimana lintasan tersebut dimulai dan berakhir di simpul 0 yaitu simpul depot. Didefinisikan variabel yang bersesuaian dengan satu rute yaitu variabel !! dimana variabel !! bernilai 1 apabila rute ! ∈ ! bagian dari solusi dan bernilai 0 apabila sebaliknya. Didefinisikan juga !! sebagai biaya pengantaran suatu kendaraan menggunakan rute ! dimana nilai dari !! terdiri dari biaya pengantaran barang dari tiap busur yang dilewati rute !. Kemudian didefinisikan juga !!" yang merepresentasikan berapa kali rute ! melewati pelanggan !. Bentuk master problem dari VRPSTW menjadi set partitioning problem, karena akan dicari sehimpunan rute dengan biaya minimum dimana sehimpunan rute yang dipilih tersebut dapat memenuhi permintaan setiap pelanggan. Sehingga formulasi master problem dari VRPSTW adalah sebagai berikut. min

!! !! !∈!

d.s. !!" !! = 1 , ∀! ∈ ! !∈!

!! ∈ 0,1 ∀! ∈ ! Penyelesaian dari set partitioning master problem tersebut lebih mudah dilakukan dengan merelaksasi bentuk dari set partitioning problem menjadi set covering problem, yaitu dengan cara kendala pada master problem diubah menjadi kendala dengan tanda ≥. Bentuk subproblem dari VRPSTW merupakan shortest path problem, dimana akan dicari rute dengan nilai reduced cost yang paling minimum. Subproblem dari VRPSTW juga harus mengatasi kendala pada model matematis dari VRPSTW. Kendala-kendala tersebut diantaranya adalah waktu mulai pelayanan pada simpul ! yang harus berada dalam time windows simpul !, jumlah permintaan dari pelanggan yang dikunjungi pada suatu rute harus kurang dari atau sama dengan kapasitas kendaraan, dan setiap rute dimulai dan berakhir pada simpul 0 atau depot. Kendala-kendala ini disebut sebagai resource constraint. Biaya penalty terhadap keterlambatan waktu mulai pelayanan juga diberlakukan di penyelesaian dari subproblem. Selain itu setiap pelanggan harus dikunjungi tepat satu kali oleh suatu rute, sehingga bentuk subproblem menjadi elementary shortest path problem with resource constraint (ESPPRCLAP).


Penyelesaian ESPPRCLAP dilakukan untuk mendapatkan kolom baru yang berpotensi untuk meminimumkan nilai dari fungsi tujuan. Kolom yang berpotensi untuk meminimumkan nilai dari fungsi tujuan merupakan kolom yang memiliki nilai reduced cost yang paling minimum. Apabila kolom dengan reduced cost yang paling minimum tersebut ditemukan, maka dibentuk suatu variabel yang bersesuaian dengan kolom tersebut kemudian variabel ditambahkan ke RMP yang kemudian dioptimisasi kembali. Penyelesaian dari ESPPRCLAP menggunakan graf dari VRPSTW dengan transformasi nilai !!" karena akan dicari rute (kolom) dengan nilai reduced cost yang paling minimum, sehingga nilai !!" pada setiap busur diganti dengan nilai reduced cost, yaitu: ′ = !′ − ! !!" ! !"

(Qureshi, A., 2010). Rute yang akan menjadi solusi dari ESPPRCLAP dapat digunakan oleh setiap kendaraan karena sifat kendaraan yang identik dan berkapasitas sama. Oleh karena itu, pada formulasi dari ESPPRCLAP setiap indeks ! yang merupakan indeks kendaraan dihilangkan. Sehingga model matematis ESPPRCLAP untuk VRPSTW adalah sebagai berikut. ′ ! !!" !"

min !"∈!

Dengan syarat !! !∈!

!!" ≤ ! !∈!

!!! = 1 !∈!

!!! − !"#

!!! = 0 ∀ℎ ∈ ! !"#

!!! = 1 !∈!

!! + !!" − !! ≤ 1 − !!" !

∀!" ∈ !

!! ≤ !! ≤ !!′ ∀! ∈ ! !!" ∈ 0,1 , ∀ !, ! ∈ ! Penyelesaian dari ESPPRCLAP dilakukan dengan labeling algorithm berdasarkan Irnich dan Villeneuve (2003). Setiap lintasan (rute) pada graf yang dimulai dari depot ke suatu simpul


direpresentasikan sebagai suatu label yang mengandung informasi mengenai lintasan tersebut. Penyelesaian ESPPRCLAP dengan labeling algorithm menggunakan graf awal dari VRPSTW, dengan simpul depot direpresentasikan sebagai dua simpul. Masing-masing simpul depot direpresentasikan sebagai simpul awal dan simpul akhir dari rute pengantaran barang oleh kendaraan. Simpul depot yang merupakan simpul akhir dari rute merupakan simpul ke-(! + 1), dimana bobot dari simpul tersebut sama dengan bobot dari simpul depot pada graf awal dari VRPSTW, dan busur yang menghubungkan simpul lain dengan simpul tersebut juga memiliki bobot yang sama dengan graf awal dari VRPSTW. Pada iterasi labeling algorithm, suatu label dipilih berdasarkan kriteria yang menentukan apakah lintasan yang direpresentasikan oleh label tersebut berpotensi meminimumkan fungsi tujuan. Kriteria tersebut disebut sebagai dominance rule dan apabila label tersebut merupakan label yang memiliki potensi, label tersebut diperpanjang ke sejumlah simpul lainnya pada graf sampai ditemukan rute yang merupakan rute dengan nilai reduced cost yang paling minimum. Suatu label yang berisi informasi mengenai suatu rute didefinisikan sebagai ! = !"# ! , ! ! , ! ! , ! ! , !"# ! , !"#$ ! , ! ! , !"#$% !". , dimana: !"# ! = simpul akhir dari rute yang direpresentasikan oleh label !, !(!) = waktu mulai pelayanan pada !"# ! , !(!) = jumlah permintaan sepanjang rute yang berakhir di !"# ! , !(!) = biaya sepanjang rute yang berakhir di !"# ! , !"#(!) = matriks baris yang jumlah elemennya sebanyak simpul pada graf !, dengan elemen ke-! bernilai 1 apabila simpul ! tidak dapat dikunjungi oleh rute, dan bernilai 0 sebaliknya, !"#$(!) = nomor label predecessor dari label !, !(!) = jumlah simpul yang tidak dapat dikunjungi oleh rute dari !"# ! . Label no. = nomor yang diberikan pada tiap label. Juga didefinisikan himpunan ! sebagai himpunan yang berisi label yang belum diproses, dan !(!) sebagai himpunan label yang memiliki potensi untuk memberikan rute dengan nilai reduced cost yang paling minimum. Langkah-langkah pada labeling algorithm untuk menyelesaikan ESPPRCLAP adalah sebagai berikut: 1. Lakukan inisialisasi yaitu dengan mendefinisikan ! = !! , dimana !! merupakan label merepresentasikan rute yang dimulai dari simpul 0, yaitu !! = {0,0,0,0, !!× ! , 0,1,1},


dimana !!× ! merupakan matriks baris dengan ! kolom, dengan entri dari kolom pertamanya adalah 1. Kemudian definisikan juga himpunan ! ! = ∅ untuk setiap ! ∈ !. 2. Pilih label !′ dengan nilai !(!′) yang paling minimum dari himpunan !, kemudian misalkan ! sebagai !"#(!! ). Himpunan ! ! = {! ∈ !|!"# ! = !. Kemudian himpunan ! ! dikeluarkan dari himpunan !, sehingga ! = !\!(!). 3. Dominance rule diterapkan kepada semua label yang ada pada himpunan !(!). Kemudian buat himpunan !! ! = !(!) ! yang dominan}. Elemen dari himpunan !! ! kemudian digabungkan kepada himpunan ! ! . 4. Lakukan path extension atau perpanjang lintasan untuk setiap label ! ∈ !! ! . Untuk setiap simpul ! yang bernilai 0 pada entri didalam !"#(!), perpanjang ! ke setiap simpul !. Apabila ! bernilai ! + 1, yaitu simpul tambahan yang sama seperti simpul depot, tambahkan ! kedalam ! ! + 1 . Hal ini berarti ! merupakan salah satu rute yang memiliki nilai reduced cost yang paling minimum. Tetapi apabila ! ≠ ! + 1, tambahkan ! ke himpunan !. 5. Ulangi langkah 3, 4 dan 5 sampai dipenuhi ! = ∅. Apabila tidak ada lagi entri dari himpunan !, maka tidak ada lagi label yang perlu diproses. 6. Lakukan tahap label filtration, yaitu dengan melihat label pada himpunan !(! + 1) yang memiliki nilai !(!) yang negatif. Rute yang direpresentasikan pada label yang didapat dari tahap label filtration tersebut merupakan solusi dari ESPPRCLAP. Berikutnya akan dijelaskan mengenai aturan-aturan pada dominance rule, path extension, dan label filtration. Dominance Rule Misalkan terdapat dua buah label yang berbeda !! dan !! dengan keduanya memiliki simpul akhir yang sama, yaitu !"# !! = !"# !! . Berikut adalah kriteria !! mendominasi !! ; ! !! ≤ ! !! ! !! ≤ ! !! ! !! ≤ ! !! ! !! ≤ ! !! Jika seluruh kriteria tersebut terpenuhi, maka !! dihapus dan tidak diperpanjang. Perpanjangan dari lintasan yang direpresentasikan oleh label !! sudah dipenuhi oleh label !!


yang memiliki nilai reduced cost lebih kecil, waktu mulai pelayanan yang lebih awal dan jumlah permintaan yang lebih sedikit. Path Extension Rute dengan simpul akhir ! diperpanjang ke setiap simpul lain pada ! yang mungkin dilalui dengan memperbarui nilai !(!), !(!), dan !(!). Apabila lintasan yang memiliki label dengan !"! !! = ! diperpanjang ke label dengan !"# !! = ! dengan menggunakan busur (!, !), maka berlaku aturan berikut ! !! = max ! !! + !!" , !!" ! !! = ! !! + !! ! !! =

! !! + !!" , jika !(!! ) ≤ !! ! !! + !!" + !! ! !! − !! , jika !(!! ) > !!

Matriks !"#(!! ) juga diperbarui dengan merubah entri ke ℎ yang menunjukkan apakah dari simpul ! pelayanan bisa dilanjutkan ke simpul ℎ. Entri k-ℎ tersebut ditentukan dengan melihat apakah kendala waktu mulai pelayanan dan kapasitas kendaraan terpenuhi, yaitu dengan pertidaksamaan berikut. ! !! + !!! < !!! ! !! + !! < ! Dari pertidaksamaan tersebut, entri ke-ℎ dari matriks !"#(!! ) akan bernilai 0 apabila simpul ℎ dapat dikunjungi dari simpul ! dan bernilai 1 apabila simpul ℎ tidak dapat dikunjungi dari simpul !. Label Filtration Rute yang merupakan solusi dari ESPPRCLAP adalah rute pada !(! + 1) yang memiliki nilai !(!) paling minimum dari semua label pada himpunan tersebut. Misalkan ! memiliki nilai !(!) paling minimum diantara label lainnya, berarti akan ditentukan rute ! ∈ ! dengan entri pertama dari rute tersebut adalah !"#(!). Kemudian, dicari label !′ yang memiliki nomor label yang sama dengan nilai dari !"#$ ! . Hal ini terus dilakukan sampai didapat rute yang dimulai dan berakhir di simpul depot. Kemudian dihitung biaya dari rute tersebut berdasarkan biaya pengantaran barang yang sebenarnya. Selanjutnya rute ! diasosiasikan dengan suatu variabel dan kolom ! yang memiliki nilai !!" = 1 untuk setiap pelanggan ! yang dikunjungi oleh rute !.


Berikut akan diberikan flowchart penyelesaian ESPPRCLAP dengan labeling algorithm.

Inisialisasi label !! , himpunan ! dan !!

ya ! = ∅ tidak STOP

Label Selection !!

Tambahkan !! pada !

Dominance Rule tidak !! dominan

Hapus !!

Tambahkan !! pada !!

Path Extension Tambahkan !! pada !!!!

!! → !!

tidak

ya ! = depot Gambar 1. Flowchart Labeling Algorithm


Berikut adalah flowchart penyelesaian VRPSTW dengan metode column generation.

Inisialisasi Rute: Satu kendaraan untuk melayani tiap pelanggan

Hitung nilai reduced cost STOP

Penyelesiaan ESPPRCLAP

ya

Solusi bilangan bulat

kolom dengan reduced cost negatif tidak Kolom baru pada RMP

Branching Pada variabel !!"

ya Optimisasi RMP Didapat: Solusi RMP, !!

tidak

ya Solusi bilangan bulat

ya

tidak Nilai !! tidak berubah

Gambar 2. Flowchart Metode Column Generation pada VRPSTW


Berikut ini akan diberikan contoh sederhana masalah optimisasi rute pengantaran barang yang akan diselesaikan dengan metode column generation. Misalkan terdapat suatu perusahaan distributor barang yang akan mengantarkan barang dengan sejumlah kendaraan ke 4 pelanggan yang berada pada lokasi yang berbeda-beda dan jumlah permintaan yang berbeda-beda. Setiap kendaraan yang mengantarkan barang memiliki kapasitas yang sama, dan kendaraan memulai dan mengakhiri perjalanannya di depot. Setiap pelanggan memiliki time windows waktu pelayanan yang berbeda-beda, dimana barang harus tiba pada pelanggan dalam interval waktu tersebut. Apabila kendaraan datang lebih awal dari time windows pada suatu pelanggan, maka kendaraan diperbolehkan menunggu sampai batas awal time windows, dan dikenakan biaya penalty pada kendaraan tersebut apabila datang terlambat. Tabel 1. Permintaan dan Time Windows Pelanggan

Pelanggan Permintaan 0 1 2 3 4 5 6 7

0 117 100 133 300 150 167 83

Waktu Awal 8:30 10:15 9:10 9:00 10:10 11:00 10:20 9:00

Waktu Akhir 20:00 15:00 16:45 16:30 16:00 15:20 16:15 17:00

Time Windows [0,690] [10 5,390] [40,495] [30,480] [100,450] [150,410] [110,465] [30,510]

Batas Keterlambatan 690 428 535 510 484 453 499 538

Kemudian diketahui waktu perjalanan dalam menit dan biaya perjalanan dalam 1.000 rupiah antar depot dan tiap pelanggan dan jarak antar pelanggan adalah sebagai berikut: Tabel 2. Waktu Perjalanan

i j 0 1 2 3 4 5 6 7

0 0 64 60 45 49 75 48 32

1 57 0 18 28 13 26 11 24

2 72 25 0 29 27 19 31 25

3 39 26 35 0 20 45 15 11

4 51 20 24 15 0 24 7 19

5 72 26 15 45 28 0 39 24

6 44 11 29 11 10 35 0 17

7 36 23 22 9 18 21 11 0


Tabel 3. Biaya Perjalanan

i j 0 1 2 3 4 5 6 7

0 0 35 34 22 26 40 28 17

1 29 0 9 14 8 15 6 11

2 37 12 0 17 14 9 18 12

3 19 13 19 0 10 21 7 6

4 26 10 12 7 0 13 3 10

5 40 12 7 23 14 0 20 13

6 23 6 15 6 4 19 0 9

7 18 13 11 3 9 11 6 0

Diketahui juga waktu pelayanan pada tiap pelanggan berdasarkan jumlah permintaan pelanggan dan lama waktu operasional pada depot adalah sebagai berikut: Tabel 4. Waktu Pelayanan

0 45

1 10

2 8

3 11

4 25

5 13

6 14

7 7

Sehingga didapat nilai !!" untuk setiap (!, !) ∈ ! adalah sebagai berikut: Tabel 5. Waktu Perjalanan dan Waktu Pelayanan

j

i 0 1 2 3 4 5 6 7

0 1 2 3 0 102 117 84 74 0 35 36 68 26 0 43 56 39 40 0 74 38 52 45 88 39 32 58 62 25 45 29 39 31 32 18

4 5 6 96 117 89 30 36 21 32 23 37 26 56 22 0 53 35 37 0 48 21 53 0 26 31 24

7 81 33 30 20 43 34 25 0

Dengan fixed utilization cost sebanyak 50, didapat nilai !!" untuk setiap (!, !) ∈ ! adalah sebagai berikut:


Tabel 6. Biaya Pengantaran

i j 0 0 0 1 35 2 34 3 22 4 26 5 40 6 28 7 17

1 79 0 9 14 8 15 6 11

2 87 12 0 17 14 9 18 12

3 69 13 19 0 10 21 7 6

4 76 10 12 7 0 13 3 10

5 90 12 7 23 14 0 20 13

6 73 6 15 6 4 19 0 9

7 68 13 11 3 9 11 6 0

Dengan menggunakan metode column generation, tahap inisialisasi yang dilakukan adalah pengantaran barang dengan menggunaan kendaraan sebanyak jumlah pelanggan yaitu 7 kendaraan dengan biaya pengantaran 615. Setelah dilakukan optimisasi dengan beberapa iterasi, didapat solusi dari permasalahan adalah menggunakan 4 kendaraan dengan rute sebagai berikut. Tabel 7. Rute Optimal

Kendaraan

Rute

1

0-4-0

2

0-3-7-0

3

0-6-1-0

4

0-2-6-0

dengan biaya minimum adalah 439. Jadi, dengan dilakukannya optimisasi, biaya pengantaran berkurang dari 615 menjadi 439, dan jumlah kendaraan yang digunakan untuk mengantarkan barang berkurang dari 7 kendaraan menjadi 4 kendaraan. Kesimpulan Berdasarkan pembahasan mengenai optimisasi rute pengantaran barang diperoleh kesimpulan bahwa masalah optimisasi rute pengantaran barang dapat dimodelkan menjadi Vehicle Routing Problem with Soft Time Windows (VRPSTW) dan penyelesaiannya dapat dilakukan dengan mengaplikasikan metode column generation. Penyelesaian VRPSTW dengan


metode column generation cukup efisien karena tidak diperlukan untuk mengetahui semua rute yang mungkin dilewati. Berdasarkan contoh sederhana yang diberikan sebelumnya dapat dilihat bahwa pada tahap inisialisasi sebelum dilakukan optimisasi rute, pengantaran barang dilakukan dengan menggunakan 7 kendaraan dan biaya pengantaran yang dikeluarkan adalah 615. Sedangkan setelah dilakukan optimisiasi rute dengan metode column generation, pengantaran barang dapat dilakukan dengan 4 kendaraan dan biaya pengantaran yang dikeluarkan adalah 439. Sehingga, dengan dilakukannya optimisasi rute pengantaran barang, biaya pengantaran barang yang dikeluarkan oleh pihak penyedia layanan logistik lebih minimum dibandingkan dengan biaya yang dikeluarkan sebelum dilakukan optimisasi. Selain itu, jumlah kendaraan yang digunakan untuk mengantarkan barang juga berkurang sehingga dapat mengurangi dampak kendaraan besar bagi lingkungan dan masyarakat. Daftar Referensi [1] Desrosiers, J., Lubbecke, M.E. (2003). A Primer in Column Generation. Technische Universitat Berlin. 2003/48. [2] Lubbecke, M.E., Desrosiers, J. (2002). Selected Topics in Column Generation. Les Cahiers du GERAD G2001-64, HEC Montreal. [3] Qureshi, A.G., Taniguchi, E., Yamada, T. (2009). An Exact Approach for Vehicle Routing and Scheduling Problems with Soft Time Windows. Transportation Research Part E 45 (2009) 960-977. [4] Qureshi, A.G., Taniguchi, E., Yamada, T. (2010). Exact Solution for Vehicle Routing Problem with semi Soft Time Windows and its Application. Procedia Social and Behavioral Sciences 2 (2010) 5931-594. [5] Taniguchi, E. (2012). Concept and best practices in city logistics. Presented at International Transport Forum, Leipzig. [6] Taniguchi, E., Thompson, R.G. (2008). Innovations in City Logistics. New York: Nova Science Publisher. [7] Wu, N., dan Coppins, R. (1981). Linear Programming and Extensions. McGraw-Hill Series in Industrial Engineering and Management Science.


Pendekatan Metode Column Generation pada Vehicle Routing Problem dengan Soft Time Windows

Recommend Documents