Pengembangan Algoritma Heuristik Ant Colony System Untuk Menyelesaikan Permasalahan Dynamic Vehicle Routing Problem Dengan Time Window (DVRPTW) Pada Penyedia Jasa Inter-City Courier
Nurlita Gamayanti (2207 202 001) Pembimbing : Prof. Ir. Abdullah Alkaff, M.Sc, P.Hd Dr. Ir. Ahmad Rusdiansyah, M.Eng
PENDAHULUAN
Latar Belakang • Pentingnya penentuan rute dan penjadwalan pada Inter-City Courier untuk menghasilkan perjalanan yang efektif dan efisien. • Adanya online request yang menyebabkan rute inisial menjadi tidak optimal, sehingga perlu dilakukan update terhadap rute inisial. • Penyelesaian DVRP dengan algoritma ant colony system belum banyak dibahas, apalagi dengan model permasalahan inter-city courier seperti pada penelitian ini . • Ketidaksesuaian penelitian R. Montemanni tentang penyelesaian Dynamic Vehicle Routing Problem (DVRP) dengan ant colony system jika diterapkan pada permasalahan DVRP pada penyedia jasa Inter-City Courier dengan time windows.
Rumusan Masalah • Bagaimana mengembangkan algoritma heuristik untuk menentukan rute pengambilan paket yang meminimumkan total travel time untuk permasalahan Dynamic Vehicle Routing Problem dengan Time Windows pada penyedia jasa Inter-City Courier • Bagaimana performansi dari algoritma yang dikembangkan
Tujuan Penelitian (1) 1. Mengembangkan model untuk permasalahan Dynamic Vehicle
Routing Problem dengan Time Window (DVRPTW) pada penyedia jasa Inter-City Courier 2. Mengembangkan algoritma heuristik Ant Colony System yang dapat digunakan untuk menyelesaikan permasalahan DVRPTW pada penyedia jasa Inter-City Courier. 3. Membuat perangkat lunak untuk mengimplementasikan
algoritma. 4. Melakukan uji eksperimen menggunakan data test yang diadopsi dari data test standar di literatur (Chen). 5. Menerapkan algoritma yang dihasilkan pada data jaringan jalan
kota Surabaya.
Tujuan Penelitian (2) 6. Membandingkan algoritma yang dipakai dengan algoritma lain
yang sudah ada yaitu Nearest Neighbor dan Nearest Neighbor + Node Insertion
Batasan Masalah 1. Permasalahan dibatasi hanya untuk penyedia jasa
Inter-City Courier . 2. Pengiriman paket dibatasi sampai consolidation
point saja, pengiriman lebih lanjut ke kota tujuan diabaikan 3. Sebatas pengembangan algoritma saja
Asumsi 1. Paket – paket yang dikirimkan dianggap dapat diangkut pada satu kendaraan yang sama tanpa membedakan jenisnya. 2. Kapasitas kendaraan dianggap homogen 3. Jumlah kendaraan tidak terbatas 4. Travel time pada tiap arc diasumsikan sama setiap waktu (non timedependent)
TINJAUAN PUSTAKA
Studi Literatur (1) 1. Gambardella, Taillard, Agazzi, ”MACS-VRPTW : A Multiple Ant Colony System for Vehicle Routing Problem with Time Window”, 1999 VRPTW, meminimumkan total travel time Kapasitas tiap kendaraan dibatasi dan homogen. Algoritma multiple ant colony system (MACS), koloni semut satu untuk meminimumkan jumlah kendaraan dan koloni semut dua untuk meminimumkan total travel time. MACS : Algoritma ACS standar (Dorigo dan Gambardella, 1997) dalam papernya “Ant colony for the travelling salesman problem” Kelemahan : tidak bisa mengatasi permasalahan dynamic problem
Studi Literatur (2) 2. Montemanni, Gambardella, Rizzoli, Donati, “A new algorithm for a Dynamic Vehicle Routing Problem based on Ant Colony System”, 2002 DVRP, meminimumkan total travel time Algoritma ACS standar (Dorigo dan Gambardella, 1997) DVRP dimodelkan sebagai sekuen Static Vehicle Routing Problem, tiap Static VRP akan dicari rute dengan travel time paling minimum dengan menggunakan algoritma ACS. Lamanya tiap hari kerja dibagi menjadi beberapa time slot, tiap time slot memuat satu Static VRP. Pada time slot ke-1, semua offline request akan diproses. Jika ada order yang belum dikerjakan, maka order tersebut dikerjakan pada time slot berikutnya bersama dengan order baru yang diterima pada permulaan time slot, dan begitu seterusnya.
Kelemahan : - tidak terdapat time window constraint pada masing-masing node konsumen. - Tidak bisa mengatasi penerimaan order baru yang service time-nya terletak dalam time slot armada yang sudah meninggalkan depo. Hal ini disebabkan karena himpunan order yang ditugaskan pada tiap armada tidak akan mengalami perubahan.
Studi Literatur (3) 3. Chen, Ting, “An Improved Ant Colony System for the Vehicle Routing Problem”, 2004
VRP, meminimumkan total travel Kapasitas tiap kendaraan terbatas dan homogen. Algoritma Improved Ant Colony System (IACS). IACS menggabungkan construction rule yang baru, pheromone update rule yang baru dan pendekatan local search seperti 2opt atau node insertion move. Kesimpulan : IACS memiliki rata-rata hasil yang lebih bagus dibandingkan ACS standar (Dorigo dan Gambardella). Kelemahan : - Tidak terdapat time window constraint pada masingmasing node konsumen. - Tidak bisa mengatasi permasalahan dynamic problem
Studi Literatur (4) 4.
S.Ichoua, M. Gendreau, J. Potvin, “Diversion Issues in Real-Time Vehicle Dispatching”, 2000 Dynamic vehicle routing problem dengan time window (DVRPTW), meminimumkan total travel time Kapasitas kendaraan tidak dibatasi Menggunakan konsep diversion strategy. Diversion strategy memungkinkan kendaraan mengalihkan /merubah rute dalam perjalanannya menuju node selanjutnya karena adanya order baru. Algoritma parallel tabu search Kelemahan : kapasitas kendaraan tidak dibatasi
Posisi Penelitian Terdahulu • Posisi penelitian – penelitian terdahulu untuk Permasalahan DVRPTW pada Inter-City Courier dapat dilihat pada tabel berikut
Inter-City Courier Pintu masuk tol 1
Kota 1
CP4 Armada 1
7
6
1
D
Pintu masuk tol 2
2 CP3
Armada 2
3
Kota 2
4,5
5 Pintu masuk tol 3
4 Pintu masuk tol 4
CP1
1,2,3
6,7 Kota 3
CP2
METODE PENELITIAN
Model Permasalahan Inter-City Courier Permasalahan Permasalahan Statis Statis
Offline Offline Request Request
Permasalahan Permasalahan dinamis dinamis
Online Online Request Request
Permasalahan Permasalahan Inter-CityCourier Courier Inter-City
Deskripsi Permasalahan Statis Inter-City Courier (1) Notasi V
: Himpunan armada pengangkut
N
: Himpunan node konsumen
C
: Himpunan consolidasi point
0
: Depo
Q
: Kapasitas maksimum tiap armada pengangkut : Jumlah paket (kg) yang harus diambil di node : travel time dari node i ∈ N ke node j ∈ N , t ij termasuk service time pada node i
di
t ij
w kj
ei
: waiting time armada pengangkut k ∈ V di node j ∈ N : batas awal time window di node i ∈ N
Deskripsi Permasalahan Statis Inter-City Courier (2) li
: batas akhir time window di node
gc
: batas awal time window di consolidation point
hc
: batas akhir time window di consolidation point
mc b kj
x
k ij
k
: waktu dimana armada pengangkut k ∈ V sampai di consolidation point c ∈ C : waktu dimana armada pengangkut k ∈ V memulai service di node j∈N = 1 : jika armada pengangkut k ∈ V mengunjungi node j ∈ N segera setelah node i ∈ N , i ≠ j = 0 : lainnya
Formulasi Permasalahan Statis Inter-City Courier (1) 1. Fungsi Obyektif meminimumkan total travel time dan waiting time setiap armada pengangkut pada setiap node. k k t x + w ∑∑ ∑ ij ij j k∈V i∈N j∈N
2. Flow Constraint
-
Setiap node konsumen hanya dikunjungi tepat satu kali oleh satu armada pengangkut saja =1
∀j ∈ N \ {0}
k x ∑ ∑ ij = 1
∀i ∈ N \ {0}
∑∑ x k∈V i∈N
k∈V j∈N
k ij
Formulasi Permasalahan Statis Inter-City Courier (2) - Setiap armada pengangkut harus meninggalkan node konsumen yang baru saja dikunjungi
∑x
k ih
i∈N
−
∑x j∈N
k hj
= 0 ∀h ∈ N \ {0}, ∀k ∈ V
- Setiap armada pengangkut harus berangkat dari depo ∀k ∈ V ∑{ x} = 1 i∈N \ 0
k i0
- Setiap armada pengangkut harus berakhir di consolidasi point yang sama k x ∑ ic = 1
i∈N \{0 ,c}
∀k ∈ V
Formulasi Permasalahan Statis Inter-City Courier (3) 3. Capacity Constraint Total permintaan pada setiap armada pengangkut tidak boleh melebihi kapasitas maksimumnya
∑d ∑ x i
i∈N
j∈N
k ij
≤Q
∀k ∈ V
4. Time Window Constraint k ∈ V tidak akan sampai di node j ∈ N sebelum bik + tij , jika ia melintas dari node i ∈ N ke node j ∈ N
- Armada pengangkut
(
) = max {e
xijk bik + tij ≤ b j b kj
j
k
∀i ∈ N , ∀j ∈ N , ∀k ∈ V
,bik + t ij
}
Formulasi Permasalahan Statis Inter-City Courier (4) - Waktu untuk memulai service di tiap node konsumen bagi setiap armada pengangkut harus berada di dalam interval time window tiap node ei ≤ bik ≤ li
∀i ∈ N , ∀k ∈ V
- Setiap armada pengangkut harus sampai di consolidation point dalam interval time window consolidation point g c ≤ mc ≤ hc k
∀c ∈ C , ∀k ∈ V
Deskripsi Permasalahan Dinamis Inter-City Courier Initial Route CP3
9
CP4
8
7
5
6
CP2
6
4
5
6
CP2
2 7
4
2
CP1
1
2
3
7
1
2
3
4
6
7
8
9
9
1
2 7
4
2
3 CP1
1
3 CP1
1
D 5
CP2
8
3
4
D 0
5
6
4
2
3
7
5
9
1
4
3
CP4
6
8
5
1
CP3
8
7
6
5
9
CP3
9
CP4
8
Update Route
New Orders / Online Requests
0
1
2
3
4
D 5
6
7
position
8
0
9
1
2
reroute Dispatch center/ control room
3
4
5
6
7
8
9
Pemodelan Jaringan Jalan (1)
Pemodelan Jaringan Jalan (2)
6 5
4 3
Pemodelan Jaringan Jalan (3) C
D 6 6
4
5 3
A
B
4 6
4
E
3 3
F
Pemodelan Jaringan Jalan (4) C
3
E
4
3
A
B
4
6 F
6
D
Tahapan Penyelesaian Masalah Input Offline Request
Input Online Request
Penyelesaian Permasalahan Statis Inter-City Courier (VRPTW)
Penyelesaian Permasalahan Dinamis Inter-City Courier (VRPTW)
Penyelesaian Permasalahan Statis Input konsumen (Offline request) Database Jalan
Pencarian travel time tercepat menggunakan Djikstra
Pencarian rute tercepat menggunakan IACS
Penyusunan rute dan urutan jalan
Database travel time antar node
Ant Colony System (1) Dasar perumusan : kemampuan dari sekumpulan semut (colony) yang dapat menemukan jalur terpendek dari sumber makanan ke sarangnya.
Seekor semut akan meninggalkan jejak pheromone ketika dia melalui suatu lintasan. Dengan bantuan pheromone ini juga sekumpulan semut dapat beradaptasi terhadap perubahan dalam jalur yang telah mereka lalui.
Ant Colony System (2) •
Prosedur 1.
Menentukan parameter dan inisialisasi jumlah pheromone pada setiap arc. 2. Setiap semut akan membangun solusi (rute) berdasarkan state trantition rule dan meng-update jumlah pheromone pada setiap arc yang dilaluinya berdasarkan local pheromone update. 3. Melakukan local search pada setiap solusi. 4. Meng-update jumlah pheromone berdasarkan global pheromone update pada arc yang membentuk solusi terbaik.
IACS (1) IACS
Ant Colony System (Dorigo, Gambardella) yang mengalami perbaikan pada : route construction rule pheromone update rule
IACS (2) • IACS dan ACS
ACS
IACS
Route Construction Rule : - Dalam 1 iterasi, terdapat b solusi (b=juml.semut) - Dalam 1 iterasi, local search dikenakan pada setiap solusi - Parameter ηij fungsi dari travel time tiap arc
Route Construction Rule : - Dalam 1 iterasi, terdapat b-1 solusi - Dalam 1 iterasi, local search dikenakan pada solusi terbaik saja - Memasukkan unsur waiting time pada parameter ηij
Global Pheromone Update Rule - Sesuai dengan pers (2.30) - Global pheromone update dikenakan pada arc2 pembentuk solusi terbaik iterasi sekarang
Global Pheromone Update Rule - Sesuai dengan pers (3.16)-(3.17) - Global pheromone update dikenakan pada arc2 pembentuk solusi terbaik iterasi sekarang dan sebelumnya
Prosedur IACS (1) • Langkah 1 : Menentukan parameter IACS dan inisialisasi jumlah pheromone Start time = 00.00 • Langkah 2 : Membangkitkan InitialSolution menggunakan Nearest Neighbor. • Langkah 3 : Menerapkan insertion heuristics pada InitialSolution dan disimpan sebagai 1stSolution. Iterasi = 1, Ant = 2, consolidation point = 1
Prosedur IACS (2) • Langkah 4 : Bentuk solusi berdasarkan state transition rule dan lakukan local pheromone update pada setiap arc yang dilalui. Ant = Ant + 1 • Langkah 5 : Jika Ant > JumlahMaxAnt maka Ant = 2 dan lakukan langkah 6. Jika Ant <= JumlahMaxAnt maka lakukan langkah 4 • Langkah 6 : Urutkan solusi ke-2 s/d solusi ke-JumlahMaxAnt, lakukan Insertion Heuristics pada solusi yang terbaik dan simpan sebagai 2ndSolution
Prosedur IACS (3) • Langkah 7 : Lakukan Global Pheromone Update pada arc-arc yang membentuk 1stSolution dan 2ndSolution • Langkah 8: Bandingkan 1stSolution dan 2ndSolution, simpan solusi yang terbaik sebagai TheBestSolution. Pada iterasi berikutnya, 1stSolution = TheBestSolution. Iterasi = Iterasi + 1 (Jika Iterasi > MaxIterasi) maka ke langkah 9 (Jika Iterasi <= MaxIterasi) maka kembali ke langkah 4
Prosedur IACS (4) • Langkah 9 : consolidation point = consolidation point + 1 Jika (consolidation point > jumlah consolidation point) maka ke langkah 10 Jika (consolidation point <= jumlah consolidation point) kembali ke langkah 4, Iterasi = 1
• Langkah 10 : Menentukan start time pada TheBestSolution untuk meminimumkan total travel time. Pada tiap tour, Start time = batas awal time window node konsumen kesatu - t 01 t 01 adalah travel time dari depo menuju node konsumen kesatu
• Langkah 11 : Stop
Inisialisasi Pheromone • Inisialisasi jumlah pheromone pada setiap arc adalah :
τ0 = (N x LNN )
−1
State Transition Rule Setiap semut yang berada di node i akan memilih node j atau arc (i,j) berdasarkan state transition rule berikut : ¾ Jika q ≤ q 0 (Eksploitasi)
{
j : = arg max (τ ij ) (ηij ) j∈S ' ( i )
α
β
}
¾ Jika q > q 0 (Eksplorasi)
(τ ) (η ) ∑ (τ ) (η ) α
- Hitung , Pij = - Hitung Fij
β
ij
ij
α
j∈S ' ( i )
Cj
β
Cj
- Jika (q > Fia ) dan (q < Fib ) maka : j = b
Menentukan besarnya ηij : - Jika (syarat kapasitas) dan (syarat time windows) terpenuhi maka : ηij =
1 t ij + w kj
- Jika (syarat kapasitas) dan (syarat time windows) tidak terpenuhi maka : η ij = 0
Global Pheromone Update Setelah semua semut telah membentuk solusinya masing-masing, maka arc – arc yang membentuk 1st Solution dan 2nd Solution pada setiap iterasi akan berubah jumlah pheromonenya berdasarkan Global Pheromone Update : τij
new
= (1 − γ ) τij
Δτij =
old
+ γ Δτij
( A − B)+ ( A − C ) A
A = cost (total travel time) terbaik ke-3 pada tiap iterasi B = cost (total travel time) terbaik secara keseluruhan C = cost (total travel time) terbaik pada tiap iterasi
Local Pheromone Update • Setiap kali melewati arc(i,j), semut – semut akan meng-update jumlah pheromone pada arc(i,j) berdasarkan Local Pheromone Update berikut : τij
new
= τij
old
+ (1 − ρ) τ0
Penyelesaian Permasalahan Dinamis (1) Diagram Alir
Online request,request time Rute inisial, Posisi kendaraan saat ini, Himpunan konsumen yang sudah dikunjungi Meentukan himpunan node yang belum dikujungi berdasarkan request time
Database jalan
Pencarian travel time tercepat antara online request dengan semua node yang belum dikunjungi Identifikasi service time online request
Menyisipkan node online request pada rute inisial Pencarian rute tercepat menggunakan insertion heuristics Penyusunan rute dan urutan jalan
Database travel time antar online request dan semua node konsumen (Offline Request)
Penyelesaian Permasalahan Dinamis (2) Prosedur : • Langkah 1 : Mengidentifikasi posisi setiap armada pengangkut saat ini . Ada 3 kemungkinan : - armada pengangkut tepat berada di node konsumen. - armada pengangkut berada diantara dua node konsumen. - armada pengangkut sedang menunggu karena waktu kedatangannya di node konsumen tertentu sebelum batas awal time window node yang bersangkutan.
• Langkah 2 : Menentukan himpunan node yang belum dikunjungi berdasarkan request time
Penyelesaian Permasalahan Dinamis (3) • Langkah 3 : Menghitung travel time terpendek antara node online request dengan semua node yang terdapat pada rute inisial dengan menggunakan algoritma Djikstra. • Langkah 4 : Mengidentifikasi service time dari online request. Menyisipkan online request pada rute inisial dengan mempertimbangkan time window constraint dan capacity constraint. Jika time window constraint dan atau capacity constraint tidak terpenuhi, maka dibentuk tour baru.
Penyelesaian Permasalahan Dinamis (4) • Langkah 5 : Menerapkan node insertion heuristics untuk mendapatkan rute baru dengan total travel time minimum secara keseluruhan.
HASIL PENELITIAN & PEMBAHASAN
Perangkat Lunak (1) • Memasukkan data konsumen (halaman Order)
Perangkat Lunak (2) • Parameter IACS (halaman Parameter)
Perangkat Lunak (3) • Optimasi (halaman Optimation)
Perangkat Lunak (4) • New Order
Menentukan Jumlah Sample • Dari data rute pelayanan konsumen didapatkan total travel time rata – rata hasl nearest neighbor sebesar 28633,2 detik dan varians populasi sebesar 6150,48 detik. (tingkat ketelitian taksiran µ sebesar 5% dari total travel time rata-rata dengan selang kepercayaan 90% ) 2 ⎛ Z α 2 .σ ⎞ ⎟ = ⎛⎜ 1,96 × 6150 ,48 ⎞⎟ = 17 ,27 n = ⎜⎜ ⎟ e ⎝ 0 ,1 × 28633 ,2 ⎠ ⎝ ⎠ 2
Pengujian Algoritma (1) • Perbandingan total travel time IACS, NN, dan NN + NI pada fase statis (Data standar Chen) 60000
Total travel time
50000 40000 IACS NN
30000
Penghematan thd NN = 25,57%
NN + NI 20000
Penghematan thd NN+NI = 20,11%
10000 0 1
2
3
4
5
6
7
8
9 Data
10 11 12 13 14 15 16 17
Pengujian Algoritma (2) • Perbandingan jumlah armada hasil IACS, NN, dan NN+NI pada fase statis (Data standar Chen) 12
Jumlah Armada
10 8
IACS
6
NN NN+N!
4 2 0 1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 Data
Pengujian Algoritma (3) • Perbandingan total travel time IACS, NN, dan NN + NI pada fase dinamis (Data standar Chen) 90000 80000 Total travel time
70000 60000 IACS
50000
NN
40000
NN + NI
30000 20000 10000 0 1
2
3
4
5
6
7
8
9 Data
10 11 12 13 14 15 16 17
Penghematan thd NN = 20,47% Penghematan thd NN+NI = 16,49%
Pengujian Algoritma (4) • Perbandingan jumlah armada hasil IACS, NN, dan NN+NI pada fase dinamis (Data standar Chen) 12
Jumlah Armada
10 8
IACS
6
NN NN+NI
4 2 0 1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 Data
Implementasi Algoritma (1) • Perbandingan total travel time hasil IACS, NN, danNN+NI pada fase statis pada jaringan jalan kota Surabaya Total Travel Time (detik) No
Jumlah Offline Request
Optimasi IACS (%)
IACS
NN
NN + Node Insertion
NN
NN + Node Insertion
1
12
16237
20436
19502
25,86
20,11
2
15
14692
17426
17255
18,61
17,45
Rata - rata
22,23
18,78
Implementasi Algoritma (2) •
Perbandingan total travel time hasil IACS, NN, dan NN+NI pada fased inamis pada jaringan jalan kota Surabaya Total Travel Time (detik) Jum. Off. Req
Jum. On. Req
IACS
1
12
2
2
15
2
No
Optimasi IACS (%)
NN
NN + Node Insertion
NN
NN + Node Insertion
20260
29095
27804
43,61
37,24
17424
19808
19449
13,68
11,62
Rata - rata
28,65
24,43
Kesimpulan •
Pencarian travel time tercepat dalam jaringan jalan dapat dimodelkan dalam permasalahan lintasan tercepat, dan dengan pemodelan yang tepat dapat diselesaikan dengan menggunakan algoritma Dijkstra.
•
Perencanaan pengangkutan paket konsumen pada penyedia jasa inter-city courier menuju ke consolidation point dapat dimodelkan dalam permasalahan Dynamic Vehicle Routing Problem with Time Windows.
•
Berdasarkan hasil pengujian algoritma dengan data standar Chen, algoritma yang digunakan memiliki performansi yang baik dalam menyelesaikan permasalahan DVRPTW pada inter-city courier baik pada fase statis maupun pada fase dinamis..
•
Algoritma yang digunakan dapat diimplementasikan dengan baik pada jaringan jalan kota Surabaya.
Saran • Perlu dikembangkan metode yang berbeda untuk menyelesaikan permasalahan DVRPTW pada inter-city courier sebagai pembanding dan sekaligus melengkapi kelemahan masing – masing. • Dikembangkan untuk mencari total travel time tercepat dengan memperhitungkan parameter dinamis lainnya selain order baru (online request), misalnya kemacetan lalu lintas dsb. • Dikembangkan untuk mencari total travel time tercepat dengan travel time antar node yang bergantung pada waktu (time dependent)
TERIMA KASIH .....
