PEMBUATAN SKEMA JALUR ANGKUTAN KOTA PALU BERDASARKAN PENCARIAN LINTASAN DENGAN BOBOT MAKSIMUM MENGGUNAKAN ALGORITMA ANT COLONY SYSTEM (ACS)

JIMT Vol. 12 No. 1 Juni 2015 (Hal. 44 – 52) Jurnal Ilmiah Matematika dan Terapan ISSN

: 2450 – 766X

PEMBUATAN SKEMA JALUR ANGKUTAN KOTA PALU BERDASARKAN PENCARIAN LINTASAN DENGAN BOBOT MAKSIMUM MENGGUNAKAN ALGORITMA ANT COLONY SYSTEM (ACS) L. Nurhayati1, I W. Sudarsana2, dan A. Sahari3 1,2,3

Program Studi Matematika Jurusan Matematika FMIPA Universitas Tadulako Jalan Soekarno-Hatta Km. 09 Tondo, Palu 94118, Indonesia. [email protected],[email protected],[email protected]

ABSTRACT Traveling salesman problems related to the (TSP) is a matter of search maximum weight on some points where every point only visited once and back to the point of origin.The purpose of this research is to determine the route with weights maximum of transport routes city transport in Palu. This research used algorithms ant colony system (ACS) to determine the route with weights maximum from the path of city transport which are already existing.Acs is a the algorithms that took the inspiration of research on behavior real ants containing there are a bunch of ants artificial, named ants, who cooperate to find solutions to a problem maximum results. Formerly , transport route city was undertaken at random and does not have special dismissal of the route .By the use of algorithms ant colony system (ACS) , formed 10 route 5 from terminal each route that 's been created are as follow. Terminal mamboro-terminal petobo consisting of 6 routes, terminal mamboro-terminal tipo route 5, terminal manondaterminal mamboro route 7, terminal manonda-terminal petobo route 4, terminal pantoloan-terminal tipo route 4, terminal pantoloan-terminal mamboro route 4, terminal pantoloan-terminal manonda routa 4, terminal pantoloanterminal petobo route 4, terminal petobo-terminal tipo route 4, and terminal tipo-terminal manonda route 4. So the route that formed from the city transport a hammer is as much as 47 routes. Keywords

: Ant Colony System Algorithm, Traveling Salesman Problem.

ABSTRAK Traveling Salesman Problem (TSP) adalah masalah pencarian bobot maksimum pada beberapa titik, dimana setiap titik hanya dikunjungi satu kali dan kembali ketitik asal. Tujuan dari penelitian ini adalah untuk menentukan rute dengan bobot maksimum dari rute transportasi angkutan kota di wilayah Kota Palu. Dalam penelitian ini digunakan algoritma Ant Colony System (ACS) untuk menentukan rute dengan bobot maksimum dari jalur angkutan kota yang sudah ada. ACS merupakan suatu algoritma yang mengambil inspirasi dari riset atas perilaku semut riil yang didalamnya terdapat sekumpulan semut buatan, dinamai ants, yang bekerjasama untuk mencari solusi terhadap suatu masalah optimalisasi. Sebelumnya, rute angkutan kota dilakukan secara acak dan tidak mempunyai rute pemberhentian khusus. Dengan menggunakan algoritma ant colony system (ACS), dari 5 terminal terbentuk 10 rute yaitu : Terminal Mamboro-Terminal Petobo terdiri dari 6 rute, Terminal Mamboro-

44

Terminal Tipo 5 rute, Terminal Manonda-Terminal Mamboro 7 rute, Terminal Manonda-Terminal Petobo 4 rute, Terminal Pantoloan-Terminal Tipo 4 rute, Terminal Pantoloan-Terminal Mamboro 4 rute, Terminal PantoloanTerminal Manonda 4 rute, Terminal Pantoloan-Terminal Petobo 4 rute, Terminal Petobo-Terminal Tipo 4 rute, dan Terminal Tipo-Terminal Manonda 4 rute. Jadi rute yang terbentuk dari jalur angkutan kota Palu adalah sebanyak 47 rute. Kata Kunci

I.

: Algoritma Ant Colony System, Traveling Salesman Problem

PENDAHULUAN 1.1.

Latar Belakang Pada saat ini, transportasi adalah salah satu hal yang sangat penting, karena

