ALGORITMA MULTIPLE ANT COLONY SYSTEM PADA VEHICLE ROUTING PROBLEM WITH TIME WINDOWS SKRIPSI

UNIVERSITAS INDONESIA

ALGORITMA MULTIPLE ANT COLONY SYSTEM PADA VEHICLE ROUTING PROBLEM WITH TIME WINDOWS

SKRIPSI

SISKA AFRIANITA

0706261934

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM PROGRAM STUDI SARJANA MATEMATIKA DEPOK DESEMBER 2011

Algoritma multiple..., Siska Afrianita, FMIPA UI, 2011

UNIVERSITAS INDONESIA

ALGORITMA MULTIPLE ANT COLONY SYSTEM PADA VEHICLE ROUTING PROBLEM WITH TIME WINDOWS

SKRIPSI Diajukan sebagai salah satu syarat untuk memperoleh gelar sarjana sains

SISKA AFRIANITA 0706261934

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM PROGRAM STUDI SARJANA MATEMATIKA DEPOK DESEMBER 2011


HALAMAN PERNYATAAN ORISINALITAS

Skripsi ini adalah hasil karya sendiri, dan semua sumber baik yang dikutip maupun dirujuk telah saya nyatakan dengan benar.

iii


HALAMAN PENGESAHAN

Skripsi ini diajukan oleh Nama NPM Program Studi Judul Skripsi

: : : :

Siska Afrianita 0706261934 Sarjana Matematika Algoritma Multiple Ant Colony System pada Vehicle Routing Problem with Time Windows

Telah berhasil dipertahankan di hadapan Dewan Penguji dan diterima sebagai bagian persyaratan yang diperlukan untuk memperoleh gelar Sarjana Sains pada Program Studi S1 Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia.

Ditetapkan di Tanggal

: Depok : 16 Desember 2011

iv


KATA PENGANTAR

Alhamdulillah, puji syukur kepada Allah swt. atas semua rahmat dan karunia yang telah Dia berikan sehingga penulis dapat menyelesaikan tugas akhir ini. Penulis sadar bahwa penyelesaian tugas akhir ini tidak terlepas dari bantuan dan dukungan dari berbagai pihak. Oleh karena itu, pada kesempatan ini penulis ingin mengucapkan terima kasih kepada pihak-pihak yang telah berjasa dalam penulisan tugas akhir ini maupun selama penulis kuliah. Ucapan terima kasih ditujukan kepada: 1. Rahmi Rusin, S.Si, M.Sc.Tech, selaku pembimbing I dan Dhian Widya, S.Si, M.Kom selaku pembimbing II yang telah meluangkan waktu dan pikiran serta memberikan saran serta semangat untuk penulis dalam menyelesaikan tugas akhir ini. 2. Dr. Yudi Satria, M.T. selaku ketua departemen, Rahmi Rusin, S.Si, M.Sc.Tech selaku sekretaris departemen, dan Dr. Dian Lestari selaku koordinator pendidikan yang telah membantu proses penyelesaian tugas akhir ini. 3. Dra. Ida Fithriani, M. Si selaku pembimbing akademik penulis, yang telah memberikan arahan serta dukungan selama proses perkuliahan sampai proses penyelesaian tugas akhir ini. 4. Seluruh staf pengajar di Departemen Matematika UI atas ilmu pengetahuan yang telah diberikan. 5. Seluruh karyawan (Mba Santi, Pak Saliman, Mba Rusmi, Pak Wawan, dkk) di Departemen Matematika UI atas bantuan yang telah diberikan. 6. Mama, Papa dan Adik-adik (Anggi, Robby dan Keysha) tercinta yang selalu memberikan doa, nasihat, semangat, dukungan dan perhatian. 7. Tante Rini beserta keluarga dan Nenek tersayang yang telah memberikan semangat dan dukungan kepada penulis terutama selama penyusunan skripsi ini.

v


8. Hikma, Andi, Siti, Riski, Syahrul, Zulfalah, Yoshanda, Putri, Mitha, Misda, Sica, Adi, Kak Stefano, Dheni dan teman-teman lain yang telah berjuang bersama selama penyusunan skripsi. 9. Wiwi, Dita, Stefi, Widi, Gamar, Anjar, Shafa, Isna, Shafira, Nora, Lois, Farah, Winda, Widya, Manda, Nene, Arip, Anis, Zul, Adit, Ferdy, Bowo, Ayat, Afni, Fauzan, Hanif, dan semua teman-teman angkatan 07 tercinta. 10. Ayin, Frida, Uli, Dini, Lala, Kiki, Hendri, Yudo, Pandu, Icon, Eka serta sahabat-sahabat penulis yang memberikan dukungan dan semangat. 11. Yaqozho Tunnisa sebagai teman, sahabat serta saudari yang senantiasa memberi dukungan dan perhatian kepada penulis. 12. Rino Isma Aditya Saputra yang selalu memberikan semangat serta dukungan untuk tetap berusaha menyelesaikan tugas akhir ini. 13. Semua teman-teman di Matematika UI angkatan 2008, 2009, 2010 dan 2011 terima kasih atas semangat dan dukungannya selama masa perkuliahan.

Penulis juga ingin mengucapkan terima kasih kepada seluruh pihak yang tidak disebutkan satu per satu, yang telah membantu dalam penyusunan skripsi ini. Akhir kata, penulis mohon maaf jika terdapat kesalahan atau kekurangan dalam skripsi ini. Penulis berharap semoga skripsi ini bermanfaat bagi pembaca.

Penulis 2011

vi


HALAMAN PERNYATAAN PERSETUJUAN PUBLIKASI TUGAS AKHIR UNTUK KEPENTINGAN AKADEMIS

