LINEARISASI KOMPAK UNTUK MENYELESAIKAN MASALAH RUTE KENDARAAN

LINEARISASI KOMPAK UNTUK MENYELESAIKAN MASALAH RUTE KENDARAAN

TESIS

Oleh

YUSNAR 067021032/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008

Yusnar : Linearisasi Kompak Untuk Menyelesaikan Masalah Rute Kendaraan, 2008 USU e-Repository © 2008

LINEARISASI KOMPAK UNTUK MENYELESAIKAN MASALAH RUTE KENDARAAN

TESIS

Untuk Memperoleh Gelar Magister Sains Dalam Program Studi Magister Matematika Pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh

YUSNAR 067021032/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008


Judul Tesis Nama Mahasiswa Nomor Pokok Program Studi

: LINEARISASI KOMPAK UNTUK MENYELESAIKAN MASALAH RUTE KENDARAAN : Yusnar : 067021032 : Matematika

Menyetujui, Komisi Pembimbing

(Drs. Opim Salim S, MIkom, PhD) Ketua

( Prof. Dr. Herman Mawengkang) Anggota

Ketua Program Studi

Direktur

(Prof. Dr. Herman Mawengkang)

(Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)

Tanggal lulus: 6 Juni 2008


Telah diuji pada Tanggal 6 Juni 2008

PANITIA PENGUJI TESIS Ketua

:

Drs. Opim Salim S, MIkom,PhD

Anggota

:

Prof. Dr. Herman Mawengkang Drs. Marihat Situmorang, M.Kom Dr. Tulus, M.Si


ABSTRAK Sebagian besar masalah pemograman integer, khususnya dalam masalah rute kendaraan adalah masalah pemogram mempunyai formulasi yang tak-linier, baik pada fungsi sasaran maupun fungsi kendalanya. Penyelesaian masalah yang taklinier dapat dilakukan memakai metode optimasi tak-linier atau memakai memakai metode yang khusus dipakai untuk menyelesaikan optimasi linier, tetapi formulasinya harus disederhanakan sehingga menjadi linier. Linearisasi kompak ternyata dapat digunakan untuk menyederhanakan masalah optimasi tak-linier menjadi linier. Kata kunci: pemograman integer, masalah rute kendaraan, linearisasi kompak

i Yusnar : Linearisasi Kompak Untuk Menyelesaikan Masalah Rute Kendaraan, 2008 USU e-Repository © 2008

ABSTRACT Most formulation of objective function and constraints on the integer programming problems, especially in vehicle routing problem, are non-linear. The solution of these non-linear problems can be done using non-linear methods or linear methods with some modification in its formulation. Compact linearization can be used to reduce the non-linear problems become linear problems. Keyword: integer programming, vehicle routing problem, compact linearization

ii Yusnar : Linearisasi Kompak Untuk Menyelesaikan Masalah Rute Kendaraan, 2008 USU e-Repository © 2008

KATA PENGANTAR Puji dan syukur penulis panjatkan ke hadirat Allah SWT, karena berkat rahmat dan karunia-Nya penulis dapat menyelesaikan tesis ini dengan judul ”Compact Linearization (CL) untuk menyelesaikan Vehicle Routing Problem (VRP)”. Tesis ini dibuat dalam rangka memenuhi syarat untuk menyelesaikan kuliah Program Studi Magister Matematika SPs Universitas Sumatera Utara di Medan . Pada kesempatan ini perkenankanlah penulis menyampaikan rasa terima kasih yang tak terhingga terutama kepada : Bappedasu, atas bantuan dana pendidikan yang diberikan selama penulis mengikuti pendidikan Program Studi Magister Matematika SPs Universitas Sumatera Utara. Istri tercinta Aida Fitriani, S.Pd , kedua orang tua kami,dan anak kami M. Rusyda Dzakwan atas semua bantuan, perhatian dan dukungannya. Prof. DR. Herman Mawengkang selaku Ketua Prodi sekaligus Pembimbing II, yang telah membimbing dengan sabar serta telah memberikan jurnal-jurnal untuk menambah bahan bacaan pada penulis. Drs. Opim Salim Sitompul MIkom, PhD selaku Pembimbing I, yang telah memberikan masukan demi kesempurnaan tesis ini. Seluruh Staf Pengajar Pada Program Studi Magister Matematika SPs Universitas Sumatera Utara yang telah memberikan ilmunya lewat perkuliahan, sehingga dapat membantu penulis dalam memahami text book dan jurnal jurnal.

iii Yusnar : Linearisasi Kompak Untuk Menyelesaikan Masalah Rute Kendaraan, 2008 USU e-Repository © 2008

Drs. Amin Sirait selaku Kepala SMA Muhammadiyah 1 Medan yang telah memberikan kesempatan kepada penulis untuk mengikuti pendidikan Program Studi Magister Matematika SPs di USU. Teman-teman sesama mahasiswa yang selalu memberikan semangat dan dukungan kepada penulis. Serta semua pihak yang tidak bisa penulis sebutkan yang telah membantu penyelesaian makalah ini. Penulis menyadari bahwa masih banyak kekurangan pada tesis ini, oleh karena itu penulis mengaharapkan kritik dan saran yang bersifat membangun untuk memperbaiki tesis ini di masa yang akan datang. Semoga tesis ini bisa memberikan manfaat terutama bagi penulis dan bagi pembaca pada umumnya. Akhirnya kepada Allah jugalah semuanya kita kembalikan.

Medan, Penulis,

Yusnar

iv Yusnar : Linearisasi Kompak Untuk Menyelesaikan Masalah Rute Kendaraan, 2008 USU e-Repository © 2008

Juni 2008

