Always run back to the future …..

Tugas Akhir : 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:

Abstract : DEVELOPING HEURISTIC ALGORITHM FOR DYNAMIC PICK UP AND DELIVERY PROBLEM WITH TIME WINDOWS (DPDPTW) FOR CITY-COURIER PROVIDER

Add to FacebookAdd to DiggAdd to Del.icio.usAdd to StumbleuponAdd to RedditAdd to BlinklistAdd to TwitterAdd to TechnoratiAdd to FurlAdd to Newsvine

One response

  1. laudza

    assalamua’laikum
    saya lala, salam kenal mbak, saya tertarik dengan pembahasan mbak mengenai algoritma heuristic seperti nearest,farthest dan cheapest dll… saya sedang mempelajarinya, secara teori saja saya rasa saya sudah cukup mengerti akan tetapi dalam hal coding berbasis GUI saya dan teman-teman masih kebingungan. oleh karena itu saya dan teman2 ingin menanyakan dimana kami bisa mendapatkan source code berbasis GUI yang mengimplementasikan algoritma trsebut?? hal yang sama sudah saya tanyakan di berapa forum, salah satunya forum kaskus pada thread berikut : http://www.kaskus.us/showthread.php?t=6348465 akan tetapi hasilnya nihil, besar harapan kami mbak bisa membantu..salam🙂

    June 23, 2011 at 4:21 AM

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s