PEMODELAN VEHICLE ROUTING PROBLEM TERBUKA DENGAN KETERBATASAN WAKTU

PEMODELAN VEHICLE ROUTING PROBLEM TERBUKA DENGAN KETERBATASAN WAKTU

TESIS

Oleh

DARMASIUS TARIGAN 067021013/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008

Darmasius Tarigan: Pemodelan Vehicle Routing Problem Terbuka Dengan Keterbatasan Waktu, 2008. USU e-Repository © 2008

PEMODELAN VEHICLE ROUTING PROBLEM TERBUKA DENGAN KETERBATASAN WAKTU

TESIS

Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh

DARMASIUS TARIGAN 067021013/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008


Judul Tesis Nama Mahasiswa Nomor Pokok Program Studi

: PEMODELAN VEHICLE ROUTING PROBLEM TERBUKA DENGAN KETERBATASAN WAKTU : Darmasius Tarigan : 067021013 : Magister Matematika

Menyetujui, Komisi Pembimbing

(Drs. Opim Salim Sitompul, M.Ikom, PhD) Ketua

(Dr. Saib Suwilo, MSc) Anggota

Ketua Program Studi

Direktur

(Prof. Dr. Herman Mawengkang)

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

Tanggal lulus : 4 Juni 2008


Telah diuji pada : Tanggal 4 Juni 2008

PANITIA PENGUJI TESIS

Ketua

:

Drs. Opim Salim Sitompul, M.Ikom, PhD

Anggota

:

Dr. Saib Suwilo, MSc Prof. Dr. Herman Mawengkang Drs. Sawaluddin, MIT


ABSTRAK Pada tesis ini penulis mengangkat vehicle routing problem terbuka dengan keterbatasan waktu. Jenis dari pemecahan masalah untuk menemukan kumpulan dari rute kembalian non-depot, untuk armada kendaraan berkapasitas harus memenuhi permintaan pelanggan dalam interval waktu tertentu yang menggambarkan waktu pelayanan paling awal dan paling akhir sehingga dapat melayani seluruh pelanggan. Suatu model matematika mencakup rumusan pengambilan semua aspek dari masalah dan semua perhatian kritik praktis digabungkan pada pemodelan. Kerangka dasar dari pemodelan adalah program integer. Kata kunci: open vehicle routing problem, time windows.

i Darmasius Tarigan: Pemodelan Vehicle Routing Problem Terbuka Dengan Keterbatasan Waktu, 2008. USU e-Repository © 2008

ABSTRACT In this thesis, we consider the open vehicle routing problem with time windows (OVRPTW). This kind of problem solve to find a set of non-depot returning router, for a fleet of capacitated vehicles, to satisfy customers demands, for a fixed time intervals that represent the earliest and latest time during the day that customers service can take place. A comprehensive mathematical model is formulated to capture all aspects of problem, and incorporate in the model all critical practical concern. The basic framework of the model is integer programming. Keywords: open vehicle routing problem, time windows.

ii Darmasius Tarigan: Pemodelan Vehicle Routing Problem Terbuka Dengan Keterbatasan Waktu, 2008. USU e-Repository © 2008

KATA PENGANTAR Dengan rendah hati , penulis mengucapkan puji syukur kehadirat Tuhan Yang Maha Esa atas anugrah dan berkat-Nya yang telah diberikan, sehingga penulis dapat menyelesaikan tesis ini dengan judul: Pemodelan Vehicle Routing Problem Terbuka dengan Keterbatasan Waktu. Tesis ini merupakan salah satu persyaratan penyelesaian studi pada Program Studi Magster Matemtika Sekolah Pascasarjana Universitas Sumatera Utara (USU). Pada kesempatan ini penulis menyampaikan terima kasih yang sebesarbesarnya kepada: Prof. Dr. Chairuddin P. Lubis, DTM&H, Sp. AK selaku Rektor USU. Prof. Dr. Ir. T. Chairun Nisa. B,M.Sc selaku Direktur Sekolah Pascasarjana USU yang telah memberi kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di SPs USU. Prof.

Dr.

Herman Mawengkang selaku Ketua Program Studi Magister

Matematika SPs USU yang selalu memberi motivasi kepada penulis. Dr. Saib Suwilo, MSc selaku Sekretaris Program Studi Magister Matematika SPs USU sekaligus selaku Pembimbing II yang selalu memberi motivasi kepada penulis. Drs. Opim Salim Sitompul, MIkom, PhD selaku pembimbing I yang telah meluangkan waktu untuk diskusi dalam penulisan tesis ini. Seluruh Staf Pengajar pada Program Studi Magister Matematika SPs USU iii Darmasius Tarigan: Pemodelan Vehicle Routing Problem Terbuka Dengan Keterbatasan Waktu, 2008. USU e-Repository © 2008

yang telah memberikan ilmunya selama masa perkuliahan. Dr. RE. Nainggolan, MM selaku Kepala Bappeda Sumatera Utara yang telah memberikan beasiswa kepada penulis. Drs. Karbin Tarigan, MPd selaku Kepala SMA Negeri 17 Medan yang telah memberikan kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di SPs USU. Semua teman-teman Staf Pengajar dan Staf Pegawai SMA Negeri 17 Medan yang selalu memberi dorongan dan telah memberi bantuan moril dan materil kepada penulis dalam penulisan tesis ini. Semua rekan-rekan Mahasiswa Program Studi Magister Matematika SPs USU yang telah memberi bantuan moril dan materil serta dorongan kepada penulis dalam penulisan tesis ini dan tidak lupa Saudari Misiani, SSi selaku Staf Administrasi Program Studi Magister Matematika SPs USU yang telah memberi pelayanan yang baik kepada penulis. Kepada Bapak/Ibu dan Saudara/i yang telah disebut diatas, penulis berdoa kepada Tuhan Yang Maha Esa, kiranya Tuhanlah yang memberi balasan atas semua jasa-jasa yang telah diberikan kepada penulis. Terakhir penulis mengucapkan terima kasih sebesar-besarnya kepada keluarga, Istri tercinta H. br Saragih dan anak-anak Ira Octavia br Tarigan, Ivo Deka Vicilia br Tarigan, Ian Ricky Tanikato Tarigan, dan Ayu Nikita br Tarigan atas dukungan yang sangat besar.