RIWAYAT HIDUP Yusnar dilahirkan di Firdaus pada tanggal 15 Juni 1979 dan merupakan anak keempat dari delapan bersaudara dari ayah Amiruddin dan ibu Kholidah. Menamat Sekolah Dasar (SD) Negeri 102019 di Firdaus pada tahun 1992. Sekolah Menengah Pertama (SMP) Negeri 1 Sei. Rampah pada tahun 1995 dan Sekolah Menengah Atas (SMA) Negeri 1 Sei. Rampah jurusan Ilmu Pengetahuan Alam (IPA) pada tahun 1998. Pada tahun 2002 memperoleh Gelar Sarjana Pendidikan dari Universitas Muhammadiyah Sumatera Utara (UMSU) Fakultas Keguruan dan Ilmu Pendidikan (FKIP) Program Studi Matematika. Penulis mengajar di SMA Muhammadiyah 1 Medan dari tahun 2000 sampai sekarang dan di Program Studi Matematika FKIP UMSU dari tahun 2007 sampai sekarang. Pada tahun 2006 mengikuti pendidikan Program Studi Magister Matematika di Sekolah Pasca Sarjana Universitas Sumatera Utara (USU) Selanjutnya pada akhir tahun 2006 menikah dan dikaruniai seorang anak pada awal tahun 2008. Sampai sekarang tinggal di Jl. Utama No.115 AA Medan. Demikian riwayat hidup ini penulis perbuat dengan sebenar-benarnya.

v Yusnar : Linearisasi Kompak Untuk Menyelesaikan Masalah Rute Kendaraan, 2008 USU e-Repository © 2008

DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .

iii

RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .

v

DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .

1

1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . .

2

1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .

2

1.4 Konstribusi . . . . . . . . . . . . . . . . . . . . . . . .

2

1.5 Metodologi Penelitian . . . . . . . . . . . . . . . . . . .

2

BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . .

4

BAB 3 LANDASAN TEORI . . . . . . . . . . . . . . . . . . . . .

10

3.1 Pemrograman Integer . . . . . . . . . . . . . . . . . . .

10

3.2 Vehicle Routing Problem . . . . . . . . . . . . . . . . .

12

3.2.1 Pengertian VRP . . . . . . . . . . . . . . . . . .

12

3.2.2 Formulasi VRP . . . . . . . . . . . . . . . . . . .

14

3.3 Linearisasi . . . . . . . . . . . . . . . . . . . . . . . .

16

BAB 4 APLIKASI LINEARISASI . . . . . . . . . . . . . . . . . .

18

4.1 Linearisasi Biasa . . . . . . . . . . . . . . . . . . . . .

18

vi Yusnar : Linearisasi Kompak Untuk Menyelesaikan Masalah Rute Kendaraan, 2008 USU e-Repository © 2008

4.2 Linearisasi Compact . . . . . . . . . . . . . . . . . . . .

19

BAB 5 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . .

22

5.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . .

22

DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .

23

vii Yusnar : Linearisasi Kompak Untuk Menyelesaikan Masalah Rute Kendaraan, 2008 USU e-Repository © 2008

BAB 1 PENDAHULUAN

1.1 Latar Belakang Permasalahan optimasi merupakan bagian dari permasalahan kehidupan manusia sehari-hari. Dalam usaha untuk memenuhi kebutuhannya, manusia membutuhkan optimasi dalam pekerjaannya. Optimasi (Bhavikatti, 2003) adalah meminimumkan biaya pengerjaan serta memaksimumkan pendapatan pengerjaan. Akan tetapi dalam pengerjaannya, manusia selalu menghadapi batasan-batasan dalam usaha mengoptimasi. Salah satu contoh permasalahan yang memberi batasan pada manusia untuk mengoptimasi adalah masalah rute kendaraan atau Vehicle Routing Problem (VRP), karena VRP (Applegate et al., 2001) adalah sebuah problem optimalisasi kombinatorial yang bertujuan untuk melayani beberapa pelanggan dengan sejumlah kendaraan. Banyak metode yang dapat dipakai untuk mencari solusi yang baik, tetapi untuk lingkup yang lebih besar, fungsi biaya untuk mencari nilai minimum global sangatlah kompleks. Dalam beberapa sektor pasar, transportasi sangat berpengaruh pada harga barang yang ditetapkan. VRP (Toth & Vigo, 2001) merupakan sebuah masalah pemrograman integer yang masuk kategori masalah polinomial sukar, yang berarti usaha komputasi yang digunakan akan semakin sulit dan banyak, seiring dengan meningkatnya ruang lingkup masalah yang terjadi. Untuk masalah-masalah seperti ini, biasanya yang dicari adalah aproksimasi solusi yang terdekat, karena solusi tersebut dapat

1 Yusnar : Linearisasi Kompak Untuk Menyelesaikan Masalah Rute Kendaraan, 2008 USU e-Repository © 2008

2 dicari dengan cepat dan cukup akurat. Dan biasanya masalah ini juga terselesaikan dengan menggunakan berbagai variasi dari metode heuristik yang memerlukan sedikit pengamatan pada ruang lingkup masalah (Russell, 1995).

1.2 Perumusan Masalah Dari latar belakang diatas terlihat bahwa formulasi VRP merupakan program integer tak linear yang dikategorikan masalah polinomial sukar. Salah satu teknik untuk mengatasi ketidaklinearan adalah dengan linearisasi. Namun linearisasi mengakibatkan penambahan variabel dan kendala, sehingga perlu diajukan suatu bentuk linearisasi kompak dengan variabel dan kendala seminimal mungkin.

1.3 Tujuan Penelitian Adapun tujuan dari penelitian ini adalah untuk memperoleh suatu bentuk linearisasi yang kompak pada model VRP, dalam rangka penyederhanaan proses penyelesaian VRP.

