Abstrak
Penelitian ini dilakukan atas
dasar sebuah permasalahan yang disebut TSP atau Travelling Salesman Problem.
TSP adalah sebuah masalah yang melibatkan pertidaksamaan, pemrograman,
persamaan linear, dll.
Penelitian ini menggunakan
desain penelitian kuantitatif, yaitu penelitian sistematis yang menggunakan
model matematika untuk menghitung data yang telah didapatkan. Populasi yang
diambil dalam penelitian ini yaitu Perumahan Gema Pesona yang berletak di Jalan
Tole Iskandar di daerah Depok Timur, seluruh rumah di dalam perumahan tersebut
dianggap sebagai sampel dalam penelitian ini. Jarak total seluruh perumahan
yaitu 2820 meter atau 2,82 kilometer.
Setelah bentuk permasalahan
TSP dimasukkan kedalam Microsoft Excel, dan kendala – kendalanya dimasukkan
kedalam program Solver, program tersebut menganalisis permasalahan dan kendala
– kendala yang telah dimasukkan, sehingga akhirnya didapatlah hasil minimum
permasalahan tersebut. Sales mengambil jalan yang dimulai dari persimpangan A
lalu menuju ke persimpangan C, lalu menuju F, lalu seterusnya sampai kembali
lagi ke persimpangan A, dengan hasil akhir jarak minimum 2640 meter atau 2,64
kilometer.
Kata
kunci: Travelling Salesman Problem, pertidaksamaan, persamaan linear, program
Solver
1.
Pendahuluan
Travelling Salesman Problem atau
yang biasa disingkat dengan TSP merupakan sebuah permasalahan yang dipelajari
di dalam riset operasi dan ilmu komputer teoritis. Masalah yang biasa terdapat
dalam TSP yaitu bagaimana caranya menemukan rute terpendek untuk mengunjungi
tiap kota tepat satu kali dan akhirnya kembali ke kota asal. Masalah ini pertama
kali dirumuskan tahun 1930 dan merupakan salah satu masalah yang paling
intensif dipelajari dalam optimasi. Salah satu contoh TSP adalah
seorang sales yang menawarkan barang
secara door-to-door pada sebuah
perumahan. Tiap melakukan pekerjaannya, sales
memilih solusi perjalanan yang efektif. Sales
pun harus memilih jalan yang akan dipilih terlebih dahulu dengan
memperkirakan jaraknya. Selain itu, permasalahan tersebut juga terdapat pada
pekerjaan petugas PLN.Untuk menyelesaikan
permasalahan tersebut, dibuatlah model persamaan matematika dengan bentuk
sistem pertidaksamaan linear yang akan diselesaikan dengan menggunakan program Solver yang merupakan bagian dari Microsoft Excel. Dalam penelitian ini
akan dibahas mengenai cara menyelesaikan TSP dengan menggunakan program Solver. Adapun manfaat dari penelitian
ini adalah sebagai berikut:
1. Dapat
menambah pengetahuan lebih banyak tentang TSP beserta cara pemecahannya.
2. Dapat
menambah wawasan dan keahlian dalam menggunakan program Solver.
3. Menambah
keahlian dan wawasan dalam menggunakan Microsoft Excel dan program –
programnya.
2. Metodologi penelitian
Penelitian
ini menggunakan desain penelitian kuantitatif, yaitu penelitian sistematis yang
menggunakan model matematika untuk menghitung data yang telah didapatkan.
Populasi
yang diambil dalam penelitian ini yaitu Perumahan Gema Pesona yang berletak di
Jalan Tole Iskandar di daerah Depok Timur, seluruh rumah di dalam perumahan
tersebut dianggap sebagai sampel dalam penelitian ini. Jarak
total yang didapat dari perumahan tersebut yaiu 2820 meter atau 2,82 kilometer.
Instrumen
– instrumen yang dibutuhkan dalam penelitian ini adalah sebagai berikut:
-
Microsoft
Office
-
Program Solver
-
Google
Map
Teknik
pengumpulan data dalam penelitian ini adalah sebagai berikut:
a.
Mencari sumber – sumber yang berhubungan dengan
data – data penelitian.
b.
Mencatat data – data yang berasal dari sumber –
sumber tersebut.
c.
Menuliskan
data – data yang telah dicatat di komputer
Prosedur – prosedur yang dilakukan dalam penelitian ini adalah sebagai berikut:
1.
Persiapan:
- Peneliti menyiapkan instrumen – instrument
yang dibutuhkan dalam penelitian
2.
Pengambilan data:
- Mengunjungi
perumahan yang dijadikan sampel penelitian.
- Menelusuri dan menganalisis seluk – beluk
perumahan tersebut dengan mengendarai motor.
- Membuat sketsa perumahan tersebut dengan
melihat Google Map pada komputer dan
menggunakan alat berupa kertas dan pensil
- Mengevaluasi
data dan membuat asumsi – asumsi yaitu:
a. Memperkirakan
jarak dari tiap persimpangan ke persimpangan lainnya. Mengukur jarak dengan
cara menggunakan patokan satu rumah. Tiap rumah lebarnya 10 meter.
b. Mengasumsikan
bahwa sebisa mungkin sales tidak
mengambil jalan yang jauh yang mengharuskan memutar, dan menghindari jalan yang
diperkirakan dilewati dua kali.
Data –
data yang telah diperoleh kemudian dibentuk menjadi model permasalahan berupa
pertidaksamaan linear, contohnya ac 
1. Lalu
dimasukkan kedalam program Solver
untuk dicari solusinya
1. Lalu
dimasukkan kedalam program Solver
untuk dicari solusinya
3.
Hasil
dan Pembahasan
Hasil
penelitian ini yaitu sebagai berikut:
|
Objective Cell (Min)
|
|||||
|
Cell
|
Name
|
Original Value
|
Final Value
|
||
|
$GI$5
|
>= 28
|
50
|
50
|
||
|
Variable Cells
|
|||||
|
Cell
|
Name
|
Original Value
|
Final Value
|
Integer
|
|
|
$B$2
|
a-c
|
1
|
1
|
Integer
|
|
|
$C$2
|
b-a
|
1
|
1
|
Integer
|
|
|
$D$2
|
b-i
|
1
|
1
|
Integer
|
|
|
$E$2
|
c-e
|
0
|
0
|
Integer
|
|
|
$F$2
|
c-f
|
1
|
1
|
Integer
|
|
|
$G$2
|
d-b
|
2
|
2
|
Integer
|
|
|
$H$2
|
d-c
|
0
|
0
|
Integer
|
|
|
$I$2
|
d-e
|
1
|
1
|
Integer
|
|
|
$J$2
|
e-d
|
1
|
1
|
Integer
|
|
|
$K$2
|
e-h
|
1
|
1
|
Integer
|
|
|
$L$2
|
f-e
|
1
|
1
|
Integer
|
|
|
$M$2
|
f-g
|
0
|
0
|
Integer
|
|
|
$N$2
|
g-f
|
0
|
0
|
Integer
|
|
|
$O$2
|
g-h
|
0
|
0
|
Integer
|
|
|
$P$2
|
g-j
|
1
|
1
|
Integer
|
|
|
$Q$2
|
h-g
|
1
|
1
|
Integer
|
|
|
$R$2
|
h-i
|
0
|
0
|
Integer
|
|
|
$S$2
|
h-j
|
0
|
0
|
Integer
|
|
|
$T$2
|
i-b
|
0
|
0
|
Integer
|
|
|
$U$2
|
i-d
|
2
|
2
|
Integer
|
|
|
$V$2
|
i-h
|
0
|
0
|
Integer
|
|
|
$W$2
|
j-g
|
0
|
0
|
Integer
|
|
|
$X$2
|
j-k
|
0
|
0
|
Integer
|
|
|
$Y$2
|
j-o
|
1
|
1
|
Integer
|
|
|
$Z$2
|
k-i
|
1
|
1
|
Integer
|
|
|
$AA$2
|
k-j
|
0
|
0
|
Integer
|
|
|
$AB$2
|
k-l
|
1
|
1
|
Integer
|
|
|
$AC$2
|
l-k
|
1
|
1
|
Integer
|
|
|
$AD$2
|
l-m 1
|
1
|
1
|
Integer
|
|
|
$AE$2
|
l-m 2
|
0
|
0
|
Integer
|
|
|
$AF$2
|
m-l 1
|
0
|
0
|
Integer
|
|
|
$AG$2
|
m-l 2
|
1
|
1
|
Integer
|
|
|
$AH$2
|
m-n
|
0
|
0
|
Integer
|
|
|
$AI$2
|
n-k
|
1
|
1
|
Integer
|
|
|
$AJ$2
|
n-m
|
0
|
0
|
Integer
|
|
|
$AK$2
|
o-p 1
|
2
|
2
|
Integer
|
|
|
$AL$2
|
o-p 2
|
0
|
0
|
Integer
|
|
|
$AM$2
|
p-o 2
|
1
|
1
|
Integer
|
|
|
$AN$2
|
p-aa
|
1
|
1
|
Integer
|
|
|
$AO$2
|
q-n
|
1
|
1
|
Integer
|
|
|
$AP$2
|
q-s
|
0
|
0
|
Integer
|
|
|
$AQ$2
|
r-q
|
1
|
1
|
Integer
|
|
|
$AR$2
|
r-s
|
0
|
0
|
Integer
|
|
|
$AS$2
|
s-q
|
0
|
0
|
Integer
|
|
|
$AT$2
|
s-r
|
0
|
0
|
Integer
|
|
|
$AU$2
|
s-t
|
0
|
0
|
Integer
|
|
|
$AV$2
|
t-s
|
0
|
0
|
Integer
|
|
|
$AW$2
|
t-u
|
1
|
1
|
Integer
|
|
|
$AX$2
|
t-v
|
0
|
0
|
Integer
|
|
|
$AY$2
|
u-t
|
0
|
0
|
Integer
|
|
|
$AZ$2
|
u-v
|
1
|
1
|
Integer
|
|
|
$BA$2
|
u-w
|
0
|
0
|
Integer
|
|
|
$BB$2
|
u-z
|
1
|
1
|
Integer
|
|
|
$BC$2
|
v-t
|
1
|
1
|
Integer
|
|
|
$BD$2
|
v-u
|
0
|
0
|
Integer
|
|
|
$BE$2
|
v-ae
|
1
|
1
|
Integer
|
|
|
$BF$2
|
w-u
|
1
|
1
|
Integer
|
|
|
$BG$2
|
w-x 1
|
0
|
0
|
Integer
|
|
|
$BH$2
|
w-x 2
|
0
|
0
|
Integer
|
|
|
$BI$2
|
x-w 1
|
0
|
0
|
Integer
|
|
|
$BJ$2
|
x-w 2
|
1
|
1
|
Integer
|
|
|
$BK$2
|
x-y
|
0
|
0
|
Integer
|
|
|
$BL$2
|
y-x
|
1
|
1
|
Integer
|
|
|
$BM$2
|
y-z
|
1
|
1
|
Integer
|
|
|
$BN$2
|
y-aj
|
0
|
0
|
Integer
|
|
|
$BO$2
|
z-u
|
0
|
0
|
Integer
|
|
|
$BP$2
|
z-y
|
0
|
0
|
Integer
|
|
|
$BQ$2
|
z-ae
|
1
|
1
|
Integer
|
|
|
$BR$2
|
aa-ab
|
1
|
1
|
Integer
|
|
|
$BS$2
|
aa-ah
|
1
|
1
|
Integer
|
|
|
$BT$2
|
ab-aa
|
1
|
1
|
Integer
|
|
|
$BU$2
|
ab-ac 1
|
0
|
0
|
Integer
|
|
|
$BV$2
|
ab-ac 2
|
1
|
1
|
Integer
|
|
|
$BW$2
|
ac-ab 1
|
1
|
1
|
Integer
|
|
|
$BX$2
|
ac-ab 2
|
0
|
0
|
Integer
|
|
|
$BY$2
|
ac-ah
|
0
|
0
|
Integer
|
|
|
$BZ$2
|
ad-r
|
1
|
1
|
Integer
|
|
|
$CA$2
|
ad-ae
|
0
|
0
|
Integer
|
|
|
$CB$2
|
ae-v
|
1
|
1
|
Integer
|
|
|
$CC$2
|
ae-z
|
0
|
0
|
Integer
|
|
|
$CD$2
|
ae-ad
|
1
|
1
|
Integer
|
|
|
$CE$2
|
ae-ag
|
0
|
0
|
Integer
|
|
|
$CF$2
|
af-ad
|
0
|
0
|
Integer
|
|
|
$CG$2
|
af-ag
|
1
|
1
|
Integer
|
|
|
$CH$2
|
ag-ae
|
0
|
0
|
Integer
|
|
|
$CI$2
|
ag-af
|
0
|
0
|
Integer
|
|
|
$CJ$2
|
ag-aj
|
1
|
1
|
Integer
|
|
|
$CK$2
|
ah-ac
|
0
|
0
|
Integer
|
|
|
$CL$2
|
ah-ai
|
1
|
1
|
Integer
|
|
|
$CM$2
|
ai-af
|
1
|
1
|
Integer
|
|
|
$CN$2
|
ai-aj
|
0
|
0
|
Integer
|
|
|
$CO$2
|
aj-y
|
1
|
1
|
Integer
|
|
|
$CP$2
|
aj-ag
|
0
|
0
|
Integer
|
|
|
$CQ$2
|
aj-ai
|
0
|
0
|
Integer
|
|
Berdasarkan
analisis yang telah dilakukan oleh program Solver,
dan setelah dimasukkan kendala – kendala sebagai berikut:
1. Harus
melewati jalan yang ada rumahnya, untuk setiap suku 
dan 
dan
2. Dalam
denah perumahan tersebut, terdapat lebih dari sama dengan 28 jalan yang
didapati melewati rumah, sehingga 28 jalan tersebut kemungkinan dipilih atau
dilewati.
3.
Terdapat jalan satu arah di perumahan tersebut,
sehingga memungkinkan sales untuk
memutar atau melewati jalan yang sudah dilewati (dua kali).
Maka
diperoleh hasil analisis Solver seperti
yang dapat dilihat pada tabel diatas. Integer artinya bilangan bulat. Dapat
disimpulkan bahwa sales memutuskan
untuk mengambil jalan dari persimpangan a ke persimpangan c dahulu, setelah itu
menuju ke persimpangan c, lalu ke persimpangan f, dan seterusnya. Jika
diurutkan, maka rute perjalanan sales dari
pintu masuk hingga kembali ke pintu keluar yaitu sebagai berikut:
ac – cf
– fe – ed – db – bi – id – de – eh – hg – gj – jo – op1 – po2 – op1 – paa –
aaab – abac2 – acab1 – abaa – aaah – ahai – aiaf – afag – agaj – ajy – yx – xw2
– wu – uz – zae – aev – vt – tu – uv – vae – aead – adr – rq – qn – nk – kl –
lm1 – ml2 – lk – ki – id – db – ba.
Setelah
rute tersebut ditempuh oleh sales,
maka diperoleh jarak terpendek yang ditempuh oleh sales yaitu:
40 + 60
+ 60 + 20 + 20 + 50 + 40 + 20 + 40 + 50 + 80 + 30 + 110 + 100 + 110 + 150 + 20
+ 60 + 50 + 20 + 90 + 40 + 80 + 20 + 50 + 60 + 30 + 50 + 40 + 40 + 30 + 20 + 40
+ 60 + 60 + 30 + 20 + 60 + 30 + 90 + 130 + 30 + 130 + 130 + 30 + 30 + 40 + 20 +
30 = 2640 meter/2,64 kilometer.
Pada tabel hasil analisis Solver terdapat beberapa jalan yang bernilai 2, itu artinya jalan –
jalan tersebut dilewati 2 kali seperti yang dapat dilihat pada kendala pertama
dan ketiga. Terdapat 28 jalan yang wajib dilewati oleh sales dikarenakan terdapat rumah pada jalan tersebut. Total yaitu sales melewati jalan sebanyak 50 kali,
seperti yang dapat dilihat pada kendala kedua.
4.
Kesimpulan
Dalam karya ilmiah ini, telah
dijelaskan tentang Travelling Salesman
Problem, yaitu permasalahan yang melibatkan pemrograman, persamaan linear,
pertidaksamaan, dan lain – lain. Penelitian ini menggunakan program Solver untuk menyelesaikan TSP tersebut.
Kesimpulan dari penelitian ini yaitu program Solver dapat digunakan sebagai salah satu solusi dalam pemecahan
TSP yang terdapat dalam pekerjaan seorang sales.
5.
Saran
Saran peneliti yaitu jika
mendapat penelitian dengan topik yang sama, diharapkan agar mencari dan
mencantumkan data dengan akurat dan menggunakan aplikasi atau program yang
lebih efektif.
6. Daftar pustaka
[1] Arifin, Johar. 2008. Aplikasi Excel untuk Perencanaan Bisnis (Business Plan). Jakarta. PT Elex Media
Komputindo.
[2] Nasendi,B.D & Anwar,
Affendi. 1985. Program Linear dan
Variasinya. Jakarta: Universitas Indonesia.
[3] Robert,
Grauer & Maryann, Barber. 2002. Exploring
Microsoft Office XP Professional, Vol 2.
[4] Simangunsong, Wilson. 2003. PKS Matematika sekolah Menengah Atas dan
mudraah Aliyah kelas X. Jakarta: Gematama.
[5] Supriansyah, Haris. 2006. Buku pintar Microsoft Office Excel.
Bandung: OASE MEDIA.
[6] Taha. Hamdy A. 1987. Operations Research an Introduction. New York. Macmillan.
[7]http://it-dimas.blogspot.com/2010/12/travelling-salesman-problem.html/
Diakses pada hari Kamis, 4
Oktober 2012 14.24 WIB
[8]http://staff.blog.ui.ac.id/komarudin74/2010/09/14/traveling-salesman-problem-tsp/
Diakses pada hari Kamis, 4
Oktober 2012, 14.32 WIB
[9]http://www.bookoopedia.com/daftar-buku/pid-5655/riset-operasi-dengan-excel.html\
Diakses pada hari Sabtu, 6
Oktober 2012, 17.32 WIB
[10]http://fingelia.blogspot.com/2009/12/beberapa-pengertian-program-linier.html
Diakses
pada hari Senin, 8
Oktober 2012, 20.09 WIB
[11]http://qiulight.blogspot.com/2010/12/contoh-makalah-matematika-program.html
Diakses
pada hari Selasa, 16 Oktober 2012, 15.11 WIB
[12]http://nnoviamanis.blogspot.com/2008/07/pengertian-dan-macam-macam
program_23.htmlDiakses pada hari
Senin, 23 Oktober 2012 17.54 WIB
No comments:
Post a Comment