PENGEMBANGAN ALGORITMA HEURISTIK UNTUK PENYELESAIAN DYNAMIC PICK UP AND DELIVERY PROBLEM WITH TIME WINDOWS (DPDPTW) UNTUK PENYEDIA JASA CITY - COURIER

PENGEMBANGAN ALGORITMA HEURISTIK UNTUK PENYELESAIAN DYNAMIC PICK UP AND DELIVERY PROBLEM WITH TIME WINDOWS (DPDPTW) UNTUK PENYEDIA JASA CITY - COURIER Fitri Karunia Rani1, Ahmad Rusdiansyah2 1) Statistical and Managerial Decision Laboratory 2) Logistics and Supply Chain Management Laboratory Jurusan Teknik Industri Institut Teknologi Sepuluh Nopember (ITS) Surabaya Kampus ITS Sukolilo Surabaya 60111 Email: [email protected] ; [email protected]

Abstrak Pada dasarnya pada perusahaan penyedia layanan jasa courier dalam kota, customer meminta pelayanan jemput (pick up) dan antar (delivery). Lebih lagi biasanya customer memiliki batasan waktu tertentu pada lokasi delivery. Ini berarti paket yang dikirimkan harus sampai pada time windows tertentu. Setelah requests terkumpul, selanjutnya penentuan dan penjadwalan rute kendaraan ditentukan. Permasalahan seperti ini dikenal dengan sebutan Pickup and Delivery Problem with Time Windows (PDPTW). Tujuan dari permasalahan ini adalah meminimasi total cost yang terdiri dari travel time dan keterlambatan di lokasi delivery dengan tetap memperhatikan critical constraints seperti Precedence, Node-Pairing dan Time Windows constraints. Saat ini penyedia jasa City-Courier telah dilengkapi dengan teknologi IT yang canggih seperti GIS dan GPS untuk menangani permintaan baru yang muncul secara dinamis. Sehingga kendaraan tidak hanya dapat melayani request yang diketahui sebelumnya namun juga dapat merespon request berdasarkan real time information. Karenanya permasalahan ini dikenal sebagai Dynamic Pickup and Delivery Problem with Time Windows (DPDPTW). Permasalahan ini menjadi semakin sulit dibanding PDPTW yang dikenal sebagai NP-Hard Problem. Dalam penelitian ini dikembangkan dua tahap algoritma yaitu Tabu search dan Insertion Heuristic untuk menyelesaikan DPDPTW dan teknik untuk mengumpulkan new requests. Selanjutnya pada algoritma yang dikembangkan ini dilakukan percobaan numerik untuk mengetahui keefektifannya. Kata kunci : City Courier, Dynamic Pickup and Delivery Problem with Time Windows, Heuristics, Pairing and Precedence Constraints, Tabu Search, Time Slot ABSTRACT Basically, in the business of a city courier service provider, a customer requests to pickup letters (or packages) from a pickup place and deliver them to a delivery node. Moreover, customers usually also determine time windows for delivery node. This means that the letters must be arrived in desired time windows. After collecting all requests, the vehicle dispatcher will determine vehicle routes and schedules. In the literature such a problem is known as Pickup and Delivery Problem with Time Windows (PDPTW). The objective is to minimize total cost which consist of travel time and vehicle lateness while satisfying some critical constraints such as Precedence, Node-Pairing as well as Time Windows constraints, Nowadays, city courier service providers have been equipped with sophisticated IT based devices such as Geographical Information Systems, Global Position System device, can handle request from customers dynamically. Thus, the vehicle dispatcher not only handle requests before dispatching the vehicle, but can also respond real time requests and may reassign the vehicles that have been already dispatched. The problem is considered Dynamic Pickup and Delivery Problem with Time Windows (DPDPTW). This problem becomes much more difficult due to PDPTW have been known as a NP Hard problem. We develop two phase Tabu Search algorithm combined with insertion heuristics to solve the DPDPTW. We also develop some techniques in collecting and processing later requests. We finally conduct numerical experiments to verify the effectiveness of the algorithms. Keywords: City Courier, Dynamic Pickup and Delivery Problem with Time Windows, Heuristics, Pairing and Precedence Constraints, Tabu Search, Time Slot

Copyright by Fitri Karunia Rani 2008

dokumen-dokumen. Wilayah operasi dari citycourier ini hanyalah sebatas kota itu sendiri.

1. Pendahuluan Saat ini isu yang berkembang pada penyedia jasa City-Courier adalah isu dinamis. Isu dinamis disini memiliki arti bahwa request mengenai pick-up dan delivery dengan time window tertentu tidak hanya dapat terjadi sebelum kendaraan berjalan (offline) namun juga dapat terjadi setelah kendaraan sudah memulai rutenya (on line). Akibat adanya permintaan yang sifatnya dinamis tersebut maka penjadwalan rute pada kendaraan akan menjadi dinamis pula. Artinya penjadwalan rute bisa saja berubah akibat adanya permintaan baru.

1. Delivery Only /Pick Up Only Service Dalam hal ini customer hanya menginginkan layanan pengantaran (delivery) saja tanpa penjemputan (pick up) atau sebaliknya.

Gambar 2. 1 Tipe Layanan City-Courier

C

O

PY

2. Pick Up dan Delivery Service Dalam hal ini customer menginginkan layanan baik penjemputan maupun pengantaran.

Perlu diketahui bahwa yang menjadi fokus pada penelitian ini adalah tipe layanan Pick Up and Delivery.

N

O

T