iv Darmasius Tarigan: Pemodelan Vehicle Routing Problem Terbuka Dengan Keterbatasan Waktu, 2008. USU e-Repository © 2008

Demikian juga untuk keluarga Tarigan mergana yang selalu memberi dorongan dan mendoakan penulis. Semoga Tuhan Yang Maha Esa selalu melindungi kita dan memberikan kesehatan dan damai sejahtera bagi kita semua. Semoga kedepan Program Studi Magister Matematika SPs USU lebih baik dan lebih berjaya dalam menghasilkan sumber daya manusia yang handal, berbudi pekerti luhur dan berahklak mulia.

Medan, 20 Juni 2008 Penulis,

Darmasius Tarigan

v Darmasius Tarigan: Pemodelan Vehicle Routing Problem Terbuka Dengan Keterbatasan Waktu, 2008. USU e-Repository © 2008

RIWAYAT HIDUP Darmasius Tarigan dilahirkan di Tigapanah, Karo pada tanggal 19 September 1961 dan merupakan anak kedua dari 9 orang bersaudara dari ayah (Alm) G. Tarigan dan ibu (Almh) G. br Ginting. Menamatkan Sekolah Dasar (SD) Negeri 1 di Tigapanah pada tahun 1973, Sekolah Menengah Pertama (SMP) Swasta di Tigapanah pada tahun 1979, dan Sekolah Menengah Atas (SMA) Negeri Kabanjahe Jurusan IPA pada tahun 1982 di Kabanjahe. Pada tahun 1983 memasuki Perguruan Tinggi Negeri FPMIPA IKIP Medan Jurusan Pendidikan Matematika, dan menamatkan Program D-3/ A-3 pada tahun 1986. Terhitung 1 Maret 1987 diangkat menjadi guru di SMA Negeri Parapat. Pada tahun 1994 pindah menjadi guru di SMA Negeri 17 Medan. Pada tahun 1996 memasuki PGSM di FPMIPA IKIP Negeri Medan dan memperoleh Gelar Sarjana Pendidikan (SPd), Jurusan Pendidikan Matematika pada tahun 1997. Pada tahun 2006 mengikuti pendidikan Program Studi Magister Matematika di Sekolah Pascasarjana USU Medan. Pada tahun 1989 menikah dan dikaruniai anak 1 putra dan 3 putri. Hingga saat ini masih sebagai Staf Pengajar di SMA Negeri 17 Medan

vi Darmasius Tarigan: Pemodelan Vehicle Routing Problem Terbuka Dengan Keterbatasan Waktu, 2008. USU e-Repository © 2008

DAFTAR ISI

Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

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

ii

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

iii

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

vi

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

vii

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

1

1.1 Latar belakang . . . . . . . . . . . . . . . . . . . . . .

1

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

2

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

3

1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . .

3

1.5 Metodologi penelitian

. . . . . . . . . . . . . . . . . .

3

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

5

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

9

3.1 Vehicle Routing Problem . . . . . . . . . . . . . . . . .

9

3.1.1 Jenis-jenis VRP

. . . . . . . . . . . . . . . . . .

3.1.2 VRP dengan waktu terbatas

10

. . . . . . . . . . . .

12

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

13

vii Darmasius Tarigan: Pemodelan Vehicle Routing Problem Terbuka Dengan Keterbatasan Waktu, 2008. USU e-Repository © 2008

3.3 Pemakaian Algoritma Clarke Wright(CW) Paralel yang dimodifikasi untuk OVRP . . . . . . . . . . . . . . . . .

16

BAB 4 PEMBENTUKAN MODEL . . . . . . . . . . . . . . . . . .

17

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

22

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

22

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

23

viii Darmasius Tarigan: Pemodelan Vehicle Routing Problem Terbuka Dengan Keterbatasan Waktu, 2008. USU e-Repository © 2008

BAB 1 PENDAHULUAN

1.1 Latar belakang Depot tunggal Vehicle Routing Problem (VRP) didefinisikan sebagai menentukan himpunan rute untuk armada kendaraan dari basis depot agar terpenuhi permintaan pelanggan yang tersebar secara geografis sehingga total biaya perjalanan minimum. Sedangkan Open Vehicle Routing Problem (OVRT) merupakan varian dari VRP dimana kendaraan tidak dipersyaratkan kembali ke depot. Tidak banyak pembahasan OVRP didalam jurnal, dibanding dengan VRP (Aksen et al. 2007). Problema ini mula-mula dideskripsikan oleh Schrage (1981) tanpa ada usaha penyelesaian. Bodin et al. (1983) mengajukan pemakaian OVRP pada distribusi pos udara ekspres di Amerika Serikat dan menyelesaikan dua problem rute terpisah, yang satu untuk antaran dan yang kedua untuk jemputan. Sariklis dan Powell (2000) mengajukan metode heuristic klasik untuk menyelesaikan OVRP simetris yang tidak mencakup pembatasan panjang rute maksimum. Mereka tidak mengajukan suatu model analitik terhadap problem. Tarantilis dan Kiranoudis (2002) memandang problema distribusi daging segar dan memformulasikannya sebagai OVRP multi depot. Tetapi dalam makalah mereka tidak diajukan suatu model analitik tertentu. Bentuk problem dikemukakan dalam suatu jaringan graph dan kemudian diselesaikan dengan metode metaheuristic.

1 Darmasius Tarigan: Pemodelan Vehicle Routing Problem Terbuka Dengan Keterbatasan Waktu, 2008. USU e-Repository © 2008