` Sebagai sivitas akademik Universitas Indonesia, saya yang bertanda tangan di bawah ini: Nama NPM Program Studi Departemen Fakultas Jenis karya

: : : : : :

Siska Afrianita 0706261934 Sarjana Matematika Matematika Matematika dan Ilmu Pengetahuan Alam Skripsi

demi pengembangan ilmu pengetahuan, menyetujui untuk memberikan kepada Universitas Indonesia Hak Bebas Royalti Noneksklusif (Non-exclusive Royalty Free Right) atas karya ilmiah saya yang berjudul : Algoritma Multiple Ant Colony System pada Vehicle Routing Problem with Time Windows. beserta perangkat yang ada (jika diperlukan). Dengan Hak Bebas Royalti Noneksklusif ini Universitas Indonesia berhak menyimpan, mengalihmedia/format-kan, mengelola dalam bentuk pangkalan data (database), merawat, dan memublikasikan tugas akhir saya selama tetap mencantumkan nama saya sebagai penulis/pencipta dan sebagai pemilik Hak Cipta. Demikian pernyataan ini saya buat dengan sebenarnya.

vii


ABSTRAK

Nama : Siska Afrianita Program Studi : Matematika Judul : Algoritma Multiple Ant Colony System pada Vehicle Routing Problem with Time Windows Vehicle Routing Problem with Time Windows (VRPTW) merupakan permasalahan kombinatorik yang sering terjadi pada sistem pendistribusian barang. VRPTW adalah masalah penentuan rute sejumlah kendaraan untuk mendistribusikan barang ke sejumlah pelanggan dengan biaya minimum. Kendaraan yang digunakan memiliki kapasitas serta setiap kendaraan memulai dan mengakhiri perjalanan di depot. Setiap pelanggan yang dilayani akan memberikan time windows dan setiap pelanggan hanya boleh dilayani satu kali. Untuk memperoleh tujuan VRPTW, ada dua tujuan yang harus dicapai yaitu meminimumkan banyaknya kendaraan yang digunakan dan meminimumkan total waktu tempuh kendaraan. Pada skripsi ini akan digunakan algoritma Multiple Ant Colony System (MACS) yang dikembangkan dari algoritma Ant Colony System (ACS) yang termasuk dalam Ant Colony Optimization (ACO). ACO merupakan suatu metode metaheuristik yang terinspirasi dari perilaku hewan yaitu semut. Pada algoritma MACS ini, terdapat dua koloni semut yang masing-masing akan mengoptimisasi tujuan yang akan dicapai pada VRPTW. Kata Kunci

: Vehicle Routing Problem with Time Windows (VRPTW), Ant Colony System, Ant Colony Optimization (ACO) xii + 49 halaman ; 10 gambar Daftar Pustaka : 9 (1997-2007)

viii

Universitas Indonesia


ABSTRACT

Name : Siska Afrianita Study Program : Mathematics Title : Multiple Ant Colony System (MACS) Algorithm for Vehicle Routing Problem with Time Windows (VRPTW) Vehicle Routing Problem with Time Windows (VRPTW) is one of combinatorial problems which mostly happen in a logistic system. VRPTW is an optimization problem which aims to minimize cost of using fleets of vehicles. The vehicles start and end the route at depot must serve or distribute goods to several customers. Every customer gives time windows and should be visited only once. The objective of VRPTW can be reached by multiple objectives. First, minimizes number of vehicles used, and then minimizes the total travel time. In this final project, it will be used Multiple Ant Colony System algorithm for solving VRPTW. MACS is based on Ant Colony System (ACS) algorithm which is one of Ant Colony Optimization (ACO). ACO is a metaheuristic method inspired by foraging behavior of real colonies of ant. MACS algorithm consider a hierarchical objective for solving VRPTW and these objectives would be optimized by two colonies of ants. Keywords xii + 49 pages Bibliography

: Vehicle Routing Problem with Time Windows (VRPTW), Ant Colony System. ; 10 pictures : 9 (1997-2007)

ix



DAFTAR ISI

HALAMAN JUDUL …………………………………….……………………… ii HALAMAN PERNYATAAN ORISINALITAS ................................................. iii HALAMAN PENGESAHAN ............................................................................. iv KATA PENGANTAR ......................................................................................... v HALAMAN PERNYATAAN PERSETUJUAN PUBLIKASI ........................... vii ABSTRAK ....................................................................................................... viii ABSTRACT ....................................................................................................... ix DAFTAR ISI ....................................................................................................... x DAFTAR GAMBAR .......................................................................................... xi DAFTAR TABEL ............................................................................................. xii BAB 1 PENDAHULUAN................................................................................... 1 1.1 Latar Belakang ............................................................................................. 1 1.2 Perumusan Masalah dan Ruang Lingkup ...................................................... 4 1.3 Jenis Penelitian ............................................................................................. 4 1.4 Tujuan penelitian .......................................................................................... 4 BAB 2 LANDASAN TEORI .............................................................................. 5 2.1 Teori Graf ..................................................................................................... 5 2.2 Vehicle Routing Problem (VRP) ................................................................... 6 2.3 Vehicle Routing Problem with Time Windows (VRPTW) .............................. 8 2.4 Ant Colony Optimization (ACO) ................................................................. 16 2.5 Ant Colony System (ACS) ........................................................................... 20 2.5.1 2.5.2 2.5.3

ACS Ant Activity ............................................................................. 21 Local Pheromone Trail Update ....................................................... 21 Global Pheromone Trail Update ..................................................... 22

2.6 Local Search............................................................................................... 22 BAB 3 MULTIPLE ANT COLONY SYSTEM PADA VEHICLE ROUTING PROBLEM WITH TIME WINDOWS .............................................................. 24 3.1 Algoritma MACS Untuk Menyelesaikan VRPTW ...................................... 24 3.2 Model Solusi MACS Untuk Menyelesaikan VRPTW ................................. 27 3.3 Inisialisasi Solusi Awal ............................................................................... 28 3.4 Prosedur Konstruksi New_Active_Ant ......................................................... 31 3.5 Tahapan Pada Koloni ACS_VEI ................................................................. 35 3.6 Tahapan Pada Koloni ACS_TIME .............................................................. 43 BAB 4 ............................................................................................................... 48 KESIMPULAN ................................................................................................ 48 DAFTAR PUSTAKA ....................................................................................... 49

x



DAFTAR GAMBAR

Gambar 2.1 (a) Graf lengkap tidak berarah dan berbobot dan (b) Graf lengkap tidak berarah .................................................................................... 5 Gambar 2.2 Ilustrasi VRPTW (a) Rute kendaraan, (b) Time windows ................. 12 Gambar 2.3 Skema algoritma-algoritma ACO .................................................... 17 Gambar 2.4 Contoh intra-route .......................................................................... 23 Gambar 2.5 Contoh inter-route .......................................................................... 23 Gambar 3.1 Dua koloni pada MACS………………………………………….... 25 Gambar 3.2 Diagram alir proses algoritma MACS ………………………...…... 26 Gambar 3.3 (a) Solusi layak, (b) Solusi tidak layak ............................................ 27 Gambar 3.4 Diagram alir metode nearest neighbor heuristic .............................. 29 Gambar 3.5 Prosedur local search...................................................................... 34 Gambar 3.6 Distribusi probabilitas kumulatif ..................................................... 40

xi



DAFTAR TABEL

Tabel 2.1 Waktu tempuh antara depot dan setiap pelanggan ............................... 13 Tabel 2.2 Time windows dan jumlah permintaan setiap pelanggan...................... 14 Tabel 3.1 Pengecekan kriteria pelanggan............................................................ 30 Tabel 3.2 Inisialisasi pheromone pada koloni ACS_VEI .................................... 37 Tabel 3.3 Hasil pengecekan simpul untuk depot terduplikasi pertama ................ 37 Tabel 3.4 Nilai visibility yang diperoleh ............................................................. 38 Tabel 3.5 Hasil pengecekan untuk simpul 4 ....................................................... 39 Tabel 3.6 Rute agen 1 pada koloni ACS_VEI ..................................................... 40 Tabel 3.7 Rute agen 2 pada koloni ACS_VEI ..................................................... 41 Tabel 3.8 Global updating pheromone pada

............................ 42

Tabel 3.9 Global updating pheromone pada

di ACS_VEI .......................... 42

Tabel 3.10 Inisialisasi pheromone pada koloni ACS_TIME ............................... 44 Tabel 3.11 Rute agen 1 pada koloni ACS_TIME ................................................ 44 Tabel 3.12 Rute agen 2 pada koloni ACS_TIME ................................................ 45 Tabel 3.13 Global updating pheromone pada

xii

di ACS_TIME ..................... 46



BAB 1 PENDAHULUAN

1.1

Latar Belakang

Di bidang transportasi, permasalahan menentukan rute dan penjadwalan kendaraan termasuk permasalahan optimisasi kombinatorik yang mempengaruhi sistem logistik (pendistribusian barang). Permasalahan menentukan rute kendaraan yang digunakan untuk mendistribusikan barang ke sejumlah pelanggan dari suatu depot dengan tujuan meminimumkan total biaya perjalanan yang memenuhi kendala-kendala yang diberikan lebih dikenal dengan istilah Vehicle Routing Problem (VRP). Beberapa contoh kendala yang diberikan adalah kapasitas kendaraan, keterbatasan aksesibilitas pelanggan, permintaan pick-ups delivery dan time windows atau kendala waktu (Cordeau dkk, 2007). VRP yang memiliki kendala kapasitas kendaraan dengan penambahan kendala time windows yang diberikan oleh setiap pelanggan untuk menerima barang dan time window yang ditentukan oleh depot lebih dikenal dengan Vehicle Routing Problem with Time Windows (VRPTW) (Gambardella, 1999). Time windows pelanggan didefinisikan sebagai interval waktu yang diberikan oleh setiap pelanggan untuk menerima barang sesuai dengan waktu yang diinginkan sehingga tidak mengganggu kegiatan pelanggan tersebut dan time window depot didefinisikan sebagai batas waktu kendaraan kembali ke depot. Sebagai contoh time windows pelanggan adalah waktu yang diinginkan pelanggan untuk menerima barang (ready time), interval waktu pelayanan pengiriman barang (service time), dan batas waktu penerimaan barang (due date) (Gambardella, 1999). Permasalahan VRPTW dapat diaplikasikan ke berbagai permasalahan optimisasi seperti food delivery, mailing newspapers, urban trash collection, snow cleaning routes, rute bus sekolah, dan lain-lain. Karena VRPTW merupakan salah satu contoh dari NP hard problem, maka metode eksak tidak dapat digunakan untuk menemukan solusi yang optimal dengan ukuran permasalahan

1



2

yang cukup besar dalam waktu komputasi yang wajar. Metode eksak akan lebih efisien jika solusi yang diperoleh dibatasi oleh time windows yang singkat sehingga kombinasi dari pelanggan akan lebih sedikit dan memungkinkan memperoleh solusi yang optimal (Gambardella, 1999). Pada tahun 1997, Kohl dkk. berhasil memperoleh solusi VRPTW yang melayani 100 pelanggan. Sedangkan untuk permasalahan yang cukup besar, ada beberapa contoh metode pendekatan yang dikembangkan seperti metode heuristik (Construction Heuristics, Improvement Heuristics) atau metode metaheuristik (Tabu Search, Genetic Algorithm, Simulated Annealing dan Ant Colony Optimization). Penyelesaian VRPTW dengan menggunakan metode heuristik atau metode metaheuristik akan lebih efisien dari sisi waktu perhitungan untuk mendapatkan solusi dibandingkan dengan metode eksak. Namun metode heuristik atau metode metaheuristik tidak selalu menghasilkan solusi yang optimal (Cordeau dkk, 2007). Pada skripsi ini akan digunakan salah satu metode metaheuristik yang termasuk dalam algoritma Ant Colony Optimization (ACO) untuk menyelesaikan VRPTW. ACO merupakan metode optimisasi berbasis swarm intelligence, yang terinspirasi dari perilaku hewan yaitu perilaku semut. Pada kehidupan nyata, semut-semut akan meninggalkan sarang untuk mencari jalur menuju sumber makanan dan kembali ke sarangnya. Selama proses pencarian jalur menuju sumber makanan tersebut, semut mengeluarkan substansi aromatik yang disebut pheromone, sehingga dalam perjalanan tersebut akan terbentuk jalur pheromone. Semakin sering suatu jalur dilalui oleh semut maka intensitas pheromone pada jalur tersebut semakin kuat, sebaliknya jalur yang tidak dilewati oleh semut maka intensitas pheromone pada jalur tersebut akan berkurang. Berkurangnya intensitas pheromone terjadi karena adanya evaporasi, yaitu proses penguapan pheromone. Pada ACO, semut dinyatakan sebagai agen. Agen-agen inilah yang mencari solusi dari masalah optimisasi. Pencarian solusi pada ACO terdiri dari pemilihan jalur yang akan dilalui agen dan pembaharuan intensitas pheromone. Fenomena pada perilaku koloni semut dikategorikan sebagai artificial inteligence dan menghasilkan kumpulan algoritma Ant Colony Optimization (ACO) (Dorigo dkk, 2006).

Universitas Indonesia Algoritma multiple..., Siska Afrianita, FMIPA UI, 2011

3

Algoritma-algoritma yang termasuk dalam ACO adalah Ant System (AS) (1991), Ant-Q (1995), Ant Colony System (ACS) (1996), Max-Min Ant System (MMAS) (1997), Ant System Rank (AS-Rank) (1999), dan Best-Worse Ant System (2000). Hal yang membedakan algoritma-algoritma ACO adalah aturan pemilihan jalur dan aturan pembaharuan pheromone pada jalur (ant activity), serta aturan pembaharuan pheromone yang dilakukan hanya pada beberapa solusi yang diperoleh (daemon activity) (Dorigo dkk, 2006). Pada awalnya ACO digunakan untuk menyelesaikan masalah Travelling Salesman Problem (TSP), yang selanjutnya dikembangkan dan digunakan untuk menyelesaikan masalah optimisasi lainnya, antara lain: tipe masalah routing seperti VRP, masalah penugasan seperti sequential ordering dan quadratic assignment, masalah penjadwalan, multiple knapsack dan graph colouring. Algoritma pada ACO yang berhasil digunakan untuk menyelesaikan VRPTW adalah Ant Colony System (ACS) (Cordeau dkk, 2007). Beberapa algoritma dari ACO yang telah dibahas pada skripsi di Departemen Matematika Universitas Indonesia, yaitu Max-Min Ant System untuk menyelesaikan General Assignment Problem (GAP) oleh Lisa di tahun 2005, Ant System dan Ant System 3-Opt untuk menyelesaikan Travelling Salesman Problem (TSP) oleh Ni Made di tahun 2007, serta Ant-Q dan Ant- Q 3-Opt untuk menyelesaikan TSP oleh Dhini di tahun 2007. Pada skripsi ini, algoritma ACO yang akan digunakan adalah algoritma Ant Colony System (ACS) yang dikembangkan untuk menyelesaikan VRPTW. Algoritma ACS dikembangkan menjadi algoritma Multiple Ant Colony System (MACS) yang dapat digunakan untuk menyelesaikanVRPTW. Algoritma MACS memiliki tujuan hirarki untuk menyelesaikan VRPTW, tujuan ini akan dioptimisasi oleh dua koloni semut dimana setiap koloni menerapkan algoritma ACS. Koloni pertama memiliki tujuan untuk meminimumkan banyaknya kendaraan yang digunakan untuk melayani sejumlah pelanggan, sedangkan koloni kedua meminimumkan total waktu tempuh kendaraan. Selama proses pembentukan rute pelanggan yang akan dilayani, semut pada setiap koloni melakukan pembaharuan intensitas pheromone secara lokal. Setelah solusi rute perjalanan terbaik diperoleh, intensitas pheromone


4

diperbaharui secara global. Solusi terbaik dari rute perjalanan dengan total waktu tempuh minimum inilah yang menjadi solusi dari VRPTW.

1.2

Perumusan Masalah dan Ruang Lingkup

Bagaimana algoritma MACS diterapkan dalam penyelesaian Vehicle Routing Problem with Time Windows? Ruang lingkup dari skripsi ini adalah penyelesaian VRPTW menggunakan algoritma MACS dengan contoh permasalahan yang disesuaikan dengan data Benchmark.

1.3

Jenis Penelitian

Penelitian dilakukan dengan studi pustaka.

1.4

Tujuan penelitian

Penulisan skripsi ini bertujuan untuk menjelaskan algoritma MACS untuk menyelesaikan VRPTW.


BAB 2 LANDASAN TEORI

Pada bab ini akan diberikan dasar-dasar teori yang digunakan untuk menyelesaikan Vehicle Routing Problem with Time Windows (VRPTW) yang meliputi teori graf, Vehicle Routing Problem (VRP), Ant Colony Optimization (ACO), Ant Colony System (ACS), dan local search.

2.1

Teori Graf

Suatu graf G adalah suatu pasangan terurut (V, E) dimana V adalah suatu himpunan tak kosong yang berisi simpul-simpul dan E adalah himpunan busur. Busur yang menghubungkan simpul i dan j dinotasikan sebagai

.

Beberapa contoh dari graf misalkan graf berarah (graf yang setiap busurnya mempunyai arah), graf tidak berarah (graf yang setiap busurnya tidak mempunyai arah), graf berbobot (graf yang setiap busurnya mempunyai bobot) serta graf lengkap (graf yang setiap simpulnya terhubung dengan simpul yang lain). Pada Gambar 2.1 ditunjukan contoh graf: (a) graf lengkap tidak berarah dan berbobot dengan 4 simpul dan (b) graf lengkap berarah dengan 5 simpul. 1 C12

1 C13

C23

2 C14

3

C24

2

3

4 C34 4

5

Gambar 2.1 (a) Graf lengkap tidak berarah dan berbobot dan (b) Graf lengkap berarah

5



6

Pada umumnya graf digunakan untuk memodelkan masalah dengan merepresentasikan objek-objek dan hubungan antara objek tersebut dengan simpul dan busur. Busur yang menghubungkan simpul dapat digunakan untuk merepresentasikan suatu hubungan sembarang antara objek-objek tertentu. Sedangkan bobot pada busur tersebut menyatakan suatu nilai yang terkait pada hubungan sembarang antara simpul.

2.2

Vehicle Routing Problem (VRP)

Permasalahan penentuan rute kendaraan atau Vehicle Routing Problem merupakan salah satu permasalahan optimisasi kombinatorik. Tujuan dari VRP adalah bagaimana menentukan rute sejumlah kendaraan yang digunakan untuk mendistribusikan barang dari suatu depot ke sejumlah pelanggan dengan memenuhi beberapa kendala yang diberikan. Beberapa metode optimisasi seperti metode eksak, heuristik atau metaheuristik telah dihasilkan sejak publikasi artikel pertama tentang VRP di awal tahun 1960 yaitu mengenai ‘truck dispatching’ oleh Dantzig dan Ramser (Cordeau dkk, 2007). Berikut beberapa contoh VRP beserta kendalanya : 1. Capacitated Vehicle Routing Problem (CVRP): VRP dengan kendala kapasitas kendaraan. 2. Multiple Depots Vehicle Routing Problem (MDVRP): VRP dengan lebih dari satu depot yang dapat melayani pelanggan. 3. Split Deliveries Vehicle Routing Problem (SDVRP): VRP dengan kondisi pengiriman barang ke pelanggan bisa dilakukan lebih dari satu kali pelayanan. 4. Vehicle Routing Problem with Backhauls (VRPB): VRP dimana pelanggan dapat melakukan permintaan pengiriman atau pengambilan sejumlah barang. Dalam setiap rute kendaraan, pengambilan dilakukan setelah semua pengiriman barang telah selesai. 5. Vehicle Routing Problem with Pickups and Deliveries (VRPPD): VRP dimana pelanggan dapat menerima dan mengirim barang secara


7

bersamaan. Pada VRPPD, pengambilan barang dapat dilakukan secara bersamaan tanpa harus menunggu semua pengiriman selesai. 6. Dynamic Vehicle Routing Problem (DVRP): VRP dimana terdapat penambahan pelanggan baru saat kendaraan sedang melayani pelanggan, sehingga terjadi perubahan rute kendaraan secara spontan. 7. Vehicle Routing Problem with Time Windows (VRPTW): CVRP dengan penambahan time windows pada setiap pelanggan untuk dapat menerima barang dan time window depot. Kendala yang umum terdapat pada VRP adalah kendala kapasitas kendaraan, dimana VRP dengan kendala ini lebih dikenal dengan istilah Capacitated Vehicle Routing Problem (CVRP). Pada CVRP, terdapat sejumlah pelanggan dimana setiap pelanggan meminta pengiriman sejumlah barang. Barang harus diantar dari satu depot dimana tersedia sejumlah kendaraan yang memiliki kapasitas yang seragam. Karena kapasitas kendaraan terbatas, maka kendaraan harus kembali ke depot jika kapasitas muatan kendaraan yang tersisa tidak cukup untuk melayani pelanggan berikutnya. Berdasarkan teori graf, CVRP dapat direpresentasikan oleh graf lengkap dan berbobot G (V, E) yang memiliki himpunan simpul dimana

dan himpunan busur

merupakan simpul depot (tempat setiap kendaraan memulai dan

mengakhiri rute perjalanan) dan simpul lain menunjukkan letak atau posisi pelanggan yang harus dikunjungi. Setiap simpul i memiliki sejumlah permintaan yang dinotasikan sebagai

dimana

untuk depot. Setiap busur

menunjukkan bahwa simpul i dan j terhubung dan setiap busur memiliki bobot yang menyatakan waktu tempuh (travel time) antara simpul i dan j. Tujuan dari CVRP adalah menemukan rute perjalanan yang memiliki total waktu tempuh minimum (minimum total travel time) dengan batasan berikut: setiap rute dimulai dan diakhiri di depot, setiap pelanggan dikunjungi hanya satu kali oleh satu kendaraan dan banyaknya barang yang dikirim tidak boleh melebihi kapasitas kendaraan (Gambardella, 1999). Ketika setiap pelanggan memberikan informasi tambahan mengenai interval waktu (time windows) pengiriman barang serta waktu pelayanan kepada depot dan depot juga memberikan time window maka terdapat tambahan kendala Universitas Indonesia Algoritma multiple..., Siska Afrianita, FMIPA UI, 2011

8

waktu pada permasalahan CVRP. Permasalahan seperti ini lebih dikenal sebagai Vehicle Routing Problem with Time Windows (VRPTW ) yang akan dibahas pada Subbab 2.3.

2.3

Vehicle Routing Problem with Time Windows (VRPTW)

Vehicle Routing Problem with Time Windows (VRPTW) dapat direpresentasikan oleh graf berarah dan berbobot G (V, E) yang memiliki himpunan simpul

dimana 0 dan n +1 menunjukkan simpul

yang sama yaitu depot dan {1,2,…,n} menunjukkan sejumlah pelanggan yang harus dilayani. Setiap pelanggan memiliki permintaan sejumlah barang yang dinotasikan dengan

. Solusi layak dari rute kendaraan dimulai dari simpul

lalu melayani seluruh pelanggan dan kembali ke simpul

. Himpunan

kendaraan yang seragam dengan kapasitas Q yang tersedia di depot dinotasikan dengan K. Misalkan

menyatakan waktu pelayanan (service time) pada simpul i

(dimana

) dan

Time window

menyatakan waktu tempuh antara simpul i dan j.

berkaitan dengan simpul pelanggan i dimana

sedangkan time windows

dan

berkaitan dengan

simpul depot. Jika tidak ada batasan khusus terhadap jumlah kendaraan yang tersedia, dapat dinyatakan bahwa {

}

{

}

(Cordeau dkk, 2007). VRPTW merupakan CVRP dengan tambahan kendala time windows yang diberikan oleh setiap simpul pelanggan i dimana waktu kendaraan tiba pada simpul i boleh sebelum time windows dimulai, yang artinya kendaraan harus menunggu (ketika kendaraan menunggu tidak dikenakan biaya tambahan) dan kendaraan harus tiba sebelum time windows yang diberikan berakhir. Selain itu, depot juga mempunyai batas awal dan akhir kendaraan untuk memulai perjalanan dan kembali ke depot. Artinya kendaraan memulai perjalanan ketika time window depot dimulai dan harus kembali ke depot sebelum time window depot berakhir. Universitas Indonesia Algoritma multiple..., Siska Afrianita, FMIPA UI, 2011

9

Tujuan dari VRPTW adalah menentukan rute perjalanan yang memiliki biaya minimum untuk melayani semua permintaan pelanggan dengan memenuhi kendala kapasitas kendaraan, time windows yang diberikan oleh setiap pelanggan dan time window depot. Berikut beberapa asumsi yang digunakan: 

Terdapat sebuah depot dan sejumlah kendaraan yang seragam yang selalu tersedia di depot dengan kapasitas Q untuk mendistribusikan barang ke sejumlah pelanggan.



Kecepatan rata-rata kendaraan yang digunakan konstan dan kemacetan lalu lintas diabaikan.



Setiap kendaraan memulai rute perjalanan dari depot dan kembali ke depot setelah melayani pelanggan.



Data mengenai waktu tempuh antara depot dan setiap pelanggan diberikan.



Setiap pelanggan hanya boleh dikunjungi satu kali oleh satu kendaraan.



Banyaknya permintaan pelanggan yang dilayani oleh setiap kendaraan tidak melebihi kapasitas kendaraan Q.



Setiap pelanggan i memiliki permintaan sejumlah

barang,

,

dan memberikan time windows yang terdiri dari waktu awal (ai), waktu akhir (bi) dan waktu pelayanan

. Time windows ini didefinisikan sebagai

interval waktu yang diberikan pelanggan untuk menerima barang. Time windows yang diberikan setiap pelanggan berada pada interval waktu depot. 

Pengiriman barang ke setiap pelanggan harus memenuhi time window depot [a0,b0]. Time window depot yang dimaksud adalah waktu paling awal untuk kendaraan berangkat dari depot (a0) dan waktu paling akhir untuk kendaraan kembali ke depot (b0).

Berikut akan diberikan model matematis dari VRPTW. Misalkan i menyatakan simpul asal i

dimana

menyatakan himpunan simpul tujuan j yang memiliki kemungkinan untuk dikunjungi setelah melayani simpul i, j menyatakan simpul tujuan j dimana

menyatakan himpunan simpul asal Universitas Indonesia


10

i yang memiliki kemungkinan untuk dikunjungi setelah melayani simpul j. Himpunan kendaraan yang tersedia di depot dinyatakan dengan

Variabel

keputusan untuk masalah VRPTW adalah: { untuk

dan

. Selain terdapat variabel keputusan,

juga terdapat variabel kontinu

yang menunjukkan waktu ketika kendaraan ke-

k mulai melayani simpul i. Formulasi dari VRPTW dengan tujuan meminimumkan total biaya penggunaan kendaraan untuk melayani seluruh pelanggan adalah: ∑ dengan kendala

∑

∑

(2.1)

∑

(2.2)

∑ ∑

∑

∑ (

)

(2.6) (2.7)

∑

∑

(2.8) (2.9)

Pada formulasi fungsi tujuan (2.1),

menyatakan biaya yang dikeluarkan

yang diperoleh dari waktu yang ditempuh kendaraan untuk melayani simpul i lalu menuju simpul j. Selanjutnya kendala (2.2) menyatakan bahwa setiap simpul pelanggan i hanya dikunjungi satu kali oleh satu kendaraan. Kendala (2.3) menyatakan bahwa setiap kendaraan hanya digunakan satu kali dan memulai perjalanan dari depot. Kendala (2.4) menyatakan bahwa kendaraan yang telah melewati beberapa simpul tidak akan kembali melewati simpul tersebut untuk kedua kalinya. Kendala (2.5) menyatakan bahwa setelah seluruh pelanggan terlewati, kendaraan harus kembali ke depot. Kendala (2.6) menyatakan bahwa akumulasi waktu kendaraan k untuk memulai pelayanan simpul i waktu tempuh dari simpul i ke j

beserta waktu pelayanan simpul i

dan

tidak boleh melebihi waktu untuk memulai Universitas Indonesia


11

pelayanan simpul j

, karena jika kondisi ini tidak terpenuhi artinya simpul j

tidak dapat dituju setelah simpul i (dimana waktu pelayanan untuk depot

).

Kendala (2.7) menunjukkan waktu kendaraan k untuk memulai pelayanan simpul i berada pada time window yang diberikan simpul i. Kendala (2.8) menyatakan bahwa banyaknya permintaan dari beberapa simpul yang dilayani oleh kendaraan k tidak boleh melebihi kapasitas kendaraan. Kendala (2.9) mengacu pada variabel keputusan yang merupakan variabel biner. Kendala (2.6) merupakan kendala non linier sehingga permasalahan VRPTW merupakan masalah pemrograman non linier. Kendala pada formulasi ini dapat dijadikan kendala linier sebagai berikut: (2.10) adalah konstanta.

dengan

Solusi layak VRPTW dari formulasi di atas merupakan sekumpulan rute kendaraan yang memiliki total waktu tempuh minimum dengan banyaknya kendaraan yang digunakan untuk melayani semua pelanggan minimum dan memenuhi semua kendala yang diberikan Selanjutnya diberikan ilustrasi mengenai contoh solusi layak dari VRPTW. Pada Gambar 2.2 (a), terdapat satu rute kendaraan yang memulai perjalanan dari depot dan diakhiri di depot dimana pelanggan pertama yang dilewati adalah pelanggan 3 lalu pelanggan 1 kemudian pelanggan 2 dan terakhir pelanggan 4 yang memenuhi semua kendala.

1 2 3

4

depot (a)


12

t3 t1 t2

20

t4

to

0

30

80 85

100 110

120 140

195 200

de

Keterangan:

time windows waktu menunggu waktu pelayanan

(b) Gambar 2.2 Ilustrasi VRPTW (a) Rute kendaraan, (b) Time windows Pada Gambar 2.2 (b) diberikan ilustrasi mengenai time windows, waktu kendaraan menunggu dan waktu pelayanan. Misalkan interval time window depot (t0)= [0,200], time window pelanggan 1 (t1)=[80,100], time window pelanggan 2 (t2)=[110,140], time window pelanggan 3 (t3)=[30,85], time window pelanggan 4 (t4)=[120,195]. Berdasarkan contoh solusi layak pada Gambar 2.2 (a) terlihat bahwa pertama kali depot akan melayani pelanggan 3, misalkan waktu tempuh yang dibutuhkan kendaraan menuju pelanggan 3 adalah 20, sedangkan time windows pelanggan 3 adalah 30 maka kendaraan harus menunggu sampai pelanggan 3 dapat dilayani. Pelanggan berikutnya yang akan dilayani adalah pelanggan 1, misalkan setelah melayani pelanggan 3, waktu kendaraan sampai pada pelanggan 1 adalah 95 yang artinya waktu kendaraan tiba berada pada interval time windows yang diberikan pelanggan 1. Kemudian setelah melayani pelanggan 1, terlihat pula pada gambar bahwa waktu tempuh kendaraan seteleah melayani pelanggan 1 berada di luar time windows yang diberikan pelanggan 1 yang artinya waktu setelah melayani pelanggan boleh melebihi time window yang diberikan.


13

Setelah melayani pelanggan 1, kendaraan selanjutnya melayani pengiriman barang ke pelanggan 2 lalu pelanggan 4 tanpa harus menunggu. Hal ini dapat terlihat bahwa anak panah yang menunjukkan waktu ketika kendaraan tiba pada pelanggan 2 dan 4 berada pada interval time window sehingga pelayanan dapat langsung dilakukan. Misalkan waktu yang telah di tempuh kendaraan untuk melayani seluruh pelanggan dan kembali ke depot adalah 195 sedangkan batas akhir waktu yang diberikan depot ( ) adalah 200 sehingga tidak melanggar kendala bahwa kendaraan harus kembali ke depot tanpa melebihi time window yang diberikan depot. Selanjutnya diberikan Contoh 2.1 mengenai formulasi VRPTW beserta penjelasan. Contoh 2.1 Misalkan terdapat 6 pelanggan yang memesan roti ke sebuah toko roti. Roti yang dipesan akan diantarkan oleh pegawai toko dengan menggunakan kendaraan yang memiliki kapasitas 70. Kendaraan-kendaraan tersebut telah disediakan oleh pemilik toko untuk mengantarkan pesanan roti, hanya saja pemilik toko menginginkan penggunaan kendaraan seminimum mungkin agar biaya yang dikeluarkan untuk mengantarkan pesanan tidak mahal. Pegawai hanya bisa mengantarkan pengiriman roti ketika toko roti tersebut dibuka dan pengiriman tidak bisa dilakukan jika toko roti sudah tutup. Jadi, setiap pelanggan memberitahukan waktu yang mereka inginkan kepada pegawai toko untuk menerima roti pesanan mereka. Informasi mengenai pengiriman pesanan roti diberikan dalam Tabel 2.1 dan Tabel 2.2. Tabel 2.1 Waktu tempuh antara depot dan setiap pelanggan D

1

2

3

4

5

6

D

0

29,15

11,18

25

14,14

20,62

15,81

1

29,15

0

36,4

36,4

43,01

20,62

22,36

2

11,18

36,4

0

36,06

15

21,21

26,93

3

25

30,41

36,06

0

30,41

38,08

11,18

4

14,14

43,01

15

30,41

0

33,54

25,5

5

20,62

20,62

21,21

38,08

33,54

0

26,93

6

15,81

22,36

26,93

11,18

25,5

26,93

0


14

Tabel 2.2 Time windows dan jumlah permintaan setiap pelanggan Simpul

Jumlah

Waktu

Waktu

Waktu

Pemintaan

awal

akhir

pelayanan

0/7

0

0

200

0

1

20

120

160

10

2

30

80

150

10

3

15

50

100

10

4

25

40

70

10

5

20

70

110

10

6

25

60

120

10

Pada Tabel 2.1 diberikan informasi waktu tempuh

antara pelanggan

dan lokasi toko yang kemudian disebut menjadi depot. Sedangkan Tabel 2.2 yang menunjukkan jumlah permintaan

, waktu awal ( ), waktu akhir ( ) dan

waktu pelayanan ( ). Dengan

dimana 0 dan 7 adalah depot dan .

Pada Contoh 2.1 di atas, pegawai toko dapat mengirimkan pesanan dalam waktu bersamaan namun tidak boleh ada pengiriman pesanan yang sama dilakukan oleh pegawai yang berbeda artinya pelanggan hanya boleh dilayani satu kali oleh satu pegawai. Setelah pegawai melayani pengiriman pesanan, pegawai harus kembali ke toko sebelum toko ditutup. Jadi pegawai toko harus bisa menentukan pelanggan manakah yang akan dilayani terlebih dahulu. Contoh masalah ini dapat dimodelkan secara matematis berdasarkan model yang telah diberikan sebelumnya. Didefinisikan variabel keputusan { dengan

secara berturut-turut menyatakan simpul asal, menyatakan simpul tujuan dan

menyatakan kendaraan

yang akan digunakan untuk mengirimkan pesanan. Tujuan dari masalah di atas adalah meminimumkan biaya yang dikeluarkan untuk mengirimkan pesanan, sehingga fungsi tujuannya adalah


15 ∑

∑

dimana

dengan kendala berikut ∑ ∑ ∑

(

(

)

(

)

) (

(

)

)

Seperti yang telah disebutkan bahwa untuk menyelesaikan formulasi VRPTW yang merupakan masalah NP- hard problem yang bersifat kombinatorial ada beberapa contoh metode yang telah berhasil digunakan antara lain metode eksak (Langrangian Relaxation Based Algorithm, Column Generation Algorithm, dan A branch-and-cut Algorithm), serta metode heuristik (Construction heuristics, Improvement heuristics). Karena metode eksak tidak efisien untuk menyelesaikan VRPTW berukuran besar sehingga dikembangkan beberapa metode metaheuristik Universitas Indonesia Algoritma multiple..., Siska Afrianita, FMIPA UI, 2011

16

yang berhasil menyelesaikan VRPTW seperti Tabu Search, Genetic Algorithm, Ant Colony Optimization (ACO). Penyelesaian VRPTW pada skripsi ini menggunakan algoritma Multiple Ant Colony System (MACS) yang dikembangkan dari algoritma Ant Colony System (ACS) yang termasuk dalam Ant Colony Optimization ( ACO ). Berikut diberikan penjelasan mengenai Ant Colony Optimization (ACO).

2.4

Ant Colony Optimization (ACO)

Ant Colony Optimization (ACO) adalah kumpulan algoritma untuk menyelesaikan masalah optimisasi khususnya masalah optimisasi kombinatorik. Algoritma-algoritma ACO merupakan algoritma berbasis swarm intelligence. Swarm intelligence adalah suatu metode pemecahan masalah yang terinspirasi dari perilaku serangga atau hewan lainnya (Dorigo dkk, 2006). ACO terinspirasi dari sifat koloni semut di dunia nyata dan diadaptasi sebagai artificial intelligence. Masalah optimisasi yang dimaksud antara lain: Traveling Salesman Problem (TSP), General Assignment Problem (GAP), graph colouring, Vehicle Routing Problem (VRP), penjadwalan dan sequential ordering. Perilaku semut yang diadaptasi menjadi artificial intelligence adalah perilaku semut ketika mencari atau membentuk jalur selama proses pencarian sumber makanan. Selama proses pencarian jalur menuju sumber makanan, semut akan mengeluarkan substansi aromatik yang disebut dengan pheromone. Subtansi aromatik ini digunakan semut untuk memberikan tanda pada jalur yang dilalui sehingga semut dapat kembali ke sarangnya. Karena semut cenderung hidup berkoloni maka semut lain dapat mengetahui jalur yang berhasil ditemukan oleh semut sebelumnya melalui pheromone yang terletak pada jalur yang dilalui. Jadi, secara tidak langsung pheromone berfungsi sebagai alat komunikasi pada semutsemut yang berkoloni tersebut. Semakin sering suatu jalur dilewati oleh semut maka intensitas pheromone pada jalur akan semakin bertambah. Bertambahnya intensitas pheromone pada suatu jalur akan mengakibatkan semut-semut cenderung memilih jalur tersebut. Sedangkan intensitas pheromone pada jalur yang jarang dilewati akan lebih lemah atau berkurang dari intensitas pheromone


17

pada jalur yang lain, akibatnya jalur ini cenderung tidak akan dipilih oleh semut untuk dilalui. Berkurangnya intensitas pheromone disebabkan adanya proses evaporasi (penguapan) pheromone selama semut membentuk jalur. Proses pembentukan jalur menuju sumber makanan berdasarkan intensitas pheromone yang terletak pada jalur inilah yang membuat semut dapat menentukan rute terbaik yang akan dilalui dari sarang menuju sumber makanan yang ditemukan. Pada ACO, semut direpresentasikan sebagai agen. Agen inilah yang akan menelusuri setiap jalur untuk mencari solusi dengan menggunakan aturan tertentu pada algoritma ACO. Pada awalnya ACO digunakan untuk menyelesaikan TSP, dimana setiap kota harus dikunjungi tepat satu kali. Agen pada ACO dibekali dengan memori untuk menyimpan simpul yang telah dikunjungi sebagai batasan untuk memperoleh solusi yang layak. Pada awalnya ACO menggunakan satu agen (single agent) untuk menyelesaikan masalah optimisasi. Kemudian ACO berkembang menggunakan lebih dari satu agen (multi agent). Multi agent ini lebih menggambarkan kehidupan semut yang sebenarnya yaitu hidup berkoloni. Perilaku semut yang berkoloni ini menginspirasi suatu metode optimisasi yang digunakan untuk menyelesaikan VRPTW. Algoritma-algoritma yang termasuk dalam ACO antara lain Ant System (AS), Ant-Q, Ant Colony System (ACS), Max-Min Ant System (MMAS), AS-Rank, dan Best Worst Ant System. Urutan munculnya algoritma-algoritma ACO dapat dilihat pada Gambar 2.3 yang menunjukkan skema algoritma yang termasuk dalam kumpulan algoritma ACO. Ant System (1991) Pseudorandom

Ant Q (1995) Ant Colony Optimization

Ant Activity (Online Delayed Pheromone Update)

Pseudorandom Proportional

Daemon Activity ( Offline Pheromone Update)

Global Best

Ant Colony System (1996)

Max-Min AS (1997)

Random Proportional

Iteration Best

AS Rank (1999) Best Worst AS (2000)

Gambar 2.3 Skema algoritma-algoritma ACO


18

Terlihat bahwa Ant System (AS) adalah algoritma pertama dalam ACO. AS menginspirasikan munculnya algoritma-algoritma lain seperti Ant-Q, Ant Colony System, Max-Min AS, AS-Rank, dan Best-Worse. Untuk menyelesaikan VRPTW, algoritma ACO yang berhasil digunakan adalah algoritma Ant Colony System. Hal yang membedakan algoritma-algoritma pada ACO adalah ant activity dan daemon activity. Ant activity merupakan aturan yang dilakukan semut dalam membentuk solusi yang terdiri dari pemilihan jalur dan pembaharuan pheromone. Untuk memilih jalur mana yang akan dilewati semut, dipengaruhi oleh intensitas pheromone dan bobot yang terdapat pada jalur tersebut. Sedangkan pembaharuan pheromone yang dilakukan terdiri dari 2 jenis yaitu online step by step pheromone update dan online delayed pheromone update. Online step by step pheromone update adalah pembaharuan pheromone yang dilakukan semut ketika semut melakukan perpindahan dari satu simpul ke simpul lain, sedangkan online delayed pheromone update adalah pembaharuan pheromone yang dilakukan setelah semut berhasil membentuk solusi. Pada ant activity terdapat 3 cara pemilihan jalur yang dapat dilakukan oleh agen. Aturan pemilihan jalur tersebut yang dilakukan selama proses pembentukan solusi rute perjalanan dipengaruhi oleh 2 hal yaitu intensitas pheromone trail, (

) pada busur

yang menunjukkan seberapa diinginkan jalur tersebut

untuk dipilih oleh agen dan nilai visibility (

) yang nilainya diperoleh dari suatu

fungsi yang dihitung untuk simpul yang layak dipilih. Semakin tinggi intensitas pheromone pada suatu jalur maka semakin besar kemungkinan jalur tersebut akan dipilih oleh agen. Untuk menentukan aturan mana yang akan dipakai dalam pemilihan jalur, terdapat dua parameter yang mempengaruhi yaitu Parameter

adalah konstanta dengan

dengan nilai r yang diambil secara acak dengan bagaimana pemilihan jalur dilakukan. Parameter

dan .

, yang akan dibandingkan , untuk menentukan adalah bilangan bulat yang

menunjukkan kontribusi dari nilai visibility dalam pemilihan jalur. Jika nilai , pemilihan jalur hanya berdasarkan intensitas pheromone trail, sedangkan jika nilai

terlalu besar artinya pemilihan jalur cenderung memilih jalur dengan

nilai visibility yang besar. Kecenderungan ini mengakibatkan intensitas Universitas Indonesia Algoritma multiple..., Siska Afrianita, FMIPA UI, 2011

19

pheromone trail tidak cukup dipertimbangkan dalam pemilihan jalur. Hal ini tidak sesuai dengan pemilihan jalur pada algoritma-algoritma ACO yang juga mempertimbangkan intensitas pheromone trail. Ketiga aturan pemilihan jalur tersebut adalah : 1.

Pseudorandom rule Agen m di simpul memilih busur a. Jika

berdasarkan aturan:

, pilih busur dengan nilai attractiveness terbesar yaitu dimana

trail pada busur (i, j),

merupakan intensitas pheromone

adalah nilai visibility pada busur (i, j) dan

Ni(m) menyatakan himpunan simpul yang belum dikunjungi agen m ketika berada di simpul . Agen juga melakukan local updating pheromone trail selama proses pemilihan jalur . b. Jika 2.

. Pilih sembarang simpul

secara acak.

Pseudorandom proportional rule Agen m di simpul memilih busur a. Jika

berdasarkan aturan:

pilih busur (i, j) dengan nilai attractiveness terbesar {[

][

] }

(2.11)

Pemilihan busur dengan mekanisme ini disebut mekanisme eksploitasi. b. Jika

pilih busur (i, j) berdasarkan distribusi probabilitas berikut: [

{

dimana

∑

][

]

[

][

(2.12)

]

adalah probabilitas agen k memilih busur

. Untuk

menentukan jalur yang akan dilalui, diambil sebuah bilangan secara acak yaitu rpn yang nilainya

untuk memperoleh jalur


20

mana yang akan dilalui berdasarkan distribusi probabilitas. Pemilihan busur seperti ini disebut dengan mekanisme eksplorasi. 3.

Random proportional rule Agen m di simpul memilih busur

hanya berdasarkan distribusi

probabilitas pada persamaan (2.12). Aturan pemilihan jalur jenis ini sama dengan aturan pemilihan simpul jenis pseudorandom proportional rule dimana bilangan acak

selalu lebih kecil dari

.

Selain aturan pemilihan jalur dan pembaharuan pheromone, juga terdapat aturan untuk memperbaiki kinerja algoritma-algoritma ACO yang disebut daemon activity. Tidak semua algoritma pada ACO melakukan daemon activity. Namun Ant Colony System (ACS) adalah salah satu algoritma ACO yang melakukan daemon activity. Contoh daemon activity yaitu pembaharuan pheromone dengan cara menambahkan intensitas pheromone hanya pada beberapa solusi dengan aturan tertentu secara global best atau iteration best. Daemon activity yang dilakukan secara iteration best yaitu penambahan pheromone hanya dilakukan pada solusi terbaik per-iterasi yang diperoleh oleh agen. Sedangkan global best merupakan penambahan pheromone yang dilakukan pada solusi terbaik selama proses pembentukan solusi yang dilakukan oleh agen (Dorigo dkk, 2006). Pada skripsi ini akan dibahas algoritma MACS yang merupakan pengembangan dari algoritma ACS. Pada ACS, aturan pemilihan jalur dan pembaharuan pheromone (ant activity) yang dilakukan adalah aturan pseudorandom proportional rule sedangkan aturan penambahan intensitas pheromone hanya pada beberapa solusi (daemon activity) yang dilakukan adalah iteration best. Penjelasan lebih lanjut mengenai ACS diberikan pada Subbab 2.5 berikut.

2.5

Ant Colony System (ACS)

Ant Colony System (ACS) pertama kali diperkenalkan oleh Dorigo (1996), yang merupakan salah satu metode metaheuristik yang telah diperkenalkan untuk


21

meningkatkan kinerja dari algoritma Ant System. Tujuan yang ingin dicapai dari ACS adalah menemukan rute terpendek. Pada ACS, terdapat sejumlah agen yang ditugaskan untuk membentuk rute. Setiap agen secara acak ditugaskan membuat rute dari simpul awal sampai semua simpul dikunjungi dan menghasilkan solusi. Setiap rute dimulai dari simpul awal selanjutnya ke simpul lain dengan cara setiap agen secara iteratif menambahkan simpul-simpul baru sampai semua simpul dikunjungi. Ada beberapa hal yang terkait dengan pembuatan rute yang dilakukan agen dengan menggunakan algoritma ACS yang akan dijelaskan sebagai berikut.

2.5.1 ACS Ant Activity Aturan pemilihan jalur dan pembaharuan pheromone (ant activity) yang dilakukan pada ACS adalah aturan pseudorandom proportional rule seperti yang telah dijelaskan pada Subbab 2.4. Pada aturan pseudorandom proportional rule, mekanisme yang dilakukan dalam pemilihan adalah eksploitasi yang memenuhi persamaan (2.11) atau eksplorasi dengan persamaan (2.12). Mekanisme yang dilakukan ditentukan oleh parameter

. Semakin besar nilai parameter

maka

semakin besar kemungkinan pemilihan jalur dengan mekanisme eksplorasi sebaliknya jika nilai semakin kecil, maka semakin besar kemungkinan pemilihan jalur dengan mekanisme eksploitasi. Pada ACS, jalur pheromone diperbaharui secara lokal dan global. Pembaharuan lokal dilakukan selama pembentukan rute, sedangkan pembaharuan global dilakukan setelah agen memperoleh solusi. Pengaruh dari pembaharuan lokal adalah mengubah secara dinamis intensitas pheromone pada busur yang akan dipilih.

2.5.2

Local Pheromone Trail Update Sebagai tambahan informasi untuk pembaharuan global, agen

menggunakan aturan pembaharuan jalur secara lokal. Ketika agen bergerak dari simpul ke simpul melalui busur yang menghubungkan kedua simpul tersebut,


22

intensitas pheromone pada busur

akan berkurang karena adanya proses

evaporasi yang dinyatakan dengan parameter . Pembaharuan pheromone secara lokal dilakukan berdasarkan persamaan berikut: (2.13) dimana

adalah inisialisasi intensitas pheromone pada jalur. Nilai yang baik

untuk parameter

, dimana

adalah total waktu tempuh pada solusi

awal yang dihasilkan oleh nearest neighbor heuristic (Flood, 1956) pada inisialisasi pheromone dan n adalah banyaknya simpul. Parameter

merupakan parameter yang diambil secara acak

dan menyatakan besarnya evaporasi (penguapan) pheromone. Jika nilai berarti tidak ada evaporasi pheromone pada busur sedangkan jika nilai berarti intensitas pheromone kembali ke intensitas awal pheromone sebelum dilakukan pembaharuan. Jadi semakin besar nilai parameter

mengakibatkan

semakin berkurang intensitas pheromone pada busur (Gambardella, 1999).

2.5.3 Global Pheromone Trail Update Setelah agen memperoleh solusi, akan dipilih rute terbaik dan dilakukan global pheromone updating. Pembaharuan intensitas pheromone secara global ini dilakukan setelah agen berhasil membentuk rute yang mengunjungi semua simpul. Artinya, sudah tidak ada simpul yang harus dikunjungi. Pembaharuan secara global dilakukan dengan persamaan (2.14) berikut: (2.14)

dimana

adalah parameter yang berkaitan dengan evaporasi,

total waktu tempuh perjalanan dari rute

merupakan

yang merupakan solusi terbaik yang

dibentuk oleh agen.

2.6

Local Search


23

Local search merupakan salah satu improving heuristic yang digunakan untuk mengoptimalkan rute yang telah dibentuk. Secara umum, pada metode ini dilakukan perpindahan simpul dari suatu rute sehinggga terbentuk rute yang baru. Ada 2 jenis perpindahan simpul yang dilakukan, yaitu Intra-route dan Inter-route. Intra-route merupakan perpindahan simpul dalam satu rute tanpa mempengaruhi urutan simpul pada rute yang lain, perpindahan simpul seperti contoh yang ditunjukkan pada Gambar 2.4. Terdapat dua rute, masing-masing rute diawali dan diakhiri di depot (D). Rute pertama: D-1-2-3-4-5-D setelah dilakukan intra-route, berubah menjadi D-1-2-5-4-3-D. Sedangkan pada rute kedua: D-6-78-9-10-D berubah menjadi D-6-8-7-9-10-D. depot

1

2

3

4

5

depot

depot

6

7

8

9

10

depot

depot

1

2

5

4

3

depot

depot

6

8

7

9

10

depot

Gambar 2.4 Contoh intra-route Inter-Route merupakan perpindahan simpul yang melibatkan 2 subrute. Misalkan rute pertama yaitu D-1-2-3-4-5-D dan rute kedua yaitu D-6-7-8-9-10-D. Setelah dilakukan inter-route rute pertama menjadi D-1-3-4-5-D sedangkan rute kedua menjadi D-6-7-2-8-9-10-D dengan simpul 2 pada rute pertama pindah ke rute kedua di antara simpul 7 dan 8 seperti yang terlihat pada Gambar 2.5. depot

1

2

3

4

5

depot

depot

6

7

8

9

10

depot

depot

1

depot

6

3

7

2

4

8

5

depot

9

10

depot

Gambar 2.5 Contoh inter-route


BAB 3 MULTIPLE ANT COLONY SYSTEM PADA VEHICLE ROUTING PROBLEM WITH TIME WINDOWS

Pada bab ini akan dibahas mengenai algoritma Multiple Ant Colony System (MACS) untuk menyelesaikan VRPTW. Pada Subbab 3.1, diberikan penjelasan mengenai algoritma MACS dengan beberapa proses yang harus dilakukan untuk memperoleh solusi VRPTW, antara lain pembentukan solusi awal VRPTW dengan menggunakan metode nearest neighbor heuristic, dilanjutkan dengan perbaikan solusi awal yang dilakukan oleh agen-agen pada koloni pertama kemudian solusi terbaik yang diperoleh dicoba untuk diperbaiki kembali oleh solusi yang berhasil dibentuk agen-agen pada koloni kedua. Sebelum memulai setiap tahapan dalam algoritma MACS, akan diberikan penjelasan tentang model solusi pada Subbab 3.2. Kemudian, untuk memulai algoritma MACS, terlebih dahulu ditentukan jumlah iterasi yang diinginkan pada setiap koloni, selanjutnya dilakukan pembentukan solusi awal dengan metode nearest neighbor heuristic yang akan dibahas pada Subbab 3.3. Setelah itu, tahapan berikutnya adalah tahapan pembentukan solusi yang dilakukan oleh masing-masing agen pada koloni pertama yang dibahas pada Subbab 3.4 serta dilanjutkan pada Subbab 3.5 mengenai pembentukan solusi dilakukan masingmasing agen pada koloni kedua.

3.1

Algoritma MACS Untuk Menyelesaikan VRPTW

Untuk menyelesaikan VRPTW, algoritma Ant Colony System (ACS) dikembangkan menjadi algoritma MACS agar memperoleh tujuan yang diinginkan. Pada algoritma MACS terdapat dua tujuan yang ingin dicapai, tujuan ini dioptimisasi oleh dua koloni seperti yang terlihat pada Gambar 3.1, koloni pertama adalah ACS_VEI dan koloni kedua adalah ACS_TIME. Pada setiap koloni, terdapat sejumlah artificial ant (agen) yang ditugaskan untuk membentuk solusi VRPTW. Koloni ACS_VEI bertugas untuk mencapai tujuan pertama VRPTW yaitu meminimumkan banyaknya penggunaan kendaraan, sedangkan 24



25

koloni ACS_TIME bertugas untuk mencapai tujuan kedua yaitu meminimumkan waktu tempuh penggunaan kendaraan. MACS

ACS_VEI

ACS_TIME

Agen

Agen

Gambar 3.1 Dua koloni pada MACS Masing-masing koloni baik ACS_VEI dan ACS_TIME akan menggunakan jalur pheromone yang berbeda tetapi kedua koloni akan saling memberikan informasi mengenai solusi layak terbaik

, yang terdiri dari

banyaknya kendaraan minimum yang digunakan dan total waktu tempuh minimum. Pada awalnya, solusi awal untuk VRPTW diperoleh dari metode nearest neighbor heuristic. Lalu, solusi tersebut diperbaiki oleh dua koloni yang terdapat pada algoritma MACS. Pada koloni ACS_VEI, banyaknya kendaraan yang digunakan diupayakan berkurang dari banyaknya kendaraan yang digunakan dari solusi yang diperoleh sebelumnya. Sedangkan tujuan dari koloni ACS_TIME adalah mengoptimisasi total waktu tempuh kendaraan yang digunakan dari solusi layak terbaik yang berhasil ditemukan. Jika koloni ACS_VEI tidak berhasil membentuk solusi layak dengan menggunakan kendaraan yang banyaknya lebih sedikit dari solusi awal, maka koloni ACS_TIME mencoba memperbaiki solusi awal yang diperoleh dengan metode nearest neighbor heuristic. Solusi diperbaharui setiap kali salah satu koloni berhasil menemukan solusi yang lebih baik. Ketika solusi berhasil diperbaiki dengan solusi layak yang menggunakan r-1 kendaraan, maka algoritma MACS menghentikan proses pada koloni ACS_VEI dan koloni ACS_TIME. Selanjutnya dilakukan iterasi dan kedua koloni bekerja kembali untuk mencoba mengurangi banyaknya kendaraan yang digunakan dan total waktu tempuh kendaraan sampai diperoleh solusi layak terbaik

.

Secara garis besar, algoritma MACS dapat digambarkan dengan diagram alir pada Gambar 3.2.


26

Data mengenai kapasitas kendaraan, jumlah permintaan dan time windows Tentukan jumlah iterasi yang diinginkan dan input parameter MACS Inisialisasi solusi awal dengan metode nearest neighbor heuristic

ACS_VEI Pilih solusi layak antara dua koloni yang berhasil memperbaiki solusi layak terbaik

ACS_TIME

tidak Apakah solusi layak dapat diperbaiki?

ya

tidak Iterasi bertambah

Jumlah iterasi yang ditentukan= jumlah iterasi yang dilakukan

ya Solusi layak terbaik (banyaknya kendaraan yang digunakan dan total waktu tempuh minimum) end

Gambar 3.2 Diagram alir proses algoritma MACS Untuk memulai algoritma MACS, setelah diperoleh data mengenai kapasitas kendaraan, banyaknya permintaan, dan time windows pelanggan dan depot serta ditentukan terlebih dahulu jumlah iterasi yang diinginkan, lalu dilakukan pencarian solusi awal VRPTW dengan metode nearest neighbor heuristic, kemudian dilanjutkan pada tahapan koloni ACS_VEI, setelah itu tahapan koloni ACS_TIME. Tahapan pada koloni ACS_VEI dan ACS_TIME


27

dilakukan sampai solusi layak terbaik

VRPTW diperoleh dan iterasi yang

ditentukan telah tercapai.

3.2

Model Solusi MACS Untuk Menyelesaikan VRPTW

Pada algoritma MACS, digunakan sebuah model solusi dimana setiap agen membangun sebuah rute. Sebelum membentuk rute, depot diduplikasi sebanyak kendaraan yang dibutuhkan berdasarkan solusi awal yang diperoleh, dimana depot terduplikasi dianggap sebagai pelanggan dan jarak antar depot terduplikasi adalah 0. Pendekatan ini membuat permasalahan rute kendaraan pada VRPTW lebih menyerupai masalah TSP tradisional. Di dalam TSP dan model ini, solusi layak adalah sebuah rute yang mengunjungi semua simpul hanya satu kali. Pada Gambar 3.3, dimana subrute yang mempunyai dua simpul depot terduplikasi di awal dan akhirnya merupakan rute dari satu kendaraan. Jadi banyaknya subrute yang memenuhi kondisi tersebut menunjukkan banyaknya kendaraan yang digunakan. Depot-depot terduplikasi ditunjukan sebagai titik hitam sedangkan pelanggan adalah titik putih. Semua depot terduplikasi mempunyai lokasi yang sama namun depot-depot tersebut digambarkan terpisah karena dianggap sebagai pelanggan. Pada Gambar 3.3 (a) agen berhasil membentuk solusi layak yang mempunyai 4 subrute yang memenuhi kondisi di atas, sedangkan pada Gambar 3.3 (b) solusi yang dibentuk agen bukan solusi layak karena ada 3 pelanggan yang ditunjukkan dengan titik hitam tidak terlayani. Dengan representasi model solusi seperti ini, berdasarkan aturan pembaharuan pheromone, jalur menuju depot terduplikasi menjadi kurang menarik dikunjungi dibandingkan pada kasus hanya tersedia satu depot. Hal ini berpengaruh positif terhadap kualitas solusi yang terbentuk (Gambardella, 1999).

(a)

(b)

Gambar 3.3 (a) Solusi layak, (b) Solusi tidak layak Universitas Indonesia Algoritma multiple..., Siska Afrianita, FMIPA UI, 2011

28

Selanjutnya akan dijelaskan beberapa tahapan yang akan dilakukan pada algoritma MACS untuk menyelesaikan VRPTW yang dimulai dengan tahapan inisialisasi solusi awal.

3.3

Inisialisasi Solusi Awal Seperti yang telah disebutkan sebelumnya, setelah ditentukan jumlah

iterasi yang diinginkan, dilakukan inisialisasi solusi awal dengan metode nearest neighbor heuristic. Pembentukan solusi awal ini dilakukan untuk memperoleh banyaknya kendaraan yang dibutuhkan dan rute yang dilalui kendaraan-kendaraan tersebut. Solusi awal tersebut juga akan digunakan untuk inisialisasi intensitas pheromone ( ) yang diperoleh dari persamaan (3.1) dimana n adalah banyaknya pelanggan dan

merupakan total waktu tempuh yang diperoleh dari solusi awal

dengan metode nearest neighbor heuristic (Flood, 1956). (3.1) Proses pembentukan solusi awal dengan metode nearest neighbor heuristic ditunjukan dengan diagram alir pada Gambar 3.4. Ketika agen berada di depot, pelanggan pertama yang akan dilalui dipilih secara acak, kemudian muatan kendaraan dan waktu agen diperbaharui. Selanjutnya pelanggan yang belum dikunjungi dimasukan ke dalam daftar pelanggan yang akan dikunjungi. Untuk memilih pelanggan berikutnya ada beberapa kriteria yang harus terpenuhi, antara lain: jumlah permintaan pelanggan yang dilayani tidak boleh melebihi kapasitas kendaraan dan waktu agen sampai ke pelanggan tidak boleh melebihi batas akhir waktu yang diberikan pelanggan. Kemudian, dipilih jarak pelanggan terdekat di antara pelanggan yang memenuhi kriteria tersebut. Jika tidak ada, agen kembali ke depot dan memilih kembali secara acak pelanggan yang akan dikunjungi. Setiap kali agen mengunjungi pelanggan, muatan kendaraan dan waktu agen diperbaharui kembali. Proses pemilihan pelanggan dilakukan sampai semua pelanggan berhasil dikunjungi dan diperoleh banyaknya kendaraan serta total waktu tempuh agen untuk mengunjungi semua pelanggan.


29

Data Data pelanggan pelanggan yang yang harus harus dikunjungi. dikunjungi. Inisialisasi Inisialisasi ketika ketika agen agen didepot, didepot, muatan= muatan= kapasitas kapasitas kendaraan kendaraan Pilih Pilih pelanggan pelanggan secara secara acak acak

Update Update muatan muatan dan dan waktu waktu agen agen

Daftar Daftar pelanggan pelanggan yang yang belum belum dikunjungi dikunjungi Periksa Periksa kriteria kriteria pelanggan pelanggan Daftar Daftar pelanggan pelanggan yang yang memenuhi memenuhi kriteria kriteria

Banyaknya Banyaknya pelanggan pelanggan yang yang memenuhi memenuhi kriteria kriteria >0 >0

Agen Agen kembali kembali ke ke depot depot

tidak

ya Pilih Pilih pelanggan pelanggan terdekat terdekat dengan dengan waktu waktu tempuh tempuh minimum minimum dari dari pelanggan pelanggan sebelumnya sebelumnya dilalui dilalui Update Update muatan muatan dan dan waktu waktu agen agen

ya Ada Ada pelanggan pelanggan yang yang belum belum dikunjungi? dikunjungi?

tidak Solusi Solusi awal awal dengan dengan metode metode NNH NNH (banyaknya (banyaknya kendaraan, kendaraan, total total waktu waktu tempuh tempuh agen) agen)

Gambar 3.4 Diagram alir metode nearest neighbor heuristic


30

Contoh 3.1 Berdasarkan contoh yang telah diberikan pada Contoh 2.1, akan dilakukan pembentukan solusi awal dengan metode nearest neighbor heuristic untuk memperoleh banyaknya kendaraan yang dibutuhkan serta rute yang kemudian akan digunakan untuk inisialisasi intensitas pheromone pada koloni semut di tahapan selanjutnya. Misalkan terpilih pelanggan pertama secara acak adalah pelanggan 3, maka rute yang terbentuk : D-3 dimana permintaan pelanggan 3 ialah 15. Data mengenai permintaan barang setiap pelanggan dapat dilihat kembali di Tabel 2.2. Setelah memilih pelanggan, muatan kendaraan diperbaharui dari muatan awal 70 dikurangi banyaknya permintaan pelanggan 3 yaitu 15 sehingga muatan kendaraan menjadi 55 dan waktu agen setelah melayani pelanggan 3 juga diperbaharui yaitu 60 (waktu awal + waktu pelayanan). Waktu awal, waktu akhir dan waktu pelayanan setiap pelanggan dapat dilihat di Tabel 2.2. Daftar pelanggan yang belum dikunjungi adalah {1,2,4,5,6} lalu dilakukan pengecekan kriteria pelanggan yang dapat dikunjungi seperti yang terlihat pada Tabel 3.1. Pada Tabel 3.1 dapat diketahui bahwa pelanggan 3 telah dikunjungi, pelanggan 1,2,5 dan 6 memenuhi kriteria pelanggan yang akan dikunjungi sedangkan pelanggan 4 tidak memenuhi kriteria. Pelanggan yang terpilih untuk dikunjungi setelah pelanggan 3 adalah pelanggan yang memiliki waktu tempuh minimum yaitu pelanggan 6. Data mengenai waktu tempuh antara pelanggan dapat dilihat di Tabel 2.1 dengan asumsi kecepatan rata-rata kendaraan konstan dan hambatan selama perjalanan (misalkan macet, kecelakaan) diabaikan. Tabel 3.1 Pengecekan kriteria pelanggan Pelanggan

1

2

3

4

5

6

Update muatan

35

45

-

40

35

40

Waktu agen

90,41

96,06

-

90,41

98,08

71,18

Dapat

Ya

Ya

-

Tidak

Ya

Ya

30,41

36,06

-

-

38,08

11,18

dikunjungi? Jarak


31

Setelah diperoleh pelanggan berikutnya yang akan dikunjungi, dilakukan proses yang sama sampai semua pelanggan dikunjungi, sehingga diperoleh rute berikut: D-3-6-1-D-2-D-4-5-D. Jadi diperoleh solusi

awal dimana agen

kembali ke depot sebanyak 3 kali sehingga banyaknya kendaraan yang dibutuhkan adalah 3, yaitu kendaraan pertama melayani pelanggan 3,6,1 kemudian kendaraan kedua melayani pelanggan 2 dan kendaraan ketiga melayani pelanggan 4 dan 5 serta total waktu tempuh yang digunakan agen untuk melayani semua pelanggan adalah 345,54. Sebelum masuk ke tahapan pada koloni ACS_VEI dan ACS_TIME, berikut diberikan penjelasan prosedur konstruksi new_active_ant yang dilakukan oleh masing-masing agen untuk mengkonstruksi solusi pada setiap koloni.

3.4

Prosedur Konstruksi New_Active_Ant

Pada setiap koloni, baik koloni ACS_VEI maupun koloni ACS_TIME terdapat sejumlah agen yang bertugas untuk membentuk solusi dimana masingmasing agen melakukan prosedur konstruksi new_active_ant. Hal yang membedakan new_active_ant yang dilakukan pada koloni ACS_VEI dan koloni ACS_TIME adalah prosedur local search yang hanya dilakukan oleh ACS_TIME. Koloni ACS_VEI belum tentu berhasil menemukan solusi layak sedangkan agen pada koloni ACS_TIME dapat dipastikan akan membentuk solusi yang layak dan rute yang terbentuk pada solusi layak tersebut akan dioptimalkan melalui prosuder local search. Setiap agen melakukan prosedur new_active_ant dengan langkah-langkah sebagai berikut: 1. Setiap agen memulai perjalanan dari sebuah depot terduplikasi yang dipilih secara acak. Misalkan agen m ditempatkan pada salah satu depot terduplikasi dengan inisialisasi waktu tempuh agen=0 dan permintaan yang dilayani=0, kemudian depot terduplikasi ini menjadi simpul asal.


32

2. Perjalanan dimulai dari simpul asal i, lalu dilanjutkan dengan pemeriksaan simpul j yang layak untuk dikunjungi. Beberapa kriteria yang harus terpenuhi untuk pelanggan agar dapat dilayani antara lain sebagai berikut:  Jumlah permintaan pelanggan akan yang dilewati tidak melebihi kapasitas kendaraan.  Waktu tiba agen tidak melebihi waktu akhir pelayanan pelanggan yang akan dikunjungi.  Waktu agen setelah melayani pelanggan dan waktu agen kembali ke depot setelah melayani pelanggan tidak melebihi batas waktu depot. Jika semua kriteria di atas terpenuhi, simpul j dimasukkan dalam himpunan dari

. Selanjutnya untuk setiap simpul j yang merupakan anggota

, dihitung nilai visibility,(

) dari simpul j yang layak dilayani setelah

simpul i. Nilai visibility dapat diperoleh dengan memasukkan perhitungan waktu tempuh

antara simpul i dan j, time window

dengan simpul j dan nilai

yang berkaitan

yang menunjukkan simpul j tidak termasuk pada

solusi. Nilai

pada koloni ACS_TIME bernilai 0 karena tujuan agen dari

koloni ini mencoba memperbaiki solusi layak yang ada. Dengan kata lain, seluruh simpul pasti sudah termasuk pada solusi, sehingga nilai

tidak

diperlukan. Sedangkan pada koloni ACS_VEI, agen bertugas untuk menemukan solusi dengan mencoba mengurangi banyaknya kendaraan yang digunakan, yang dilakukan adalah dengan memaksimumkan banyaknya pelanggan yang dilayani. Jadi, nilai

diperlukan untuk memberikan tanda

pada pelanggan yang sering tidak termasuk dalam solusi. Semakin besar nilai , semakin besar nilai visibility-nya, sehingga kemungkinan simpul j yang dimasukkan dalam solusi akan bertambah besar. Selanjutnya nilai visibility dapat diperoleh berdasarkan persamaan berikut: (

)

(3.2) (3.3)


33

(3.4) (3.5) (3.6) Setelah diperoleh nilai visibility untuk setiap simpul j dalam

, dilakukan

proses pemilihan pelanggan dengan mekanisme eksploitasi atau eksplorasi. Waktu tempuh agen dan jumlah permintaan yang dilayani diperbaharui dan dilakukan pembaharuan intensitas pheromone secara lokal berdasarkan persamaan (2.13). Jika simpul j yang terpilih adalah depot terduplikasi, maka waktu tempuh agen dan jumlah permintaan yang dilayani kembali menjadi nol. Tahapan 2 ini dilakukan sampai himpunan

kosong, yang artinya sudah

tidak ada simpul yang layak dikunjungi. Rute yang berhasil dibentuk agen disimpan pada solusi

.

3. Tahapan selanjutnya adalah memperbaiki solusi

dengan menambahkan

pelanggan yang dapat dilayani secara tentatif dengan prosedur best feasible insertion. Insertion dilakukan dengan mempertimbangkan semua pelanggan yang belum dikunjungi, yang terurut secara menurun berdasarkan banyaknya permintaan . Untuk setiap pelanggan tersebut, dicari posisi terbaik untuk memasukkan pelanggan ke dalam solusi, dengan tetap menjaga terpenuhinya kendala kapasitas kendaraan dan time windows serta memiliki total waktu tempuh paling minimum sampai tidak ada lagi pelanggan yang layak dimasukkan. 4. Setelah diperoleh solusi layak, dilakukan prosedur local search untuk mengoptimalkan solusi yang diperoleh seperti yang telah dibahas di Subbab 2.6. Tahapan ini hanya dilakukan oleh agen pada koloni ACS_TIME. Pada Gambar 3.5 diberikan prosedur local search yang menunjukkan langkahlangkah dalam mencari rute yang lebih optimal dari rute yang sudah terbentuk oleh agen. Setiap simpul yang terhubung dalam rute yang sudah terbentuk diperiksa apakah sudah menempati posisi yang tepat untuk menghasilkan total waktu tempuh optimal. Untuk mempermudah pengecekan tersebut, setiap simpul pada rute diberikan indeks, sehingga pengecekan total waktu tempuh sudah optimal atau belum dapat dicek melalui persamaan (3.7) Universitas Indonesia Algoritma multiple..., Siska Afrianita, FMIPA UI, 2011

34

(3.7) dengan t(p,q) menyatakan waktu tempuh antara simpul p dan q. Pengecekan rute optimal dimulai dari indeks

. Pengecekan rute tidak

dilakukan ketika indeks p menunjukan simpul depot terduplikasi. Apabila kondisi (3.7) terpenuhi, maka rute belum optimal. Jika rute dengan urutan simpul yang disusun berdasarkan ruas kanan pada persamaan (3.7) memenuhi kendala kapasitas kendaraan dan time windows, maka posisi simpul-simpul tersebut diubah. Proses ini dilakukan sampai tidak ada pelanggan pada rute yang dapat diubah posisinya. Rute yang dibentuk oleh agen m

Setiap simpul diberikan indeks lalu pengecekan rute optimal dimulai dari indeks p=2, q=3

Apakah waktu tempuh optimal sudah memenuhi persamaan (3.7)?

tidak

ya

Apakah memenuhi kendala kapasitas dan time windows

ya

ya tidak

Ubah posisi simpul pada rute

Apakah masih ada simpul yang dapat diubah posisinya (pengecekan dengan indeks p dan q bertambah)?

tidak Rute optimal yang diperoleh agen m

Gambar 3.5 Prosedur local search Universitas Indonesia Algoritma multiple..., Siska Afrianita, FMIPA UI, 2011

35

5. Rute-rute yang diperoleh setelah prosedur insertion digunakan dalam koloni ACS_VEI. Sedangkan koloni ACS_TIME menggunakan rute yang terbentuk setelah melakukan prosedur local search. Pada subbab-subbab berikutnya akan dibahas mengenai tahapan yang dilakukan pada koloni ACS_VEI dan ACS_TIME.

3.5

Tahapan Pada Koloni ACS_VEI

Setelah tahapan awal dilakukan dengan metode nearest neighbor heuristic dan diperoleh solusi awal

, tahapan selanjutnya adalah tahapan pada koloni

ACS_VEI. Agen-agen pada koloni ACS_VEI akan mencari solusi layak dengan memaksimumkan banyaknya pelanggan yang dikunjungi, tetapi dengan menggunakan kendaraan yang banyaknya lebih sedikit dari yang digunakan pada solusi

sebelumnya. Kendaraan yang dikurangi adalah kendaraan yang

melayani paling sedikit pelanggan. Selama proses pencarian solusi ini, agen pada koloni mungkin menghasilkan solusi yang tidak layak karena terdapat beberapa pelanggan yang tidak dikunjungi. Pada koloni ACS_VEI, rute dengan kendaraan yang lebih sedikit disimpan sebagai solusi

. Solusi

akan

diperbaiki ketika banyaknya pelanggan yang dikunjungi oleh agen yang berhasil membentuk

bertambah.

Algoritma ACS yang dilakukan oleh koloni ACS_VEI berbeda dengan algoritma ACS yang diterapkan untuk Travelling Salesman Problem. Pada ACS_VEI, solusi terbaik

yang diperoleh pada umumnya tidak layak

dengan maksimum banyaknya pelanggan yang dikunjungi sedangkan pada algoritma ACS pada TSP adalah solusi layak terbaik dengan jarak terpendek yang ditempuh untuk melewati semua pelanggan. Jika solusi semua pelanggan, maka solusi

sudah melayani

dalam algoritma MACS diperbaharui. Setiap

kali agen pada koloni ACS_VEI berhasil membentuk solusi, jalur pheromone diperbaharui secara global dengan dua solusi yang berbeda, yaitu

yang

merupakan solusi yang tidak layak dengan maksimum banyaknya pelanggan yang dikunjungi dan

yang merupakan solusi layak dengan banyaknya kendaraan

minimum dan total waktu tempuh minimum. Universitas Indonesia Algoritma multiple..., Siska Afrianita, FMIPA UI, 2011

36

Pembaharuan pheromone secara global ilakukan sesuai persamaan (3.8) (3.9) dimana

merupakan solusi yang tidak layak sedangkan Pada solusi

solusi layak.

, jalur yang melalui pelanggan yang tidak termasuk

dalam solusi tidak diperbaharui intensitas pheromone-nya, sedangkan pada solusi yang berhasil dibentuk, semua pelanggan mempunyai jalur yang mengalami pembaharuan intensitas pheromone.

Contoh 3.2 Dengan menggunakan hasil yang diperoleh pada solusi layak pada Contoh 3.1, selanjutnya diberikan contoh tahapan pada koloni ACS_VEI. Tahapan ACS_VEI dimulai dengan inisialisasi banyaknya kendaraan yang akan digunakan, intensitas pheromone, dan penentuan banyaknya agen yang bertugas dalam pembentukan solusi. Berdasarkan hasil yang diperoleh pada Contoh 3.1 bahwa solusi layak

awal adalah dengan total waktu tempuh minimum 345.54,

dengan banyaknya kendaraan yang digunakan adalah 3 dan rute D-3-6-1-D-2-D4-5-D. Pada koloni ACS_VEI dilakukan pengurangan banyaknya kendaraan yang digunakan, maka 1 rute kendaraan yang melayani paling sedikit pelanggan dihilangkan. Rute yang terbentuk adalah D-3-6-1-D-4-5-D dimana digunakan 2 kendaraan dan diperoleh total waktu tempuh dengan 2 kendaraan yang melayani 5 pelanggan adalah 244,16. Selanjutnya dilakukan inisialisasi intensitas pheromone berdasarkan persamaan (3.1) sebagai berikut:

Setiap busur memiliki intensitas pheromone awal dengan nilai yang sama yaitu

seperti yang terlihat pada Tabel 3.2.


37

Tabel 3.2 Inisialisasi pheromone pada koloni ACS_VEI D

1

2

3

4

5

6

D

0

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

1

8,2.10-4

0

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

2

8,2.10-4

8,2.10-4

0

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

3

8,2.10-4

8,2.10-4

8,2.10-4

0

8,2.10-4

8,2.10-4

8,2.10-4

4

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4 0

8,2.10-4

8,2.10-4

5

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4 0

6

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

0

Misalkan pada tahapan ACS_VEI ditentukan 2 agen yang ditugaskan dalam pembentukan solusi. Berikut diberikan contoh bagaimana agen-agen pada koloni ACS_VEI membentuk solusi. Diberikan contoh pembentukan solusi oleh agen pertama sebagai berikut: 1. Agen 1 ditempatkan pada salah satu depot terduplikasi (D), dan jumlah permintaan yang dilayani=0. 2. Jika agen terletak pada depot, simpul yang diperiksa kelayakan untuk dikunjungi yaitu simpul

. Dapat dilihat pada Tabel 3.5

hasil pengecekan simpul yang layak dikunjungi. Tabel 3.3 Hasil pengecekan simpul untuk depot terduplikasi pertama 1

2

3

4

5

6

20

30

15

25

20

25

Waktu agen

29,15

11,18

25

14,14

20,62

15,81

Time window depot

159,15

101,18

85

64,14

100,62

85,81

Memenuhi?

ya

ya

ya

ya

ya

ya

Jumlah permintaan yang sudah dilayani

Setelah diperoleh himpunan simpul yang layak dikunjungi, dihitung nilai visibility simpul-simpul tersebut berdasarkan persamaan (3.2)-(3.6). Hasil perhitungan nilai visibility dapat dilihat pada Tabel 3.4.


38

Tabel 3.4 Nilai visibility yang diperoleh Simpul j

1

2

3

4

5

6

5,21.10-5

8,33.10-5

2.10-4

3,57.10-4

1.3.10-4

1,39.10-4

Pada tahap inisialisasi new_active_ant pada ACS_VEI, agen 1 berada di depot terduplikasi. Untuk mengetahui apakah pemilihan jalur melalui mekanisme eksploitasi atau mekanisme eksplorasi, dijelaskan sebagai berikut : misalkan ditentukan

lalu bilangan r diambil secara acak yang nilainya

Misalkan diperoleh

. Karena

.

maka agen 1 akan

memilih jalur yang dilalui melalui mekanisme eksploitasi dengan

,

. Jalur dengan nilai attractiveness terbesar akan terpilih untuk dilalui oleh agen pertama. Berikut nilai attractiveness yang dihitung menurut persamaan (2.12): → → → → → →

𝑃 𝑃 𝑃 𝑃 𝑃 𝑃

9

Dapat dilihat bahwa nilai maksimum :

9

9

terdapat pada jalur

menuju pelanggan 4. Jadi, waktu agen setelah melayani pelanggan 4 adalah 50 banyaknya permintaan pelanggan 4 adalah 25. Selanjutnya dilakukan local pheromone update sebagai berikut: 𝑑

𝑜

Sekarang agen 1 berada pada pelanggan 4, lalu dicek kembali simpul lain yang layak dikunjungi setelah simpul 4 yaitu

. Karena agen 1 tidak

terletak pada depot terduplikasi, pengecekan juga harus dilakukan untuk depot terduplikasi. Himpunan tersebut belum kosong, artinya masih ada pelanggan yang


39

bisa dilalui sehingga pemilihan jalur dilanjutkan. Hasil pengecekan dapat dilihat pada Tabel 3.5. Tabel 3.5 Hasil pengecekan untuk simpul 4 1

2

3

5

6

D

45

55

40

45

50

25

Waktu agen

93,01

65

80,41

83,54

75,5

64,14

Time window depot

159,15

101,18

115,41

114,16

101,31

64,14

Memenuhi?

ya

ya

ya

ya

ya

ya

Jumlah permintaan yang sudah dilayani

Misalkan pemilihan simpul berikutnya dilakukan dengan mekanisme eksploitasi, maka simpul yang terpilih adalah simpul 3. Waktu agen setelah melayani pelanggan 3 adalah 9

dan jumlah permintaan yang sudah dilayani

adalah 40. Kemudian dilakukan local pheromone update kembali. Sekarang agen 1 berada pada pelanggan 3, sehingga

. Karena himpunan

tersebut belum kosong, artinya masih ada pelanggan yang belum dilalui, maka pemilihan jalur dilanjutkan. Untuk memberikan ilustrasi pemilihan jalur dengan mekanisme eksplorasi akan dijelaskan pada pemilihan jalur berikutnya. Sebelum melakukan mekanisme eksplorasi, harus dilakukan pemeriksaan terlebih dahulu terhadap simpul-simpul apakah layak dikunjungi setelah pelanggan 3. Ternyata setelah diperiksa, simpul yang layak dikunjungi adalah

. Selanjutnya untuk

memilih jalur yang akan dilewati, bilangan r kembali diambil secara acak, misalkan masing

. Untuk menentukan pemilihan jalur, akan dihitung masingdengan

.

Probabilitas agen 1 memilih pelanggan 1 adalah sebagai berikut:


40

Dari perhitungan di atas diperoleh

, dengan cara yang sama

9 dan

diperoleh

. Setelah diperoleh perhitungan

nilai distribusi probabilitas, distribusi kumulatif diberikan pada Gambar 3.6. Garis bilangan yang memuat distribusi kumulatif ini digunakan untuk mempermudah melihat jalur mana yang mempunyai kemungkinan lebih besar untuk dipilih agen. 9 busur (3,1) 0

busur (3,2) 0,22

busur (3,6) 0,43

busur(3,depot) 0,82

1

Gambar 3.6 Distribusi probabilitas kumulatif Untuk menentukan jalur mana yang dipilih agen, ambil nilai rpn secara acak

. Jika

Jika

maka jalur yang terpilih adalah busur (3,1). maka busur (3,2) yang terpilih, jika

maka busur yang terpilih busur (3,6) sedangkan jika terpilih adalah busur (3,6). Misalkan terpilih

yang artinya busur yang

terpilih adalah busur (3,1). Selanjutnya intensitas pheromone kembali diperbaharui secara lokal pada jalur yang dipilih agen. Pemilihan jalur dilanjutkan sampai agen berhasil memperoleh rute atau sampai himpunan

telah kosong

artinya semua pelanggan telah dilewati. Berikut diberikan Tabel 3.6 yang menunjukan rute lengkap yang berhasil dibentuk agen 1 beserta mekanisme yang dilakukan dalam pemilihan jalur: Tabel 3.6 Rute agen 1 pada koloni ACS_VEI Tahap

Nilai r

Mekanisme

Pelanggan

Rute

1

-

Pilih secara acak

D

D

2

0.35

Eksploitasi

4

D-4

3

0.33

Eksploitasi

3

D-4-3

4

0.67

Eksplorasi, rpn=0.2

1

D-4-3-1

5

0,46

Eksploitasi

D

D-4-3-1-D

6

0,25

Eksploitasi

6

D-4-3-1-D-6-2

7

0,80

Eksplorasi, rpn=0,12

2

D-4-3-1-D-6-2

8

0.36

Eksploitasi

D

D-4-3-1-D-6-2-D


41

Berdasarkan Tabel 3.6 dapat diperoleh bahwa banyaknya pelanggan yang dilayani adalah 5, yang artinya tidak lebih banyak dibandingkan banyaknya pelanggan yang dilayani pada

. Jadi solusi yang diperoleh oleh agen 1

tidak layak karena masih ada pelanggan yang belum terlayani. Selanjutnya agen 2 pada ACS_VEI ditugaskan untuk mencari rute solusi yang lain dengan catatan bahwa agen 1 memberikan informasi bahwa pelanggan 5 tidak terlayani pada solusi yang diperoleh oleh agen 1. Informasi ini disimpan dalam INj. Prosedur new_active_ant juga dilakukan oleh agen 2 dan menghasilkan solusi yang tertera pada Tabel 3.7. Tabel 3.7 Rute agen 2 pada koloni ACS_VEI Tahap

Nilai r

Mekanisme

Pelanggan

Rute

1

-

Pilih secara acak

D

D

2

0.28

Eksploitasi

4

D-4

3

0.7

Eksplorasi,rpn=0,65

6

D-4-6

4

0.2

Eksploitasi

3

D-4-6-3

5

0,4

Eksploitasi

D

D-4-6-3-D

6

0,5

Eksploitasi

5

D-4-6-3-D-5

7

0,6

Eksploitasi

2

D-4-6-3-D-5-2

8

0.8

Eksplorasi,rpn=0,15

1

D-4-6-3-D-5-2-1

9

0.15

Eksploitasi

D

D-4-6-3-D-5-2-1-D

Ternyata agen 2 berhasil memperoleh jumlah pelanggan yang lebih banyak dibandingkan

, yaitu 6 sehingga

diperbaiki dari hasil

agen 2 dengan total waktu tempuh 318,44. Karena solusi oleh agen 2 adalah solusi layak maka solusi

yang diperoleh

digunakan untuk memperbaiki

algoritma MACS untuk VRPTW, yang artinya agen 2 berhasil

mengurangi banyaknya kendaraan yang digunakan pada solusi layak sebelumnya. Sebelum masuk ke tahapan ACS_TIME, intensitas pheromone diperbaharui secara global menurut persamaan (3.8) dan (3.9) yang dapat dilihat pada Tabel 3.8 dan Tabel 3.9.


42


di ACS_VEI

D

1

2

3

4

5

D

0

8,2.10-4

8,2.10-4

8,2.10-4

1,1.10-3 8,2.10-4

1,1.10-3

1

1,1.10-3

0

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

2

1,1.10-3

8,2.10-4

0

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

3

8,2.10-4

1,1.10-3

8,2.10-4

0

8,2.10-4

8,2.10-4

8,2.10-4

4

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

5

8,2.10-4

8,2.10-4

8,2.10-4 8,2.10-4

8,2.10-4 0

6

8,2.10-4

8,2.10-4

1,1.10-3 8,2.10-4

8,2.10-4

1,1.10-3 0


6

8,2.10-4

8,2.10-4

0

di ACS_VEI

D

1

2

3

4

D

0

8,2.10-4

8,2.10-4

8,2.10-4

1,1.10-3

1,1.10-3 8,2.10-4

1

1,1.10-3

0

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

2

8,2.10-4

1,1.10-3

0

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

3

1,1.10-3 8,2.10-4

8,2.10-4

0

8,2.10-4

8,2.10-4

8,2.10-4

4

8,2.10-4

8,2.10-4

8,2.10-4 8,2.10-4

0

8,2.10-4

1,1.10-3

5

8,2.10-4

8,2.10-4

1,1.10-3 8,2.10-4

8,2.10-4 0

6

8,2.10-4

8,2.10-4

8,2.10-4

8,2.10-4

1,1.10-3

5

6

8,2.10-4

8,2.10-4

0

Setelah dilakukan satu iterasi oleh masing-masing agen untuk membentuk solusi, ternyata agen 2 pada koloni ACS_VEI berhasil menemukan solusi layak sehingga

dapat diperbaiki dengan banyaknya kendaraan yang digunakan 2

dan total waktu tempuh minimum adalah 318,44. Tahapan selanjutnya adalah tahapan pada koloni ACS_TIME yang bertujuan untuk menemukan rute dengan total waktu tempuh minimum.


43

3.6

Tahapan Pada Koloni ACS_TIME

Pada koloni ACS_TIME, algoritma yang digunakan adalah algoritma ACS yang diterapkan untuk masalah TSP dengan tujuan menemukan rute dengan total waktu tempuh minimum. Setiap solusi yang dibentuk oleh setiap agen juga dilakukan dengan prosedur yang dilakukan pada proses new_active_ant yang sudah dijelaskan pada Subbab 3.4. Namun pada ACS_TIME, proses new_active_ant dilakukan sampai prosedur local search. Setiap kali agen berhasil membentuk solusi, solusi tersebut dibandingkan dengan

dan jika salah satu solusi yang berhasil dibentuk agen pada

ACS_TIME lebih baik maka solusi ini akan memperbaiki

. Setelah solusi

terbaik diperoleh, dilakukan pembaharuan pheromone global dengan persamaan (3.9).

Contoh 3.3 Berikut akan diberikan contoh tahapan ACS_TIME dengan inisialisasi yang dilakukan berdasarkan hasil yang diperoleh pada Contoh 3.2 yaitu tahapan ACS_VEI karena salah satu agen pada koloni ACS_VEI berhasil memperoleh solusi layak dengan mengurangi banyaknya kendaraan yang digunakan. Tahapan ACS_TIME dimulai dengan inisialisasi banyaknya kendaraan yang akan digunakan adalah 2 dengan rute D-4-6-3-D-5-2-1-D dan total waktu tempuh 318,44. Jika agen pada koloni ACS_VEI tidak berhasil menemukan solusi layak maka banyaknya kendaraan yang digunakan pada ACS_TIME adalah banyaknya kendaraan yang diperoleh dari solusi layak yang diperoleh sebelumnya. Selain itu juga dilakukan inisialisasi intensitas pheromone dan menentukan banyaknya agen yang bertugas dalam pembentukan solusi. Berdasarkan hasil yang diperoleh, solusi layak

yang sudah diperbaiki oleh ACS_VEI, diperoleh inisialisasi

pheromone sebagai berikut:


44

Sehingga setiap busur memiliki intensitas pheromone awal dengan nilai yang sama yaitu

seperti yang terlihat pada Tabel 3.10 berikut:

Tabel 3.10 Inisialisasi pheromone pada koloni ACS_TIME D

1

2

3

4

5

6

D

0

5,23.10-4

5,23.10-4

5,23.10-4

5,23.10-4

5,23.10-4

5,23.10-4

1

5,23.10-4

0

5,23.10-4

5,23.10-4

5,23.10-4

5,23.10-4

5,23.10-4

2

5,23.10-4

5,23.10-4

0

5,23.10-4

5,23.10-4

5,23.10-4

5,23.10-4

3

5,23.10-4

5,23.10-4

5,23.10-4

0

5,23.10-4

5,23.10-4

5,23.10-4

4

5,23.10-4

5,23.10-4

5,23.10-4

5,23.10-4

0

5,23.10-4

5,23.10-4

5

5,23.10-4

5,23.10-4

5,23.10-4

5,23.10-4

5,23.10-4

0

5,23.10-4

6

5,23.10-4

5,23.10-4

5,23.10-4

5,23.10-4

5,23.10-4

5,23.10-4

0

Misalkan pada tahapan ACS_TIME ditentukan 2 agen yang ditugaskan membentuk solusi. Prosedur yang dilakukan oleh agen-agen pada koloni sama halnya dengan prosedur yang dilakukan pada ACS_VEI yaitu new_active_ant. Berikut diberikan rute yang berhasil diperoleh oleh agen 1 pada Tabel 3.11dan agen 2 pada Tabel 3.12.

Tabel 3.11 Rute agen 1 pada koloni ACS_TIME Tahap

Nilai r

Mekanisme

Pelanggan

Rute

1

-

Pilih secara acak

D

D

2

0.35

Eksploitasi

4

D-4

3

0.28

Eksploitasi

3

D-4-3

4

0.87

Eksplorasi, rpn=0.8

6

D-4-3-6

5

0,29

Eksploitasi

D

D-4-3-6-D

6

0,46

Eksploitasi

5

D-4-3-6-D-5-2

7

0,72

Eksplorasi,rpn=0,65

2

D-4-3-6-D-5-2-1

8

0.91

Eksplorasi,rpn=0,12

1

D-4-3-6-D-5-2-1

9

0,34

Eksploitasi

D

D-4-3-6-D-5-2-1-D


45

Tabel 3.12 Rute agen 2 pada koloni ACS_TIME Tahap

Nilai r

Mekanisme

Pelanggan

Rute

1

-

Pilih secara acak

D

D

2

0,71

Eksplorasi, rpn=0,89

6

D-6

3

0,63

Eksploitasi

3

D-6-3

4

0,87

Eksplorasi,rpn=0,7

2

D-6-3-2

5

0,52

Eksploitasi

D

D-6-3-2-d

6

0,46

Eksploitasi

4

D-6-3-2-D-4

7

0,24

Eksploitasi

5

D-6-3-2-D-4-5

8

0,75

Eksplorasi, rpn=0,4

1

D-6-3-2-D-4-5-1

9

0,13

Eksploitasi

D

D-6-3-2-D-4-5-1-D

Berdasarkan Tabel 3.11, agen pertama pada koloni ACS_TIME berhasil membentuk solusi layak dengan rute D-4-3-6-D-5-2-1-D dengan total waktu tempuh agen 1 adalah 324,16. Sedangkan berdasarkan Tabel 3.12, agen kedua berhasil membentuk solusi layak dengan rute D-6-3-2-D-4-5-1-D dengan total waktu tempuh agen 2 adalah 307,57. Sebelum menentukan solusi terbaik di antara agen pertama dan kedua, prosedur selanjutnya adalah melakukan prosedur local search yang diharapkan dapat memperbaiki solusi rute yang dihasilkan oleh setiap agen. Contoh 3.4 Contoh ini akan menunjukkan prosedur local search yang dilakukan untuk solusi yang diperoleh agen 1, pada solusi

D-4-3-6-D-5-2-1-D dimana total

waktu tempuh agen 1 adalah 324,16. Mula-mula untuk setiap simpul diberikan indeks sebagai berikut: Rute

:D - 4 - 3 - 6 - D - 5- 2 - 1 - D

Indeks : 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 Berdasarkan persamaan (3.7) dilakukan pengecekan pertama, waktu tempuh untuk indeks

yang melibatkan rute D-4-3-6.


46

Setelah diperiksa, kondisi tidak terpenuhi sehingga indeks pelanggan berikutnya yang terdapat pada rute lengkap akan dicoba disisipkan setelah pelanggan 3. Pelanggan yang akan disisipkan adalah pelanggan 6 ketika p=2 dan q=3 pertukaran simpul tidak terpenuhi kemudian diperiksa kembali apakah rute D-4-6-3 memenuhi kendala yang ada. Setelah diperiksa, diperoleh bahwa pelanggan 6 bisa dilayani setelah pelanggan 4 dan sebelum pelanggan 3. Maka rute yang telah dioptimalkan diperbaharui menjadi D-4-6-3-D-5-2-1-D. Proses ini terus dilakukan sampai sudah tidak ada pelanggan pada rute yang bisa diubah posisinya. Dari tahapan ini diperoleh solusi rute yang lebih optimal yaitu D-4-6-3D-5-2-1-D dengan total waktu tempuh agen 1 adalah 318,44. Hal yang sama dilakukan oleh agen kedua dengan solusi

yaitu D-6-3-

2-D-4-5-1-D dimana waktu tempuh agen 2 yaitu 307,57. Setelah dilakukan local search diperoleh rute yang lebih optimal yaitu D-3-6-2-D-4-5-1-D dengan total waktu tempuh 278,44. Dibandingkan dengan solusi total waktu tempuh lebih pendek sehingga solusi solusi

, solusi

mempunyai

inilah yang menggantikan

sebelumnya. Setelah diperoleh solusi terbaik, intensitas pheromone

diperbaharui secara global sesuai dengan hasil yang diperoleh agen 2 pada koloni ACS_TIME. Pembaharuan pheromone tersebut dapat dilihat pada Tabel 3.13. Tabel 3.13 Global updating pheromone pada

D

di ACS_TIME

D

1

2

3

4

5

6

0

5,23.10-4

5,23.10-4

8, 3.10-4

8, 3.10-4

5,23.10-4

5,23.10-4

1

8, 3.10-4

0

5,23.10-4

5,23.10-4

5,23.10-4

5,23.10-4

5,23.10-4

2

8, 3.10-4

5,23.10-4

0

5,23.10-4

5,23.10-4

5,23.10-4

5,23.10-4

3

5,23.10-4

5,23.10-4

5,23.10-4

0

5,23.10-4

5,23.10-4

8, 3.10-4

4

5,23.10-4

5,23.10-4

5,23.10-4

5,23.10-4

0

8, 3.10-4

5,23.10-4

5

5,23.10-4

8, 3.10-4

5,23.10-4

5,23.10-4

5,23.10-4

0

5,23.10-4

6

5,23.10-4

5,23.10-4

8, 3.10-4

5,23.10-4

5,23.10-4

5,23.10-4

0

Berdasarkan solusi yang diperoleh dari koloni pertama (ACS_VEI) dan koloni kedua (ACS_TIME), dapat disimpulkan bahwa solusi terbaik untuk masalah VRPTW pada Contoh 2.1 untuk satu kali iterasi yang dilakukan adalah


47

menggunakan 2 kendaraan dengan total waktu tempuh minimum adalah 278,44, dimana rute untuk setiap kendaraan sebagai berikut: Kendaraan 1 (D-3-6-2-D) : Banyaknya pelanggan=3, waktu tempuh 119.29, sisa muatan kendaraan=0 dan waktu tunggu=25. Kendaraan 2 (D-4-5-1-D) : Banyaknya pelanggan=3, waktu tempuh= 159.15, sisa muatan kendaraan=5 dan waktu tunggu: 31,7.


BAB 4 KESIMPULAN

Berdasarkan pembahasan pada bab-bab sebelumnya, kesimpulan yang didapat dari skripsi ini adalah: 1. Algoritma MACS merupakan salah satu metode metaheuristik berbasis swarm intelligence yang dapat digunakan untuk menyelesaikan masalah yang memiliki multiple objectives. Ide dasar yang digunakan pada algoritma MACS adalah mengadaptasi aktifitas dari koloni-koloni semut, dimana setiap koloni memiliki tujuan masing-masing. 2. Algoritma MACS dikembangkan dari algoritma ACS untuk menyelesaikan VRPTW dengan dua tujuan yang ingin dicapai. Tujuan pertama adalah meminimumkan banyaknya kendaraan yang digunakan dan tujuan kedua adalah meminimumkan total waktu tempuh kendaraan yang digunakan. Solusi VRPTW diperoleh dari hasil kolaborasi antara koloni-koloni semut yang bertukar informasi mengenai solusi terbaik yang berhasil ditemukan.

48



DAFTAR PUSTAKA

Chen, C., & Ting, C. (2005). A Hybrid Ant Colony System for Vehicle Routing Problem with Time Windows. Journal of the Eastern Asia Society for Transportation Studies 6, 2822-2836. Cordeau, dkk. (2007). Vehicle Routing. In :Barnhart, G., & Laporte, G.(Eds), Handbook in OR & MS 14, 367-428. Dorigo, M., Birattari, M., & Stutzle, T. (2006). Ant Colony Optimization : Artificial Ants as A Computational Intelligence Technique. IEEE Computational Intelligence Magazine. Dorigo, M., & Blum, C. (2005). Ant colony optimization theory: A Survey. Theoretical Computer Science 344, 243-278 Gambardella, L. M., Taillard, E. D., & Agazzi, G. (1999). MACS-VRPTW: A Multiple ant colony system for Vehicle Routing Problem with Time Windows. In : Corne, D., Dorigo, M., & Glover, F. (Eds.), New ideas in Optimization. McGraw-Hill, London, 63-76. Radiastuti, D. (2007). Penerapan Ant-Q dan Ant-Q 3-Opt untuk menyelesaikan Travelling Salesman Problem. Skripsi : Depok, Departemen Matematika, FMIPA, Universitas Indonesia. Stutzle, T., dan Dorigo, M.(1999). ACO Algorithms for The Travelling Salesman Problem. 1-23. Taillard, E., dkk. (1997). A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows, Transportation Science, 170-186. Zengyuan, W., Xiaobo, W., Gang, F., & Bei, W. (2006). A Two-phase Heuristics Algorithm to Solve The Large-Scale Vehicle Routing Problem. International Technology and Innovation Conference 49 Universitas Indonesia



ALGORITMA MULTIPLE ANT COLONY SYSTEM PADA VEHICLE ROUTING PROBLEM WITH TIME WINDOWS SKRIPSI

Recommend Documents