Sejalan dengan adanya perkembangan di berbagai bidang teknologi. Saat ini teknologi mengenai data collector untuk masalah dinamis seperti yang telah disebutkan sebelumnya, telah dikembangkan dengan pesat. Misalnya saja GPS dan GIS. GPS dapat menunjukkan setiap posisi dimana suatu kendaraan yang ditugaskan berada dan juga posisi dari delivery dan juga pick-up yang dilakukan. Sehingga kondisi mengenai aktivitas urban seperti kemacetan dapat diperkirakan melalui kecepatan kendaraan pada waktu tertentu. Sedangkan GIS dapat menunjukkan posisi dari request baru. Dengan memanfaatkan informasi dari GPS dan GIS ini maka rute kendaraanpun dapat dilakukan setiap kali request baru terjadi.

Tipe layanan dari City-Courier ada bermacam – macam, namun umumnya tipe layanan dari citycourier dibedakan menjadi 2 yaitu :

D

O

Dalam penelitian ini mencoba mengembangakan algoritma heuristik untuk penyelesaian permasalahan dinamis pada City-Courier seperti penjelasan diatas. Dari penelitian ini diharapkan didapatkan algoritma heuristik yang dapat melakukan penugasan kendaraan terhadap request baru dan meminimasi total cost yang terdiri dari travel time dan keterlambatan di lokasi delivery. Sebagai informasi tambahan, penelitain ini merupakan bagian dari penelitian besar PREDICT yakni penelitian mengenai Dynamic Vehicle Routing Problem In Surabaya City dengan memanfaatkan informasi realtime yang didapat dari GPS. 2. Permasalahan 2.1 City-Courier Aktivitas transportasi yang menjadi pokok pembahasan dalam penelitian ini adalah CityCourier. City-courier merupakan penyedia jasa layanan pengantar baik parsel ataupun

2.2 Deskripsi Permasalahan Statis Untuk satu hari kerja penyedia jasa City-Courier memiliki transportation request yang hendak dilayani. Setiap transportation request terdiri dari informasi mengenai origin dan destination point yang dikehendaki oleh customer, beban yang diangkut dan waktu service pada kedua lokasi tersebut. Koordinat dari origin dan destination point disini digunakan untuk menentukan jarak dan travel time antara dua lokasi. Khusus untuk destination point (delivery location), destination point memiliki time windows tertentu dimana kendaraan bisa melakukan service. Jika kendaraan datang sebelum early time windows-nya maka kendaraan diharuskan menunggu. Sedangkan jika kendaraan datang melebihi latest time windows-nya, requests dapat dilayani namun terdapat penalti untuk pelanggaran time windows. Untuk kendaraan sendiri, kendaraan yang digunakan adalah kendaraan bermotor yang memiliki kapasitas maksimum tertentu

2 Copyright by Fitri Karunia Rani 2008

untuk mengangkut beban. Kendaraan juga memiliki waktu maksimum untuk melayani requests dalam rutenya sehingga harus kembali ke depot pada waktu yang telah ditentukan.

Sesuai yang dikemukakan oleh (Gendreau, Guertin, Potvin, 2006) bahwa biasanya fungsi objektif cost merupakan trade off antara Operational Cost dan Customer Satisfaction. Pada penelitian ini fungsi Operational Cost merupakan total travel time dari setiap rute yang ada dan customer satisfaction adalah total pelanggaran yang dilakukan terhadap latest time windows. Adapun total pelanggaran terhadap time windows (STW) dapat dihitung sebagai berikut :

Dari penjelasan paragraf diatas maka permasalahan tersebut dapat dinotasikan sebagai berikut : P+

: Himpunan lokasi Pick Up

-

: Himpunan lokasi Delivery

P P

: Himpunan lokasi dimana P = P+ ∪P-

0

: Lokasi depot

Po k

pemberhentian

S TW =

: Po = P ∪ {0}

∑ max{0, A − l } i

i∈P −

i

Sehingga dari penjelasan diatas maka fungsi objektif dapat disusun sebagai berikut :

C

: Kapasitas maksimmum kendaraan

Ci

: Kapasitas yang akan diangkut di lokasi i ∈ P+ : Kapasitas kumulatif kendaraan k

ei

: Early Time Windows pada i ∈ P-

li

: Latest Time Windows pada i ∈ P-

eo

: Depot Early start time

lo

: Depot Latest end time

si

: Service Time pada i ∈ P

M

: Himpunan kendaraan

k

: Indeks kendaraan dimana k ∈ M

n

: Jumlah requests

n+i

: Notasi pasangan lokasi delivery dari lokasi pick up pada request i

Ai

: Arrival time pada lokasi i ∈ P

STW

: Pelanggaran terhadap time windows

Tk

: Total Travel Time dari k ∈ M

To

: Maximum route pada depot

Ti

: Total Travel Time kumulatif hingga i ∈P

Di

: Departure Time pada lokasi i ∈ P

X ik, j

: merupakan bilangan binari 0 dan 1. 1 menunjukkan adanya aliran dari node i ke j oleh kendaraan k dan 0 sebaliknya

∑ Tk + ∑ max{0, A

k∈M

i

− li )

i∈P -

PY

C ik

Min

D

O

N

O

T

C

O

Setelah fungsi objektif cost di formulasikan, selanjutnya dilakukan formulasi terhadap constraint-constraint berdasarkan problem statement yang telah dikemukakan sebelumnya. Pada umumnya constraint-constraint yang digunakan pada penelitian ini mengacu pada model (mitrovic-minic, 1998). Namun disini terdapat sedikit penggabungan dengan model yang dikembangkan oleh (Nanry, Barnes, 2000) pada bagian Time Windows Constraint. Didalam penelitian ini juga ditambahkan satu constraint lagi yakni maximum route constraint. Adapun constraint-constraint tersebut adalah sebagai berikut :

Setelah dijelaskan mengenai notasi model permasalahan, maka selanjutnya dilakukan formulasi model permasalahan tersebut dalam bentuk model matematis.