1.4 Konstribusi Konstribusi yang peneliti berikan adalah memberikan suatu teknik linearisasi untuk menyelesaikan VRP.

1.5 Metodologi Penelitian Penelitian ini adalah bersifat literature. Sedangkan prosedur yang dilakukan adalah sebagai berikut :


3 1. Menjelaskan pemogramman integer 2. Menjelaskan tentang model dari VRP 3. Menjelaskan linearisasi 4. Melakukan teknik linearisasi yang kompak pada VRP.


BAB 2 TINJAUAN PUSTAKA

Beberapa rangkuman penjelasan yang berhubungan dengan VRP yang peroleh dari para peneliti sebelumnya, antara lain:

1. Capasitated VRP (CVRP) CVRP (Fukasawa, et al.,2004; Lysgaard, et al., 2004) adalah sebuah VRP dimana diberikan sejumlah kendaraan dengan kapasitas tersendiri yang harus melayani sejumlah permintaan pelanggan yang telah diketahui untuk satu komoditas dari sebuah depot dengan biaya transit minimum. Oleh karena itu, CVRP sama seperti VRP dengan faktor tambahan yaitu tiap kendaraan punya kapasitas tersendiri untuk satu komoditas.CVRP dijabarkan sebagai berikut : (a) Tujuan: Meminimalisasi jumlah kendaraan dan total waktu perjalanan, dan total permintaan barang untuk tiap rute tidak boleh melebihi kapasitas kendaraan yang melewati rute tersebut. (b) Kelayakan: Solusi dikatakan ’layak’, jika jumlah total barang yang diatur untuk tiap rute tidak melebihi kapasitas kendaraan yang melewati rute tersebut (c) Perhitungan: Misalkan Q melambangkan kapasitas sebuah kendaraan. Secara matematis, solusi untuk CVRP sama dengan VRP, tapi dengan batasan tambahan total permintaan pelanggan pada rute Ri tidak m P di ≤ Q. boleh melebihi kapasitas kendaraan Q, atau i=1


5 2. VRP dengan Tingkat Waktu (Time Windows , VRPTW) VRPTW (Thangiah,1993; Lau et al., 2003) merupakan permasalahan yang jauh lebih kompleks dari permasalahan lain yang dapat diselesaikan dengan kompleksitas polinomial. Kompleksitas disini disebabkan karena jumlah solusi yang mungkin untuk permasalahan ini meningkat sangat drastis seiring dengan pertambahan ukuran permasalahan. VRPTW memiliki batas tambahan (Lee et al.,2003), yaitu sebuah jangka waktu yang berhubungan dengan setiap pelanggan v ∈ V , yang mendefinisikan sebuah jangka waktu [ev , lv ] dimana pelanggan harus disuplai. Interval waktu [e0, l0] di gudang disebut sebagai batas penjadwalan. VRPTW dijabarkan sebagai berikut : (a) Tujuan: Meminimalisasi jumlah kendaraan dan total waktu perjalanan dan waktu menunggu yang dibutuhkan untuk menyuplai semua pelanggan pada jam-jam tertentu (Garcia et al.,1994). (b) Kelayakan: Solusi menjadi tidak layak’ jika kiriman pada pelanggan sampai setelah batas atas dari interval, jika kendaraan sampai sebelum batas bawah interval ,maka waktu menunggu pada rute tersebut menjadi bertambah. Setiap rute harus start dan berhenti dalam jangka waktu yang berkaitan dengan gudang (Solomon, 1995; Russel, 1995). 3. Multiple Depot VRP (MDVRP) Sebuah perusahaan mungkin memiliki lebih dari satu depot. Jika pelangganpelanggannya (Hjorring, 1995) terkumpul di sekitar depot-depot yang ada, maka masalah pendistribusiannya harus dimodelkan menjadi sebuah kumpulan dari VRP-VRP yang independent (bebas). Namun, jika pelanggan dan depot-depot yang ada saling bercampur aduk (tidak terkumpul secara


6 teratur, bisa ada satu pelanggan dilayani lebih dari satu depot atau sebaliknya) maka masalahnya menjadi Multiple Depot Vehicle Routing Problem atau MDVRP. Sebuah MDVRP membutuhkan pengaturan para pelanggan ke depot-depot yang ada. Tiap kendaraan pergi dari satu depot, melayani pelanggan-pelanggan yang sudah ditentukan akan dilayani oleh tersebut, dan kembali lagi ke depot tersebut. Tujuan utama dari MDVRP adalah untuk melayani semua pelanggan sementara jumlah kendaraan dan jarak perjalanan diminimalisasi. Penjabaran MDVRP sebagai berikut: (a) Tujuan: Meminimalisasi jumlah kendaraan dan total waktu perjalanan dan total permintaan barang yang harus dilakukan dari beberapa depot. (b) Kelayakan: Solusi dianggap layak jika tiap rute memenuhi batasan standar VRP dan keluar-masuk kendaraan terjadi di gudang yang sama. 4. VRP dengan Pick-Up dan Delivering (VRPPD) Righini (2000) menggambarkan VRP dengan Pick-up (mengangkut) dan Delivering (pengiriman) adalah sebuah VRP dimana ada peluang kejadian pelanggan mengembalikan barang yang sudah diantarkan. Dalam VRPPD yang perlu diperhatikan bahwa barang yang dikembalikan dapat dimasukkan ke dalam kendaraan pengantar. Batasan ini membuat perencanaan pengantaran menjadi lebih sulit dan bisa berakibat pada penyalahgunaan kapasitas kendaraan, memperbesar jarak perjalanan atau kendaraan yang diperlukan lebih dari yang seharusnya. Maka, dalam situasi seperti ini biasanya harus dipikirkan batasan keadaan dimana semua permintaan pengantaran dimulai dari depot dan semua permintaan pengambilan akan dibawa kembali ke