masyarakat selalu membutuhkan untuk berpindah tempat dari satu tempat ke tempat lainnya, untuk melakukan berbagai aktivitas.Ada bermacam-macam sarana transportasi yang umum digunakan. Ada yang berupa kendaraan pribadi seperti mobil atau motor, dan ada juga yang berupa kendaraan umum seperti bus, angkutan kota, dan sebagainya. Trayek (jalur lintasan) angkutan umum di Kota Palu sangat tidak teratur. Akibatnya arus lalulintas ikut tidak teratur, juga menjadi penyebab seringnya terjadi kericuhan antara angkutan kota dan angkutan lainnya. Menurut Dinas Perhubungan Kota, trayek (Jalur lintasan) angkutan kota sudah ada, tetapi tidak jalan. Timbul suatu pertanyaan mengapa trayek (jalur lintasan) angkutan kota tidak jalan?. Hal itu yang menjadi pertanyaan dan harus dicarikan solusinya sehingga, permasalahan angkutan kota di Kota Palu tidak terus terjadi dan menjadi korban para pengusaha angkutan. (www.sultengnews.com) Permasalahan tidak jalannya trayek angkutan kota umumnya disebabkan oleh pendapatan yang tidak merata bagi pemilik jalur angkutan. Oleh karena itu, penentuan trayek (jalur lintasan) angkutan kota dapat diselesaikan dengan pencarian jalur dengan bobot maksimum. Penentuan jalur dengan bobotmaksimum dapat dikerjakan dengan Algoritma

AntColony System (ACS). ACS merupakan suatu algoritma yang mengambil inspirasi dari riset atas perilaku semut riil yang di dalamnya terdapat sekumpulan semut buatan dinamai ants, yang bekerja sama untuk mencari solusi terhadap suatu masalah optimasi. Berdasarkan hal tersebut maka penulis tertarik untuk membahas masalah ini untuk dikaji dan dituangkan dalam sebuah penulisan tugas akhir dengan judul “Pembuatan skema jalur angkutan Kota Palu berdasarkan pencarian lintasan dengan bobot maksimum menggunakan Algoritma Ant Colony System (ACS)”.

45

1.2.

Rumusan Masalah Berdasarkan latar belakang diatas, rumusan masalah yang

dapat diangkat dalam

penelitian ini adalah bagaimana memanfaatkan Algoritma ACS dalam pencarian lintasan dengan bobot maksimum yang diaplikasikan dalam pembuatan skema jalur angkutan kota Palu. 1.3.

Tujuan Adapun tujuan yang ingin dicapai dalam penulisan tugas akhir ini adalah Menentukan

skema jalur angkutan kota palu dengan bobot maksimum dalam setiap jalur tersebut dengan menggunakan Algoritma ACS. 1.4.

Manfaat Penelitian Manfaat dari penelitian ini adalah sebagai berikut :

1.

Hasil penelitian ini diharapkan dapat menambah pengetahuan ilmiah dan pengalaman, terutama dalam mengaplikasikan Algoritma ACS.

2.

Hasil penelitian ini dapat dijadikan referensi oleh Dinas Perhubungan Kota Palu untuk membuat jalur angkutan kota.

1.5.

Batasan Masalah Batasan dalam penelitian ini adalah sebagai berikut:

1.

Berbasis jalan yang sudah ada di Kota Palu, untuk menentukan rute dengan bobot maksimum dari terminal menuju pusat perbelanjaan.

II.

2.

Bobot survey penumpang di setiap jalan Kota Palu sudah tersedia.

3.

Data angkutan sesuai dengan data yang ada di Dinas Perhubungan.

4.

Jalan satu arah sudah diperhitungkan

METODE PENELITIAN Berdasarkan penelitian Langkah-langkah yang dilakukan dalam penelitian ini yaitu :

1.

Mulai penelitian

2.

Tahap pengumpulan data. Pada tahap ini data yang digunakan berasal dari Dinas Perhubungan. Data tersebut berupa data arah angkutan kota.

3.

Tahap pembuat skema jalan kedalam sebuah graf Setelah pengambilan data dilakukan, selanjutnya pada tahap ini data tersebut diolah kedalam bentuk peta arah angkutan umum.

46

4.

Tahap pembuatan matriks bobot berarah. Pada tahap ini jumlah penumpang pada setiap angkutan yang sesuai dengan arah yang telah ditentukan dibentuk kedalam matriks bobot berarah

5.

