PERANCANGAN APLIKASI OPTIMASI RUTE MENGGUNAKAN METODE CROSS ENTROPY BERBASIS WEB DENGAN GOOGLE MAPS API
Reonaldus Maxmillian, Wikaria Gazali, Jurike. V. Moniaga Universitas Bina Nusantara, Jalan KH. Syahdan No. 9 Palmerah, Jakarta 11480, Indonesia +62858-8330-7511
[email protected],
[email protected],
[email protected]
ABSTRACT Vehicle Routing Problem is problem of determining the route for distributing goods which is constrained by some goal functions . Capacitated Vehicle Routing Problem is one of the vehicle routing problem which is constrained by the capacity of the vehicles can handle. Capacitated vehicle routing problem which is usually shortened to CVRP can be solved using exact optimization method such as integer programming, but within its process, it needs much time, moreover to solve many nodes at once (a lot of points need to be served). Cross Entropy is a new developed optimization method, this method is developed by two main procedures, they are generating the distribution data sample and updating the distribution parameter based on best samples to outcome the better samples for the next iteration. And for practicing the application of the solution of this capacitated vehicle routing problem, the solution will be implemented through a web-based application.
Kata Kunci : VRP, CVRP, Optimizazion, Optimasi, Cross-entropy, Web Application
ABSTRAK Vehicle Routing Problem merupakan permasalahan penentuan rute distribusi yang melibatkan beberapa tujuan. Capacitated Vehicle Routing Problem adalah vehicle routing problem yang dibatasi dengan kapasitas kendaraan angkut. Capacitated vehicle routing problem atau yang biasa disingkat dengan CVRP dapat diselesaikan dengan menggunakan perhitungan optimasi yang eksak seperti integer programming, namun dalam prosesnya memerlukan waktu yang sangat lama, apalagi untuk permasalahan dengan simpul yang banyak (jumlah titik yang dilayani banyak). Cross Entropy merupakan suatu metode optimasi yang masih cukup baru, metode ini dikembangkan dengan dua prosedur utama yaitu melakukan generate sampel data distribusi dan melakukan update parameter distribusi berdasarkan sampel terbaik untuk menghasilkan sampel yang lebih baik (optimal) pada iterasi yang berikutnya. Dan untuk mempermudah pengaplikasian dari penyelesaian capacitated vehicle routing problem ini, akan dibuat suatu implementasi dalam aplikasi berbasis web.
Kata Kunci : VRP, CVRP, Optimizazion, Optimasi, Cross-entropy, Web Application
PENDAHULUAN Dalam kehidupan sehari-hari, di manapun, kapanpun dan siapapun pasti semua orang menggunakan kendaraan sebagai sarana transportasi mereka. Dan sering kali perjalanan mereka melalui beberapa titik perhentian dan akan kembali ke titik awal mereka memulai perjalanan tersebut. Dalam dunia bisnis, perjalanan pengiriman barang atau distribusi merupakan salah satu bagian terpenting di mana barang hasil produksi bisa sampai ke tangan konsumen ataupun distributor lainnya. Proses distribusi ini tentunya tidak dapat terlepaskan dari sistem transportasi di mana sistem transportasi ini merupakan salah satu faktor penting dalam menentukan rute pendistribusian barang. Baik dalam kehidupan sehari-hari maupun dalam dunia bisnis, permasalahan penentuan rute kendaraan dari satu titik (bisa pabrik atau rumah) menuju ke beberapa tempat dan kembali ke titik awal dikenal dengan Vehicle Routing Problem (VRP). Pada umumnya, VRP merupakan masalah penentuan rute optimal kendaraan yang berawal dan berakhir pada titik yang sama namun harus melalui titik-titik singgah (way points) sebanyak masing-masing satu kali dengan beberapa kendaraan angkut. Untuk menekan biaya transportasi ini maka perusahaan perlu mencari jalur distribusi yang tepat atau optimal untuk mendistribusikan barangnya sedemikian sehingga barang produksi dapat sampai ke tangan konsumen atau distributor lainnya dengan efisien. Salah satu contoh VRP sederhana dalam dunia bisnis adalah masalah penentuan rute optimal untuk pendistribusian produk yang seragam misalnya gas elpiji, air minum galon atau bahan bakar dari pabrik (depot) ke beberapa pelanggan atau konsumen dengan jumlah permintaan yang berbedabeda dari setiap konsumen. Namun dalam dunia bisnis, VRP menjadi semakin kompleks mengingat bahwa banyak sekali variabel-variabel yang mempengaruhi proses pendistribusian barang yang berarti kendala-kendala yang dihadapi akan semakin banyak. VRP yang akan dipecahkan dan dibahas lebih mendalam dalam penelitian ini adalah CVRP atau Capacitated Vehicle Routing Problem. CVRP merupakan VRP yang memiliki kendala kapasitas kendaraan angkut dalam prosesnya. Pada penelitian ini CVRP tidak dipecahkan secara tuntas, namun penentuan rute terpendek (optimal) merupakan salah satu bagian utama dan terpenting dalam CVRP. Ada banyak cara dan metode yang dapat digunakan untuk melakukannya, di antaranya adalah dengan metode cross entropy. Metode cross entropy awalnya diterapkan untuk menghitung probabilitas terjadinya rare event, lalu dikembangkan untuk beberapa kasus seperti optimasi kombinatorial, optimasi kontinyu, machine learning dan beberapa kelas masalah lain. Metode cross entropy termasuk dalam keluarga teknik Monte Carlo yang biasa digunakan untuk menyelesaikan kasus estimasi maupun optimasi. Dalam hal estimasi, metode cross entropy memberikan cara yang adaptif untuk menemukan distribusi sampling yang optimal untuk beberapa masalah yang cukup luas cakupannya. Dari beberapa penelitian
sebelumnya yang menjadi referensi penulis, metode cross entropy sudah diterapkan dan berhasil memecahkan masalah VRP, CVRP, Location Routing Problem, Knapsack Problem dan sebagainya. Pada beberapa penelitian juga terdapat perbandingan metode cross entropy dengan metode optimasi lainnya seperti tabu search, PSO, ant colony dan sebagainya. Dan metode cross entropy tetap memberikan hasil yang tidak kalah optimal namun dengan waktu komputasi yang lebih singkat. Untuk memudahkan implementasi dari metode cross entropy ini dalam memecahkan CVRP, akan dibuat suatu aplikasi berbasis web. Mereka perlu registrasi kemudian login dan melakukan input sesuai dengan instruksi yang diberikan. Aplikasi berbasis web ini akan dibuat dengan bahasa pemrograman PHP dan Javascript dan interface HTML dengan CSS. Untuk management databasenya digunakan MySQL.
METODOLOGI PENELITIAN Metodologi penelitian yang digunakan oleh penulis dalam skripsi ini adalah : a.
Studi Literatur Pada tahap ini, literatur-literatur yang berkaitan dengan penelitian dikumpulkan guna menunjang penelitian yang dilakukan. Literatur-literatur yang digunakan berhubungan dengan topik mengenai algoritma metode cross entropy dan penerapannya pada pemecahan masalah optimasi penentuan rute transportasi. Topik-topik literatur ini menjadi dasar teori dalam penelitian.
b. Pembuatan Program Simulasi Setelah dasar teori terkumpul dari studi literatur. Maka dilakukan tahap pembuatan program simulasi. Pembuatan program dalam penelitian ini dilakukan dalam beberapa tahap, antara lain tahap perancangan flowchart dan UML program, desain mock-ups (story board) program, perancangan database dan perancangan user interface. c.
Uji Coba dan Evaluasi Setelah program simulasi selesai dibuat, maka program tersebut akan diuji dan dievaluasi menggunakan data-data dari penelitian-penelitian yang sudah ada sebelumnya.
METODE CROSS ENTROPY Metode cross entropy melibatkan prosedur iterasi di mana setiap iterasi tersebut melibatkan dua fase sebagai berikut (Rubinstein, 2001:p128-190).: a.
Melakukan pembangkitan sampel random (x) dengan menggunakan mekanisme atau distribusi tertentu,
b.
Memperbaharui parameter (v) atau (w) dari mekanisme random berdasarkan data sampel elit untuk menghasilkan sampel yang lebih baik pada iterasi berikutnya.
Sampel elit adalah beberapa persen dari sampel yang kita pilih untuk memperbaiki atau mengupdate parameter (v) atau (w) yang digunakan. Kedua fase di atas merupakan dua fase utama yang terdapat dalam metode cross entropy pada umumnya. Namun dalam penelitian kali ini, akan lebih banyak dibahas mengenai metode cross entropy untuk melakukan optimasi, terutama memecahkan Capacitated Vehicle Routing Problem (CVRP). Metode cross entropy menyelesaikan suatu permasalahan dengan membangkitkan sejumlah N kandidat solusi yang dibangkitkan secara random dengan distribusi tertentu yang kemudian difitkan dengan fungsi tujuan. Kemudian dari sampel tersebut dipilih sejumlah n sampel terbaik yang kemudian dijadikan inputan untuk memperbaharui parameter yang digunakan sehingga kandidat solusi pada iterasi berikutnya berasal dari sampel terbaik pada iterasi sebelumnya. Adapun pengembangan metode cross entropy dalam menyelesaikan CVRP dapat dilihat dari tahapan berikut:
a.
Pendefinisian input dan output yang dilakukan untuk menentukan input apa saja yang akan diproses dalam algoritma metode cross entropy dan output apa saja yang akan ditampilkan sebagai hasil dari proses tersebut. Namun perlu diingat pada bab ini kita hanya akan membahas input dan output yang terlibat dalam algoritma metode cross entropy itu sendiri bukan input dan output dari program hasil implementasi algoritma metode cross entropy. Input dan output yang digunakan dalam metode algoritma cross entropy untuk memecahkan CVRP adalah sebagai berikut : •
Input : lokasi pabrik/depot dan lokasi semua pelanggan yang akan dilayani, jumlah permintaan tiap pelanggan, kapasitas angkut masing-masing kendaraan, jumlah sampel yang akan dibangkitkan, parameter ρ, parameter smoothing α, toleransi pemberhentian β.
•
Output : Rute optimal, biaya perjalanan, jarak yang ditempuh, jumlah iterasi yang dilakukan.
b.
Menentukan nilai dari parameter penunjang seperti ρ, α dan β. Dan tentukan juga jumlah sampel rute yang akan dibangkitkan (N) pada setiap iterasi. Nilai α yang bagus adalah antara 0,7 dan 1. Sedangkan untuk N dan ρ ditentukan berdasarkan kasus yang diteliti. Hal ini dikarenakan ρ merupakan parameter yang digunakan untuk menentukan banyaknya sampel elit dari sampel yang dibangkitkan sejumlah N.
c.
Menentukan initial value matriks transisi P yang nilai diagonalnya adalah 0. Matriks transisi awal dihitung dengan formula berikut :
d.
Untuk permasalahan CVRP, node pertama atau titik awal dimulainya perjalanan harus sebuah pabrik/depot.
e.
Pembangkitan N sampel rute berdasarkan pada peluang matriks transisi yang dihitung menggunakan roulette wheel selection. Jika kumulatif peluang matriks transisi merupakan node yang terpilih selanjutnya. Kemudian nilai setiap baris dari kolom node yang terpilih diganti menjadi 0 supaya tidak terpilih kembali dan dilakukan normalisasi supaya jumlah peluang setiap baris tetap bernilai 1.
f.
Penentuan subrute berdasarkan kapasitas angkut kendaraan. Jika muatan suatu kendaraan yang akan disuplai melebihi kapasitas suatu kendaraan, maka untuk memenuhi kebutuhan pelanggan, selanjutnya kendaraan harus kembali ke depot untuk mengisi ulang muatan dan jika jumlah muatan kendaraan melebihi kapasitas depot sehingga depot tidak bisa menyuplai lagi dan diganti oleh depot lain.
g.
Menghitung total biaya yaitu penjumlahan biaya perjalanan, Biaya perjalanan sebanding dengan total jarak dari setiap rute yang dibangkitkan.
h.
Mengurutkan total biaya terbaik terlebih dahulu, kemudian mengambil ρ*N terbaik yang dijadikan sampel elit. Sampel elit tersebut kemudian diplot ke dalam matriks w dengan menggunakan node transition, di mana baris menyatakan node awal dan kolom menyatakan node tujuan.
i.
Memperbaharui matriks transisi P berdasarkan pembangkitan lintasan yang sesuai dengan rumus berikut : dengan w adalah probabilitas transisi yang dihitung dari adalah probabilitas transisi iterasi sebelumnya. sampel elit dan Jika syarat pemberhentian yang ditentukan telah tercapai, maka iterasi berhenti dan hasil optimasi bisa diketahui, jika belum tercapai maka proses b sampai j diulangi lagi. Syarat pemberhentian pada umumnya adalah maksimum selisih dengan < 0.005
PERANCANGAN APLIKASI
Data Flow Diagram Optimization System
Pada diagram konteks atau DFD level 0 dapat dilihat hubungan antara sistem aplikasi optimasi rute dengan entitas eksternal yaitu user selaku pengguna aplikasi dan dengan Google Maps API sebagai menyedia layanan peta dan direksi rute. Interaksi yang terjadi adalah user dapat melakukan login ke sistem apabila telah memiliki username dan password. Apabila belum, user dapat melakukan register untuk mendapatkan username dan password untuk login dan menggunakan aplikasi. Setelah login, user dapat memasukkan data-data yang diperlukan untuk melakukan optimasi. Seluruh data dan informasi yang digunakan pada aplikasi optimasi ini akan disimpan pada suatu basis data dengan struktur sebagai berikut. Data-data dan informasi tersebut antara lain adalah informasi user yang menggunakan aplikasi ini, data project yang dimiliki oleh tiap user, informasi depot, customer dan kendaraan yang dimiliki oleh tiap project dan informasi rute tersingkat yang berhasil dibangkitkan oleh metode cross entropy untuk setiap project.
Entity Relationship Diagram Optimization System
IMPLEMENTASI Aplikasi Optimization Routing hanya dapat digunakan secara online. Hal ini berarti user yang akan menggunakan aplikasi ini memerlukan koneksi internet yang stabil. Aplikasi ini dapat diakses melalui website OptimizeRoute.16mb.com. Aplikasi ini menggunakan layanan free web hosting dari Idhostinger (www.idhostinger.com).
Tampilan Awal Program
Tampilan Program Setelah Berhasil Login
Tampilan Google Maps Pada Program
Tampilan Hasil Optimasi pada Program
SIMPULAN DAN SARAN Kesimpulan yang didapatkan berdasarkan hasil perancangan aplikasi optimasi rute adalah sebagai berikut : 1.
Metode cross entropy dapat digunakan dalam pencarian rute optimal yang berawal dan berakhir pada titik yang sama melalui beberapa way points (titik singgah).
2.
Aplikasi ini dapat memberikan pilihan beberapa opsi rute optimal lengkap dengan peta dan direksi rute dalam penentuan rute yang optimal.
3.
Penerapan metode cross entropy ke dalam program aplikasi komputer bebasis web memudahkan perhitungan sehingga dapat digunakan oleh user yang telah melakukan registrasi dan login ke dalam aplikasi.
Berdasarkan perancangan aplikasi yang telah dilaksanakan terdapat beberapa saran yang dapat dijadikan masukkan, antara lain : 1.
Metode yang digunakan (metode cross entropy) memang dapat menghasilkan rute yang optimal, namun pada kenyataannya rute yang optimal belum cukup untuk mengoptimalkan proses distribusi.
2.
Penambahan jumlah titik yang dilalui (way points).
3.
Penambahan fitur GPS (Global Positioning System) sehingga dapat mempermudah perjalanan menelusuri rute yang diperoleh.
REFERENSI Aldous, Joan. M dan Wilson, Robin. J. (2004). Graph and Applications : An Introductory Approach. 4th Printing Faculty of Mathematics and Computing. The Open University. Walton Hall, Milton Keynes MK7 6AA, United Kingdom. Anonymous, (2011), Google Maps JavaScript API V3. Diambil dari : h ttp:/ /code.goog le.com/. April 2015 Arief, M. R. (2011). Pemrograman Web Dinamis Menggunakan PHP dan MySQL. Yogyakarta Botev, Z.I., Kroese, D.P., Rubinstein, R.Y, and L'Ecuyer, P. (2013). The Cross-Entropy Method for Optimization. In Handbook of Statistics, vol. 31: Machine Learning: Theory and Applications, V. Govindaraju and C.R. Rao, Eds, Chennai: Elsevier B.V., pp. 35-59. Diambil dari : http://www.maths.uq.edu.au/~kroese/ps/CEopt.pdf . April, 2015 Celeste F. dan Dambreville. (2004). Optimal Path Planning using Cross-Entropy Method. CEP, France : Department of Geomatics Imagery Perception. Diambil dari : http://www.isif.org/fusion/proceedings/fusion06CD/Papers/303.pdf. Maret, 2015 Chepuri, Krishna dan Tito Homem de Mello. (2011). Solving the Vehicle Routing Problem with Stochastic Demands using the Cross Entropy Method. Colombus, Ohio, USA : Department of Industrial, Systems Engineering. The Ohio State University. Diambil dari : http://www.optimization-online.org/DB_FILE/2004/06/893.pdf. Maret, 2015 Conolly, Thomas dan Carolyn E. Begg. (2010). Database Systems : A Practical Approach to Design, Implementation, and Management.. Jakarta De Boer, et al. (2005), January. A Tutorial on the Cross Entropy Method, Annals of Operation Research vol 134, pp. 19-67. http://www.maths.uq.edu.au/~kroese/ps/aortut.pdf. Maret, 2015 Golden, Bruce. (2008). The Vehicle Routing Problem: Latest Advances and New Challenges. New York: Springer Science & Business Media. Gunadi, G. 3 Juli (2012). Aplikasi Berbasis Web. Diambil dari http://www.academia.edu/. Mei, 2015 Kroese, D.P., Rubinstein, R.Y, and Glynn, P.W. (2013). The Cross-Entropy Method for Estimation. In Handbook of Statistics, Volume 31: Machine Learning: Theory and Applications, V. Govindaraju and C.R. Rao, Eds, Chennai: Elsevier B.V., pp. 19-34. Diambil dari http://www.maths.uq.edu.au/~kroese/ps/CEest.pdf. Juni 2015 Negrino, T. dan Smith, D. (2012). Javascript Visual Quickstart Guide. California : Peachpit Press.
Nilawati, A. R. 10 Oktober (2009). Gunadarma. Diambil dari Gunadarma Staff: http://rama.staff.gunadarma.ac.id/Downloads/files/14921/2+definisi+dan+simbol+Flowcha rt.pdf. Mei, 2015 Nugroho, B. (2009). Database Relational dengan MySQL. Yogyakarta: Andi. Pouncey, L. dan York, R. (2011). Beginning CSS (Cascading Style Sheets) for Web Design, Indiana: Wiley Publishing Incorporaion. Prabaningtyas, Nuresti dan Budi Santoso. (2012). Penerapan Metode Cross Entropy dalam Penyelesaian Capacitated Location Routing Problem. Surabaya : Jurusan Teknik Industri, Institut Teknologi Sepuluh Nopember (ITS). Diambil dari : https://www.academia.edu/1910855/PENERAPAN_METODE_CROSS_ENTROPY_DALA M_PENYELESAIAN_CAPACITATED_LOCATION-ROUTING_PROBLEM. Maret, 2015 Pressman, R. S. (2010). Software Engineering : A Practitioner's Approach. New York: McGraw-Hill. Raghavan S. dan Bala Chandran. (2003). Modeling and Solving the Capacitated Vehicle Routing Problem on Trees. Department of Industrial Engineering and Operations Research.. California, USA : University of California. The Robert H. Smith School of Business and Institute for System Research. University Of Maryland. Diambil dari : http://terpconnect.umd.edu/~raghavan/preprints/chap11.pdf. Maret, 2015 Ralphs, Ted., Joe Hartman dan Matt Galati. (2001). Pennysylvania, USA : Capacitated Vehicle Routing and Some Related Problems, Industrial and System Engineering, Lehigh University. Diambil dari : http://coral.ie.lehigh.edu/~ted/files/talks/CSE05.pdf. April, 2015 Rera, Gladiez Florista dan Budi Santoso . (2011). Penerapan Metode Cross Entropy dalam Penyelesaian Capacitated Vehicle Routing Problem (Studi Kasus : Distribusi Koran Jawa Pos Surabaya). Surabaya : Jurusan Teknik Industri, Institut Teknologi Sepuluh Nopember (ITS). Diambil dari : http://digilib.its.ac.id/public/ITS-Undergraduate-10663-Paper.pdf. Maret, 2015 Rubinstein, R.Y. (1999). The Cross Entropy Method for Combinatorial and Continuous Optimization, Methodology and Computing in Applied Probability, vol 1, Kluwer Academoc Publishers: Boston. Shneiderman, B., & Plaisant, C. (2010). Designing The User Interface (6th Edition ed.). Boston: Pearson Svennerberg, Gabriel. ( 2010). Beginn ing Google Maps API 3. Ap ress, United States of America. Tulach, Jaroslav. (2008). Practical API Design : Confessions of a Java™ Framework Architect. Ap ress, United States of America. Welling, L, & Thomson, L. (2005). PHP and MySQL Web Development. Indiana: Sams Publishing. West, M. (2013). HTML 5 Foundations. Brighton: John Wiley and Sons Ltd. Whitten, J. L., & Bentley, L. D. (2007). System Analysis and Design for The Global Enterprise (7th Edition). California: Irwin/McGraw-Hill.
RIWAYAT PENULIS Reonaldus Maxmillian lahir di kota Jakarta pada 1 Agustus 1992. Penulis menamatkan pendidikan S1 di Universitas Bina Nusantara dalam bidang ilmu Teknik Informatika dan Matematika pada tahun 2015.