7 depot, sehingga tidak ada pertukaran barang antar pelanggan. Alternatif lainnya adalah dengan memperbesar batasan bahwa semua pelanggan hanya dikunjungi satu kali. Simplifikasi yang biasa terjadi lainnya adalah dengan memikirkan bahwa tiap kendaraan harus mengantarkan semua barang sebelum mengambil kembali barang dari pelanggan.VRPPD dapat dijabarkan sebagai berikut : (a) Tujuan: Meminimalisasi jumlah kendaraan dan total waktu perjalanan dengan batasan bahwa kendaraan yang digunakan harus punya kapasitas yang cukup untuk mengantarkan barang ke pelanggan dan pengembalian barang ke gudang (b) Kelayakan: Solusi dibilang layak jika total kuantitas barang yang ditentukan untuk tiap rute tidak melebihi kapasitas kendaraan yang melalui rute tersebut dan kendaraannya harus punya kapasitas yang ckup untuk mengambil barang dari pelanggan. 5. Pengiriman Terpisah atau Split Delivery VRP (SDVRP) SDVRP (Archetti et al., 2001) adalah perluasan VRP jika tiap pelanggan dapat dilayani dengan kendaraan yang berbeda andaikan biayanya dapat berkurang. Perluasan ini perlu dilakukan jika jumlah permintaan pelanggan sama besar dengan kapasitas dari kendaraan. SDVRP dapat dijabarkan sebagai berikut: (a) Tujuan: Meminimalisasi jumlah kendaraan dan total waktu perjalanan untuk pelayanan. (b) Kelayakan: Solusi dianggap layak jika tiap rute memenuhi batasan standar VRP Solusi dianggap layak jika memenuhi batasan standar


8 VRP ditambah dengan tiap pelangan bisa dilayani oleh lebih dari satu kendaraan 6. Stochastic VRP (SVRP) Menurut Hvattum et al. (2006) Stochastic Vehicle Routing Problem (SVRP) adalah variasi VRP yang terjadi jika faktor sampingan yang muncul bersifat acak. Dalam SVRP, untuk bisa mendapatkan solusi, masalah harus dibagi menjadi dua tahap. Solusi pertama (Laporte & Louveaux, 1998) ditentukan sebelum variabel random diketahui. Pada tahap kedua, pengoreksian dilakukan jika nilai dari variabel random sudah diketahui. SVRP dapat dijabarkan sebagai berikut: (a) Tujuan: Meminimalisasi jumlah kendaraan dan total waktu perjalanan untuk melayani pelanggan dengan nilai random untuk tiap pengantaran (pelanggan, permintaan, waktu) item Kelayakan: Jika data-data yang ada bersifat acak, tidak perlu lagi memenuhi batasan-batasan yang ada untuk semua realisasi variabel random. Maka pencari solusi memerlukan antara tingkat kepuasan batasan tertentu dengan peluang yang diberikan, atau pengoreksian bila ada batasan yang dilanggar. 7. Periodic VRP (PVRP) PVRP (Angelelli & Speranza, 2002) merupakan VRP digeneralisasi dengan memperluas rentang perencanaan pengiriman menjadi M hari, dari semula hanya dalam rentang sehari. PVRP dapat dijabarkan sebagai berikut : (a) Tujuan meminimalisasi jumlah kendaraan dan total waktu perjalanan untuk melayani tiap pelanggan.


9 (b) Kelayakan: Solusi dianggap layak jika memenuhi batasan standar VRP. Ditambah dengan keadaan bahwa sebuah kendaraan tidak boleh kembali ke depot pada satu hari yang sama. Dalam M hari, tiap pelanggan harus dikunjungi minimal sekali.


BAB 3 LANDASAN TEORI

3.1 Pemrograman Integer Pemrograman Integer (IP ) adalah persoalan pemrograman, dimana pemecahan optimalnya (RAO, 1997) merupakan bilangan bulat. Dengan kata lain dari antara berbagai bilangan bulat, harus dicari nilai-nilai variabel yang fisibel dan membuat fungsi tujuan maksimum. Karakteristik permasalahan IP terdiri dari : a. Semua permasalahan IP memiliki tujuan untuk memaksimumkan atau meminimumkan sesuatu. b. Permasalahan IP memiliki kendala yang membatasi tingkatan pencapaian tujuan. c. Adanya beberapa alternatif tindakan yang bisa dipilih. Sebagai contoh, kalau suatu perusahaan menghasilkan tiga produk maka alternatif solusinya adalah apakah ia akan mengalokasikan semua sumber daya untuk satu produk, membagi rata sumber daya untuk ketiga produk, atau mendistribusikannya dengan cara yang lainnya. d. Fungsi tujuan dan kendala dalam permasalahan IP diekspresikan dalam bentuk persamaan atau pertidaksamaan linier Sedangkan asumsi dasar dari IP itu sendiri adalah : a. Koefisien dalam fungsi tujuan dan fungsi kendala dapat diketahui dengan pasti dan tidak berubah. 10 Yusnar : Linearisasi Kompak Untuk Menyelesaikan Masalah Rute Kendaraan, 2008 USU e-Repository © 2008

11 b. Semua koefisien dalam formulasi, tujuan dan kendala, merupakan koefisien yang bersifat variabel terhadap besarnya variabel keputusan c. Total semua aktivitas sama dengan jumlah setiap aktivitas individual d. Solusi permasalahan IP harus dalam bilangan bulat (integer) e. Variabel keputusan tidak boleh bernilai negative

