Paper Dynamic Pick up Delivery Problem with Time Windows untuk Layanan Antar Jemput Usaha Laundry NURUL CHAIRANY 2511 203 203 Jurusan Teknik Industri Institut Teknologi Sepuluh Nopember Surabaya (ITS)
DYNAMIC PICK UP AND DELIVERY PROBLEM WITH TIME WINDOWS UNTUK LAYANAN ANTAR JEMPUT USAHA LAUNDRY Nurul Chairany NRP 2511 203 203 Logistik and Supply Chain Management Laboratory E-mail :
[email protected] ABSTRACT Paper ini akan membahas tentang DynamicProblem with Time Windows pada pelayanan jasa antar jemput cucian di perusahaan laundry. Ada dua permasalahan yang dihadapi yaitu permasalahan statis dan permasalahan dinamis. Pada permasalahan statis di paper ini dalam bentuk Pick up and Delivery Problem with Time Windows (PDPTW), sedangkan untuk permasalahan dinamis dimodelkan dalam bentuk Dynamic Pick up and Delivery Problem with Time Windows (DPDPTW). Dalam penelitian ini menggunakan dua tahap algoritma yaitu Tabu Search dan Insertion Heuristic untuk menyelesaikan DPPTW dan time slot yang merupakan teknik mengumpulkan permintaan baru. Keywords: Dynamic Pick up and Delivery Problem with Time Windows, Insertion Heuristic, Tabu Search, Time Slot 1. Pendahuluan Permasalah dalam supply chain makin kompleks terlebihnya mengenai permasalahan pendistribusian barang dan pelayanan jasa. Masalah transportasi semakin konkrit dan kompleks. Ada tiga hal yang mengalir di rantai pasok, aliran material atau produk, informasi dan modal. Ketiga hal ini saling terkait dalam pendistribusian dan transportasi. Hal ini diakibatkan permintaan dibarengi tuntutan pelayanan yang semakin baik. Permintaan dalam rantai pasok terbagi menjadi dua yaitu permintaan yang deterministic dan stochastic. Permintaan yang tidak pasti menjadi tantangan buat perusahaan dalam mengatasi ketidakpastian itu. Pentingnya efisiensi perusahaan dalam permasalahan muatan transportasi diperkenalan dalam Laporan Europea Commision on energy and transport (European Commision, Directorate General for Energy and Transport and Enrostat, 2007). Permasalahan transportasi dan penditribusan bisa dimodelkan dalam metode Vehicle Routing Problem (VRP). VRP merupakan permasalahn optimasi dalam menetukan rute dengan keterbatasan kapasitas kendaraan dan menghadapi permintaan yang berbeda-beda tiap tempat yang ditujunya. Ketika menghadapi ketidakpastian permiintaan maka permasalahan ini biasa dinamakan dynamic transportation atau dynamic vehicle routing problem. Seiring perkembangan teknologi, telah hadir teknologi yang mampu menangani masalah dinamis. Misalnya saja Geographic Information System (GIS) dan Global Positioning System (GPS). Dalam penelitian ini, peneliti mengintegrasikan Vehicle Routing Problem (VRP) dengan information sharing guna menghadapi ketidakpastian. 1.1. Dynamic Vehicle Routing Problem (DVRP) Kallehauge dkk. (2001) mendefinisikan permasalahan m-TSP sebagai salah satu variasi dari TSP, dimana terdapat m-salesman mengunjungi sejumlah kota dan tiap kota hanya dapat dikunjungi oleh tepat satu salesman saja. Tiap salesman berawal dari suatu depot dan pada akhir perjalannya juga harus kembali ke depot tersebut. Permasalahan m-TSP ini sering disebut dengan Vehicle Routing Problem (VRP). Tujuan dari VRP yaitu meminimalkan total jarak atau total biaya perjalanan dan juga meminimalkan penggunaan kendaraan. GPS dapat menunjukkan lokasi kendaraan berada dan lokasi tempat pick-up ataupun delivery yang akan dilakukan.
GPS juga dapat membantu dalam memperkirakan aktivitas urban seperti kemacetan dengan mempertimbangkan kecepatan kendaraan pada waktu tertentu. GIS ini berfungsi menunjukkan posisi dari permintaan baru. Salah satu model perkembangan dari VRP yaittu Vehicle Routing Problem Time Windows (VRPTW). VRPTW merupakan permasalan VRP dengan kendala kapasitas saja tapi juga kendala yang mengharuskan kendaraan melayani konsumen pada time frame tertentu. Kemudian dalam pengembangannya diasosiasikan dengan Pick-up dan delivery, kemudian dinamakan Pick-up and Delivery Problem with Time Windows (Mitrovic-Minic, 1998). Tujuan dari permasalahan ini yaitu untuk meminimasi biaya yang terdiri dari waktu perjalanan dan keterlambatan dengan tetap mempertimbangkan critical constraint. Kemudian dikembangkan ke permasalahan dynamic pick-up and delivery problem with time windows (DPDPTW). Permasalahan pada DPDPTW ini lebih rumit dibandingkan dengan PDPTW dikarenakan kondisi yang dinamis. DVRP memiliki kelebihan dalam mengurangi biaya operasional, meningkatkan pelayanan pelanggan dan mengurangi dampak lingkungan. Sumber informasi terbesar dalam DVRP yaitu permintaan pelanggan secara online selama operasi. Permintaan itu lebih spesifik berupa barang atau jasa. Waktu perjalanan merupakan komponen dinamik paling signifikan dalam pengaplikasian di dunia nyata sedangkan waktu pelayanan jarang dibahas secara eksplisit tapi dimasukkan dalam waktu perjalanan. Beberapa penelitian membahas ketersediaan kendaraan secara dinamik untuk memenuhi pelanggan yang sudah diketahui. Pada gambar 1 menggambarkan rute perjalanan dari single vehicle D-VRP. Sebelum kendaraan meninggalkan depot (time t0), initial rute merencanakan mengunjungi tempat permintaan pada saat itu diketahui (A, B, C, D, E). ketika kendaraan melakukan eksekusi pada rute tersebut, terdapat dua permintaan baru (X dan Y) pada waktu t1 dan pada rute ditambahkan lokasi X dan Y untuk memenuhi permintaan mereka. Pada waktu tf, rute yang telah dieksekusi adalah A,B,C,D,Y,E,X. Hal ini menunjukkan bagaimana information sharing dalam hal ini berupa komunikasi antara dispatcher dan kendaraan untuk mengatur rute dalam perjalanan.
Gambar 1. Contoh dari Dynamic Vehicle Routing Problem
2.
Deskripsi masalah dan formulasi 2.1. Laudry Service Jasa Laundry selain menyediakan jasa cuci dan sterika pakaian, selimut, boneka, koper, dan lain-lain juga menyediakan jasa antar jemput barang yang ingin dilaundry. Wilayah operasi jasa laundry untuk layanan antar jemput itu sebatas kota itu sendiri. Diasumsikan bahwa layanan antar jemput pada usaha laundry ini tidak hanya untuk layanan antar dan jemput saja. Jadi perusahaan menerima layanan untuk pengambilan barang saja. Hal ini tentunya selain untuk meminimumkan biaya perjalanan dan juga sebagai strategi perusahaan agar penjualan meningkat. Untuk metode yang digunakan tetap menggunakan PDPTW.
-
Dalam permasalahan dinamis ada dua permasalahan yang akan dihadapi, yaitu: Offline request adalah suatu kondisi dimana permintaan diketahui sebelum dilakukan perjalanan. Hal ini juga biasa disebut dengan permasalahan statis.
-
Online request adalah suatu kondisi dimana permintaan diketahui sebelum dan saat dilakukan perjalanan. Biasa disebut dengan permasalahan dinamis.
2.2. Deskrpsi Permasalahan Statis Perusahaan laundry tiap harinya mengirimkan armadanya untuk berangkat mengambil dan menjemput barang yang akan dilaundry sesuai dengan permintaan pelanggan sebelum keberangkatan dimulai. Tiap hari perusahaan laundry memiliki permintaan antar jemput yang akan dilayani yang dibarengi dengan informasi mengenai origin dan destination point yang diinginkan oleh customer, waktu layanan dan barang apa yang akan diangkut. Destination point memiliki time windows dimana agent melakukan service. Jika agent datang awal, sebelum waktu yang disepakati atau biasa disebut dengan early time windows maka agent diharuskan menunggu. Tapi ketika agent datang melebihi latest time yang telah ditentukan maka agent mendapatkan penalty untuk pelanggaran time windows. Namun demikian permintaan tetap dilayani. Agent memiliki batasan waktu dalam melayani permintaan dalam rutenya sehingga agent harus kembali ke depot pada saat waktu yang ditentukan. Kendaraan yang digunakan oleh agent adalah kendaraan bermotor yang memiliki kapasitas tertentu. Dari penjelasan di atas maka permasalahan tersebut dapat dinotasikan sebagai berikut : P+ PP 0 Po Ck Ci
Ii I0 Si M k n n+i Ai STW Tk T0 Ti Di ,
: Himpunan lokasi pick up : Himpunan lokasi delivery : Himpunan lokasi pemberhentian dimana P = P+ ∪ P: Lokasi depot : Po = P ∪ {0} : Kapasitas maksimum kendaraan : Kapasitas yang akan diangkut di lokasi I ∈ P+ : Kapasitas kumulatif kendaraan k : early time windows pada i ∈ P+ : Latest time windows pada I ∈ P: Depot early start time : Depot latest end time : Service time pada i ∈ P : Himpunan kendaraan : Indeks kendaraan dimana k ∈ M : Jumlah request : Notasi pasangan lokasi delivery dari lokasi pick up pada request i : Arrival time pada lokasi i ∈ P : Pelanggaran terhadap time windows : Total travel time dari k ∈ M : Maximum route pada depot : Total travel time kumulativ hingga I ∈ P : Departure time pada lokasi i ∈ P : Bilangan binary 0 dan 1
2.2.1. Formulasi Matematis Permasalahan Statis Fungsi obektif untuk formulasi ini adalah meminimumkan biaya yang dimana seperti yang dikemukakan oleh (Gendreau, Guertin, Potvin, 2006) merupakan trade off antara operational cost dan customer satisfaction. Operational cost dapat dilihat dari total travel time dari setiap rute yang dilakukan. Sedangkan u ntuk customer
satisfaction adalah total pelanggaran yang dilakukan. Total pelanggaran terhadap time windows dapat dihitung sebagai berikut : = ∑ ∈
max{0,
Fungsi Objektif :
− }
Subject to : =
∑
∑
∈
∈
∈
∑ ∈ ,
∑
∈
,
,
+ ≤
,
−∑
,
,
∈
= 1
= 1
+
= 1→
+
= 1 →
= 1 →
, ∈
,
−∑
, ,
= 1→
= 1→
≤ ≤ = 0
,
,
+
∈
− +
,
= 0
+
max{0, ∈
− } ∈
, ∈
(2) (3)
∈
(6)
∈
, ∈ , ∈
,
= = ≤
= 0
(5)
∈
≤
≤
(4)
∈ , ∈
, ∈ , ∈
≤
(1)
∈ , ∈ ∈
≤
,
+
+ , ≤ + = 1→
,
= 1
= 1 →
,
∑
=
∑
+
∈
∈
∈ ∈
(7) (8)
, ∈
(9)
, ∈
(10) (11)
, ∈
(12)
∈ , ∈ ∈ , ∈ , ∈
∈ , ∈ ∈
∈ ∈
, ∈
, ∈
, ∈
(13) (14) (15) (16) (17) (18)
2.2.2. Permasalahan Dinamis Sebelumnya telah dijelaskan bahwa akan ada dua permasalahan yang akan dibahas yaitu permasalahan statis dan dinamis. Permasalahan statis telah dijelaskan bahwa kondisi dimana permintaan diketahui sebelum perjalanan. Sehingga agent dan dispatcher telah menentukan rute yang akan dilalui. Ketika dalam perjalanan terdapat tambahan permintaan oleh kustomer lain maka lokasi tujuan pada rute akan ditambah dan tidak menutup kemungkinan akan mengubah urutan lokasi dalam rute. Permintaan dinamis dalam kasus ini berupa pick-up barang. Jadi ada permintaan oleh customer untuk mengambil cucian kotor yang akan dilaundry. Permasalahan ini yang merupakan kedinamisan yang disebut Dynamic PPTW. Kasus DPPTW ini menjadwalkan dan menetukan rute kendaraan pada saat dalam perjalanan berdasarkan real time information ketika permintaan baru datang. Tipe-tipe dari real time data information ( Rani dan Rusdiansyah, 2008) adalah sebagai berikut: - Performansi pada sistem : Travel Time dimana diengaruhi oleh kemacetan, kecelakaan dan lain-lain. Service times, dan waiting time. - Permintaan customer : Lokasi, Time Windows, load size, dan pioritas customer . - Kendaraan : Lokasi dan load status.
3. Pengembangan Algoritma 3.1. Tahapan Pengembangan Algoritma Seperti yang telah diketahui bahwa ada dua permasalan yaitu permasalahan statis dalam bentuk offline request (PDPTW) dan permasalahan dinamis dalam bentuk online request (DPPTW). Dengan memandang permasalahan dinamis sebagai permasalahan statis yang terjadi secara sequential (Pankratz, 2005). Maka tahapan algortitmanya sebagai berikut :
Offline Request
Online Request
PDPTW
DPPTW
STATIS * Initial solution * Tabu Search
DYNAMIC * Update the route
Gambar 2. Tahapan Pengembangan Algoritma Dari bagan tersebut dapat dilihat tahapan pengembangan dimulai dari permasalahan statis dengan menggunakan intitial solution teknik insertion heuristic untuk tour construction kemudian dilanjutkan dengan Tabu search. Sedangkan permasalahan dinamis jika terdapat permintaan baru maka langsung di-update untuk melihat bagaimana rute selanjutnya. 3.2. AlgoritmaPermasalahan Statis 3.2.1. Initial Solution Pada tahap initial solution ini digunakan insertion heuristic untuk tour construction. Dasar-dasar insertion heuristics adalah memulai dengan tur subset dari semuakota, dan kemudian memasukkannya sisanya ke dalam heuristic (Nilson,2003). Prosedur insertion dimulai dengan lokasi pick-up terdahulu hingga didapatkan lokasi yang feasible dan biaya terkecil. Syarat insertion lokasi pick-up dikatakan feasible yaitu memenuhi capacity constraint. Tahap selanjutnya menginsertkan lokasi delivery hingga didapatkan lokasi yang feasible dan biaya yang kecil. Syarat insertion lokasi delivery dikatakan feasible yaitu memenuhi precedence constraint, dan time windows constraint. 3.2.2.Tahap Improvement Pada tahap improvement digunakan metode heuristic, Tabu Search (TS). Tabu search pertama kali diperkenalkan oleh Glover pada tahun 1986. Tabu search adalah salah satu prosedur metaheuristik tingat tinggi untuk penyelesaian permasalahan optimasi kombinatorial. Kemampuan TS dalam menghasilkan solusi yang mendekati optimal telah dimanfaatkan dalam beragam permasalahan klasik dan praktis dari berbagai bidang mulai bidang penjadwalan hingga bidang telekomunikasi. Pemilihan kandidat solusi terbaik yang digunakan oleh tabu search yaitu menggunakan prinsip global-best strategy (GB). GB adalah strategi dimana algoritma akan mengganti solusi terbaik saatini dengan solusi terbaik yang ada pada neighborhood. Yang perlu diperhatikan dalam membangun algoritma tabu search ini yaitu : 1. Solution Space Solusi S didefinisikan sebagai himpunan solusi yang akan dievaluasi. Dalam penelitian ini evaluasi dilakukan berasarkan total biaya yang merupakan penjumlahan dari travel time dan pelanggaran terhadap time windows.
2.
Membangun struktur neighborhood Solusi neighborhood adalah suatu fungsi yang memetakan setiap solusi layak S ke solusi-solusi lainnya (Kusumadewi dan Purnomo,2005). Jumlah solusi yang layak dalam neighborhood dibatasi oleh berbagai kriteria untuk mengurangi proses pencarian solusi. Cordeau dan Laporte (2002) menyatakan ada dua cara mementuk neighborhood bagi TS untuk permasalahan penentuan rute kendaraan. Pada penelitian ini menggunakan cara neighborhood dibentuk oleh perpindahan pelanggan antara dua rute sampai maksimal I-perpindahan (I-interchange). Dalam struktur neighborhood pertukaran node antar dua rute hanya diijinkan sampai sebanyak . Dalam penelitian ini bernilai satu. Maka pertukaran bisa terjadi antar rute hanya diizinkan sebanyak satu permintaan saja. Langkah-langkah dari pembentukan neighborhood (Rani dan Rusdiansyah, 2008) adalah sebagai berikut, yaitu : - Stage 0, identifikasi semua rute yang ada - Stage 1, Memilih dua rute dari K rute yang ada - Stage 2, Pilih satu request yang ada dari masing-masing node - Stage 3, Lakukan pertukaran dari keduanya - Stage 4, Evaluasi hasil pertukaran. Bila feasible pertukaran tersebut layak menajdi neighbor bila tidak maka pertukaran tersebut tidak layak menjadi neighbor - Stage 5, Lakukan pertukaran untuk setiap request pada rute k dengan semua request dari rute lainnya. Ilustrasi permasalahan untuk penelitian ini dari langkah-langkah di atas dapat dilihat di bawah ini. - Stage 0 Pada stage ini, initial solution terdiri atas dua rute dimana masing-masing memiliki request tertentu. Ilustrasinya dapat dilihat pada gambar 3.
Depo
D 1
P1
D 3
D 4
Depo
D 5
P2
D 2
Depo
Depo
P3
Gambar 3. Contoh rute awal -
Stage 1 Diasumsikan bahwa rute dalam penelitian ini ada dua maka pemilihan rute untuk melakukan metode pertukaran tidak dilakukan.
-
Stage 2 Selanjutnya dipilih dua request dalam hal ini satu request pada rute 1 dan satu request untuk rute 2. Ilustrasi dapat dilihat di gambar bawah ini.
Depo
D 1
P1
D 3
D 4
Depo
D 5
P2
D 2
Depo
P3
Gambar 4. Pemilihan request dari masing-masing rute
Depo
-
Stage 3 Dilakukan pertukaran request 1 dari rute 1 dan request 7 pada rute 2 . sehingga dapat diilustasikan seperti gambar dibawah ini.
Depo
P 2
P1
D 3
D 4
Depo
D 5
D 1
D 2
Depo
P3
Depo
Gambar 5. Rute setelah request 1 dan 7 ditukarkan -
-
3.
4.
Stage 4 Selanjutnya pada stage ini dilakukan evaluasi terhadap pertukaran apakah layak atau tidak. Bila hasilnya tidak layak maka pertukaran ini tidak dapat dilanjutkan artinya tidak ada solusi neighbor yang dihasilkan dari pertukaran ini. Stage 5 Pertukaran dilakukan terhadap keseluruhan request pada tiap rute.
Definisi tabu list dan Tabu Tenure Tabu list digunakan untuk mencatat pertukaran request antar rute yang dianggap tabu. Update terbaru tabu listdilakukan tergantung pada tabu tenture. Jika Tabu tenure dinotasikan sebagai maka pertukaran dianggap tabu akan tetap dianggap sebagai pertukaran yang tidak boleh dilakukan hingga iterasi t + . (Ghiani, Laporte, Musmanno, 2004) mengungkapkan bahwa tabu tenure biasanya dipilih antara range 5 – 10. Hal ini dilakukan untuk menghindari cycle effect yaitu terpilihnya kembali solusi yang sudah dievaluasi sebelumnya. Stopping criterion Menentukan kapan pencarian solusi akan berhenti. Dalam penelitian ini pencarian solusi akan berhenti apabila iterasi maksimum telah dicapai.
3.3. Algoritma Permasalahan Dinamis 3.3.1. Kedinamisan pada DPDPTW Jasa antar jemput untuk perusahaan Laundry dan time slot. Berdasarkan penjelasan sebelumnya bahwa permasalah dinamis dapat dipandang sebagai suatu permasalahan statis yang terjadi secara berurutan. Berdasarkan model yang telah dikembangkan oleh Rina dan Rusdiansyah, 2008 dalam penelitian DPDPTW pada jasa city-courier, untuk memperkecil degree of dynamism dengan cara membagi periode rute menjadi beberapa slot waktu. Misalnya pada periode rute dibagi menjadi tiga slot waktu. Time slot ini akan digunakan sebagai tanda kapan harus dilakukan update rute akibat adanya request baru (online request). Ketika terjadi permintaan baru pada suatu time slot tertentu, maka permintaan baru ini tidak langsung dimasukkan ke dalam rute kendaran. Dispatcher akan mengumpulkan permintaan baru tersebut bersama dengan permintaan lainnya untuk kemudian dimasukkan kedalam rute kendaraan pada update rute kendaraan untuk time slot berikutnya. Sehingga jika ada permintaan baru makan permintaan yang tadi menjadi offline request untuk time slot berikutnya. Sehingga dapat dikatakan sebagai permasalahan statis.
3.3.2. Pertimbangan Adanya Time Slot Hal-hal yang harus dipertimbangkan ketika melakukan penugasan terhadap permintaan baru, yaitu: -
Permintaan yang sudah dilayani pada time slot sebelumnya. Ketika permintaan baru datang untuk pada rute yang sudah dilayani, penugasan tidak dapat dilakukan. Posisi kendaraan harus diperhatikan. Karena ada beberapa kemungkinan posisi kendaraan bisa berada seperti ketika kendaraan sedang melayani suatu node, kendaraan sedang menunggu pada suatu node delivery dikarenakan arrival time-nya lebih awal dibandingkan early time windows dan kendaraan sedang berada diantara dua node. Ilustrasi dari posisi kendaraan dapat dilihat di gambar di bawah ini.
Gambar 6. Tiga posisi kendaraan pada time slot t
3.3.3. Membangun Algoritma Heuristik untuk Penyelesaian Dynamic Pick Up and Delivery with Time Windows. Langkah-langkah pengembangan algoritma untuk permasalah ini adalah: 1. 2.
Tentukan periode time slot Identifikasi time slot. Hal ini digunakan agar permintaan baru diletakkan di time slot berikutnya. Karena permintaan baru tidak dapat dilayani ketika lokasinya pada rute yang sudah dilayani. 3. Penugasan permintaan baru dilakukan dengan menggunakan prosedur insertion heuristic. 4. Lakukan improvement dengan menggunakan tabu seacrch terhadap rute yang telah dibentuk. Solusi neighborhood tabu search pada permasaahan dinamis kali ini sama dengan solusi neighborhood tabu search pada permasalahan statis. Karena node pick-up and delivery-nya tidak saling berkaitan untuk offline request sedangkan online request hanya berupa pick-up service saja.
5.
Kesimpulan 1. Dynamic Pick-Up and Delivery Problem with Time Windows dapat diimplementasikan dalam jasa antar jemput laundry. 2. Pengembangan algoritma heuristic untuk DPDPTW bisa dilakukan untuk layanan pick-up and delivery.
Daftar Pustaka Larsen, Allan., 2000. “The Dynamic Vehicle Routing”. IMM, DTU Mahtr. T., 2011. “Vehicle Routing under Uncertainty”. TRAIL Thesis Series Pankratz, Giselher. 2005. “Dynamic Routing Vehicle by means of Genetic Algorithm”.International Journal of Physical Distribution and Logistics Manaement, 364 Pillac,Victor., Gendreaue,Michel., Gueret, Christelle., Medaglia,Andres.2012. “A Review of Dynamic Vehicle Routing Problems”. European Journal of Operational Research 223,1 (2013) 1-11 Rani, Fitri Kurnia., Rusdiansyah,Ahmad.2008. Pengembangan Algoritma Heuristik untuk Penyelesaian Dynamic Pick Up and Delivery Problem with Time Windows (DPDPTW) untuk Penyedia Jasa CityCourier