2 Fleszar et al. (2008) mengajukan algoritma pencarian variabel sekitar berbasis semi graph untuk menyelesaikan OVRP, tanpa mengajukan suatu model analitik tertentu. Model program integer untuk problem OVRP diajukan oleh Aksen et al. (2007). Namun model yang dikemukakan adalah untuk salah satu varian dari problem OVRP dimana setiap rute kendaraan berhenti pada buhul pengemudi bukan pada lokasi pelanggan. VRP sering digunakan antara lain untuk menentukan rute bus sekolah, rute pendistribusian barang-barang, rute perjalanan wisata dan lain-lain. Sedangkan OVRP digunakan untuk mengangkut barang-barang ke daerah, dimana kedaraannya berhenti di daerah yang dituju, ataupun perusahaan yang menyewa kendaraan untuk mendistribusikan barang-barang kepada pelanggannya. Secara esensial model program integer 0-1 merupakan suatu model yang selalu dapat dipakai untuk persoalan distribusi dan penentuan rute.

1.2 Perumusan Masalah Beberapa model OVRP dengan keterbatasan waktu telah dikembangkan. Namun model-model demikian ini masih lebih banyak dinyatakan dalam bentuk konseptual. Suatu model analitik dari persoalan di harapkan dapat memberikan pengertian matematis dari persoalan , demikian pula untuk menentukan metode yang akan dipakai. Problem OVRP secara esensial memiliki bentuk struktur yang sama seperti VRP. Problem ini tercakup dalam problem pendistribusian, oleh karena itu dapat di modelkan misalnya sebagai program integer. Jadi untuk


3 menyelesaikan OVRP ini akan dimodelkan menjadi suatu model program integer. Seringkali dalam pemakaian bahwa terdapat persyaratan waktu yang diberikan untuk pendistribusian. Sehingga model yang akan dihasilkan merupakan model untuk OVRP dengan adanya keterbatasan waktu.

1.3 Tujuan Penelitian Pada tesis ini bertujuan untuk mengembangkan suatu model analitik OVRP dengan keterbatasan waktu.

1.4 Kontribusi Penelitian Penelitian ini dapat memberi kontribusi terhadap penyelesaian problem OVRPT dengan keterbatasan waktu agar dapat terselesaikan secara analitik.

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

1. Menguraikan Vehicle routing problem. 2. Pembahasan dan pemahaman tentang Vehicle routimg problem terbuka. 3. Merancang model OVRPT dengan keterbatasan waktu. a mengajukan asumsi


4 b menyayakan secara konseptual tentang problem c faktor-faktor terkait d variabel e membuat model


BAB 2 TINJAUAN PUSTAKA

Toth dan Vigo (2002) memaparkan versi klasik dari VRP, dimana kendaraan wajib kembali ke depot sesudah selesai melayani pelanggan. Sedangkan pada OVRP, kendaraan tidak wajib kembali ke depot, ataupun kendaraan dapat berhenti disalah satu pelanggan. Pada awalnya OVRP merupakan modifikasi kecil dari VRP. Jika biaya perjalanan asimetris, secara esensial tidak ada perbedaan antara OVRP dan VRP. Beberapa VRP tertutup pada n pelanggan dapat ditransformasikan ke OVRP. Kemudian masih banyak aplikasi dari OVRP dengan murni dilaksanakan. Misalnya jika perusahaan tidak memiliki armada kendaraan sendiri dan seluruh pelayanan dari depot pusat kepelanggan dijalankan oleh kendaraan sewaan yang tidak diharuskan kembali ke depot ( Tarantilis et al., 2005 ). Model yang sama dapat digunakan pada jemputan, dimana kendaraan berangkat dari salah satu pelanggan dan harus menjemput setiap permintaan pelanggan pada rute mereka dan mengantarkannya kembali ke depot. Ketika kendaraan berangkat dari depot untuk melayani pendistribusian barang ke pelanggan, kembalinya diperintahkan untuk menjemput permintaan pelanggan yang harus dikembalikan ke depot. Jika untuk setiap pelanggan permintaan jemputan tidak lebih banyak dari permintaan antaran, maka OVRP dapat digunakan. Bentuk seperti ini ditunjukkan oleh Schrage (1981) pada pengantaran pos udara kilat di Amerika Serikat. Pada beberapa situasi biaya pendistribusian dapat ditentukan dari jarak perjalanan yang ditempuh.


6 Fu et al. (2005) memberi contoh gambaran dua tempat yang berjauhan. Pertama meliputi rencana dari layanan kereta api, mulai dan berakhir di channel Tunnel. Rencana kedua meliputi rute bus sekolah dimana di pagi hari pelajarpelajar diangkut dari lokasi berbeda dan dibawa ke sekolah, dan di sore hari rute bus melayani kembali pelajar untuk diantar kerumah. Mereka menyelesaikan OVRP dengan Tabu Search (TS) heuristic dengan kendaraan berkapasitas dan panjang rute maksimum yang dapat dipaksakan. Tarantilis et al. (2005), menyelesaikan problem dengan mengimplementasikan algorithma LBTA (List Based Threshold Accepting) untuk tujuan multidepot OVRP. Brandao (2004) memaparkan solusi-solusi yang tidak feasibel juga diterima oleh bentuk-bentuk akhir yang memuat fungsi objektif. Selanjutnya Fu et al. (2005) menyediakan corrigendum yang mengoreksi beberapa kesalahankesalahan pada kode dari algorithma mereka. Li et al. (2006) memakai laporan ke laporan heuristic travel, menentukan variasi dari penguatan simulasi, menyelesaikan OVRP dan memberikan hasil komputasi pada benchmark. Pisinger dan Ropke (2006) memakai adopsi lebar lingkungan search heuristic yang pada setiap iterasi arus solusi adalah pemusnahan sebagian pelanggan dan diperbaiki dengan penghilangan beberapa pilihan. Letchford et al. (2006) yang menghadirkan metode optimasi nyata berbasis on the branch-and-cut algorithm. Tidak banyak dipelajari OVRP di jurnal jika dibandingkan dengan VRP. Schrage (1981) menyebutkan OVRP adalah sebuah artikel yang menyebutkan masalah perjalanan hidup yang sebenarnya. Sariklis dan Powell (2000) memecahkan OVRP simetris dengan dua fase algoritma yang menggunakan cluster-first-route-second mecanism. Tarantilis dan Kiranodis