Contohnya didalam suatu persoalan perkantoran (Luenberger, 1994), dimana akan dibentuk suatu panitia kerja yang anggota-anggotanya dapat bekerjasama dengan baik sekali. Misalnya ada calon sebanyak n orang. Kalau ada 2 orang calon yang tidak bisa bekerjasama, keduanya tidak akan dipakai. Variabel xi diperuntukkan bagi calon i    1, kalau calon tidak dipakai xi =   0, kalau calon dipakai Variabel xi hanya boleh mengambil salah satu dari nilai tersebut yaitu 0 n P xi = atau 1. Persoalan untuk mencapai suatu panitia yang paling harmonis i=1

minimum, dengan pembatasan xi + xj ≥ 1. untuk semua pasangan calon i dan j yang tidak bisa kerjasama dengan baik. Pengaruh dari setiap pembatasan selalu terjadi bahwa paling tidak satu calon dari pasangan i dan j harus keluar (paling tidak xi > 0 atau xj > 0). Jelas, mudah dimengerti bahwa kalau persoalan bisa dipecahkan sebagai persoalan IP , variabel-variabel yang akan membuat fungsi tujuan menjadi minimum bukan saja mempunyai nilai bilangan bulat, akan tetapi juga terdiri dari 0 (terpilih) atau 1 (tidak terpilih).


12 Contoh lain dari permasalahan IP adalah VRP, karena jawaban tidak boleh pecahan, (berapa banyaknya kota yang harus dikunjungi, berapa banyaknya tugas yang harus diselesaikan, dsb).

3.2 Vehicle Routing Problem 3.2.1 Pengertian VRP VRP (Schrijver & Alexander, 2007) adalah sebuah cakupan masalah yang di dalamnya ada sebuah problem dimana ada sejumlah rute untuk sejumlah kendaraan yang berada pada satu atau lebih depot (gudang) yang harus ditentukan jumlahnya agar tersebar secara geografis supaya bisa melayani konsumenkonsumen yang tersebar. Tujuan dari VRP adalah mengantarkan barang pada konsumen dengan biaya minimum melalui rute-rute kendaraan yang keluar-masuk gudang Ralphsy et al. (2003) menggambarkan bahwa permasalahan VRP sebagai suatu graph tak berarah G = (V, E), dengan sebuah kumpulan pelanggan V = {0, 1, · · · , n}, dan sebuah kumpulan jalur E. Pelanggan 0 adalah sebuah depot (gudang atau terminal) dengan sejumlah kendaraan yang mempunyai kapasitas yang sama, Q. Tiap tiik pelanggan i > 0, memiliki suatu demand non negative (permintaan tidak negative) qi , dan tiap edge [i, j] memiliki biaya non negative cij = cji . Permasalahan VRP bertujuan untuk menentukan suatu set trips kendaraan dengan total biaya minimal, dimana tiap perjalanan berawal dan berakhir di depot. Tiap klien dikunjungi tepat satu kali, total demand yang dibawa oleh tiap kendaraan tidak melebihi kapasitas kendaraan Q, dan biaya dari tiap perjalanan tidak melebihi batas L yang telah ditentukan.


13 VRP (Chepuri & Mello, 2005 ).adalah sebuah problem kombinatorial yang terletak pada irisan dua masalah yang sudah dikenal, yaitu:

a. Masalah Perjalanan Pedagang (Travelling Salesman Problem, TSP) Jika kapasitas dari kendaraan C tak terhingga, maka kita bisa mendapatkan sebuah keadaan untuk Multiple (berbagai) Travelling Salesman Problem (MTSP). Sebuah keadaan MTSP dapat diubah menjadi keadaan TSP yang ekuivalen dengan cara menyambungkan salinan dari node 0 dari graf k − 1 (dengan k adalah jumlah rute) dan ujung-ujung perpotongannya (tidak ada sisi diantara titik-titik depot sejumlah k). b. Masalah Pengaturan Lokasi (Bin Packing Problem, BPP) Pertanyaannya adalah apakah ada solusi yang mungkin untuk sebuah keadaan VRP dimisalkan keadaan itu adalah sebuah keadaan BPP. Penyelesaian dari masalah ini sama secara konseptual dengan pemodelan VRP dimana semua biaya pada sisi dianggap nol, sehingga semua solusi memiliki biaya yang sama.

Sebuah solusi yang tepat untuk masalah secara keseluruhan adalah sebuah graf TSP (dalam graf yang sudah diperluas) yang juga memenuhi batasan pemuatan (contoh, permintaan total untuk k segmen untuk beberapa depot yang tergabung tidak boleh melebihi C atau kapasitas total). Dikarenakan penggunaan antara dua model yang menjadi dasar, VRP dapat menjadi sangat sulit untuk diselesaikan secara praktikal.


14 3.2.2 Formulasi VRP Burrows (1998) mengandaikan n adalah jumlah pelanggan yang akan dilayani dan xi adalah waktu penjemputan aktual pelanggan ke-i, yi adalah waktu pengantaran aktualnya dan τi adalah waktu pengantaran yang diinginkan. Karena VRP sebagai suatu graph maka dapat dinyatakan dalam bentuk matrik waktu perjalanan n×n, berarti semua waktu perjalanan diasumsikan independent/bebas dari waktu eksak harian dengan masa waktu yang sedang bekerja, dan yang mempunyai entri (elemen) pada baris ke-i dan kolom ke- j. Andaikan : d00 (i, j) = waktu perjalanan minimal dari sumber pelanggan i ke sumber pelanggan j d01 (i, j) = waktu perjalanan minimal dari sumber pelanggan i ke tujuan pelanggan j. d10 (i, j) = waktu perjalanan minimal dari tujuan pelanggan i ke sumber pelanggan j. d11 (i, j) = waktu perjalanan minimal dari tujuan pelanggan i ke tujuan pelanggan j. Diasumsikan bahwa: d01(i, j) = d10 (j, i), d00(i, j) = d00 (j, i), d11(i, j) = d11 (j, i), d01 (i, i) > 0, d10 (i, i) > 0 Andaikan ρi kemungkinan keterlambatan waktu penjemputan terakhir pelanggan ke i, maka diperoleh persamaan : ρi = τi d01 (i, i)