a. Time Windows Constraint Model dari (Nanry, Barnes 2000) pada time windows constraint dipilih karena permasalahan yang diamati menggunakan time windows yang memiliki karakteristik hard time windows (kendaraan harus menunggu) pada early time windows dan soft time windows pada latest time windows. Didalam constraint ini juga terdapat tambahan service time untuk persamaan (2). Adapun constraint-nya sebagai berikut : Aj = Di + tij

i ∈ Po, j ∈ P-

(1)

Dj = Max (Aj ,ej) + sj

i ∈ P, j ∈ P-

(2)


lj

j ∈ P-

(3) 2.3 Permasalahan Dinamis

b. Multicomodity Constraint i ∈ P+ ∑ ∑ X ik, j = 1 k∈M

j∈Po

∑X

k i, j

k ∈M

∑X

j∈P +

−

j ∈ Po

k i,0

i∈P −

k j ,i

=0

=1

k 0, j

∑X

∑X

=1

Dalam penjelasan permasalahan statis mengenai permasalahan penentuan rute kendaraan atau yang dikenal dengan sebutan Pick up and Delivery Problem with Time Window (PDPTW) memiliki asumsi bahwa penentuan rute bisa dilakukan apabila semua request yang terjadi telah diketahui sebelumnya. Padahal dalam kenyataannya tidak semua request terjadi hanya pada saat rute kendaraan belum dimulai, namun request bisa terjadi pada saat kendaraan sudah memulai rutenya. Hal ini lah yang disebut kedinamisan dalam PDPTW atau disebut sebagai Dynamic PDPTW. Pada intinya dalam kasus DPDPTW yakni ketika penjadwalan dan penentuan rute kendaraan bersifat dinamis dan berdasarkan pada real time information maka ketika ada informasi baru, penentuan rute yang baru harus dilakukan. Tipetipe dari real time data information adalah sebagai berikut:

(4)

i∈P ,k ∈M

(5)

k ∈M

(6)

k ∈M

(7)

c. Route and Schedule Comptability X ik, j = 1 ⇒ Ti k + t ik, j ≤ T jk

i, j ∈ P, k ∈ M

(8)

X 0k, j = 1 ⇒ T0k + t 0k, j ≤ T jk

j ∈ P+ , k ∈ M

(9)

X ik, 0 = 1 ⇒ Ti k + t ik, 0 ≤ T jk

j ∈ P− , k ∈ M

(10)

X ik, j = 1 ⇒ Ti k + t ik, j ≤ T jk

i, j ∈ P, k ∈ M

(11)

−

d. Pairing Constraint −

∑X

j∈Po

k j ,n +i

=0

(12)

i ∈ P+ ,k ∈ M

O

(13)

Route and Capacity Comptability

D

f.

O

N

e. Precedence Constraint i ∈ P+ ,k ∈ M Ti k + t ik,n+i ≤ Tnk+ i

T

C

k i, j

O

∑X

j∈Po

X ik, j =1 ⇒ Cik + C j = C kj

i ∈ P, j ∈ P + , k ∈ M

(14)

X ik, j = 1 ⇒ Cik − C kj − n = C kj

i ∈ P, j ∈ P − , k ∈ M

(15)

X 0k, j = 1 ⇒ C 0k + C j ≤ C kj

j ∈ P+ , k ∈ M

(16)

e. Capacity Constraint

C i ≤ C ik ≤ C k C =0 k 0

i ∈ P+ ,

k ∈M

k ∈ M (17) (18)

f.. Maximum Route Penambahan constraint ini dikarenakan pada permasalahan terdapat batasan bagi kendaraan untuk kembali ke depot pada selang waktu tertentu. Sehingga constraint ini di formulasikan sebagai berikut :

e0 ≤ Tk ≤ l 0

k ∈M

(19)

Performansi pada sistem : Travel Time dimana dipengaruhi oleh kemacetan, kecelakaan dan lain-lain, Service times, dan Waiting time. Permintaan customer : Lokasi, Time Window, Load Size, dan Prioritas Customer Kendaraan : Lokasi dan Load Status

PY

≤

Aj

−

−

3. Pengembangan Algoritma 3.1 Tahapan Pengembangan Algoritma Dalam pengembangan Algoritma ini dibedakan menjadi dua tahap berdasarkan jenis request yang ada yaitu : 1. Offline Request Offline Request ini merupakan permintaan terhadap transportasi dimana requestrequest ini diketahui sebelum kendaraan memulai rutenya. 2. Online Request Online Request ini merupakan permintaan terhadap transportasi dimana requestrequest ini terjadi selama kendaraan sudah berada pada rutenya. Berdasarkan definisi kategori request, maka request-request tersebut dapat dipandang sebagai permasalahan yang berbeda. Karena request dari offline request diketahui sebelumnya maka Offline request ini dikategorikan sebagai permasalahan Statis yaitu


•

PDPTW. Sedangkan Online Request dikategorikan sebagai permasalahan Dinamis (DPDPTW).

Precedence Constraint. Dimana lokasi delivery hanya dapat ditempatkan pada lokasi setelah node Pick up –nya. • Time windows constraint • Maximum Route Dari prosedur tersebut dapat dibangun flowchart algoritma pada gambar 3.2

Dengan memandang permasalahan dinamis sebagai permasalahan statis yang terjadi secara sekuensial (Pankratz, 2005) maka tahapan algoritma yang digunakan dalam penelitian ini dapat dilihat pada bagan gambar 3.1

Set Route k = 1 Max Cap = C Max Route = To Ck = 0

Start

i ÅP Select Request i

Generate Feasible insertion For Delivery

Insert i Æ Route k i∈P-

Generate Fesible Insertion for Pick Up

Insert i Æ Route k i∈P +

Select Min Cost

Yes

Is There Feasible Insertion?

No

Is There Feasible Insertion?

No

Yes

Select Min Cost

Gambar 3. 1 Tahapan Pengembangan Algoritma

Eject Request i from route k

Ck = Ck - Ci P= P - {i}

No