7 (2002) memecahkan hal realita kehidupan dari multi depot OVRP untuk menyebarkan pertemuan pendistribusian oleh sebuah meta-heuristic yang disebut ”list based threshold accepting algorithm” (LBTA). A spatial decision support system (SDSS) yang disusun oleh Tarantilis et al. (2004). Proses solusi genetik yang disebut BoneRoute yang digunakan untuk menyelesaikan OVRP. Tarantilis et al. (2004) mengusulkan a single parameter simulated an nealing-based algorithm untuk masalah yang sama. Brandao (2004) mengusulkan a tabu search algorithm (TS) untuk OVRP dengan kendala rute menengah menjadi maksimum. TS algoritma yang lain juga dilakukan oleh Fu et al. (2005), juga subjek untuk memaksimumkan kendala rute menengah. Kedua algoritma TS ini berbeda di solusi inisialnya, struktur lingkungan, fungsi tujuan, dan tabu defenisions. Kedua algoritma kelihatannya di tampilkan dalam solusi Sariklis dan Powell. Walaupun Fu et al. (2005) memperbaiki solusi untuk beberapa masalah dari masalah-masalah pada makalah Brandao, untuk yang lainnya mereka menemukan solusi yang bertambah buruk dalam total terminal pada jarak perjalanan dan nomor yang digunakan kendaraan-kendaraan. Kendala eliminasi pada semua kendaraan yang harus kembali ke depot tidak membuat OVRP menjadi masalah yang lebih sederhana. Juga sebuah solusi yang baik untuk VRP tidak dapat diubah ke sebuah solusi OVRP yang bagus oleh penjatuhan pendapatan area sederhana dari depot. Kemudian OVRP dipelajari secara terpisah. Dua poin berbeda dalam masalah tinjauan mutakhir OVRP; Pertama adalah penggumpulan tenggat waktu setiap pelanggan yang harus dikunjungi sebelum tenggat waktunya. Kedua, perbedaan kendala setiap mengakhiri rute pada satu node pengemudi yang dispesifikasikan sebelumnya. Node pengemudi hampir cocok pada banyak parkiran atau rumah pengemudi. Kehadiran


8 dari node-node pengemudi cocok untuk situasi tertentu, khususnya situasi yang mengantarkan pelanggan-pelanggan keluar ke kantor pelayanan, atau pengemudi menggunakan kendaraan yang sama untuk menghubungkan antara rumah dan depot (Aksen, 2006).


BAB 3 LANDASAN TEORI

Teori-teori yang dijelaskan pada bab ini sebagai landasan berpikir untuk melakukan penelitian ini dan mempermudah pembahasan hasil utama pada bab selanjutnya.

3.1 Vehicle Routing Problem Kallehauge et.al (2001) mendefenisikan permasalahan m-TSP sebagai salah satu variasi dari TSP, dimana terdapat m-salesman mengunjungi sejumlah kota dan tiap kota hanya dapat dikunjungi oleh tepat satu salesman saja. Tiap salesman berawal dari suatu depot dan pada akhir perjalanannya juga harus kembali ke depot tersebut. Permasalahan m-TSP sering disebut sebagai vehicle routing problem (VRP), dimana sebuah kota diasosiasikan sebagai sebuah demand atau konsumen dan tiap kendaraan yang dipakai untuk perjalana dianggap memiliki kapasitas tertentu. Total jumlah demand dalam suatu rute tidak boleh melebihi kapasitas dari kendaraan yang ditugasi melewati rute tersebut. Hal ini membuat VRP kadang juga disebut sebagai Capasitated Vehicle Routing Problem (CVRP). Sama seperti permasalahan TSP, dalam VRP juga terdapat suatu depot, dimana tiap kendaraan harus berangkat dan kembali ke depot itu. Dalam VRP selain bertujuan untuk meminimalkan total jarak atau total biaya travel, dapat juga untuk meminimalkan jumlah kendaraan yang digunakan (m). Permasalahan VRP bertujuan untuk menentukan suatu set trips kendaraan dengan total biaya minimal, dimana tiap-tiap berawal dan berakhir di depot, tiap klien dikunjungi tepat 9 Darmasius Tarigan: Pemodelan Vehicle Routing Problem Terbuka Dengan Keterbatasan Waktu, 2008. USU e-Repository © 2008

10 satu kali, total demand yang dibawa oleh tiap kendaraan tidak melebihi kapasitas kendaraan Q, dan biaya dari tiap-tiap kendaraan tidak melebihi upper limit L yang telah ditentukan.

3.1.1 Jenis-jenis VRP Menurut IDSIA (2007), berdasarkan faktor-faktor sampingan yang muncul, VRP terdiri atas beberapa jenis antara lain:

1. Capacitated VRP (CVRP), dengan faktor: Setiap kendaraan punya kapasitas yang terbatas. CVRP adalah sebuah VRP dimana sejumlah kendaraan dengan kapasitas tertentu yang harus melayani sejumlah permintaan pelanggan yang telah diketahui untuk satu komoditas dari sebuah depot dengan biaya minimum. Pada dasarnya CVRP sama seperti VRP dengan faktor tambahan yaitu setiap kendaraan mempunyai kapasitas tertentu untuk satu komoditas. CVRP bertujuan meminimalisasi jumlah kendaraan dan total waktu perjalanan, dan total permintaan barang untuk tiap rute tidak melebihi kapasitas kendaraan yang melewati rute tersebut (Ralphsy et al. 2001). 2. VRP with Time Windows (VRPTW), dengan faktor: Setiap pelanggan harus disuplai dalam jangka waktu tertentu. 3. Multiple Depot VRP (MDVRP), dengan faktor: Distributor memiliki banyak depot untuk menyuplai pelanggan. Sebuah perusahaan yang memiliki lebih dari satu depot, dan pelangganpelanggannya tersebar di sekitar depot-depot yang ada, maka masalah pendis-


