MULTI TRAVELING SALESMAN PROBLEM (MTSP) DENGAN ALGORITMA GENETIKA UNTUK MENENTUKAN RUTE LOPER KORAN DI AGEN SURAT KABAR Oleh : Fitriana Yuli Saptaningtyas,M.Si. Jurusan Pendidikan Matematika FMIPA UNY
[email protected] Abstrak Permasalahan pendistribusian oleh beberapa loper koran di suatu agen surat kabar pada pelanggan sering mengalami keterlambatan. Bagaimana menentukan rute optimum bagi beberapa loper koran di sebuah agen surat kabar akan dimodelkan secara matematis dan akan diselesaikan menggunakan algoritma genetika. Permasalahan ini masuk dalam kategori Multi Travelling Salesman Problem (MTSP) Algoritma genetika yang mengadopsi proses evolusi makhluk hidup, pada penerapannya mengikuti langkah pembentukan populasi, menentukan nilai fitness, melakukan proses seleksi, melakukan pindah silang dan mutasi, dan membentuk individu baru. Algoritma genetika dapat digunakan untuk menentukan rute optimum perjalanan beberapa loper koran di suatu agen surat kabar. Penentuan rute perjalanan beberapa loper koran di suatu agen surat kabar dengan langkah mendefinisikan populasi,menentukan nilai fitness, melakukan proses seleksi dengan metode seleksi rangking, pindah silang dengan order cross over, melakukan mutasi dengan swapping mutation, dan memperoleh individu baru yang menuju ke penyelesaian optimum. Dari hasil simulasi di suatu agen surat kabar dengan delapan loper Koran dan 160 pelanggan diperoleh jarak terpendek sejauh 144.16 km pada iterasi ke 98. Semakin banyak iterasi yang digunakan maka akan semakin memberi solusi yang lebih optimum. Kata Kunci: Algoritma Genetika, Loper Koran, Agen Surat Kabar, MTSP
PENDAHULUAN Algoritma genetika cukup efektif dalam menyelesaikan permasalahan optimasi. Dalam perkembangannya telah diapliakasikan dalam pencarian rute optimum, penjadwalan, Travelling Salesman Problem (TSP), dan lain sebagainya. Prosedur dalam pencarian solusi yang mengadopsi proses evolusi makhluk hidup dapat digunakan untuk menyelesaiakan masalah yang memerlukan banyak perhitungan dengan menggunakan algoritma konvensional menjadi lebih sederhana. Pada permasalahan pendistribusian surat kabar oleh beberapa orang loper koran di suatu agen surat kabar dapat dikategorikan dalam masalah MTSP. Loper koran di suatu agen surat kabar bertugas untuk menyampaikan surat kabar di pagi hari. Beberapa permasalahan yang
sering dialami dalam pendistribusian surat kabar adalah keterlambatan waktu penyampaian surat kabar pada pelanggan. Pada umumnya pelanggan surat kabar adalah para pegawai kantor dengan jam keberangkatan bekerja adalah jam 07.00 WIB sehingga para pelanggan menginginkan koran sampai ke pelanggan sebelum jam tersebut. Surat kabar siap untuk diedarkan dari sebuah agen pukul 05.00 WIB, para loper koran hanya memiliki waktu sekitar dua jam untuk mendistribusikannya. Sebuah agen surat kabar memiliki beberapa orang loper untuk mendistribusikan ke pelanggan. Untuk mempercepat penyampaian surat kabar ke pelanggan langsung, para loper koran menggunakan kendaraan bermotor dengan kapasitas angkut surat kabar maksimal sebanyak 70 surat kabar. Bagaimana beberapa orang loper koran di suatu agen surat kabar menghantarkan koran pada para pelanggan dapat dimodelkan secara matematis. Permasalahan pendistribusian koran di sebuah agen surat kabar dengan lebih dari seorang loper dapat dimodelkan dalam multi traveling salesman problem (MTSP). Masalah MTSP merupakan masalah optimasi yang merupakan perluasan dari masalah travelling salesman problem (TSP). Permasalahan ini dapat dijadikan acuan dalam mencari rute terpendek maupun melakukan penjadwalan berbagai permasalahan optimasi. Permasalahan MTSP merupakan pengembangan dari masalah travelling salesman problem, dimana yang melakukan perjalanan tidak hanya seorang sales tapi lebih dari satu (Shalini Singh, 2014). Menurut Bertas(2006) permasalahan MTSP didefinisikan dalam sebuah graf G=(V,A), dengan V adalah himpunan titik yang merepresentasikan kota, A adalah himpunan sisi yang menghubungkan antar kota dengan i,j adalah penghubung antar titik kota, dan , adalah variable biner dengan ketentuan , =1 jika sisi i,j dikunjungi oleh sales dan 0 untuk sisi i,j yang tidak dikunjungi serta , adalah jarak antar kota ke-i dan kota ke-j. Permasalahan MTSP dapat diselesaikan dengan menggunakan berbagai metode. Algoritma heuristic cukup efektif untuk menyelesaikan masalah ini, walaupun solusi yang diperoleh merupakan solusi pendekatan. Salah satu algoritma heuristic adalah algoritma genetika. Algoritma genetika mengadopsi pada kemampuan mahluk hidup dalam proses seleksi alam untuk mencapai optimasinya. Algoritma genetika mengadopsi sebuah populasi individu yang merupakan himpunan solusi secara berulang. Algoritma genetika memilih individu secara acak dari populasi untuk dijadikan induk dan menggunakannya untuk menghasilkan keturunan pada generasi berikutnya. Individu yang mampu bertahan dalam proses seleksi alam analog dengan solusi optimal dalam masalah optimasi. Algoritma genetika cukup bagus diaplikasikan
dalam menyelesaikan masalah TSP. Salah satu kelebihan algoritma genetika menurut suyanto(2005) adalah kemudahan implementasi dan kemampuannya untuk menemukan solusi yang ‘bagus’ (bisa diterima) secara tepat untuk masalah-masalah berdimensi tinggi. Karena masalah MTSP merupakan bagian dari masalah TSP maka masalah MTSP juga dapat diselesaikan dengan algoritma genetika. Penelitian terkait algoritma genetika pada rute seorang loper koran telah dilakukan oleh Antonios (2013) yaitu mengenai masalah TSP dengan hasil yang cukup baik ditinjau dari solusi optimal yang diperoleh. Pada kajian ini, menerapkan algoritma genetika untuk menyelesaikan masalah MTSP pada pendistribusian surat kabar oleh lebih dari satu loper di sebuah agen surat kabar. Digunakan simulasi data dari suatu agen surat kabar dengan delapan loper koran, dari hasil simulasi akan dianalisa pengaruh banyaknya iterasi terhadap solusi optimum yang dihasilkan.
PEMBAHASAN Model matematika dalam masalah MTSP dalam perkembanganya memiliki berbagai bentuk variasi, dalam kajian ini model matematika yang akan dibangun berdasarkan kondisi rute pendistribusian surat kabar oleh beberapa orang loper di sebuah agen surat kabar. MTSP dengan kondisi bahwa beberapa orang sales harus mengunjungi beberapa tempat hanya sekali dan kembali ke tempat semula dengan semua tempat telah dikunjungi oleh salah satu dari sales yang ada. Adapun model matematika dari permasalahan ini adalah: Fungsi Objektifnya adalah = ∑ ∑ …………………(1) Dengan kendala: ∑ =
(2)
∑ =
(3)
∑ = 1, = 2,3, … ,
(4)
∑ = 1, = 2,3, … , (5) Dari fungsi tujuan di atas dalam persamaan (1) dapat diketahui akan meminimumkan perjalanan yaitu dengan meminimumkan biaya/jarak ,dengan merupakan jalan dari kota ke i ke j yang bernilai 0 atau 1, yang artinya 0 jalan tersebut tidak dikunjungi dan 1 jalan tersebut dikunjungi. Kendala pada persamaan (2) dan (3) berarti bahwa yang akan mengunjungi n kota adalah sebanyak m sales. Persamaan (4) dan (5) menunjukkan bahwa masing masing kota hanya dikunjungi satu kali.
Permasalahan MTSP di atas dapat diselesaikan dengan menggunakan algoritma genetika. Secara umum langkah–langkah dalam menyelesaikan permasalahan optimasi menggunakan algoritma genetika menurut David Goldberg (1996) dapat ditampilkan dalam alur berikut ini:
Populasi Awal
Evaluasi Fitness
Seleksi Individu
Pindah Silang dan Mutasi Individu baru
Gambar 1. Flow Chart Algoritma Genetika menurut David Goldberg (1996) Dari alur di atas dapat dijelaskan bahwa pada pembentukan populasi awal merupakan kumpulan solusi yang mungkin dari masalah optimasi yang akan diselesaikan. Proses evaluasi fitness merupakan suatu proses untuk mengetahui kemampuan makhluk hidup dalam bertahan analog dengan mengetahui bagus tidaknya suatu solusi dalam masalah optimasi.
Seleksi
individu merupakan proses pemilihan orang tua yang akan disilangkan sehingga menghasilkan keturunan. Proses pindah silang (cross over) merupakan proses menghasilkan keturunan baru yang akan diuji kemampuan bertahannya. Mutasi merupakan proses untuk mengubah nilai dari suatu gen dalam kromosom. Proses mutasi dalam kromosom digunakan untuk memperoleh individu baru yang mempunyai nilai fitness yang lebih baik. Dari hasil proses ini diperoleh poulasi baru yang akan diuji nilaifitness. Individu dengan nilai fitness terbaik merupakan solusi yang optimum. Pada permasalahan pendistribusian koran di suatu agen surat kabar dengan beberapa orang loper koran memenuhi asumsi berikut: 1. Terdapat banyak pelanggan yang harus dikunjungi tepat satu kali. Dalam hal ini yang akan digunakan untuk simulasi yaitu terdapat 160 pelanggan yang diasumsikan menjadi 40 pelanggan dengan ketentuan bahwa pelanggan yang berjarak kurang dari 20 meter dianggap satu tempat.
2. Terdapat m sales, dalam hal ini memiliki 8 loper Koran. 3. Setiap loper koran akan melakukan perjalanan dari agen ke pelanggan dan kembali lagi ke agen. Permasalahan yang akan dipecahkan adalah bagaimana rute masing-masing loper koran agar mendapatkan jarak yang optimum dengan menggunakan algoritma genetika. Adapun langkah-langkah penyelesaian masalah tersebut dengan menggunakan algoritma genetika adalah: 1. Membangun populasi awal dengan individu adalah urutan perjalanan dari 8 loper yang masing masing loper berawal dan berakhir di agen. Contoh individu -1 (1 2 3 4 5 1) (1 6 7 8 9 10 1) (1 11 12 13 14 15 1) (1 16 17 18 19 20 1) (1 21 22 23 24 25 1) (1 26 27 28 29 30 1) (1 31 32 33 34 35 1) (1 36 37 38 39 40 1) 2. Menghitung nilai fitness yaitu menggunaakan = ∑
yaitu satu
!,"
dibagi jarak rute yang dikunjungi semua sales. 3. Proses seleksi yang digunakan menggunakan seleksi rangking. Menurut Sri Kusuma Dewi (2003), prosedur dalam seleksi rangking adalah: Menghitung nilai fitness dari masing-masing individu, mengurutkan nilai fitness dari yang paling besar, kromosom terburuk diberi nilai 1 dan seterusnya, dihitung total fitness semua individu, dan dihitung probabilitas masing-masing individu, dihitung jatah pada masing-masing individu, dibangkitkan bilangan random, dari bilangan random dipilih individu yang akan terpilih dalam proses seleksi. 4. Proses pindah silang menggunakan teknik order cross over. Proses pindah silang dilakukan dengan pertukaran gen pada dua induk yang bersesuaian untuk menghasilkan individu baru. Teknik pindah silang yang digunakan adalah order cross over menurut Davis (Suyanto, 2005). 5. Proses mutasi menggunakna swapping mutation. Proses mutasi ini bertujuan untk mengubah gen–gen dalam kromosom. Teknik swapping mutation menurut Suyanto (2005) diawali dengan memilih bilangan acak kemudian gen yang berada pada posisi bilangan acak pertama ditukar dengan gen yang berada pada bilangan acak kedua dalam probabilitas tertentu. Pada kajian ini akan ditampilkan simulasi dengan menggunakan Software Matlab dari permasalahan bagaimana menentukan rute optimum dari delapan orang loper yang akan
mengunjungi 160 tempat yang direduksi menjadi 40 tempat. Pada kajian ini akan dilakukan percobaan dengan melakukan perubahan pada banyaknya iterasi. Pada simulasi yang pertama dipilih banyaknya iterasi yaitu 98 diperoleh jarak total adalah 144 km. Dari gambar di bawah ini dapat diketahui rute masing masing loper dengan rata-rata jarak yang ditempuh adalah 18 km. Apabila loper koran menempuh jarak 18 km dengan kecepatan rata –rata 50 km/jam maka memerlukan waktu 27 menit untuk melakukan perjalanan. Jika waktu yang diperlukan untuk memberikan koran pada 20 pelanggan adalah 60 menit, maka waktu total yang diperlukan sales untuk menyelesaikan tugas membagikan koran pada pelanggan adalah1 jam 27 menit. Dengan hasil ini surat kabar akan sampai keseluruh pelanggan sebelum jam 07.00 WIB. Total Distance = 144.1600, Iteration = 98 40 35 30 25 20 15 10 5 0
0
5
10
15
20
25
30
35
40
Gambar 2. Rute Optimum Pendistribusian Surat Kabar oleh delapan loper Koran menggunakan Algoritma Genetika dengan banyak iterasi 98 Pada percobaan kedua dipilih banyaknya iterasi adalah 86. Dari hasil ini diketahui bahwa rute optimumnya lebih jauh yaitu 145.8 km dengan rute masing-masing sales seperti gambar di bawah ini.
Total Distance = 145.8000, Iteration = 86 40 35 30 25 20 15 10 5 0
0
5
10
15
20
25
30
35
40
Gambar 3. Rute Optimum Pendistribusian Surat Kabar oleh delapan loper Koran menggunakan Algoritma Genetika dengan banyak iterasi 86 Pada percobaan ketiga dipilih banyaknya iterasi adalah 80. Dari hasil ini diketahui bahwa rute optimumnya lebih jauh yaitu 156.34 km dengan rute masing-masing sales seperti gambar di bawah ini.
Total Distance = 156.3400, Iteration = 80 40 35 30 25 20 15 10 5 0
0
5
10
15
20
25
30
35
40
Gambar 4. Rute Optimum Pendistribusian Surat Kabar oleh delapan loper Koran menggunakan Algoritma Genetika dengan banyak iterasi 80 Pada percobaan keempat dipilih banyaknya iterasi adalah 76. Dari hasil ini diketahui bahwa rute optimumnya lebih jauh yaitu 184.38 km dengan rute masing-masing sales seperti gambar di bawah ini.
Total Distance = 184.3800, Iteration = 76 40 35 30 25 20 15 10 5 0
0
5
10
15
20
25
30
35
40
Gambar 5. Rute Optimum Pendistribusian Surat Kabar oleh delapan loper Koran menggunakan Algoritma Genetika dengan banyak iterasi 76 Pada percobaan kelima dipilih banyaknya iterasi adalah 57. Dari hasil ini diketahui bahwa rute optimumnya lebih jauh yaitu 193.4 km dengan rute masing-masing sales seperti gambar di bawah ini.
Total Distance = 193.4400, Iteration = 57 40 35 30 25 20 15 10 5 0
0
5
10
15
20
25
30
35
40
Gambar 6. Rute Optimum Pendistribusian Surat Kabar oleh delapan loper Koran menggunakan Algoritma Genetika dengan banyak iterasi 57 Dari hasil simulasi di atas dapat diketahui bahwa semakin banyak iterasi yang digunakan maka memberikan jarak yang semakin pendek. Pada permasalahan pendistribusian surat kabar kepada 160 pelanggan dengan delapan sales di sebuah agen koran masih memungkinkan untuk
terselesaikan kurang dari dua jam. Dengan menggunakan algoritma genetika diperoleh solusi optimum dari hasil simulasi yang dilakukan adalah sejauh 144.16 km. SIMPULAN DAN SARAN Algoritma genetika dapat digunakan untuk menentukan rute optimum perjalanan beberapa loper koran di suatu agen surat kabar. Penentuan rute perjalanan beberapa loper koran di suatu agen surat kabar dengan algoritma genetika menggunakan langkah mendefinisikan populasi,menentukan nilai fitness, melakukan proses seleksi dengan metode seleksi rangking, pindah silang dengan order cross over, melakukan mutasi denganswapping mutation, dan memperoleh individu baru yang menuju ke penyelesaian optimum. Dari hasil simulasi data di suatu agen surat kabar dengan delapan loper dan 160 pelanggan diperoleh jarak terpendek sejauh 144.16 km pada iterasi ke 98. Semakin banyak iterasi yang digunakan maka akan semakin memberi solusi yang lebih baik. Pada kajian ini baru dapat menganalisa banyaknya iterasi dengan variable yang lain dianggap sama, dapat dikaji lebih lanjut pengaruh variable lain misalnya banyak individu dan lain sebagainya. Dapat digunakan berbagai tehnik mutasi dan pindah silang yang lain dalam menemukan solusi optimum.
DAFTAR PUSTAKA
Bektas,T.(2006).The multiple traveling salesman problem: an overview of formulations and solution procedures. OMEGA: The International Journal of Management Science, 34(3), 209-219. Goldberg,David. (1999). An introduction to genetic Algorithms for scientists and Engineers. Singapure:Uso-Print Shalini Singh dan Ejaz Aslam Lodhi. (2014). Comparison Study of Multiple Traveling Salesmen Problem using Genetic Algorithm.IJCSNS International Journal of Computer Science and Network Security, VOL.14 No.7, July 2014 Sri Kusuma Dewi. (2003). Artificial Intelligent (Teknik dan Aplikasinya). Yogyakarta:Graha Ilmu Suyanto.(2005). Algoritma Genetika dalam MATLAB. Yogyakarta: Andi Ofset Wayan Firdaus Mahmudy. (2008). Optimasi Multi Travelling Salesman Problem (M-TSP) Menggunakan Algoritma Genetika. Seminar Nasional BasicScience V, FMIPA, UniversitasBrawijaya, Malang, 16 February