3.2.1 Tahap Initial Solution Pada tahap initial solution ini digunakan insertion heuristic untuk Tour Construction. Adapun prosedur insertion dilakukan dengan cara meng-insertkan lokasi pick up terlebih dahulu hingga didapatkan lokasi yang feasible dan costnya minimum. Adapun syarat bahwa insertion lokasi pick up dikatakan feasible yakni memenuhi : • Capacity Constraint • Maximum Route Tahap selanjutnya kemudian menginsertkan lokasi delivery hingga didapatkan lokasi yang feasible dan costnya minimum. Adapun syarat bahwa insertion lokasi delivery dikatakan feasible yakni memenuhi :

Set k = k+1 Ck = 0

PY O C

O

N

O

D 3.2 Algoritma Permasalahan Statis

P ≠0

Yes

T

Dari bagan tersebut dapat dilihat bahwa tahapan pengembangan dimulai dari permasalahan statis dimana penyelesaian yang digunakan menggunakan teknik insertion heuristic untuk Tour Construction kemudian dilakukan improvement dengan menggunakan Tabu Search. Sedangkan pada tahap dinamis, jika terdapat request baru maka dilakukan update terhadap rute.

End

Gambar 3.2 Flowchart Algoritma Insertion Heuristik

3.2.2 Tahap Improvement Pada tahap improvement ini digunakan metode meta-heuristic Tabu Search. Adapun Hal-hal yang perlu untuk diperhatikan dalam membangun Algoritma Tabu Search ini adalah sebagai berikut : 1. Solution space Solusi S merupakan seluruh himpunan solusi yang akan dievaluasi. Dalam penelitian ini evaluasi dilakukan berdasarkan total biaya Cost (S) yang merupakan penjumlahan dari travel time dan pelanggaran terhadap time windows 2. Membangun Struktur Neighborhood Dalam penelitian ini digunakan struktur neighborhood yang dikenalkan oleh Osman (Laporte,Cordeau, 2002) dengan λ interchange. Dalam struktur neighborhood ini pertukaran/swapping node antar dua rute hanya diijinkan sampai sebanyak λ . Dalam penelitian ini λ yang digunakan bernilai satu. Artinya dalam membangun


suatu struktur neighborhood, maka pertukaran request yang terjadi antara rute hanya diijinkan sebanyak 1 request saja.

Stage 2 Selanjutnya dipilih dua request dalam hal ini request 1 pada rute 1 dan request 2 pada rute 2. Yang perlu diingat adalah pemilihan suatu request artinya adalah pemilihan pick up dan delivery dari request tersebut. Untuk lebih jelasnya dapat dilihat pada gambar 3.4

Adapun langkah-langkah dari pembentukan struktur neighborhood adalah sebagai berikut : Stage 0 ada

Identifikasi semua rute yang

Stage 1

Memilih dua rute dari K rute yang ada

D

P1

D1

P3

P5

D3

Stage 2

Pilih satu request yang ada dari masing-masing node

D

P2

P8

D8

D2

D

Stage 3

Lakukan keduanya

D

P7

P4

P6

D7

D4

Stage 4

Evaluasi hasil pertukaran. Bila feasible pertukaran tersebut layak menjadi neighbor bila tidak maka pertukaran tersebut tidak layak menjadi neighbor

dari

Rute 2

D6

D

Rute 3

Stage 3 Kemudian lakukan pertukaran request 1 dari rute 1 dengan request 2 pada rute 2. Sehingga didapatkan rute baru seperti pada gambar 3.5.

PY O D

P2

D2

P3

P5

D3

D

P1

P8

D8

D1

D

D

P7

P4

P6

D7

D4

D5

D

Rute 1

T

Rute 2

O

Stage 0

Rute 1

Gambar 3.4 Pemilihan Request dari masingmasing rute

Lakukan pertukaran untuk setiap request pada rute k dengan semua request dari ruterute lainnya.

Adapun ilustrasinya dapat dilihat pada rangkaian stage dibawah ini

D

C

Stage 5

pertukaran

D5

D

O

N

Pada stage 0 ini, initial solution terdiri atas tiga rute dimana masing-masing memiliki request tertentu. Ilustrasinya dapat dilihat pada gambar 3.3 D

P1

D1

P3

P5

D3

D

P2

P8

D8

D2

D

D

P7

P4

P6

D7

D4

D5

D

Rute 1

Rute 2

D6

D

Rute 3

Keterangan :

D6

D

Rute 3

Gambar 3.5 rute setelah request 1 dan 2 ditukarkan

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

D

Depot

Pi

Pick Up Location Request i

Di

Delivery Location Request i

Gambar 3.3 Contoh Rute Awal

Stage 1 Pada stage ini dilakukan pemilihan rute. Dari gambar 3.3 misalnya dipilih rute 1 dan rute 2 terlebih dahulu untuk dilakukan pertukaran.

Pertukaran tersebut dilakukan terhadap keseluruhan request hingga seluruh request telah ditukarkan dengan request-request yang ada pada rute lainnya. Misalnya setelah pertukaran Request 1 dari rute 1 dan request 2 dari rute 2 dilakukan, selanjutnya dilakukan pertukaran antara request 8 dari rute 2 dan seterusnya. 3. Definisi Tabu List dan Tabu Tenure Tabu list disini digunakan untuk mencatat (record) pertukaran request antar rute yang dianggap tabu. Update terhadap tabu list


dilakukan tergantung pada tabu tenure. Jika Tabu Tenure di notasikan 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.

Insertion Heuristic Output -----------------------------------------Current Tour = S Cost (Current Tour) = Cost (S) Set −−−−−−−−−−−−−−−−−−−−−−−−−−− GlobalMin = Cost(S) BestMove = S Tabu List = [φ] Cost N(S)= 0 MaxIteration TabuTenure = θ

Do Neighborhood Structure N(S)