11 tribusiannya harus dimodelkan menjadi sebuah kumpulan dari VRP-VRP yang independent. Namun jika pelanggan dan depot-depot tidak terkumpul secara teratur maka masalahnya menjadi Multi-Depot VRP atau MDVRP. Sebuah MDVRP membutuhkan pengaturan para pelanggan ke depot-depot yang ada. Setiap kendaraan berangkat dari satu depot melayani pelangganpelanggan yang sudah ditentukan oleh depot tersebut, dan kembali lagi ke depot tersebut. Tujuan utama dari MDVRP adalah untuk melayani semua pelanggan, sementara jumlah kendaraan dan jarak perjalanan diminimalisasi. 4. VRP with Pick-Up and delivering (VRPPD), dengan faktor: Pelanggan mungkin mengembalikan barang pada depot asal. VRPPD adalah sebuah VRP dimana pelanggan mengembalikan barang yang sudah diantarkan. Barang yang dikembalikan dapat dimasukkan ke dalam kendaraan pengantar. Perencanaan pengantaran menjadi lebih sulit dan dapat mengakibatkan penyalahgunaan kapasitas kendaraan, memperbesar jarak perjalanan atau kendaraan yang diperlukan lebih dari yang seharusnya. Seluruh permintaan pengantaran dimulai dari depot dan seluruh permintaan penjemputan dibawa kembali ke depot, sehingga tidak ada pertukaran barang antar pelanggan. 5. Split Delivery VRP (SDVRP), dengan faktor: Pelanggan dilayani dengan kendaraan berbeda. SDVRP adalah perluasan VRP dimana setiap pelanggan dapat dilayani dengan kendaraan yang berbeda bilamana biayanya dapat dikurangi. Perluasan ini dapat dilaksanakan jika jumlah permintaan pelanggan sama de-


12 ngan kapasitas kendaraan. Tujuan dari SDVRP untuk meminimalisasikan jumlah kendaraan dan total waktu perjalanan untuk pelayanan. 6. Stochastic VRP (SVRP), dengan faktor: Munculnya ’random values’ (seperti jumlah pelanggan, jumlah permintaan, waktu pelayanan atau waktu perjalanan). Untuk mendapatkan solusi dari SVRP, maka masalah harus dibagi dalam dua tahap, solusi pada tahap pertama ditentukan sebelum variabel random diketahui. Pada tahap kedua pengoreksian dilakukan jika nilai dari variabel random sudah diketahui (Hvattum et al. 2006). 7. Perioic VRP (PVRP), dengan faktor: Pengantaran hanya dilakukan di hari tertentu. PVRP merupakan VRP yang digeneralisasi dengan memperluas rentang perencanaan pengiriman menjadi M hari, dari semula hanya dalam rentang sehari, dengan tujuan meminimalisasi jumlah kendaraan dan total waktu perjalanan untuk melayani tiap pelanggan.

3.1.2 VRP dengan waktu terbatas Menurut Kallehauge et. al. (2001) VRP dengan time windows (VRPTW) adalah perluasan dari VRP. Jika pada VRP ditambahkan time windows pada masing-masing konsumen maka permasalahan tersebut menjadi VRPTW. Untuk VRPTW selain adanya kendala kapasitas kendaraan, terdapat tambahan kendala yang mengharuskan kendaraan untuk melayani tiap konsumen pada time frame tertentu.


13 Kendaraan boleh datang sebelum time windows ”open”, tetapi konsumen tersebut tidak dapat dilayani sampai time windows open . Kendaraan tidak diperbolehkan untuk datang setelah time windows ”clossed”. Time windows adalah two sided, yang berarti bahwa tiap konsumen harus dilayani saat atau setelah earlist time, dan sebelum latest time dari konsumen tersebut. Jika kendaraan datang ke konsumen sebelum earlist time dari konsumen tersebut maka akan menghasilkanidle atau waktu tunggu. Kendaraan yang datang ke konsumen setelah latest time adalah tardy. Terdapat pula waktu service yang diperlukan untuk melayani tiap konsumen. Biaya rute dari suatu kendaraan adalah total dari waktu travel (proposional dengan jarak), waktu tunggu dan waktu service yang diperlukan untuk mengunjungi sekumpulan konsumen.

3.2 Vehicle Routing Problem Terbuka Dalam versi klasik Vehicle Routing Problems (VRPs), kendaraan wajib kembali ke depot setelah menyelesaikan tugas (Toth & Vigo, 2002). Pada Open Vehicle Routing Problems (OVRP), bagaimanapun kendaraan tidak diperlukan untuk melakukan hal yang sama. Sebagai keuntungannya, rute-rute kendaraan bukanlah paths tertutup, melainkan terbuka bermula dari satu depot dan berakhir di salah satu pelanggan. Pada pengamatan pertama, rute-rute terbuka termasuk dari satu path tertutup yang kelihatan seperti sebuah modifikasi kecil. Sesungguhnya jika biaya perjalanan adalah asymmetric, pada dasarnya tidak ada perbedaan antara terbuka dan versi tertutup: benda-bendanya adalah lebih tidak kentara. Selain itu banyak aplikasi praktis dari OVRP secara murni dilakukan. Sebagai contoh, ketika sebuah perusahaan tidak mempunyai armada kendaraan sendiri dan se-