(3.1)

15 Andaikan C melambangkan kapasitas kendaraan, A dan B koefisien fungsi tujuan deviasi waktu pengantaran dengan kelebihan waktu perjalanan. Andaikan 2 himpunan variabel keputusan 0 1 didefinisikan berikut : Jika,    1, penjemputan pelanggan i mendahului pengantaran pelanggan j    uij = dalam urutan rute      0, untuk lainnya    1, jika pengantaran pelanggan i mendahului penjemputan pelanggan j    vij = dalam urutan rute      0, untuk lainnya    1, jika pengantaran pelanggan i mendahului pelanggan j dalam urutan rute wij =   0, untuk lainnya Untuk i, j = 1, 2, · · · · · · , tan dan i 6= j. Andaikan pelanggan ke-i, τiyi deviasi waktu pengantaran dan yi xi d01(i, j) kelebihan waktu perjalanan, maka diperoleh fungsi tujuan minimal yaitu : Minimum z=A

n X

(τi yi ) + B

i−1

n X

(yi xid01 (i, i))

(3.2)

i=1

Dengan mengurangi konstanta pindahannya maka diperoleh fungsi tujuan sebagai berikut :Minimum z = −B

n X

xi + (B − A)

i=1

n X

yi

(3.3)

i=1

Kendala : xi ≤ ρi,

i = 1, 2, · · · · · · , n

(3.4)

yi ≤ τi,

i = 1, 2, · · · · · · , n

(3.5)


16 yi xi ≥ d01(i, i) n X

uji vij ≤

i = 1, 2, · · · · · · , n i = 1, 2, · · · · · · , n

(3.6) (3.7)

j=i,j6=i

d00 (j, i) ≤ xi xj + Muij ≤ Md00 (i, j)i, j = 1, 2, · · · · · · , n, i 6= j

(3.8)

d10 (j, i) ≤ xi xj + M vij ≤ Md01 (i, j)i, j = 1, 2, · · · · · · , n, i 6= j

(3.9)

d11 (j, i) ≤ xi + Mwij ≤ Md11 (i, j)i, j = 1, 2, · · · · · · , n, i 6= j

(3.10)

xi dan yi bebas , i = 1, 2, · · · · · · , n

(3.11)

uij vij dan wij = 0 atau 1, i, j = 1, 2, · · · · · · , n, i 6= j

(3.12)

3.3 Linearisasi Andaikan A memiliki beberapa himpunan terbatas pada elemen n, dan himpunan pada variabel biner {xa |a ∈ A}. Misalkan g0 , · · · , gx menjadi variabel polinomial 0-1 masalah optimisasi berikut :Max g0 (x) Kendala gi (x) ≥ 0 untuk setiap i = 1, · · · , r x ∈ {0, 1}A

(3.13)

Cara mudah untuk melinearkan masalah (3.13) dengan menganggap himpunan T pada semua monomial yang tidak konstan muncul paling sedikit satu pada setiap gi dan menggunakan variabel biner zI untuk setiap I ∈ T , menghasilkan formulasi yang ekuivalen Max h0 (z) hi (z) ≥ 0

untuk semua i = 1, · · · , r


17 zI = Πa∈I z{a}

untuk semua I ∈ T z ∈ {0, 1}T

(3.14)

Disini hi digunakan untuk menunjukkan polynomial gi dianggap sebagai fungsi linear pada himpunan baru variabel zI . semua variabel di (3.13) adalah biner, dengan mengasumsikan bahwa setiap gi multilinear. Faktanya, dapat mengidentifikasi monomial dengan menyesuaikan himpunan bagian pada A dan menganggap T sebagai himpunan bagian 2A \{∅}. Selain itu, untuk mengurangi eksposisi, di asumsikan bahwa {a} ∈ T untuk semua a ∈ A. Misalkan F menunjukkan himpunan penyelesaian yang fisibel pada (3.14), dan misalkan P menunjukkan kecenderungan pada F , yang memiliki polytope pada Rx . Masalah (3.14) adalah masalah optimisasi polinomial, tetapi ketidaklinearan menghasilkan rumus yang terbatas. Masalah yang terakhir untuk model ini adalah pembatas ketidaksamaan linear. Cara mudahnya adalah sebagai berikut : untuk setiap I ∈ T dengan |I| ≥ 2, menggunakan ketidaksamaan linear |I| + 1 zI ≤ z{a} zI ≥

untuk semua a ∈ I X

z{a} − |I| + 1

(3.15) (3.16)

a∈I

Tetapi, relaksasi pada P yang ditunjukkan pada (3.15) dan (3.16) lebih rendah ketika menurunkan pembatas keintegralannya. Tujuannya adalah memberikan metode umum untuk memperoleh lebih banyak tingkat kesukaran pada P (Buchheim & Rinald, 2007).


BAB 4 APLIKASI LINEARISASI

4.1 Linearisasi Biasa Liberti (2006) mengandaikan x ∈ {0, 1}n merupakan variabel problem, E himpunan pasangan indeks berurut (i, j) dengan (1 ≤ i ≤ j ≤ n), dimana perkalian xi xj berada dalam problem (dengan |E| = m ) dan w ∈ Rm + himpunan variabel linearisasi non-negatif dimana wi dipakai untuk menggantikan perkalian xi xj ∀(i, j) ∈ E. Andaikan N = {1, · · · , n} dan {I1|k ∈ K} tutupan dari N , dimana K himpunan indeks yang kardinalitasnya diasumsikan terbatas oleh suatu polonomial dalam n. Suatu batasan yang lebih realistis adalah |K| ≤ n, dengan diketahui bahwa |K| merupakan ukuran tutupan dari {1, · · · , n}. Pandang problem P berikut : Min cT x + bT w