4. Stopping criterion Stopping criterion ini akan menentukan kapan pencarian solusi akan berhenti. Dalam penelitian ini pencarian solusi akan berhenti apabila iterasi maksimum telah dicapai.

Is There Feasible N(S) ?

No Select Min Cost N(S)

Setelah keempat hal tersebut dipenuhi maka algoritma tabu search untuk permasalahan Dynamic Pick up and Delivery Untuk penyedia Jasa City Courier dapat dibangun secara utuh dapat dilihat pada flowchart gambar 3.6

Yes Cost N(S) <=GlobalMin

GlobalMin =Cost N(S)

PY

No

BestMove = N(S)

Current Tour = N(S)

Update Tabu List

O

T

C

O

3.3 Algoritma Permasalahan Dinamis 3.3.1 Kedinamisan pada DPDPTW City-Courier dan Time slot.

Yes

No MaxIteration Satisfied?

D

O

N

Permasalahan dinamis sendiri memiliki ukuran untuk kedinamisannya. Biasanya disebut sebagai degree of dynamism (DOD). Ukuran ini biasanya merupakan persentase antara online request dengan total keseluruhan request yang ada (Allan Larsen, 2001). Permasalahan city courier yang menjadi fokus khusus dalam penelitian ini memiliki DOD yang cukup tinggi karena online request bisa terjadi kapan saja. Semakin banyak jumlah online request maka semakin dinamislah permasalahan tersebut. Sehingga apabila tingkat kedinamisan semakin meningkat maka akan semakin sulit untuk menyelesaikan permasalahan tersebut. Bedasarkan pengertian yang telah dijelaskan sebelumnya bahwa sebenarnya permasalahan dinamis dapat dipandang sebagai suatu

Yes

End

Gambar 3.6 Flowchart Algoritma Tabu Search

permasalahan statis yang terjadi secara sekuensial. Dalam peneltian ini, berdasarkan hal tersebut, mencoba untuk memperkecil degree of dynamism dari permasalahan city courier. Ide dasar yang diterapkan adalah dengan cara membagi periode rute menjadi beberapa slot waktu. Pada gambar 3.7 misalnya, periode rute dibagi menjadi 3 slot waktu yaitu time slot 1, time slot 2 dan time slot 3. Time slot ini digunakan sebagai tanda kapan harus dilakukannya update rute akibat adanya permintaan baru (online request). Ketika terjadi permintaan baru (New Request) pada suatu time slot tertentu, maka permintaan baru ini tidak langsung dimasukkan ke dalam rute kendaraan melainkan akan dikumpulkan


Time Slot 2

Time Slot 1

D

P1

D1

P2

P3

t

Setelah penjelasan mengenai time slot, maka selanjutanya dapat dibangun algoritma permasalahan dinamis untuk City-Courier. Namun demikian meskipun time slot telah membagi permasalahan dinamis menjadi permasalahan-permasalahan statis yang sekuensial, namun algoritma untuk permasalahan statis yang dijelaskan pada sub bab sebelumnya tidak dapat langsung digunakan. Hal ini diakibatkan karena adanya pemutusan periode pada masing-masing time slot sehingga ada beberapa hal yang harus dipertimbangkan ketika melakukan penugasan terhadap permintaan baru. Hal-hal yang harus dipertimbangkan adalah sebagai berikut:

Time Slot 3

D2

D3

D

t' PERIODE RUTE

N

D5

P5

D4

D

P4

O

PERMINTAAN BARU

Time Slot 2

Time Slot 1

D

P1

D1

P2

Time Slot 3

P3

t

D2

D3

D

t' PERIODE RUTE

WAKTU MUNCULNYA REQUEST BARU

Gambar 3.8 Posisi Waktu Kemunculan Request terhadap Time Slot

D

P1

Time Slot 3

Time Slot 2

Time Slot 1

D1

P2

P3

P4

D4

t

D2

P5

D5

D3

D

t' PERIODE RUTE

Gambar 3.9 Kemungkinan Posisi permintaan baru setelah dilakukan penugasan

3.3.2 Pertimbangan-pertimbangan adanya Time slot

akibat

1. Permintaan yang sudah dilayani pada time slot-time slot sebelumnya. Permintaan ini harus diidentifikasi karena permintaan baru tidak dapat dilakukan penugasan terhadap lokasi-lokasi pada rute diantara permintaanpermintaan yang sudah dilayani. 2. Posisi kendaraan disini menjadi suatu permasalahan yang harus dicermati. Posisi kendaraan ini akan menentukan dimana saja request baru dapat dimasukkan kedalam rute. Ada tiga kemungkinan posisi kendaraan pada waktu time slot tertentu jatuh yaitu : A. Kendaraan sedang melayani suatu node baik itu berupa pick up maupun delivery. B. Kendaraan sedang berada diantara dua node baik itu delivery maupun pick up. C. Kendaraan sedang menunggu pada suatu node delivery dikarenakan arrival time dari kendaraan lebih dahulu dibanding early time windows dari node delivery tersebut. Adapun ilustrasi dari ketiga posisi kendaraan tersebut dapat dilihat pada gambar 3.10

O C

O

T

pada periode time slot tersebut bersama dengan permintaan-permintaan lainnya untuk kemudian dimasukkan kedalam rute kendaraan pada saat update rute kendaraan untuk time slot berikutnya. Artinya jika ada beberapa request baru yang muncul pada time slot pertama maka request baru ini akan menjadi offline request untuk time slot kedua dan seterusnya. Dengan begini maka tiap slot dapat dipandang sebagai permasalahan statis. Adapun ilustrasi dari kemunculan permintaan baru dapat dilihat dari gambar 3.8 Pada gambar tersebut dapat dilihat bahwa ada dua request baru terjadi pada time slot pertama. Setelah permintaan baru ini dikumpulkan kemudian dilakukan penugasan terhadap kedua permintaan tersebut pada slot berikutnya. Adapun ilustrasinya dapat dilihat pada gambar 3.9 Pada gambar tersebut dapat dilihat posisi dari permintaan-permintaan baru tersebut sepanjang periode rute dari kendaraan.