14 mua pelayanan dari depot pusat dijalankan oleh kendaraan sewaan yang tidak diharuskan untuk kembali kedepot. Di dalam situasi demikian biaya pendistribusian mungkin dapat seimbang dengan jarak yang ditempuh. Sebuah tipe pembelajaran praktis adalah digambarkan pada Tarantilis et al. (2004-2005). Model yang sama juga bisa digunakan untuk penjemputan, dimana kendaraan kosong dimulai pada pelanggan dan harus mengangkut permintaan dari setiap pelanggan dalam rute mereka dan mengantarkannya kembali ke depot. Terdapat juga aplikasi dimana kendaraan dimulai pada depot, mengatur pelayanan dari setiap pelanggan-pelanggan dan diharuskan mengunjungi pelanggan pada rute balikan, menjemput item-item yang diminta dan harus kembali ke depot. Jika setiap jemputan permintaan pelanggan tidak lebih besar daripada permintaan antaran maka OVRP dapat digunakan. Sebuah aplikasi dari tipe ini untuk pengantaran titipan kilat, seperti yang disebutkan oleh Schrage (1981), di sebuah artikel dengan cepat menggambarkan keistimewaan routing problem praktis. Dua penggunaan area lebih lanjut di gambarkan oleh Fu et al. (2005). Pertama, perencanaan dari pelayanan kereta api mulai dan berakhir pada Channel Tunnel. Kedua, mengatur perencanaan dari rute bus sekolah dimana pada waktu pagi hari murid-murid di jemput di lokasi yang berbeda-beda dan dibawa ke sekolah, dan pada waktu sore hari rutenya adalah mengantarkan murid-murid ke rumahnya. Bodin et al. (1983) menggambaran masalah pendistribusian surat kilat di USA, yang pada dasarnya adalah sebuah penjemputan terbuka dan pengantaran VRP dengan kapasitas yang terpaksa dan jendela waktu. Versi yang hanya melibatkan kapasitas terpaksa, Sariklis dan Powell (2000) memperkenalkan dua fase minimum spanning trees, Tarantilis et al. (2004) memperkenalkan a population-based-heurietic, dan Tarantilis et al. (2005) memperkenalkan heuris-


