Metode heuristik dalam penentuan rute
Permasalahan penentuan rute biasanya merupakan permasalahan NP-Hard Problem dimana penyelesaian dengan metode exact seringkali akan memakan waktu yang cukup lama untuk menyelesaikannya. Karena sebab inilah banyak para ahli yang merancang penyelesaian suatu problem dengan menggunakan merode heuristik. Metode Heuristik adalah teknik yang dirancang untuk memecahkan masalah yang mengabaikan apakah solusi dapat dibuktikan benar, tapi yang biasanya menghasilkan solusi yang baik atau memecahkan masalah yang lebih sederhana yang mengandung atau memotong dengan pemecahan masalah yang lebih kompleks. Metode Heuristik ini bertujuan untuk mendapatkan performa komputasi atau penyederhanaan konseptual, berpotensi pada biaya keakuratan atau presisi. Metode heuristik ada dua jenis yakni metode heuristik sederhana dan metaheuristik. Metode heuristik contohnya adalah cheapest insertion, Priciest Insertion, Nearest insertion, Farthest Insertion, Nearest addition dan Clarke and Wright Saving Method. Adapun penjelasannya sebagai berikut :
1) Cheapest insertion hal pertama kali yang dilakukan adalah menentukan setiap titik yang masih tersisa dan bebas atau titik yang belum dikunjungi yang menghasilkan link optimal untuk menyisipkan titik ini. Ini sesuai dengan minimisasi pertama dalam persamaan:
Penalti penyisipan adalah jumlah jarak ke titik bebas dikurangi jarak dari link yang akan dihapus. Pada Cheapest insertion kemudian dilakukan pemilihan titik untuk disisipkan sebagai titik penyisipan dengan penalti minimum.
2) Pada Priciest insertion yang dilakukan pertama kali adalah menentukan setiap titik yang masih tersisa dan bebas atau titik yang belum dikunjungi yang menghasilkan link optimal untuk menyisipkan titik ini. Ini sesuai dengan minimisasi pertama dalam persamaan:
Identik dengan proses cheapest insertion, penalti penyisipan adalah jumlah jarak ke titik bebas dikurangi jarak dari link yang akan dihapus. Pricest Insertion kemudian dipilih titik untuk disipkan sebagai titik penyisipan dengan penalti maksimum.
3) Pada Nearest insertion yang dilakukan pertama kali adalah menentukan titik untuk disipkan dengan mencari titik bebas yang paling dekat dengan suatu titik pada tur. Algoritma pada dasarnya melakukan sebuah operasi mini-min pada jarak dari titik bebas untuk suatu titik pada tur.
Selanjutnya dengan algoritma ini, ditentukan link terbaik untuk menyisipkan titik ini. Proses ini identik dengan proses pada cheapest insertion dan farthest insertion.
4) Pada farthest insertion yang dilakukan pertama kali adalah menentukan setiap titik bebas yang memiliki jarak ke titik manapun pada tur terkecil. Kemudian masukkan titik bebas yang memiliki maksimum jarak terkecil ke titik pada tur. Algoritma ini pada dasarnya merupakan sebuah operasi maxi-mnt pada jarak dari titik bebas untuk suatu titik pada tur.
Selanjutnya ditentukan link terbaik untuk menyisipkan titik ini. Proses ini identik dengan proses pada cheapest insertion dan farthest insertion.
5) Pada Nearest addition yang pertama kali dilakukan adalah menentukan titik yang akan disisipkan dengan mencari titik bebas yang paling dekat dengan suatu titik pada tur.
Selanjutnya ditentukan link terbaik untuk menyisipkan titik ini dengan memeriksa dua link pada insiden tur ke titik tur paling dekat dengan titik bebas tersebut. Ini merupakan pencarian yang lebih terbatas dibanding dengan proses pada cheapest insertion dan farthest insertion
6) Clarke dan Wright (1964) mengembangkan prosedur konstruksi yang memanjang sebagian rute atau rute primitif pada dua titik akhir. Secara konseptual algoritma mendefinisikan titik pangkal dan menbangun sebuah tur Eulerian yang memiliki pengertian mengunjungi masing-masing titik lain dan kemudian kembali ke pangkal. Tur Eulerian kemudian dikurangi panjangnya dengan mencari jalan dengan saving terbesar. Saving dihitung sebagai jumlah dari jarak ke titik dasar dari dua titik dikuranigi jarak antara dua titik.
Gambar Ilustrasi Clarke and Wright Tour Extension
Setelah dua titik telah bergabung, titik tersebut tiidak akan pernah dipisahkan lagi oleh algoritma Clarke dan Wright. Serial varian dari algoritma memperluas parsial satu rute di ujungnya titik, yang tersambung ke titik pangkal. Titik berikutnya kemudian dipilih dengan mencari titik dengan saving terbesar untuk saat ini titik akhir dari tur parsial.
Tugas Akhirku….Title : Developing Heuristic Algorithm for Solving Dynamic Pick Up and delivery Problem with Time Windows (DPDPTW) for City Courier Service Provider
Ya ini adalah tugas akhirku. hehehehehehe,, Aku ngerjain ini setahun yang lalu. Waktu bongkar2 file tiba-tiba jadi pengen ngeposting di blog hahahahaha (dasar narsis ^^V), jadi aku post sekarang…
Tentang apa sih??
Yap,TA ku ini tentang salah satu varian dari VRP (Vehicle Routing Problem) yakni PDPTW (Pick Up Delivery Problem with Time Windows). Dari namanya aja dah ketahuan bedanya kan??? Kalo VRP biasa kendaraan cuma ngangkut barang atau ngirim barang aja dengan melewati suatu rute tertentu. Nah, kalo si PDPTW ini, dalam satu rute kendaraan ada aktivitas pick up dan delivery yang berpasangan. Oh ya karena ada TW (Time Windows)nya, maka untuk Pick Up dan delivery harus dilakukan dalam kurun waktu tertentu. Tapi disini aku pakai model dengan aturan soft time windows yakni boleh dilanggar aturan TWnya dengan syarat ada pinalti costnya….Terus karena disini aku mempertimbangkan perubahan rute akibat adanya order atau request baru sepajang periode tertentu jadilah si PDPTW ini permasalahan DPDPTW (Dyanmic Pick Up and Delivery Problem With Time Windows) Panjangnya huff….hehehehehe
Bingung??
Gambarannya kaya gini nih,, misalnya kita mau kirim barang dari rumah kita ke rumah temen, terus kita telepon ke depot center pengiriman barang misal kaya fedex, dhl, TIKI, dsb. Nah, ditelepon itu kita minta salah seorang kurirnya untuk jemput barang
kita. Waktu jemputnya boleh dibatasin, misalnya karena kita harus masuk kerja jam 8 pagi, maka si kurir cuma boleh ambil barang dari jam 6 sampe 7.30 dimana kita masih berada dirumah. Begitu juga yang nerima barang, misalkan temen kita yang akan nerima barang tersebut berada di rumah itu sekitar jam 2 sampai jam 3 sore. Terus berkaitan dengan waktu, kalo si Kurir itu dateng sebelum waktu yang ditetapin maka si kurir harus nunggu dilokasi tersebut. Tapi kalo dia dateng setelah rentang waktu tersebut, maka si kurir kena pinalti cost yang setara dengan waktu keterlambatannya. Yang jadi masalah, customernya si kurir kan ga cuma satu, kalo setiap pengiriman dan penjemputan barang dilakukan oleh satu kurir, si punya perusahaan jasa kirim barang pastinya bakal rugi. Makanya disini perlu diatur sedemikian hingga satu kurir dapat melayani beberapa customer. Kalo penugasannya asal-asalan bisa jadi repot kan?? Apalagi kalo ga ada perencaanaan yang bagus bisa-bisa selain keterlambatan nantinya cost perjalanan juga bisa membengkak. Sehingga penjadwalan rute kurir harus dilakukan. Tentu aja tujuannya yakni meminimasi cost perjalanan dari kurir. Nah, permasalahan kaya gini biasanya disebut dengan PPDTW. Dibanding dengan VRP biasa, permasalahan ini jauh lebih kompleks karena penjadwalan rute bukan hanya meperhatikan jarak antar node (customer) dan kapasitas kendaraan kurir, tapi juga memperhatikan batasan-batasan yang berkaitan dengan Pick Up dan Deliverynya. Apa aja batasan-batasan tersebut? Batasan tersebut adalah sebagai berikut:
1. Pairing Cosntraint, yakni setiap order ID memiliki dua lokasi yang akan dikunjungi yakni lokasi pick up dan deliver yang berpasangan.Berpasangan ini memiliki arti bahwa lokasi pick up dan delivery dengan order ID yang sama haru berada pada rute kendaraan yang sama.
2. Precedence Constraint, yakni untuk lokasi pick up dan delivery yang berpasangan, lokasi pick up harus terlebih dahulu dikunjungi sebelum mengunjungi lokasi delivery. Untuk jelasnya bisa dilihat pada gambar dibawah ini.
Batasan pada PDPTW yang membedakan dengan VRP
-
Batasan pada PDPTW yang membedakan dengan VRP
Terus Itukan PDPTW, nah kalo DPDPTW maksudnya gimana???
PDPTW itu untuk kasus statis dimana si depot penyedia jasa kurir menjadwalkan rute kendaraan di awal waktu operasi penyedia jasa sebelum semua kendaraan/kurir pergi dari depot. Jadi untuk pengiriman pada hari tertentu, semua order pengiriman telah dijadwalkan dan tidak boleh diganggu gugat (dirubah-rubah) bila ada order baru masuk. Untuk kasus PDPTW ini biasanya terdapat asumsi bahwa order baru yang masuk setelah rute dijadwalkan maka akan ditugaskan untuk hari berikutnya. Nah, kalo DPDPTW ini sebaliknya, depot memang menjadwalkan rute awal kendaraan, tapi dalam perjalanannya kendaraan ini diperbolehkan untuk melayani order yang baru muncul pada waktu operasi pengiriman dan penjemputan. Setiap kali ada order baru (misal melalui telepon, internet, atau sms), maka depot akan menjadwalkan ulang kendaraan dengan mengikutsertakan order baru didalam rute-rute tersebut.
Terus gimana caranya tau kendaraan sedang berada pada lokasi yang mana?
Dalam kasus ini, untuk memungkinkan dilaukannya hal tersebut tentu aja yang terpenting adalah adanya vehicle tracking system (VTS). VTS dengan teknologi GPS nya (Global Posistioning System) ini memungkinkan kendaraan yang sedang melakukan penjemputan dan pengiriman barang dalam rutenya dapat ditelusuri jejaknya dari depot hingga kembali ke depot. Jadi setiap lokasi yang telah dikunjungi kendaraan dan posisinya pada waktu tertentu dapat diidentifikasi menggunakan GPS. Hal ini akan menjadi informasi yang sangat penting dalam penentuan rute yang dinamis karena posisi kendaraan akan menentukan keputusan lokasi mana yang akan dikunjungi terlebih dahulu yakni order sesuai urutan pada rute lama atau order baru. Tentu saja
penentuan keputusannya berdasarkan cost paling rendah yang dihasilkan dari kedua skenario tersebut. Untuk lebih jelasnya dapat dilihat dari gambar dibawah ini:
Gambar Proses Penjadwalan Ulang Rute Kendaraan Setelah Ada Order Baru
-
Gambar Proses Penjadwalan Ulang Rute Kendaraan Setelah Ada Order Baru
Dari gambar tersebut dapat dilihat perubahan rute akibat adanya order baru dari customer.
Apa yang ku kerjakan??
Dalam tugas akhirku ini, yang kukerjakan adalah mengembangkan model dan algoritma dari permasalahan untuk kemudian dilakukan penyelesaiannya. Tujuan yang hendak dicapai dari pengembangan model dan algoritma penyelesaian permasalahan ini adalah mampu melakukan keputusan untuk penugasan kendaraan dan meminimasi total biaya yang terdiri dari travel time dan keterlambatan pada lokasi delivery (pinalty cost)
Berikut ini adalah abstrak dari TA ku, dapat di download di:
Recent Comments