PY

Gambar 3.7 Time slot Pada Suatu Periode Rute

3. Jika request melebihi batas maksimum diperbolehkannya kendaraan beroperasi (maximum route) maka harus ada kendaraan baru yang menangani permintaan baru tersebut. Namun demikian maximum route dari kendaraan yang baru ini tidaklah sama dengan rute yang sudah ada sebelumnya. Melainkan harus dikurangi batas akhir time slot dimana permintaan baru tersebut muncul. Sehingga tiap kendaraan memiliki batasan waktu yang sama untuk kembali


kedepot. Adapun ilustrasinya dapat dilihat pada gambar 3.11 Tiga Kemungkinan Posisi kendaraan pada saat time slot t

t

t

A

B

D

t

e

l

C

Gambar 3.10 Tiga posisi kendaraan pada saat time slot t

PY

PERIODE RUTE AWAL

t

O

PERIODE RUTE TAMBAHAN

C

t

lanjutkan rute yang sebelumnya hingga bertemu waktu time slot berikutnya 3. Penugasan permintaan baru dilakukan dengan menggunakan prosedur insertion heuristic yang telah dijelaskan pada sub bab sebelumnya dengan memperhatikan posisiposisi yang mungkin untuk dilakukan insertion. 4. Lakukan improvement dengan menggunakan tabu search terhadap ruterute yang telah dibentuk. Dalam membangun solusi neighborhood tabu search pada permasalahan dinamis berbeda dengan permasalahan statis. Pada tabu search permasalahan dinamis swapping atau pertukaran request harus memperhatikan posisi pasangan node pick up dan delivery pada. Hal ini dikarenakan ada kemungkinan pasangan node terpisah satu sama lain karena adanya perbedaan kedudukan pada time slot. Untuk permintaan-permintaan yang masuk dalam kategori ini pada saat membangun struktur neighborhood tidak dilakukan swapping. Hal ini bisa dilihat pada ilustrasi gambar 4.15. Dari gambar tersebut delivery dari request 2, 4 dan 7 tidak dapat dilakukan swapping dengan request lainnya. Hal ini disebabkan karena pick up dari ketiga request tersebut sudah dilayani. Sehingga dalam ilustrasi ini swapping/pertukaran hanya dapat dilakukan pada request 3, 5 6 dan 8.

O

T

Gambar 3.11 Periode Rute Tambahan

D

O

N

3.3.3 Membangun Algoritma Heuristik untuk penyelesaian Dynamic Pick up and Delivery with Time windows

Setelah penjelasan mengenai masalah-masalah yang dihadapi dalam membangun algoritma heuristik untuk permasalahan city - courier ini, maka selanjutnya dapat dibangun Algoritma heuristic untuk permasalahan dinamis pada City-Courier dengan mempertimbangkan halhal yang telah disebutkan sebelumnya. Adapun langkah-langkah pengembangan algoritma untuk permasalahan city courier ini adalah sebagai berikut : 1. Tentukan periode time slot 2. Identifikasi time slot. Bila ada permintaan baru maka kumpulkan permintaanpermintaan baru tersebut untuk kemudian di tugaskan kedalam rute pada time slot berikutnya. Rute yang dimaksud dapat berupa rute yang sudah ada sebelumnya, maupun rute yang benar-benar baru dibuat karena rute yang sudah ada sebelumnya tidak dapat melayani request yang baru. Bila tidak ada permintaan baru maka

Time Slot t

D

P1

D

P2

D

P7

Time Slot t +1

D1

P4

P3

P5

D3

D5

P8

D8

D2

D

P6

D7

D4

D6

D

Rute 1

Rute 2

D

Rute 3

Periode Rute Sudah Dilayani

Tidak bisa dilakukan Pertukaran

Belum Dilayani

Gambar 3.12 Neighborhood Swapping Restriction pada permasalahan dinamis

Adapun keseluruhan langkah-langkah Algoritma secara sistematis dapat dilihat pada flowchart gambar 3.13


Start

Input ------------------------------------------------------Existing Route time slot t of route New Request Assignment Vehicle Position Set of requests have been serviced

Is There New Request Assignment for time slot = t ?

Identify Possible Insertion Location for new request

Keep Existing Route Until time slot t +2

Gambar 4.1 Data Exchange (Abdullah Alkaff dkk, Proposal PREDICT ITS, 2007)

Insert new request to the route by insertion procedure

PY

Choose minimum feasible one

1. Transportation Request berupa pick up dan delivery yang dilakukan melalui telepon dimana customer mendefinisikan requestnya sendiri yaitu mengenai kapan ia akan dilayani, time window dan load yang akan dibawa 2. Lokasi kendaraan diketahui dari informasi yang diberikan GPS (Global Positioning System) 3. Lokasi Pick Up dan Delivery didapatkan dari informasi yang diberikan GIS (Geographic Information System) 4. Update kapasitas kendaraan selama berada dalam rutenya dilakukan melalui SMS (Short Message Service) 5. Travel time dapat diketahui dengan melakukan perhitungan historitical data of speed travel Kebutuhan-kebutuhan data yang diperlukan pada kondisi ideal tersebut pada penelitian ini tidak dapat dipenuhi karena penelitian ini merupakan bagian dari penelitian besar PREDICT sehingga pada penelitian ini digunakan data set benchmark problem yang disesuaikan dengan permasalahan dynamic pick up and delivery problem hingga memenuhi kebutuhan data seperti pada kondisi ideal.

T

C

O

Do Tabu Search Procedure

D

End

O

N

O

New Route For Time Slot t+1

Gambar 3.13 Gambar Flowchart Prosedur Permasalahan Dinamis