15 tic dari the threshold-accepting type. Untuk variasi yang lebih umum memuat kedua kapasitas dan panjang rute yang dipaksakan, Brandao (2004) dan Fu et al. (2005) memperkenalkan tabu search heuristics, Lie et al. (2006) memperkenalkan a record-to-record travel heuristic, dan Pisinger & Robke (2006) memperkenalkan an adaptive neighborhood search heuristic. Heuristic juga sudah ditemukan dari OVRP dengan jenis-jenis paksaan yang lain, Aksen et al. (2007), Repoussis et al. (2007) OVRP adalah variasi dari CVRP yang kurang mendapat perhatian. Munculnya masalah dalam berbagai masalah pendistribusian, dimana kendaraan sederhana berhenti setelah pengiriman terakhir. Untuk versi yang hanya mencakup kendala kapasitas, Sariklis dan Powell (2000) menggambarkan dua fase heuristic yang memuat minimum spanning tree. Baru-baru ini tabu search heuristic sudah diusulkan oleh Fu et al. dan Brandao. OVRP lebih tertutup daripada CVRP. Perbedaan diantara kedua masalah ini yaitu pada OVRP kendaraan tidak dapat kembali ke depot. Demikianlah sebuah OVRP dapat dipecah sebagai asimetris CVRP dengan pengaturan jarak dan waktu perjalanan dari setiap pelanggan ke depot. Waktu perjalanan dalam hasil rich pick up and delivery problem with time windows (RPDPTW)tidak memenuhi ketidaksamaan segitiga. Hanya alasan kita untuk menerima bahwa ketidaksamaan segitiga memuaskan untuk waktu perjalanan yang harus kita hindari situasi yang menghilangkan satu atau lebih permintaan yang disebabkan kenaikan waktu per0 } tidak pernah jalanan sebagai not rangkaian i → l → j dimana l ∈ {r10 , . . . , rm

terjadi dalam sebuah rute valid pelanggan diketidaksamaan segitiga tidak menyebabkan masalah.


16

3.3 Pemakaian Algoritma Clarke Wright(CW) Paralel yang dimodifikasi untuk OVRP Metode CW diusulkan oleh Clarke dan Wright untuk depot tunggal VRP. Algoritma ini efesien dan sederhana untuk peralatan, masih tetap terkenal sampai hari ini penyesuaian CW ke OVRP dengan waktu terbatas, yang memodifikasi jarak antara pelanggan-pelanggan dengan depot, pengemudi dengan depot. Jarak modifikasi setanda dengan apa yang diikutinya. Jarak pelanggan-depot mengatur jumlah yang tidak terakhiri karena kendaraan tak kembali ke depot secara langsung dari node pelanggan. Jarak pengemudi-pelanggan juga jumlah yang tidak terakhiri karena kendaraan diijinkan untuk memulai dari seorang pengemudi ke seorang pelanggan. Kesamaan yang benar untuk jarak pengemudi yang baik. Akhirnya jarak pengemudi garis depot yang diambil sebagai nol untuk mempercayai bahwa kendaraan akan kembali ke depot dari sebuah node pengemudi tanpa menaikkan nilai objektif. Hasil daripada jarak yang dimodifikasi sebuah rute di jamin untuk memulai dari depot, mengunjungi satu atau lebih pelanggan dan diakhiri pada node pengemudi.


BAB 4 PEMBENTUKAN MODEL

Open Vehicle Routing Problem with Time Windows (OVRPTW) mencakup tiga tipe subproblem:

1. Antaran : Kendaraan ditugaskan pada rute Antaran tanpa harus kembali ke pusat distribusi perusahaan. 2. Jemputan : Kendaraan ditugaskan pada rute jemputan yang di mulai langsung dari pelanggan pada ujung rute dan berhenti di depot. 3. Antar dan Jemput : Setelah selesai semua antaran, kendaraan kembali ke depot dengan mengunjungi pelanggan dalam urutan sebaliknya dan menjemput barang yang harus di kirim ke pusat distribusi, atau setelah selesai semua jemputan mereka kembali ke depot dengan mengikuti rute jemput dan mengantar barang ke pelanggan dengan urutan sebaliknya.

Jadi, OVRPTW dapat dinyatakan sebagai: Tentukan suatu himpunan dari rute terbuka, untuk armada kendaraan identik |V | (himpunan V menyatakan jumlah maksimum kendaraan yang dapat dipakai untuk antar atau jemput) dengan kapasitas diketahui C, melayani himpunan pelanggan dari suatu depot dengan biaya minimum, jumlah pelanggan n − 1, yaitu, |L| − 1 = n − 1, dimana L adalah himpunan pelanggan termasuk buhul berbeda dari depot. Indeks i, j dan n mengacu pada pelanggan dan bernilai antara 2 dan n, sementara i = 1 menyatakan depot. Indeks k jumlah kendaraan (k = 1, 2, . . . , |V |). 17 Darmasius Tarigan: Pemodelan Vehicle Routing Problem Terbuka Dengan Keterbatasan Waktu, 2008. USU e-Repository © 2008

18 Setiap pelanggan i mempunyai permintaan qi , dan dibatasi oleh waktu [ei , li] yang memodelkan waktu paling awal dan paling akhir dalam sembarang pelanggan dapat dilayani oleh sembarang kendaraan, (ei adalah waktu paling awal dan li adalah waktu paling akhir). Waktu servis si diperlukan untuk setiap pelanggan i, yang dilayani oleh hanya satu kendaraan. Juga terdapat biaya cij , waktu perjalanan tij , dan jarak dij yang dikaitkan dengan sikuen dari pelanggan i ke pelanggan j. Diandaikan pula bahwa cij , tij dan dij ukuran yang ekivalen dengan pengaturan sesuai. Biaya wk menyatakan aktivasi kendaraan k ∈ V . Dalam kasus, perusahaan memiliki armadanya sendiri, wk adalah biaya satu-waktu dan dikaitkan dengan biaya tetap untuk pemanfaatan kendaraan k (Tarantilis et al. 2005). Sebaliknya, jika perusahaan mengontrak angkutan luar untuk aktivitas antar atau jemput, wk menyajikan biaya sewa untuk kendaraan k ∈ V . Namun armada sewa biasanya didasarkan pada jarak total perjalanan dari titik muat awal hingga pelanggan akhir untuk setiap kendaraan pelayanan. Semua rute harus memenuhi kendala kapasitas dan waktu. Kendala terbatasnya waktu menyatakan bahwa suatu kendaraan tidak dapat melayani pelanggan i sebelum batas bawah ei dan setelah batas atas li . Namun, suatu kendaraan dapat tiba sebelum batas bawah batasan waktu dan menunggu (waktu tunggu Wt) sampai waktu pelayanan dimulai. Kendala kapasitas mengharuskan bahwa total kuantitas barang yang diantar atau dijemput tidak dapat melebihi kapasitas C dari kendaraan.


19 Diperlukan tiga kelompok variabel. Kelompok pertama memodelkan sikuen dalam nomor kendaraan mengunjungi pelanggan dan didefenisikan sebagai:    1 Jika pelanggan i mendahului pelanggan j dikunjungi oleh kendaraan k k xij =   0 Jika tidak (4.1)

Kelompok kedua diperlihatkan oleh ai dan pi untuk setiap pelanggan i, menspesifikasi waktu tiba-berangkat ke/dari pelanggan i berurut-turut. Akhirnya zk variabel liner yang didefenisikan sebagai:    1 Jika kendaraan k aktif zk =   0 Jika tidak

(4.2)

Suatu kendaraan di pandang aktif apabila ia melayani sekurang-kurangnya satu pelanggan. Jadi, problem dapat di formulasikan sebagai berikut: min

|V | P n n P P

Cij Xijk +

k=1 j=1 i=1

dengan kendala

|V | P n P

|V | P

wk zk

(4.3)

k=1

xkij = 1

∀ j = 2, 3, . . . , n

(4.4)

k=1 i=1 |V | P n P

xkij = 1 ∀ i = 2, 3, . . . , n

(4.5)

k=1 j=1

xkij ≤ zk , n P i=1

xkin − P

n P

xknj

∀ i, j = 2, 3, . . . , n

∀ k = 2, 3, . . . , |V |. ∀ n = 1, 2, . . . , n

(4.6) (4.7)

j=1

xkij ≤ |s| − 1, ∀s ≤ L, 2 ≤ |s| ≤ n, ∀k ∈ V

(i,j)∈sxs n P i=1

qi

n P

xkij

!

≤C

∀ k = 1, 2, . . . , |V |

j=1


(4.8) (4.9)

20 aj ≥ (pi + tij ) − (1 − xkij )M

∀ k = 1, 2, . . . , |V | ∀ i, j = 1, 2, . . . , n (4.10)

aj ≤ (pi + tij ) + (1 − xkij )M

∀ k = 1, 2, . . . , |V | ∀ i, j = 1, 2, . . . , n (4.11)

ai ≤ pi − si

∀ i = 2, 3, . . . , n

(4.12)

ei ≤ pi ≤ li

∀ i = 2, 3, . . . , n

(4.13)

p1 = 0

(4.14)

xkij ∈ {0, 1}

∀ k = 1, 2, . . . , |V |,

∀ i, j = 1, 2, . . . , n

(4.15)

zk ∈ {0, 1}

∀ k = 1, 2, . . . , |V |,

∀ i, j = 1, 2, . . . , n

(4.16)

Fungsi objektif (4.3) menyatakan keseimbangan antara biaya rute dan kendaraan. Suku pertama dari (4.3) merefleksikan biaya dari rute diikuti oleh semua kendaraan setelah mereka berangkat dari depot, demikian pula biaya dari sequen pertama tiap rute. Suku kedua dari (4.3) menyatakan biaya set up total kendaraan (Ioannou et al. 2001). Kendala (4.4) dan (4.5) memastikan bahwa secara tepat satu kendaraan masuk dan berangkat dari setiap pelanggan dan dari depot. Kendala (4.6) menghubungkan variabel x dan z dengan memastikan bahwa semua pelanggan telah dilayani oleh kendaraan aktif (kendaraan dengan zk = 1). Kendala (4.7) merupakan persamaan konservasi aliran yang menjamin kontinuitas rute tiap kendaraan. Kendala (4.8) mengeliminasi sub-perjalanan dan kendala (4.9) mengajukan batas atas yang sama dengan kapasitas kendaraan C dengan permintaan total pelanggan yang dimuat pada setiap kendaraan. Kendala (4.10)(4.11) dikaitkan dengan keterbatasan waktu dan menjamin kelayakan dari jadwal untuk tiap kendaraan. Khususnya, jika pelanggan i dan j berurutan dalam jadwal kendaraan k, maka waktu tiba dipelanggan j sama dengan waktu berangkat dari pelanggan i ditambah waktu perjalanan antara kedua pelanggan (M bilangan sangat besar). Dalam kasus i dan j tidak dilayani oleh kendaraan sama


21 atau tidak berurutan, kendala (4.10) dan (4.11) tidak aktif. Juga kendala (4.12)(4.13) menjamin bahwa hubungan antara waktu tiba, waktu berangkat dan waktu pelayanan terhadap pelanggan i kompatibel terhadap batasan waktu pelanggan. Kendala (4.14) menyiapkan waktu berangkat dari depot sama dengan nol, karena semua rute dimulai dari depot akhirnya kendala (4.15) dan (4.16) mendefenisikan peubah x dan z untuk kendaraan k


BAB 5 KESIMPULAN

5.1 Kesimpulan Vehicle routing problem terbuka, kendaraan tidak wajib kembali ke depot setelah selesai melayani pelanggan. Open Vehicle Routing Problem dengan time windows (OVRPTW) mencakup tiga subproblem yaitu: antaran, jemputan, dan antar dan jemput. Diperlukan tiga kelompok variabel untuk memodelkan OVRPTW, kelompok pertama memodelkan sikuen dalam nomor kendaraan, kelompok kedua menspesifikasikan waktu dan kelompok ketiga adalah kendaraan aktif. Jenis pemecahan masalah untuk menemukan rangkaian rute kembali non-depot, untuk beberapa armada kendaraan berkapasitas harus memenuhi permintaan pelanggan dalam tenggat waktu tertentu yang menggambarkan tenggat waktu pelayanan paling awal dan tenggat waktu paling akhir, sehingga seluruh pelanggan terlayani. Suatu model matematika mencakup rumusan semua aspek pengambilan dari masalah dan semua perhatian kritik praktis digabungkan pada model. Kerangka dasar dari pemodelan adalah program integer.


DAFTAR PUSTAKA

B. Kallehauge, J.Larsen, and O. B. Madsen. Lagrangean duality applied on vehicle routing with time windows experimental result. Ttechnical Report IMMREP- 2000-8, Informatics and Mathematical modelling, Technical University of Denmark, DTU, Richard Petersens Plads, Building321, DK-2800 Kgs. Lyngby, 2001. Bodin L, Golden B, Assad A, Ball M 1983.Routing and scheduling of vehicle and crews: The state of the art. Comput Oper Res 10: 63 211. Brandao J. 2004. A tabu search heuristic algorithm for oven vehicle routing problem. Eur J Oper Res 157: 552 -564. Clark G, Wright JW 1964. Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12: 568 -581. D Aksen, Z Ozurt and N Aras. 2006. The open vehicle routing problem with driver nodes and time deadlines. Koc University, Istanbul, Turkey; and Bogazici Univercity, Istanbul, Turkey. J Oper Res 1: 1-3. Fleszar K, I. H. Osman and K. S. Hindi. 2008. A variable neigboorhood Search Algorithm for The Open Vehicle Routing Problem. European Journal of Operational Research. vol 58 Fu Z, Eglese R, Li LYO (2005).A new tabu search heuristic for the open vehicles routing problem.J Oper Res Soc 56: 267 274. Fu Z, Eglese R, Li LYO (2005). Corrigendum A new tabu search heuristic for the open vehicles routing problem. J Oper Res Soc 56: 267 274. Hvattum, L.M; Lokketangen, A and Laporte, G. 2006. ”Solving a Dynamc and Stochastic Vehicle Routing Problem with a Sample Scenario Hedging Heuristic” Transportation Science; vol. 40, no. 4, Nov, pp. 421-438. IDSIA Instituto Dalle Molle di Studi sull Intelegensia Artificiale. 2007. ”Vehicle Routing Problem”. http://www.idsia.ch/. Tanggal akses: 12 Desember 2007. Ioannou G., Kriticos M. N. and Prastacos G.P. 2001. A Greedy look ahead heuristic for the vehicle routing problem with time windows. Journal of Operational Research Society. Vol. 52. pp. 552-558. Letchford E, Lysgaard J, and Eglese RW. 2006. A brach-and-cut algorithm for the capacitated open vehicle routing problm. Working paper available at the URL address http://www.hha.dk/˜lys/. Li F, Golden B, and Wasil E. 2006. The open vehicle routing problem: algorithms, large-scale test problems, and computational result. Comput Oper Res, to appear.


24 P Toth and D Vigo (eds). 2000. THE Vehicle Routing Problems. SIAM Monographs on Discrete Mathematics and Aplications. Pisinger D and Ropke S (2006). A general heuristic for vehicle routing problems. Comput Oper Res , to appear. Ralphsy T. K, Kopmanz L, Pulleyblankx WR, and Trotter L.E. 2001. ”On the Capacitated Vehicle Routing Problem” Revisi December 17,2001 Repoussis. P.P, CD Tarantilis and G. Ioannou. 2007. The Open Vehicle Routing Problem with Time Windows, Journal of Operational Research Society. vol. 58, pp. 355 367. Rochet Y and Tailard ED. 1995. Probabilistic diversification and intensification in local search for vehicle routing. J Heuristic 1: 147-167. Sariklis D, and Powell S. 2000. A heuristic method for the open vehicle routing problem. J Oper Res Soc 51: 564-573. Sariklis D, Powel S 2000. A heuristic method for open vehicle routing problems. J Oper Res Soc 51: 564 Schrage L. 1981. Formulation and structure of morecomplex/rrealistic routing and scheduling problems. Networks 11: 229-232. Tarantilis CD, and Kiranoudis CT. 2000. Distribution of fresh meat. J Food Eng 51: 85-91. Tarantilis CD, Diakoulaki D, Kiranoudis CT (information system and efficient routing algorithms for reallife distribution) 2004. Combination of geographical operations. Eur J Oper Res 152: 437-453. Tarantilis CD, Ioannou G, Kiranoudis CT,Prastacos GP. 2005. Solving the open vehicle routing problem via single parameter meta-heuristic algorithm. J Oper Res Soc 56: 588-596.


PEMODELAN VEHICLE ROUTING PROBLEM TERBUKA DENGAN KETERBATASAN WAKTU

Recommend Documents