(4.1)

g(x, w) ≤ 0 X xi = 1 ∀k ∈ K

(4.2)

x,w

(4.3)

i∈Ik

∀(i, j) ∈ E,

wij = xi xj

(4.4)

∀i ∈ N, xi ∈ {0, 1}

(4.5)

∀(i, j) ∈ E, wij ≥ 0

(4.6)

Dimana c ∈ Rn dan b ∈ Rm dan g vektor dari fungsi x, w linearisasi dibawah ini yang disebut linearisasi biasa. Memformulasikan problem P menjadi program 18 Yusnar : Linearisasi Kompak Untuk Menyelesaikan Masalah Rute Kendaraan, 2008 USU e-Repository © 2008

19 cacah campuran linear dengan mengajukan kendala linearisasi berikut ; ∀(i, j) ∈ E, (wij ≤ xi )

(4.7)

∀(i, j) ∈ E, (wi,j ≤ xj )

(4.8)

∀(i, j) ∈ E, (wi,j ≥ xi + xj 1)

(4.9)

Dengan menghilangkan kendala kuadrat (4.4). Jika xi atau xj bernilai nol, maka oleh (4.6) dan (4.7) atau (4.8) terdapat wij = 0, jika xi = xj = 1,maka oleh (4.7) dan (4.9) wij = 1. Jadi ini merupakan reformulasi yang tepat, reformulasi ini dinyatakan dengan L1 (P )

4.2 Linearisasi Compact Dengan mengandaikan (Liberti, 2006) (K, I) =

(i, j) (i, j) ∈ ∪ (Ik × Ik ) ∧ i 6 j k ∈K

(4.10)

dan F = F (K, I) . Andaikan bahwa syarat tutupan berikut berlaku : E∈F

(4.11)

Kalikan (4.3) dengan xj (untuk j ∈ Ik ), membentuk sistem berikut : ! X xi xj = x j ∀ k ∈ K, j ∈ Ik i ∈ Ik

kemudian substitusi wij = xi xj untuk memperoleh sistem linear berikut :     ∀ k ∈ K, j ∈ Ik  

X i ∈ Ik (i,j) ∈ F ∨ (j,i) ∈ F


wij

  = xj  

(4.12)

20 Kemudian bentuk L2 (P ) dengan mensubsitusikan kendala (4.7) - (4.9) kedalam L1 (P ) dengan (4.12). Teorema 1. Asalkan syarat (4.11) berlaku L2 (P ) merupakan reformulasi tepat dari L1 (P ) Bukti : Oleh (4.12) terdapat, ∀(i, j) ∈ F,

(wi,j ≤ xj )

(4.13)

∀(i, j) ∈ F,

(wi,j ≤ xi )

(4.14)

yang mana oleh (4.11) mengakibatkan (4.7) - (4.8). Untuk menyederhanakan notasi, akan diandaikan bahwa wij terdefenisi untuk i j juga dan bahwa wij = wji berlaku dalam kasus demikian, maka (4.12) dapat ditulis sehingga   X  ∀ k ∈ K, j ∈ Ik  wij = xj 

(4.15)

i ∈ Ik

Setiap penjumlahan dari (4.14) mempertahankan ke pertidaksamaan. Jadi



 X wf j 6 ∀ k ∈ K, (i, j) ∈ F  f ∈ Ik \ (i)

X f ∈Ik \ (i)

Tambahkan dan kurangkan wij dari ruas kiri (4.16)   X ∀ k ∈ K, (i, j) ∈ F  wf j − wij 6 f ∈ Ik \ (i)

Subsitusi xj =

P



 xf 

(4.16)



X f ∈Ik \ (i)

 xf 

(4.17)