Mencari lintasan angkutan kota dengan bobot maksimum dengan menggunakan Algoritma ACS dan dengan bantuan Software Matlab R.2008b Pada tahap ini proses algoritma ACS memenuhi beberapa langkah diantaranya yaitu aturan transisi status, aturan pembaruan feromonlokal, dan aturan pembaruan feromon global.

6.

Menyimpulkan hasil penelitian.

7.

Selesai

III.

HASIL DAN PEMBAHASAN 3.1.

Hasil penelitian 3.1.1. Mencari Bobot Maksimum Menggunakan Algoritma Ant Colony System (ACS). Dalam mencari algoritma ACS, untuk mencari bobot maksimum dilalui tiga tahapan yaitu: 1.

Pemilihan yang akan dituju a.

Sebelum masuk dalam perhitungan algoritma ACS, terlebih dahulu akan

ditentukan jumlah semut dan iterasinya, serta penempatan semut pada awal pemberangkatan, jumlah semut yang digunakan disini yaitu 10 serta iterasinya berjalan sebanyak 4 kali, hal ini dikarenakan jumlah semut dan iterasinya sudah cukup optimal dalam menyelesaikan kasus ini. Dan penempatan semut di tiap titik dilakukan secara acak. Setelah itu akan dihitung nilai invers disini nantinya akan digunakan persamaan (1) nilai yang akan dijadikan invers berasal dari nilai bobot jumlah penumpang dari setiap titik. Contoh perhitungan pada (𝐽5 _𝐽6 ) 𝜂(𝑡, 𝑢𝑖 ) = 𝜂(𝐽5 _𝐽6 ) =

1 𝑗𝑎𝑟𝑎𝑘(𝑡,𝑢𝑖 )

............................................................................... (1) 1

𝐽𝑢𝑚𝑙𝑎ℎ𝑝𝑒𝑛𝑢𝑚𝑝𝑎𝑛𝑔(𝐽5 _𝐽6 )

=

1 20

= 0,05

Nilai awal pada perhitungan ini yaitu 0,01. b.

Pada tahapan ini terlebih dahulu akan ditetapkan nilai dari β≥0.

𝛽merupakan parameter perhitungan untuk mendapatkan nilai optimal pada ACS. Berdasarkan beberapa kali perhitungan ditemukan nilai yang tepat untuk β yaitu β=3. Selanjutnya dilakukan perhitungan untuk mendapatkan nilai temporary (t,v) berdasarkan persamaan(2) dan nilai probabilitas berdasarkan

47

persamaan (3) dari titik awal (t) ke titik selanjutnya yang belum dilalui (v). Dalam hal ini nilai temporary dan probabilitas serta hasil perhitungannya dapat dilihat sebagai berikut : Temporary (t,v) =[τ(t, v)]. [η(t, v) ]β ...................................................... (2) Temporary (r,s) =[τ(t, v)]. [η(t, v) ]3 [τ(t,v)].[η(t,v) ]β

Probabilitas=∑n

i=1[τ(t,v)].[η(t,v) ]

β

............................................................... (3)

Dalam menentukan persamaan sebagai acuan untuk memilih titik atau lokasi yang akan dituju selanjutnya, maka akan dibangkitkan suatu bilangan acak (𝑞) dengan kisaran 0 sampai 1 serta menetapkan bilangan pembatas (𝑞0 ) antara 0 sampai 1. 2.

Tahap Pembaharuan Feromon (𝜏) Lokal. Setelah titik selanjutnya yang akan dituju telah ditemukan maka tahapan

selanjutnya yaitu perubahan feromonsecara lokal dengan menggunakan persamaan 4. Contoh perhitungan dan hasil perhitungannya adalah sebagai berikut: 𝜏(𝑡, 𝑣) ← (1 − 𝜌)𝜏(𝑡, 𝑣) + ∆𝜏(𝑡, 𝑣) .................................................................... (4) 1 ∆𝜏(𝑡, 𝑣) = 𝐿𝑛𝑛 . 𝐶 dimana : 𝐿𝑛𝑛

:

Jumlah penumpang yang diperoleh angkutan

𝐶

:

Jumlah jalan yang dilalui

𝜌

:

Parameter dengan nilai 0 sampai 1

Pada perhitungan ini dibutuhkan suatu parameter dengan nilai 0 sampai 1. Untuk memasukkan pengaruh evaporasi kedalam perhitungan ini, ditetapkan nilai parameter 0.5. Parameter ini nantinya digunakan sebagai tingkat evaporasi atu penguapan dari nilai feromonyang ada. 3.