4.

Percobaan Numerik

4.1 Data Kondisi ideal yang terjadi dilapangan berkaitan dengan isu dinamis pada VRP dapat dilihat dari Gambar 4.1. Pada gambar tersebut dapat dilihat bahwa sebenarnya data berdasarkan pertukarannya dapat di clusterkan kedalam 3 cluster . Setiap cluster memiliki data yang kemudian dipertukarkan dengan cluster lainnya. Dari gambar tersebut dapat dilakukan identifikasi bahwa data yang diperlukan pada kondisi ideal untuk permasalahan City-Courier yaitu :

Data set yang digunakan pada penelitan mengenai pengembangan algoritma heuristik untuk Dynamic Pick Up and Delivery Problem With Time Windows pada penyedia jasa City Courier ini adalah Solomon’s VRP bencmark data yang selanjutnya dimodifikasi oleh Pankratz untuk permasalahan DPDPTW.


Problem Instance ini bisa dilihat dan didownload dari alamat directory dibawah ini

RUTE 6 : P10-P13-D13-D10-O0RUTE 7 : P16-P17-D16-D17-O0-

/ftp-dir/pub/fachb/wiwi/winf/forschng/dpdptw

[TOTAL COST] : 2048.15093901739

RUTE 8 : P4-P18-D18-D4-P8-D8-O0-

Dari output diatas dapat diketahui bagaimana algoritma yang dikembangkan melakukan penugasan kendaraan untuk melayani request baru. Dari contoh diatas diketahui pula bahwa rute paling minimum untuk meng-insertkan request 22 adalah rute 1. Sedangkan untuk request 23 adalah rute 2.

4.2 Percobaan Numerik

Percobaan 1

Rancangan percobaan Percobaan ini dicoba pada problem instance R101 dengan 25 request, maksimum iterasi tabu search 10 dan θ = 10 DOD 20% dan time slot = 6. Percobaan ini dilakukan untuk menunjukkan apakah algoritma dinamis yang telah dikembangkan mampu menyelesaikan permasalahan Dynamic Pick Up and Delivery Problem with Time Windows untuk penyedia jasa City-Courier yakni : a. b.

Selanjutnya dilakukan improvement dengan tabu search dan didapatkan hasil sebagai berikut : === Perubahan Rute Request Time Slot -1

Optimal

dari

Kumpulan

RUTE 1 : P22-P9-P19-D19-D9-D22-O0RUTE 2 : P3-P4-P14-D14-D4-D3-O0RUTE 3 : P5-P6-D5-P1-D1-D6-P8-D8-O0-

Melakukan penugasan kendaraan untuk melayani request baru Meminimasi cost akibat adanya request baru

RUTE 4 : P20-P21-P2-D2-D21-D20-O0RUTE 5 : P11-P12-P15-D12-D11-D15-O0RUTE 6 : P10-P13-D13-D10-O0RUTE 7 : P16-P17-D16-D17-O0-

O

RUTE 2 : P3-P14-D14-D3-O0-

N

RUTE 3 : P5-P6-D5-P1-D1-D6-P7-D7-O0RUTE 4 : P20-P2-D2-D20-O0

O

RUTE 5 : P11-P12-P15-D12-D11-D15-O0RUTE 7 : P16-P17-D16-D17-O0-

D

RUTE 6 : P10-P13-D13-D10-O0RUTE 8 : P4-P18-D18-D4-P8-D8-O0[TOTAL COST] : 1577.23997151948

Dari rute ini kemudian di insertkan 2 request baru pada time slot 1. Sehingga didapatkan hasil sebagai berikut : === >> Perubahan Rute Akibat Request : S22 RUTE 1 : P22-P9-P19-D19-D9-D22-O0-[UPDATED] RUTE 2 : P3-P14-D14-D3-O0-

Dari hasil running diatas dapat dilihat adanya penurunan cost setelah dilakukan improvement dengan menggunakan tabu search dari cost initial sebesar 2048.2 menjadi 1787.3. Yakni ada penurunan cost sebesar 12.7%

O

T

RUTE 1 : P9-P19-D19-D9-O0-

[TOTAL COST] : 1787.30815319543

C

Hasil Percobaan Dari hasil running didapatkan rute permasalahan statis sebagai berikut :

PY

RUTE 8 : P23-P18-D18-D23-P7-D7-O0-

Percobaan 2 Rancangan Percobangan Percobaan numerik ini dilakukan dengan melakukan 12 skenario percobaan yang dilakukan terhadap 2 problem instance yaitu R101 dan R 103 dengan 25 request. Adapun skenario percobaannya dapat dilihat pada tabel 6.6. Percobaan ini dilakukan unuk menunjukkan hubungan time slot terhadap total cost dan juga computational time.

RUTE 3 : P5-P6-D5-P1-D1-D6-P7-D7-O0RUTE 4 : P20*P21-P2-D2-D21-D20-O0RUTE 5 : P11*P12-P15-D12-D11-D15-O0RUTE 6 : P10-P13-D13-D10-O0RUTE 7 : P16-P17-D16-D17-O0RUTE 8 : P4-P18-D18-D4-P8-D8-O0[TOTAL COST] : 2048.1809323248

Hasil Percobaan Adapun hasil percobaannya dapat dilihat pada tabel 4.1. Bila tabel tersebut disajikan dalam bentuk grafik maka hasilnya dapat dilihat pada gambar 4.2 dan gambar 4.3

=== >> Perubahan Rute Akibat Request : S23 RUTE 1 : P22-P9-P19-D19-D9-D22-O0RUTE 2 : P3-P23-P14-D14-D23-D3-O0-[UPDATED] RUTE 3 : P5-P6-D5-P1-D1-D6-P7-D7-O0RUTE 4 : P20*P21-P2-D2-D21-D20-O0RUTE 5 : P11*P12-P15-D12-D11-D15-O0-