wf j (yang berlaku oleh (4.15) dalam (4.17)

f ∈Ik



∀ k ∈ K, (i, j) ∈ F xj − wij 6

X f ∈ Ik \ (i)



xf 

Tambahkan dan kurangkan xi dari ruas kanan (4.18) ∀ k ∈ K, (i, j) ∈ F

xj − wij 6

X f ∈ Ik


xf − x i

!

(4.18)

(4.19)

21 Akhirnya, dengan mensubsitusikan 1 =

P

xf (yang berlaku oleh (4.3) dalam

f ∈Ik

(4.18) ∀ k ∈ K, (i, j) ∈ F (xj − wij 6 1 − xi )

(4.20)

yang oleh syarat (4.11), membentuk (4.9)· · · · · · · · · (terbukti) Teknik linearisasi kompak ini diterapkan pada model VRP (persamaan (3.2) (3.12)). Pada persamaan (3.7) dalam model ini terdapat bentuk tak linear, yaitu : n X

uji vij 6 C − 1 , i = 1, 2, · · · , n

(4.21)

j =i j 6= 1

yang menyatakan perkalian dari 2 variabel linear. Dengan mensubtitusikan wij = uji vij hanya terdapat penambahan kendala seperti pada persamaan (4.12).


BAB 5 KESIMPULAN

5.1 Kesimpulan Berdasarkan hasil pembahasan dari tesis ini, dapat ditarik kesimpulan sebagai berikut:

a. VRP adalah sebuah problem optimalisasi kombinatorial yang bertujuan untuk melayani beberapa pelanggan dengan sejumlah kendaraan b. Tujuan utama dari VRP adalah meminimalisasi biaya yang keluar untuk proses pendistribusian barang c. Formulasi VRP yang memiliki variabel dan kendala yang relatif banyak, ternyata dapat di minimalkan dengan cara linearisasi kompak d. Linearisasi kompak yang dilakukan pada formulasi VRP adalah dengan mensubstitusikan atau mengeliminasikan kendala yang tak-linear, agar terbentuknya formulasi baru dengan variabel dan kendala yang lebih sedikit dari formulasi awalnya e. Tingkat kerumitan dari proses linearisasi kompak berdasarkan polinomial yang terbentuk pada formulasi VRP itu sendiri d. Linearisasi kompak berpengaruh terhadap proses penyelesaian VRP, karena dengan varibel dan kendala yang sederhana ,maka proses penyelesaian akan lebih sederhana juga.


DAFTAR PUSTAKA

Angelelli, E & Speranza, M.G., 2002. ”The Periodic Vehicle Routing Problem with Intermediate Facilities”, European Journal of Operational Research 137:233247. Applegate,D; Bixby,R; Chvatal,V & Cook, W., 2001. ”Computational Combinatorial Optimization”, D. Naddef and M. Junger, eds., Springer, Berlin, 261303 Archetti, C; Mansini, R; Speranza, M.G.,2001. ”The Split Delivery Vehicle Routing Problem with Small Capacity”, Tecnical Report n. 201,Department of Quantitative Methods, University of Brescia Bhavikatti, S.S., Structural Optimization Using Sequential Linear Programming, Vikas Publishing House PVT LTD, New Delhi., 2003 Buchheim, C & Rinald, G., 2007. ” Efficient Reduction of Polynomial Zero-One Optimization to The Quadratic Case” SIAM J. OPTIM; Vol. 18, No. 4, pp. 13981413 Burrows, W., 1998.”The Vehicle Routing Problem with Loadsplitting: A Heuristic Approach”. In 24th Annual Conference of the Operational Research Society of New Zealand, pages 33-38 Chepuri, K., & de Mello,T.H. 2005. ”Solving the vehicle routing problem with stochastic demands using the cross entropy method. Annals of Operations Research 134 153181 Fukasawa, R; Lysgaard, J; de Aragao,M.P; Reis, M; Uchoa, E & Werneck,R.F., 2004 ”Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem”, LNCS 3064, Springer-Verlag, pp. 115. Garcia, B; Potvin, J & Rousseau, J.M .,1994 ” Aparallel implementation of the tabu search heuristic for vehicle routing problems with time window constraints.” Computers & Operations Research vol. 21, no. 9, pp. 1025-1033 Hjorring, C,. 1995 ”The Vehicle Routing Problem and Local Search Metaheuristics”, Chapter 2. PhD thesis, Department of Engineering Science, The University of Auckland Hvattum, L.M; Lkketangen, A & Laporte, G., 2006. ”Solving a Dynamic and Stochastic Vehicle Routing Problem with a Sample Scenario Hedging Heuristic” Transportation Science; vol. 40, no. 4, Nov , pp. 421-438 Laporte, G & Louveaux, F.V., 1998. ”Solving Stochastic Routing Problems with the Integer L-shaped Method”. In Fleet Management and Logistics, T.G. Crainic and G. Laporte (eds.), 159-167, Kluwer Academic Publishers, Boston. Lau,H.C; Sim, M & Teo,K.M.,2003. ”Vehicle Routing Problem with Time Windows and a Limited Number of Vehicles”, European Journal of Operational Research 148: 559-569 23 Yusnar : Linearisasi Kompak Untuk Menyelesaikan Masalah Rute Kendaraan, 2008 USU e-Repository © 2008

24 Lee, L.H; Tan, K.C; Ou, K & Chew, Y.H., 2003. ”Vehicle Capacity Planning System: A Case Study on Vehicle Routing Problem With Time Windows”, IEEE Transactions on Systems, Man and Cybernetics, Part A, 33(2), 169-178 Liberti, L., 2006.”Compact linearization for binary quadratic Problems” LIX, Ecole Polytechnique, F-91128 Palaiseau, France, page : 302-316 Luenberger, D.G., 1994.”Linear and Nonlinear Programming”, Addison Wesley Publishing Company, Reading, Massachusetts Lysgaard,J; Letchford, A.N & Eglese, R.W. ”A New Branch-and-cut Algorithm for Capacitated Vehicle Routing Problems”, Math. Program., Ser. A 100: 423445, Springer-Verlag, 2004 Ralphsy, T.K; Kopmanz, L; Pulleyblankx,WR & Trotter, L.E., 2003 ”On the Capacitated Vehicle Routing Problem” Mathematical Programming Series B 94 343 Rao, S.S., 1997. ”Optimization Theory and Applications” wiley eastern limited,new delhi Righini,G., 2000. ”Approximation algorithms for the vehicle routing problem with pick-up and delivery”, Note del Polo - Ricerca 33, Polo Didattico e di Ricerca di Crema, Universit degli Studi di Milano, Luglio Russell RA.,1995 ”Hybrid heuristics for the vehicle routing problem with time windows”. Transportation Science 29: 156166. Schrijver & Alexander., 2007. ”A Course in Combinatorial Optimization”. Transportation Science 209: 106136 Solomon, M.M., 1995 ”Algorithms for the Vehicle Routing Problem with Time Windows”. Transportation Science, 29(2), pp. 156-166. Thangiah, S., 1993. ”Vehicle routing with time windows using genetic algorithms”. Articial Intelligence and Robotics Laboratory, Computer Science Department, Slippery Rock University, Slippery Rock, PA. Technical Report Toth, P & Vigo, D.,2001 ”The Vehicle Routing Problem”. Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia.


LINEARISASI KOMPAK UNTUK MENYELESAIKAN MASALAH RUTE KENDARAAN

Recommend Documents