Tahap Pembaharuan Feromon (𝜏) Global Setelah melalui tahap pembaharuanferomonlokal untuk membentuk suatu rute,

maka tahap selanjutnya yang akan dilalui yaitu perubahan feromon secara global dengan menggunakan persamaan (5). Persamaan dari perubahan feromon secara global serta contohnya dapat dilihat sebagai berikut : 𝜏(𝑡, 𝑣) ← (1 − 𝛼). 𝜏(𝑡, 𝑣) + 𝛼. ∆𝜏(𝑡, 𝑣) ............................................................... (5) ∆τ(t,v)= {

Lgb -1 jika(t,v)∈turterbaik 0 jika(t,v)∉turterbaik

48

dimana : 𝜏(𝑡, 𝑣)

= Nilai feromon akhir setelah menagalami pembaharuan lokal

𝐿𝑔𝑏

= Jumlah penumpang terbanyak

𝛼

= Parameter dengan nilai antara 0 sampai 1

∆𝜏

= Perubahan feromon Setelah melalui beberapa iterasi tahap satu dan dua dengan bantuan program

MATLAB maka didapatkan rute sebagai berikut: 1.

Rute Terminal Mamboro_Terminal Petobo dengan 6 jumlah lintasan

2.

Rute Terminal Mamboro_Terminal Tipo dengan 5 jumlah lintasan

3.

Rute Terminal Manonda_Terminal Mamboro dengan 7 jumlah lintasan

4.

Rute Terminal Pantoloan_Terminal Manonda dengan 4 jumlah lintasan

5.

Rute Terminal Petobo_Terminal Tipo dengan 4 jumlah lintasan

6.

Rute Terminal Tipo_Terminal Manonda dengan 4 jumlah lintasan

7.

Rute Terminal Petobo_Terminal Pantoloan dengan 4 jumlah lintasan

8.

Rute Terminal Pantoloan_Terminal Tipo dengan 4 jumlah lintasan

9.

Rute Terminal Pantoloan_Terminal Mamboro dengan 4 jumlah lintasan

10.

Rute Terminal Manonda_Terminal Petobo dengan 5 lintasan

Adapun peta rute angkutan kota dapat dilihat pada gambarberikut :

Gambar1

: Peta rute angkutan kota Terminal Mamboro_Terminal Petobo

49

Notasi𝛼 merupakan tingkat (bobot) kepentingan relative yang diberikan untuk peromon. Dalam perhitungan ini nilai 𝛼 yang ditetepkan berdasarkan beberapa kali uji coba dalam program, dan dalam hal ini diperoleh nilai 𝛼 = 1, maka pembaruan

feromonglobalnya adalah 𝛼 = 1 dan 𝐿𝑔𝑏 = 30. Nilai feromonakhir 

Untuk (t,v) bagian dari rute dengan bobot maksimum ∆𝜏(𝑡, 𝑣) = 𝐿𝑔𝑏 −1 ................................................................................... (6)

Sebagai contoh akan digunakan pembaharuan feromon global pada (𝐽5− 𝐽6 ), yaitu dengan mensubstitusi persamaan(5) dengan persamaan (6) adalah sebagai berikut : 𝜏(𝐽5− 𝐽6 ) ← (1 − 𝛼). 𝜏(𝐽5− 𝐽6 ) + 𝛼. ∆𝜏 𝜏(𝐽5− 𝐽6 ) ← 0.03333 

Untuk (t,v) bukan bagian dari rute dengan bobot terbanyak ∆𝜏(𝑡, 𝑣) = 0 .......................................................................................... (7)

Sebagai contoh digunakan titik yang bukan merupakan jalur yang dilalui dengan mensubtitusi persamaan (5) dengan persamaan (7) 𝜏(𝐽5− 𝐽6 ) ← (1 − 𝛼). 𝜏(𝐽5− 𝐽6 ) + 𝛼. ∆𝜏 𝜏(𝐽5− 𝐽6 ) ← 0 3.2.

Pembahasan Algoritma Ant Colony System (ACS) merupakan salah satu metode untuk

menyelesaikan masalah Travelling Salesmen Problem (TSP). Dalam proses kerjanya algoritma ini akan mencari bobot maksimum dari awal pemberangkatannya, Setelah itu nilai

feromondari titik tersebut dirubah dengan aturan pembaharuan feromonlokal, Kedua proses ini akan berulang sampai semua titik terlalui. Setelah melalui beberapa kali iterasi akan ditemukan suatu rute dengan bobot maksimum. Rute inilah yang nantinya nilai peromonnya akan kembali diubah dengan menggunakan aturan pembaharuan feromon global. Setelah semua proses dilalui, maka akan didapat suatu solusi berupa rute untuk kasus TSP. Pada penelitian ini kita memulai dengan langkah pengambilan data, data yang dibutuhkan berupa data terminal, data jalan, dan data pusat perbelanjaan. Data terminal yang diperoleh yaitu sebanyak 5 terminal, Setelah data diperoleh kemudian

dengan 160 titik jalan dan 10 pusat perbelanjaan. membuat jalur kedalam graf.

Dalam proses

perhitungannya algoritma ini akan membentuk suatu lintasan dengan titik awal juga menjadi titik akhir, dengan memperhitungkan bobot jumlah penumpang dari setiap rute yang terbentuk disetiap iterasinya.

50

Dengan bantuan software Matlab akan dibentuk suatu program yang secara otomatis akan mencocokkan setiap titik – titik yang lain, sehingga membentuk suatu rute sesuai dengan proses kerja algoritma ACS. Dan rute-rute tersebutmembentuk 47 lintasan diantaranya adalah sebagai berikut :

IV.

1.

Rute Terminal Mamboro_Terminal Petobo dengan 6 jumlah lintasan

2.

Rute Terminal Mamboro_Terminal Tipo dengan 5 jumlah lintasan

3.

Rute Terminal Manonda_Terminal Mamboro dengan 7 jumlah lintasan

4.

Rute Terminal Pantoloan_Terminal Manonda dengan 4 jumlah lintasan

5.

Rute Terminal Petobo_Terminal Tipo dengan 4 jumlah lintasan

6.

Rute Terminal Tipo_Terminal Manonda dengan 4 jumlah lintasan

7.

Rute Terminal Petobo_Terminal Pantoloan dengan 4 jumlah lintasan

8.

Rute Terminal Pantoloan_Terminal Tipo dengan 4 jumlah lintasan

9.

Rute Terminal Pantoloan_Terminal Mamboro dengan 4 jumlah lintasan

10.

Rute Terminal Manonda_Terminal Petobo dengan 5 lintasan

KESIMPULAN Berdasarkan hasil yang telah dilakukan maka dapat disimpulkan sebagai berikut .Dalam

penelitian ini rute dengan bobot maksimum dari algoritma ACS membentuk 47 lintasan yaituRute Terminal Mamboro_Terminal Petobo dengan 6 jumlah lintasan, Rute Terminal Mamboro_Terminal Tipo dengan 5 jumlah lintasan, Rute Terminal Manonda_Terminal Mamboro dengan 7 jumlah lintasan, Rute Terminal Pantoloan_Terminal Manonda dengan 4 jumlah lintasan, Rute Terminal Petobo_Terminal Tipo dengan 4 jumlah lintasan, Rute Terminal Tipo_Terminal Manonda dengan 4 jumlah lintasan, Rute Terminal Petobo_Terminal Pantoloan dengan 4 jumlah lintasan, Rute Terminal Pantoloan_Terminal Tipo dengan 4 jumlah lintasan, Rute Terminal Pantoloan_Terminal Mamboro dengan 4 jumlah lintasan, Rute Terminal Manonda_Terminal Petobo dengan 5 lintasan. DAFTAR PUSTAKA [1].

………2013. Http:// www.sultengnews.com /150/trayek-di-kota-palu-amburadul/diakses.

20

Februari 2013. [2].

Dinas Perhubungan Provinsi Sulawesi Tengah. 2010. Masalah Transportasi Kota Palu. Palu. Sulawesi Tengah. Indonesia.

[3].

Mindaputra, E. 2009. Penggunaan Algoritma Ant Colony System dalam Traveling Salesman

Problem (Tsp) pada Pt. Eka Jaya Motor. Skripsi. Semarang.

51

[4].

Munir, R. 2009.Teori Graf. (http://asimtot.files.wordpress.com/2010/06/teori_graf.pdf/).Diakses 17 Februari 2013.

[5].

Nugroho, H.2011. Penggunaan Ant Colony System pada pendistribusian Koran di Universitas

Tadulako. Skripsi. Palu. [6].

Sudjana, M.A.,M.SC.1996. Metode Statistika. Penerbit Tarsito. Bandung.

52