Tabel 4.1 Hasil percobaan 2


Computational Time (ms)

DOD 60% Computational Time Vs Time Slot 14000 12000 10000 8000 6000 4000 2000 0 4.0

6.0

8.0

10.0

Time Slot R101

R103

Gambar 4.2.c DOD 60% Rata-Rata Computational Time VsTime Slot Computational Time (ms)

14000 12000 10000 8000 6000 4000 2000 0 4

8

10

PY

Time Slot DOD 20%

DOD 40%

DOD 60%

O

Gambar 4.2.d Rata-rata computational time Vs Time Slot

T

C

10000 9000 8000 7000 6000 5000 4000 3000 2000 1000 0

O

DOD 20% Total Cost Vs Time Slot

8.0

10.0

Time Slot R101

Total Cost

N O 6.0

D

4.0

R103

Gambar 4.2.a DOD 20%

2000 1800 1600 1400 1200 1000 800 600 400 200 0 4.0

DOD 40% Computational Time Vs Time Slot

6.0

8.0

10.0

Time Slot R101

12000

R103

Gambar 4.3.a DOD 20%

10000 8000


6000 1950

4000

1900

2000

1850

0 4.0

6.0 Time Slot R101

8.0

R103

Gambar 4.2.b DOD 40%

10.0

Total Cost

Computational Time (ms)

Computational time (ms)

DOD 20% Computational Time Vs Time Slot

6

1800 1750 1700 1650 1600 1550 4.0

6.0

8.0

10.0

Time Slot R101

R103

Gambar 4.3.b DOD 40%


Total Cost


3.

2150 2100 2050 2000 1950 1900 1850 1800 1750 1700

4.

6. Daftar Pustaka 4.0

6.0

8.0

10.0

Abdullah Alkaff, Zulkifli Hidayat, Ahmad Rusdiansyah, Suhadi Lili, Nurlita gamayanti, Reesa Akbar, Fitri Karunia Rani, Yaniar Isnarti . 2007. Developing Dynamic Vehicle Routing Systems in Surabaya City. Proposal Penelitian PREDICT ITS

Time Slot R101

R103

Gambar 4.3.c DOD 40% Rata-Rata Total Cost Vs Time Slot Computational Time (ms)

2500 2000

Ballou, R H. 2004. Business Logistics/ Supply Chain Management: Planning, Organizing, and Controlling the Supply Chain, Pearson Education, Inc., New Jersey

1500 1000 500 0 4

6

8

10

DOD 40%

DOD 60%

O

DOD 20%

D

O

N

O

T

Dari gambar 4.2 dapat dilihat bahwa pada setiap DOD baik untuk problem instance R101 dan R103, semakin banyak time slot maka semakin tinggi computational time-nya. Kemudian pada grafik rata-rata dapat dilihat bahwa semakin tinggi DOD semakin tinggi pula computational time.

C

Gambar 4.3.d DOD 60%

Dari gambar 4.3 dapat dilihat bahwa pada setiap DOD baik untuk problem instance R101 dan R103, didapatkan grafik yang tidak beraturan sehingga dapat disimpulkan bahwa tidak terdapat hubungan antara total cost dan time slot begitu juga dengan DOD yang ditunjukkan grafik rata-rata. 5. Kesimpulan Kesimpulan yang dapat diambil dari penelitian ini adalah sebagai berikut :

2.

Cordeau, J. F., Laporte, G. 2002. “Tabu Search Heuristics for The Vehicle Routing Problem”. Canada Research and GERAD

PY

Time Slot

1.

dan juga meminimasi cost akibat adanya tambahan request baru Ada hubungan berbanding lurus antara banyaknya time slot dengan computational time. Tidak ada hubungan antara banyaknya time slot dan total cost

Telah dilakukan pengembangan algoritma heuristik untuk Dynamic Pick Up and Delivery Problem with Time Windows untuk penyedia jasa City-Courier Telah dilakukan pengembangan algoritma heuristik yang mampu melakukan penugasan kendaraan terhadap request baru

DPDPTW Instance. September 2007 . Gendreau, M., Guertin, F., Potvin, J.Y., Se´guin, R. 2006. “Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries”, Transportation Research Part C 14 Giani, G., Laporte, G., Musmanno, R. 2004. Introduction to Logistics Systems Planning and Control. John Wiley & Sons, Inc. I Nyoman Pujawan. 2005. Supply Chain Management. Surabaya : Guna Widya. Larsen, Allan., 2000. The Dynamic Vehicle Routing. IMM, DTU Lau, Hoong Chuin , Liang, Zhe. 2001. “Pickup and Delivery with Time Windows: Algorithms and Test Case Generation”. Proceedings of the 13th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'01


Mitrovic, Snezana., Minic. 1998. Pick Up and Delivery Problem With Time Windows : A Survey Nanry, William P., Barnes, J Wesley. 2000. “Solving the pick up and delivery problem with time windows using reactive tabu search”.Transportation Research Part B 34 (2000) 107-121 Pankratz, Giselher. 2005. “Dynamic Routing Vehicle by Means of Genetic Algorithm”. International Journal of Physical Distribution & Logistics Management, 364 Potvin, J.Y., Ying Xu, Ilham Benyahia. 2006. “Vehicle Routing and Scheduling with Dynamic Travel Times”. Computer & Operation Research 33 1129-1137 Sri Kusuma Dewi dan Hari Purnomo. 2005. Penyelesaian Masalah Optimasi dengan Teknik-Teknik Heuristik. Graha Ilmu : Surabaya.


PENGEMBANGAN ALGORITMA HEURISTIK UNTUK PENYELESAIAN DYNAMIC PICK UP AND DELIVERY PROBLEM WITH TIME WINDOWS (DPDPTW) UNTUK PENYEDIA JASA CITY - COURIER

Recommend Documents