ANALISIS RUTE PENDISTRIBUSIAN DENGAN MENGGUNAKAN METODE NEAREST INSERTION HEURISTIC PERSOALAN THE VEHICLE ROUTING PROBLEM WITH TIME WINDOWS (VRPTW) (STUDI KASUS DI KORAN HARIAN PAGI TRIBUN JABAR) Agus Purnomo Jurusan Teknik Industri Fakultas Teknik Universitas Pasundan Hasil penelitian yang dipublikasikan pada Prosiding Seminar Nasional Teknik Industri : “Pemberdayaan Rekayasa Industri Berbasis Eco-Efficiency pada Era Perdagangan Bebas”, Program Studi Teknik Industri UNISBA, 24 November 2010, ISBN : 978-602-98058-0-2 Abstrak : Permasalahan dalam penelitian ini yaitu mahalnya ongkos transportasi dalam pendistribusian koran Harian Pagi Tribun Jabar ke para agen di Kota Bandung. Dengan demikian tujuan penelitian ini untuk menentukan rute pendistribusian koran Harian Pagi Tribun Jabar agar diperoleh jarak tempuh dan ongkos transportasi yang minimum dengan mempertimbangkan kapasitas angkut kendaraan dan waktu pelayanan tertentu yang ditetapkan oleh para agen. Metode pemecahan yang digunakan adalah Insertion Heuristic pada persoalan The Vehicle Routing Problem With Time Windows (VRPTW) Hasil penelitian diperoleh 3 rute, yaitu rute pertama : A,J,K,D,Q,P,H,F,A dengan jarak tempuh 50,4 Km, waktu tempuh 102 menit dengan alokasi kapasitas kendaraan 1,88 ton; rute kedua A,G,M,C,A dengan jarak tempuh 50,4 Km, waktu tempuh 102 menit dengan alokasi kapasitas kendaraan sebesar 2 ton; rute ketiga A,B,E,L,N,O,I,A dengan jarak tempuh 64,5 Km, waktu tempuh 123 menit dengan alokasi kapasitas kendaraan sebesar 1,76 ton. Ongkos total transportasi yang minimum sebesar Rp.8.680.735,78,-/bulan. Kata kunci : Rute Pendistribusian, The Vehicle Routing Problem With Time Windows (VRPTW), Insertion Heuristic, Jarak Tempuh, Ongkos Transportasi.
I. PENDAHULUAN
Vehicle Routing Problem with Time Windows (VRPTW) merupakan permasalahan yang sering terjadi pada banyak sistem logistik. VRPTW adalah permasalahan bagaimana sebuah depot, pusat distribusi barang, dengan sejumlah kendaraan berkapasitas tertentu melayani sejumlah pelanggan pada titik-titik lokasi terpisah, dengan permintaan dan batasan time windows (jangka waktu) tertentu artinya, dengan tujuan meminimalkan total biaya perjalanan, tanpa mengabaikan batasan kapasitas kendaraan dan time window depot. Dalam VRPTW, sebuah kendaraan tidak diizinkan untuk sampai pada pelanggan setelah waktu terakhir untuk memulai layanan. Namun, jika kendaraan tiba terlalu dini di pelanggan, maka diperbolehkan untuk menunggu sampai waktu yang paling awal untuk memulai layanan, Lenstra and Rinnooy Kan [1]. Desain rute dilakukan sedemikian hingga setiap pelanggan hanya dikunjungi sekali oleh satu kendaraan, dan setiap kendaraan memulai dan mengakhiri rutenya pada depot, Solomon [2]. VRP adalah sebuah problem pemrograman integer yang masuk kategori NP-Hard Problem, yang berarti usaha komputasi yang digunakan akan semakin sulit dan banyak seiring dengan meningkatnya ruang lingkup masalah, Desrosiers et al. [3]. Untuk
masalah-masalah seperti ini, biasanya yang dicari adalah aproksimasi solusi yang terdekat, karena solusi tersebut dapat dicari dengan cepat dan cukup akurat. Biasanya masalah ini diselesaikan dengan menggunakan berbagai variasi dari metode heuristik yang memerlukan sedikit pengamatan pada ruang lingkup masalah, Kolen et al. [4]. Harian Pagi Tribun Jabar merupakan koran yang terbit di Kota Bandung dengan wilayah distribusi adalah Jawa Barat. Namun pada penelitian ini hanya dibatasi untuk agen - agen atau titik drop yang berada di wilayah distribusi Kota Bandung. Setiap agen mempunyai permintaan koran yang berbeda-beda dan tidak menerima pengiriman barang di luar jam yang telah ditentukan, sementara kendaraan yang dipakai untuk pendistribusian koran sendiri memiliki kapasitas yang terbatas. Karena banyak permintaan agen yang harus dilayani dengan kapasitas angkut kendaraan yang terbatas maka menyebabkan rute pengiriman bisa dilalui lebih dari sekali sehingga membuat jarak tempuh dan ongkos transportasi meningkat. Bila kendaraan sampai ditempat agen sebelum waktu pelayanan dimulai maka kendaraan harus menunggu, tetapi jika kendaraan datang melewati batas akhir waktu pelayanan maka kendaraan tidak akan dilayani.
Agus Purnomo – Jurusan Teknik Industri UNPAS
1
Permasalahan dalam penelitian ini yaitu bagaimana merencanakan rute, ongkos transportasi, kapasitas angkut dan permintaan waktu pelayanan dengan waktu tertentu untuk setiap agen. Pemecahan persoalan ini menggunakan VRPTW dengan Metode Nearest Insertion yaitu algoritma yang menentukan titik untuk disisipkan dengan mencari titik bebas yang paling dekat dengan suatu titik pada tur. Algoritma ini 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 yang merupakan algoritma yang membangun suatu tour dari sikel-sikel kecil dengan bobot minimal dan secara berturut-turut ditambah dengan titik baru sampai semua titik berhasil dilalui, Cunha, C.B. and Swait, J.D. [5].
3.
4.
II. METODOLOGI Dalam VRP ini terdapat serangkaian perencanaan set kendaraan (m) yang dimulai dan berakhir pada depot dan terdapat batasan waktu pelayanan/pengiriman yang berbeda pada setiap node yang disebut dengan Vehicle Routing Problems With Time Windows (VRPTW) atau versi sederhana disebut dengan Node Routing and Scheduling Problems with Time Windows (NRSPTW) dengan langkahnya Nearest Insertion yang terdapat didalam salah satu metode Nearest Insertion Heuristic. Metode ini melakukan pembentukan rute dengan cara memilih pelanggan yang akan disisipkan kedalam suatu rute yang sudah ada. Proses penyisipan dilakukan hingga rute yang bersangkutan dinyatakan penuh, baik berdasarkan kapasitas kendaraan maupun jadwal waktu pelayanan di masing-masing pelanggan. Tujuannya adalah untuk membentuk satu atau beberapa rute pelayanan dengan total ongkos perjalanan yang minimum. Diasumsikan besarnya ongkos proporsional terhadap jarak dan waktu tempuh. Langkah-langkah dalam memecahkan permasalahan dengan menggunakan algoritma Nearest Insertion dapat digambarkan pada flowchart gambar 1 dengan uraian sebagai berikut : 1. Buat Matrik jarak dan Waktu Tempuh. 2. Tentukan seluruh node (tidak termasuk depot) yang belum masuk ke dalam rute sebagai node bebas. Pilih satu node bebas untuk dijadikan node awal dari rute yang akan dibentuk, nyatakan node tersebut sebagai node i. Pemilihan node awal dapat berdasarkan pada jarak node terhadap depot atau jadwal waktu pelayanan. Tetapkan rute awal sebagai R = {0,i, n +1} dengan 0 dan n +1 adalah depot.
5.
6.
7.
8.
9.
Tentukan node bebas yang dipertimbangkan untuk disisipkan dengan node u dimana µ ≥ 0. Tetapkan nilai parameter 1 yaitu bobot yang diberikan terhadap total jarak yang terjadi akibat penyisipan node u dan parameter 2 yaitu bobot yang diberikan terhadap perubahan waktu pelayanan akibat penyisipan node u ( 1 + 2 =
1). Tetapkan nilai parameter yaitu bobot yang diberikan bagi ongkos perjalanan dari depot ke node u jika node u tidak disisipkan kedalam rute ( ≥ 0). Tentukan rute saat ini sebagai R = {0,i,....., j}dimana 0 dan j adalah depot. Untuk setiap node bebasa u, hitung total tambahan jarak yang terjadi jika node u disisipkan dengan menggunakan formula : Z11(i, u, j) = diu + dju - µ dij ≥ 0; dimana : diu , dju dan dij masing-masing adalah jarak antara node i dengan node u, node u dengan node j, dan node i dengan node j. Hitung tambahan waktu untuk kendaraan tiba dan memulai pelayanan di node i jika node u disisipkan dengan menggunakan formula : Z12 (i, u, j) = t0u + tu + tui – t0i ; dimana : t0u , tui , t0i masing – masing adalah waktu tempuh dari depot ke node u, dari node u ke node i, dan dari depot ke node i , sedangkan tu adalah waktu pelayanan di node u Hitung besarnya ongkos penyisipan yang besarnya proporsional terhadap tambahan jarak dan tambahan waktu tempuh untuk tiba di node i jika node u disisipkan dengan menggunakan formula : Z1 (i, u, j) = 1 Z11 (i, u, j) + 2 Z12 (i, u, j) ; 1 ≥ 0 ; 2 ≥ 0 ; 1 + 2 =1. Sisipkan node bebas u yang memiliki nilai Z1 (i, u, j) minimum ke dalam rute diantara node i dan node j yang sudah ada. Jika kapasitas kendaraan dan batas waktu pelayanan masih memungkinkan, maka lakukan penyisipan sebagai berikutnya dimana nilai Z2 (i, u, j) maksimum, dimana ; Z2 (i, u, j) = d0u Z1 (i, u, j) ; ≥ 0; dimana : Z2 (i, u, j) menyatakan selisih antara ongkos penyisipan yang terjadi jika node u ditempuh langsung dari depot dengan ongkos yang terjadi jika node u disisipkan kedalam rute. Sesuaikan dengan jumlah permintaan tiap node dari rute yang terbentuk dengan kapasitas angkut. Jika masih terdapat node bebas maka ulangi dengan dimulai dari langkah 3 hingga keseluruhan node masuk kedalam rute. Untuk setiap rute yang terbentuk lakukan perubahan posisi node atau urutan pelanggan
Agus Purnomo – Jurusan Teknik Industri UNPAS
2
yang dikunjungi untuk memperoleh total jarak dan total waktu menunggu yang minimum.
MULAI
Sedangkan untuk ongkos transportasi dalam Fixed Cost dan Variabel cost berdasarkan jarak tempu dengan rumusan adalah : Transportation Cost = Fixed Cost + Variable Cost
Menentukan Matrik Jarak dan Waktu tempuh
n
= a + b.
i 1
Pilih Node yang Memiliki Jarak Terdekat dengan depot
Xi ..………..(1)
dimana : a = fixed cost/bulan( Rp); b = variable cost/km(Rp.); x = jarak yang ditempuh (km). Kategori fixed cost dalam penelitian ini adalah : biaya tetap kendaraan (penurunan nilai jual motor), dan biaya pengemudi (gaji pengemudi). Sedangkan yang termasuk dalam variable cost adalah : biaya bahan bakar, biaya penggantian ban, biaya penggantian minyak pelumas ( oli ), dan biaya perawatan (kampas rem, minyak rem, dll.).
Hitung Tambahan Jarak dan Waktu Tempuh untuk Setiap Node Bebas
Hitung Besarnya ongkos Penyisipan dan Sisipkan Node yang Memiliki Nilai Z1 Minimum
Hitung Besarnya Selisih Ongkos Jika tidak lakukan Penyisipan u dan Sisipkan Node Yang Memiliki Nilai Z2 Minimum
Tidak
Apakah Kapasitas Angkut Sesuai Dengan Jumlah Seluruh Permintaan Tiap Node?
Ya Periksa Kembali Urutan Pelanggan Yang Dikunjungi Untuk Memperoleh Total Jarak dan Waktu Menunggu Yang Minimum
SELESAI
Gambar 1. Flowchart Algoritma Insertion Heuristic Langkah-langkah Pemecahan Masalah Penelitian ini disajikan pada gambar 2 berikut ini.
Agus Purnomo – Jurusan Teknik Industri UNPAS
3
III. HASIL DAN PEMBAHASAN MULAI
Studi Lapangan
Studi Pustaka
Perumusan Masalah Bagaimana menentukan rute pendistribusian agar diperoleh jarak tempuh yang minimum dan sesuai dengan kapasitas angkut serta waktu pelayanan dengan waktu tertentu yang ditetapkan oleh agen agar diperoleh total ongkos transportasi yang minimum
Tujuan Penelitian Menentukan rute pendistribusian agar diperoleh jarak tempuh yang minimum dan sesuai dengan kapasitas angkut serta waktu pelayanan dengan waktu tertentu yang ditetapkan oleh agen agar diperoleh total ongkos transportasi yang minimum
Pengumpulan Data 1. Peta jaringan jalan wilayah Kota Madya Bandung; 2. Data umum perusahaan; 3. Jenis & kapasitas kendaraan yang digunakan; 4. Permintaan/demand tiap agen; 5. Jadwal waktu pengiriman(Time windows) tiap agen; 6. Matriks jarak dan waktu tempuh
3.1 Demand Harian Setiap Agen dan Jadwal Permintaan Berikut ini adalah demand atau permintaan untuk setiap agen yang berada di wilayah Kota Bandung : Tabel 1. Demand harian setiap Agen di wilayah Kota Bandung Tahun 2010 KODE
AGEN
EKS
KG
TON
-
-
-
-
Jalan Leuwipanjang
5,500
500
0.5
02:30 – 04:20
C
Jalan Terusan Pasirkoja
1,687
153
0.15
02:00 – 05:00
D
Jalan Antanan
813
74
0.07
02:30 – 05:00
E
Jalan Baladewa Indah
5,246
477
0.48
02:00 – 05:00
F
Jalan Doktor Otten
4,100
373
0.37
02:00 – 06:00
G
Jalan Cihampelas
18,099
1,645
1.65
02:30 – 06:00
H
Jalan Sukajadi
1,638
149
0.15
02:00 – 05:00
I
Jalan Sirnagalih
1,543
140
0.14
02:00 – 04:45
J
Jalan Listrik 2
1,370
125
0.12
02:10 – 02:35
K
Jalan Jenderal Abdul Haris Nasution
1,085
99
0.1
02:00 – 04:09
L
Jalan Caringin
1,050
95
0.1
02:20 – 05:9
M
Jalan Babakan Ciparay
2,150
221
0.2
02:30 – 05:11
N
Jalan Holis
2,870
261
0.26
02:30 – 05:00
O
Jalan Raya Cibeureum
3,039
276
0.28
02:00 – 04:19
P
Jalan Kebon Kawung
3,039
276
0.28
02:00 – 03:13
Q
Jalan Buah Batu
8,700
791
0.79
02:05 – 05:14
A
DEPOT (Rancaekek)
B
Jdwl. Permintaan
Keterangan : EKS (Exsemplar) = bilangan 1 buah Koran 1KG = 11 EKS 3.2 Matrik Jarak dan Matrik Waktu Tempuh 3.2.1 Matrik Jarak Data jarak tempuh dari Depot dan setiap agen (asal dan tujuan) disajikan pada tabel 2 berikut. Tabel 2. Matrik Jarak (Km) asal dan tujuan distribusi Koran. AGEN
Pengolahan Data Penentuan rute dengan menggunakan NRPTW dengan metodenya Insertion Heuristic (Nearest Insertion)
Analisis
Kesimpulan dan Saran
SELESAI
Gambar 3. Langkah-langkah Pemecahan Masalah
DEPOT(Rancaekek)
KODE A A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
0 22.2 22.4 17.1 24 22.5 21.6 22.9 23.4 8.2 9.3 23.4 23.8 25.4 26.6 21.9 20
Jalan Leuwipanjang
B
22.2 0
2.5 8.8 5.2 4.9 7.4 6.1 7.4 16.4 15.3 1.1 1.6 4.4 6.5 3.9 2.7
Jalan Terusan Pasirkoja
C
22.4 2.5
0
Jalan Antanan
D
17.1 8.8 7.3
Jalan Baladewa Indah
E
Jalan Doktor Otten
F
0
0.6
1
Jalan Cihampelas
G
21.6 7.4 2.4 5.4 2.4 0.6
0
1.3 2.5 14.4 13.2 4.9 4.5 4.4 10 0.8 4.35
Jalan Sukajadi
H
22.9 6.1 3.2 5.9 1.8
1.3
0
1 15.3 14.1 5.6 5.1 4.2
8
Jalan Sirnagalih
I
23.4 7.4 4.5 6.4 2.8 2.5 2.5
1
0 15.6 14.4 5
4.3 2.9 7.1
Jalan Listrik 2
J
8.2 16.4 16 9.1 17.2 15.5 14.4 15.3 15.6 0
0.9 17.3 17.6 18.6 19.5 15 13.8
Jalan Jend. A. H. Nasution
K
9.3 15.3 14.8 7.8 16 14.2 13.2 14.1 14.4 0.9
0 16.3 16.4 17.4 18.3 13.8 12.6
Jalan Caringin
L
23.4 1.1 2.3 9.4 4.2 4.5 4.9 5.6
Jalan Babakan Ciparay
M
23.8 1.6 1.9 9.3 3.5 3.9 4.5 5.1 6.2 17.6 16.4 0.5
Jalan Holis
N
25.4 4.4 2.7 9.9 2.1 3.5 4.4 4.2
5 18.6 17.4 3.2 2.3
0
2
3.4
Jalan Raya Cibeureum
O
26.6 6.5 4.2 10.2 4.4 7.8 10
4.3 19.5 18.3 5.3 4.5
2
0
4.2 6.5
Jalan Kebon Kawung
P
21.9 3.9 1.4 6.1 1.9 0.4 0.8 1.8 2.9 15 13.8 3.9 3.4 3.4 4.2
Jalan Buah Batu
Q
20 20 2.2 5.8 4.4 4.37 4.35 4.4 7.1 13.8 12.6 3.5 3.6
7.3 2.3
2
0
8
6.3 5.4 5.9 6.4 9.1 7.8 9.4 9.3 9.9 10.2 6.1 5.8
24 5.2 2.3
8
0
1.5 2.4 1.8 2.8 17.2 16 4.2 3.5 2.1 4.4 1.9 4.4
22.5 4.9
6.3 1.5
2
1
2.4 3.2 4.5 16 14.8 2.3 1.9 2.7 4.2 1.4 2.2
8
2.5 15.5 14.2 4.5 3.9 3.5 7.8 0.4 4.37
5 17.3 16.3 0
6.2
5
1.8 4.4
0.5 3.2 5.3 3.9 3.5 0
2.3 4.5 3.4 3.6
5
0
3.6
6.5 3.6
0
3.2.2 Matrik Waktu Tempuh Untuk menghitung waktu tempuh (menit) dengan cara membagi jarak tempuh dengan rata-rata kecepatan kendaraan.
Agus Purnomo – Jurusan Teknik Industri UNPAS
5
4
Waktu Tempuh =
x 60 Jarak (km) kecepa tan rata rata
a) Jika jarak dari node J (Jln. Listrik 2) ke node C (Jln.Terusan Pasirkoja) adalah 16 Km b) Jika jarak dari node C (Jln.Terusan Pasirkoja) ke node A (depot) adalah 22,4 Km c) Jika jarak dari node J (Jln. Listrik 2) ke node A (depot) adalah 8,2 Km Maka (J,C)= d(J,C) + d(C,A) - d(J,A) = 16 Km + 22,4 Km - 8,2 Km = 30,2 Km Hasil perhitungannya dimasukan ke dalam Tabel 4.
Keterangan : Kecepatan rata-rata adalah 30 km /jam; dan 1 Jam = 60 menit Contoh perhitungan waktu tempuh dari Depot (A) ke Jln.Leuwipanjang (B) =
22,2 Km x 60 30 Km / jam
= 44,4 menit dibulatkan = 44 menit Hasil perhitungan waktu tempuh (menit) dari asal ke tujuan distribusi disajikan pada tabel 3 berikut.
Tabel 4. Penghematan Jarak untuk Rute 1
Tabel 3. Matrik Waktu Tempuh (menit) asal dan tujuan distribusi Koran. AGEN
KODE A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
i
u
d(i,u ) d(u ,A) d(i ,A)
Z 11
J
B
16.4
22.2
8.2
30.4
C
16
22.4
8.2
30.2
D
9.1
17.1
8.2
18
E
17.2
24
8.2
33
F
15.5
22.5
8.2
29.8
DEPOT(Rancaekek)
A
0
44
45
34
48
45
43
46
47
16
19
47
48
51
53
44
40
Jalan Leuwipanjang
B
44
0
5
18
10
10
15
12
15
33
31
2
3
9
13
8
5
Jalan Terusan Pasirkoja
C
45
5
0
15
5
4
5
6
9
32
30
5
4
5
8
3
4
G
14.4
22.9
8.2
29.1
Jalan Antanan
D
34
18
15
0
16
13
11
12
13
18
16
19
19
20
20
12
12
H
15.3
23.4
8.2
30.5
Jalan Baladewa Indah
E
48
10
5
16
0
3
5
4
6
34
32
8
7
4
9
4
9
Jalan Doktor Otten
F
45
10
4
13
3
0
1
2
5
31
28
9
8
7
16
1
9
I
15.6
8.2
8.2
15.6
Jalan Cihampelas
G
43
15
5
11
5
1
0
3
5
29
26
10
9
9
20
2
9
K
0.9
9.3
8.2
2
Jalan Sukajadi
H
46
12
6
12
4
2
3
0
2
31
28
11
10
8
16
4
9
L
17.3
23.4
8.2
32.5
Jalan Sirnagalih
I
47
15
9
13
6
5
5
2
0
31
29
10
12
10
9
6
14
M
17.6
23.8
8.2
33.2
Jalan Listrik 2
J
16
33
32
18
34
31
29
31
31
0
2
35
35
37
39
30
28
Jalan Jend. A. H. Nasution
K
19
31
30
16
32
28
26
28
29
2
0
33
33
35
37
28
25
N
18.6
25.4
8.2
35.8
Jalan Caringin
L
47
2
5
19
8
9
10
11
10
35
33
0
1
6
11
8
7
O
19.5
26.6
8.2
37.9
Jalan Babakan Ciparay
M
48
3
4
19
7
8
9
10
12
35
33
1
0
5
9
7
7
P
15
21.9
8.2
28.7
Jalan Holis
N
51
9
5
20
4
7
9
8
10
37
35
6
5
0
4
7
10
Jalan Raya Cibeureum
O
53
13
8
20
9
16
20
16
9
39
37
11
9
4
0
8
13
Q
13.8
20
8.2
25.6
Jalan Kebon Kawung
P
44
8
3
12
4
1
2
4
6
30
28
8
7
7
8
0
7
Jalan Buah Batu
Q
40
40
4
12
9
9
9
9
14
28
25
7
7
10
13
7
0
3.3 Penentuan Rute Kendaraan Berdasarkan matrik jarak dan matrik waktu tempuh, maka dapat ditentukan rute kendaraan dengan langkah-langkah sebagai berikut: 1. Menentukan node yang memiliki jarak terdekat dengan depot. Node J (Jln. Listrik 2) adalah jarak terdekat dari node, sehingga R1 = {A,J,A} 2. Perhitungan penghematan jarak dan waktu tempuh terhadap seluruh node untuk menentukan node sisipan antara node J (Jln. Listrik 2) ke node A (depot) yang disesuaikan dengan kapasitas angkut. a. Contoh untuk perhitungan penghematan jarak (Z11) pada rute 1: 1) Penghematan jarak di node (J,B) Jika jarak dari node J (Jln. Listrik 2) ke node B (Jln. Leuwipanjang) adalah 16,4 Km Jika jarak dari node B (Jln. Leuwipanjang) ke node A (depot) adalah 22,2 Km Jika jarak dari node J (Jln. Listrik 2) ke node A (depot) adalah 8,2 Km Maka (J,B) = d(J,B) + d(B,A) - d(J,A) = 16,4 Km + 22,2 Km - 8,2 Km = 30,4 Km 2) Penghematan jarak di node (J,C)
b. Contoh untuk perhitungan penghematan waktu tempuh (Z12) pada rute 1:: 1) Penghematan waktu tempuh di node (J,B) a) Jika waktu tempuh dari node J (Jln. Listrik 2) ke node B (Jln. Leuwipanjang) adalah 33 menit b) Jika waktu tempuh dari node B (Jln. Leuwipanjang) ke node A (depot) adalah 44 menit c) Jika waktu tempuh dari node J (Jln. Listrik 2) ke node A (depot) adalah 16 menit d) Waktu pelayanan adalah 5 menit Maka (J,B) = d(J,B) + waktu pelayanan + d(B,A) - d(J,A) = 33 menit + 5 + 44 menit - 16 menit = 66 menit 2) Penghematan waktu tempuh di node (J, C) a) Jika waktu tempuh dari node J (Jln. Listrik 2) ke node C (Jln.Terusan Pasirkoja) adalah 32 menit b) Jika waktu tempuh dari node C (Jln.Terusan Pasirkoja) ke node A (depot) adalah 45 menit c) Jika waktu tempuh dari node J (Jln. Listrik 2) ke node A (depot) adalah 16 menit d) Waktu pelayanan adalah 5 menit
Agus Purnomo – Jurusan Teknik Industri UNPAS
5
Maka (6,2) = d(J,C) + waktu pelayanan + d(C,A) - d(J,A) = 33 menit + 5 + 45 menit - 16 menit = 65 menit * Perhitungan yang diperoleh dimasukan ke dalam Tabel 5. Tabel 5. Penghematan Waktu Tempuh untuk Rute 1 (menit) i J
u
d(i,u ) d(u , A) d(i , A)
Z12
kapasitas maksimal angkut kendaraan adalah 2 Ton..
Tabel 6. Node Terbaik yg. disisipkan ke. dl Rute 1 i
u
J
B C
Z1 (i,u,j ) i (u ) j (u ) Z2 (i,u,j ) A 33.94 J -11.74 A 33.72 J -11.32
D
20.3
J
A
-3.2
E
36.8
J
A
-12.8 -10.78
B
33
44
16
66
32
45
16
65
F
33.28
J
A
C
G
32.51
J
A
-9.61
D
18
34
16
41
H
34.05
J
A
-10.65
E
34
48
16
71
I
17.66
J
A
-9.46
F
31
45
16
65
K
2.7
J
A
6.6
G
29
46
16
63
L
36.25
J
A
-12.85
H
31
47
16
66
M
37.02
J
A
-13.22
31
16
16
36
39.88
J
A
I
N
-14.48
O
42.19
J
A
-15.59
K
2
19
16
9
P
32.07
J
A
-10.17
L
35
47
16
70
Q
28.66
J
A
-8.66
M
35
48
16
71
N
37
51
16
77
O
39
53
16
81
P
30
44
16
62
Q
28
40
16
56
Perhitungan dalam menentukan node terbaik pada rute 1 sebagai berikut : a. Contoh perhitungan pada Z1 (i,u,j) 1. Z1(J,B) = ( 1 x Z11) + ( 2 x Z12) = (0,9 x 30,4) + (0,1 x 66) = 33,94 2. Z1(J,C) = ( 1 x Z11) + ( 2 x Z12) = (0,9x30,2) + (0,1x 65,8) = 33, 72 b. Contoh perhitungan pada Z2 (i,u,j) 1. Z2(J,B) = d(A,u) - Z1(J,B) = 22, 2 - 33,94 = -11,74 2. Z2(J,C) = d(A,u) - Z1(J,C) = 22,4 – 33,72 = -11,32 Perhitungan yang diperoleh dimasukan ke dalam Tabel 6. Menentukan posisi node terbaik di rute 1 yang akan disisipkan diantara node J (Jln. Listrik 2) ke node A (depot) adalah sebagai berikut : a) Mengambil nilai terkecil pada kolom Z1(i,u,j) Yang terpilih adalah node K (Jln. Jendral Abdul Haris Nasution), sehingga rute 1 adalah {J,K,A}. Demand node J adalah 0,12 Ton dan demand node K adalah 0,10 Ton dengan total demand 0,22 Ton. Dengan
b) Kapasitas angkut tersisa Karena kapasitas angkut tersisa maka sisipkan node berikutnya dengan mengambil nilai terbesar dengan berurutan pada kolom Z2(i,u,j) sampai kapasitas angkut tercukupi. 3.4 Rute, Waktu dan Ongkos Transportasi Hasil Perhitungan dengan metode Insertion Heuristic Hasil pengolahan menghasilkan 3 (tiga) rute sebagai berikut : Rute 1 dengan agen–agen : A,J,K,D,Q,P,H,F,A dengan A adalah depot (Rancaekek) diteruskan ke J adalah Jln. Listrik 2 diteruskan ke K adalah Jln. Jendral Abdul Haris Nasution diteruskan ke D adalah Jln. Antanan diteruskan ke Q adalah Jln. Buah Batu diteruskan ke P adalah Jln. Kebon Kawung diteruskan ke H adalah Jln. Sukajadi ke F adalah Jln. Doktor Otton kemudian kembali menuju A adalah depot (Rancaekek). Dengan waktu sebagai berikut diurutkan dalam tabel 6. Tabel 6. Waktu dan sisa kapasitas Pengiriman untuk rute 1
Agus Purnomo – Jurusan Teknik Industri UNPAS
6
Agen
PERMASALAHAN SOLUSI Jadwal Waktu Waktu Sisa Permintaan pengiriman yg. kedatangan keberangkatan Kapasitas (ton) ditentukan agen kendaraan kendaraan (ton)
A
PERMASALAHAN
Jadwal Waktu Waktu Sisa Permintaan pengiriman yg. kedatangan keberangkatan Kapasitas (ton) ditentukan agen kendaraan kendaraan (ton)
2:00
2
J
0,12
02:10 – 02:35
2:16
2:21
1,88
K
0,10
02:00 – 04:09
2:23
2:28
1,78
D
0,07
02:30 – 05:00
2:46
2:51
1,71
B
0,50
02:30 – 04:20
Q
79
02:05 – 05:15
3:03
3:08
0,92
E
0,48
P
0,28
02:00 – 03:14
3:12
3:17
0,64
L
0,10
H
0,15
02:00 – 05:00
3:21
3:26
0,49
N
F
0,37
02:00 – 06:00
3:28
3:33
0,12
O I
Rute 2 dengan agen–agen : A,G,M,C,A dimana dari A adalah depot (Rancaekek) diteruskan ke G adalah Jln. Cihampelas diteruskan ke M adalah Jln. Babakan Ciparay diteruskan ke C adalah Jln. Terusan Pasirkoja kemudian kembali menuju A adalah depot (Rancaekek). Dengan waktu sebagai berikut diurutkan dalam tabel 7. Tabel 7. Waktu dan sisa kapasitas Pengiriman untuk rute 2 PERMASALAHAN
Agen
SOLUSI
Jadwal Waktu Waktu Sisa Permintaan pengiriman yg. kedatangan keberangkatan Kapasitas (ton) ditentukan agen kendaraan kendaraan (ton)
A
2:00
2
G
1,65
02:30 – 06:00
2:43
2:48
0,35
M
0,20
02:30 – 05:11
2:57
3:02
0,15
C
0,15
02:00 – 05:00
3:06
3:11
0
Rute 3 dengan agen – agen atau titik drop A,B,E,L,N,O,I,A dimana dari A adalah depot (Rancaekek) diteruskan ke B adalah Jln.Leuwipanjang diteruskan ke E adalah Jln..Baladewa Indah diteruskan ke L adalah Jln. Caringin diteruskan ke N adalah Jln. Holis diteruskan ke O adalah Jln. Raya Cibeureum diteruskan ke I adalah Jln. Sinargalih kemudian kembali menuju A adalah depot (Rancaekek). Dengan waktu sebagai berikut diurutkan dalam tabel 8. Tabel 8. Waktu dan sisa kapasitas Pengiriman untuk rute 3
Agen
SOLUSI
A
2:00
2
2:44
2:49
1,50
02:00 – 05:00
2:59
3:04
1,02
02:20 – 05:10
3:12
3:17
0,92
0,26
02:30 – 05:00
3:23
3:28
0,66
0,28
02:00 – 04:20
3:32
3:37
0,38
0,14
02:00 – 04:45
3:46
4:01
0,24
3.5 Analisis Rute dan Ongkos Transportasi 3.5.1 Rute dan Ongkos Transportasi Perusahaan saat ini Berdasarkan data dari perusahan koran Harian Pagi Tribun Jabar rute pendistribusian koran digambarkan pada gambar 4, sedangkan uraian rutenya adalah sebagai berikut: Rute 1 dengan agen–agen : A,J,K,Q,B,L,A, dengan A = (Rancaekek) diteruskan ke J = Jln. Listrik 2 diteruskan ke K = Jln. Jendral Abdul Haris Nasution diteruskan ke Q = Jln. Buah Batu diteruskan ke B = Jln. Leuwipanjang diteruskan ke L = Jln. Caringin melalui (Tol Cileunyi – Rahayu) kembali menuju A = depot (Rancaekek). Dengan perhitungan Jarak = 8,2 ditambah 0,9 ditambah 12,6 ditambah 20 ditambah 1,1 ditambah (23,4 ditambah 5) hasilnya dengan jarak 71,2 Km. Untuk perhitungan waktu = 16 ditambah 2 ditambah 25 ditambah 40 ditambah 2 ditambah (47 ditambah 10) hasilnya = 142 menit Rute 2 dengan agen–agen : A,H,I,G,P,A dengan A = depot (Rancaekek) melalui (Tol Cileunyi – Bandung kulon) diteruskan ke I = Jln. Sinargalih diteruskan ke H = Jln. Sukajadi diteruskan ke G = Jln. Cihampelas diteruskan ke P = Jln. Kebon Kawung kembali menuju A = depot (Rancaekek). Dengan perhitungan jarak = (22,9 ditambah 7,2) ditambah 1 ditambah 2,5 ditambah 0,8 ditambah 21,9 hasilnya = 56,3 Km. Untuk perhitungan waktu adalah (46 ditambah 14,4) ditambah 2 ditambah 5 ditambah 43 hasilnya adalah 110,4 menit dibulatkan menjadi 110 menit Rute 3 dengan agen–agen : A,M,C,N,O,F,E,D,A dengan A = depot (Rancaekek) melalui (Tol Cileunyi - Pasteur) diteruskan ke M = Jln.
Agus Purnomo – Jurusan Teknik Industri UNPAS
7
Babakan Ciparay diteruskan ke C = Jln. Terusan Pasirkoja diteruskan ke N = Jln. Holis diteruskan ke O = Jln. Raya Cibeureum diteruskan ke F = Jln. Doktor Otton diteruskan ke E = Jln..Baladewa Indah diteruskan ke D = Jln. Antanan kembali menuju A = depot(Rancaekek). Dengan perhitungan jarak = (23,9 ditambah 4,6) ditambah 1,9 ditambah 2,7 ditambah 2 ditambah 3,9 ditambah 1,5 ditambah 8 ditambah 17,1 hasilnya = 65,6 Km. Untuk perhitungan waktu adalah (48 ditambah 8,1) ditambah 4 ditambah 5 ditambah 4 ditambah 8 ditambah 1 ditambah 3 ditambah 16 ditambah 34 hasilnya = 131,1 menit dibulatkan menjadi 132 menit.
H E
F
Rute 3 A,M,C,N,O,F,E,D,A
Jarak Tempuh/Km
71,2 Km
56,3 Km
65,6 Km
142 menit
110 menit
132 menit
demand
1,61 Ton
1,94 Ton
1,79 Ton
Biaya Tol
Rp.3.500,-
Rp. 4.000,-
Rp. 6.000,-
Hari Kerja
26 Hari
26 Hari
26 Hari
Fixed Cost
Rp.2.129.000,-
Rp.2.129.000,-
Rp.2.129.000,-
Variabel Cost/Km
Rp. 533,7,-
Rp. 533,7,-
Rp. 533,7,-
Rp. 3.120.485,44,- Rp.2.914.230,06,- Rp. 3.045.278,7,-
TOTAL 193,1 Km 5,34 Ton
Rp. 9.079.994,2,/Bulan
3.5.2
Rute dan Ongkos Transportasi Hasil Perhitungan dengan Metode Insertion Heuristic Rekap hasil perhitungan mengenai rute, jarak, waktu, demand dan ongkos untuk keseluruhan rute dengan menggunakan metode Insertion Heuristic disajikan pada tabel 10, sedangkan gambar rute pendistribusian untuk semua jalur disajikan pada gambar 5.
D G K P
N
Rute 2 A,H,I,G,P,A
Waktu Tempuh/mnt
Ongkos total
I
O
Rute 1 A,J,K,Q,B,L,A
J
C Q M L B
A
Tabel 9. Rekap Rute dan Ongkos Total untuk Setiap Jalur
KETERANGAN Rute 1 Rute 2 Rute 3
Gambar 4. Rute Pendistribusian Koran saat ini oleh Perusahaan Rekap mengenai rute, jarak, waktu, demand dan ongkos untuk keseluruhan rute pendistribusian Koran saat ini disajikan pada tabel 9.
Rute 1
Rute 2
Rute 3
A,J,K,D,Q,P,H,F,A
A,G,M,C,A
A,B,E,L,N,O,I,A
Jarak Tempuh/Km
50,4 Km
50,4 Km
64,5 Km
TOTAL 165,3 Km
Waktu Tempuh/mnt
102 menit
102 menit
123 menit
327 menit
Demand
1,88 Ton
2 Ton
1,76 Ton
5,64 Ton
Hari Kerja
26 Hari
26 Hari
26 Hari
Fixed Cost
Rp.2.129.000,-
Rp.2.129.000,-
Rp.2.129.000,-
Rp. 533,7,-
Rp. 533,7,-
Rp. 533,7,-
Variabel Cost/Km
Ongkos total
Rp.2.828.360,48,- Rp.2.828.360,48,-
Rp.3.024.014,9,-
Rp.8.680.735,78,/Bulan
Tabel 9. Rekap Rute dan Ongkos Total untuk Setiap Jalur pendistribusian Koran saat ini
Agus Purnomo – Jurusan Teknik Industri UNPAS
8
I H
D
O E
F
G K P
N
J
C Q M L B
A KETERANGAN Rute 1 Rute 2 Rute 3
Gambar 5. Rute Pendistribusian Koran Hasil Perhitungan dengan metode Insertion Heuristic 3.5.3 Analisis Penghematan Ongkos Total Perbandingan ongkos total antara rute distribusi perusahaan saat ini dengan rute hasil metode Insertion Heuristic, serta penghematannya disajikan pada tabel 10. Tabel 5.7 Penghematan Ongkos Transportasi setiap Rute dan Total Kondisi Saat ini Dengan Metode Insertion Heuristic
Rute 1
Rute 2
Rute 3
Total
Rp. 3.120.485,44,-
Rp.2.914.230,06,- Rp. 3.045.278,7,- Rp. 9.079.994,2,-/Bulan
Rp.2.828.360,48,-
Rp.2.828.360,48,- Rp.3.024.014,9,-
Rp.8.680.735,78,-/Bulan
Rp.85.869,58,-
Rp. 399.258.34,-/Bulan
Penghematan ongkos Rp.292.066,7,% Penghematan ongkos 10.33%
3.04%
Rp.21.263,8,0.70%
4.60%
Persentase penghematan terbesar terdapat pada Rute 1 yaitu 10,33% atau sebesar Rp. 292.066,7,- per bulan, sementara jika dilihat secara total maka penghematan yang terjadi untuk semua rute adalah 4,60% atau Rp. 399.258,34,- per bulan. IV. SIMPULAN DAN SARAN 4.1. Simpulan Penelitian Permasalahan pendistribusi Harian Pagi Tribun Jabar yang merupakan persoalan The Vehicle Routing Problem With Time Windows (VRPTW) dapat diselesaikan dengan menggunakan Metode Insertion Heuristic sehingga diperoleh 3 rute pendistribusian,
yaitu rute pertama : A,J,K,D,Q,P,H,F,A dengan jarak tempuh 50,4 Km, waktu tempuh 102 menit dengan alokasi kapasitas kendaraan 1,88 ton; rute kedua A,G,M,C,A dengan jarak tempuh 50,4 Km, waktu tempuh 102 menit dengan alokasi kapasitas kendaraan sebesar 2 ton; rute ketiga A,B,E,L,N,O,I,A dengan jarak tempuh 64,5 Km, waktu tempuh 123 menit dengan alokasi kapasitas kendaraan sebesar 1,76 ton. Ongkos total transportasi yang minimum sebesar Rp.8.680.735,78,-/bulan, dan bila dibandingkan dengan ongkos total transportasi perusahaan saat ini yang sebesar Rp. 9.079.994,2,/Bulan, maka terdapat penghematan sebesar Rp. 399.258.34,-/Bulan atau 4.60%. 4.2. Saran Manager Sirkulasi sebaiknya melakukan pengawasan yang baik terhadap para pengemudi kendaraan yang melakukan pendistribusian koran agar sesuai dengan rute hasil penelitian ini, agar dapat meningkatkan pelayanan pada agen-agen dan meminimasi total ongkos transportasi. V. DAFTAR PUSTAKA [1] Lenstra, J. K. and Rinnooy Kan, A.H.G., (1981), Complexity of vehicle and scheduling problems. Networks, 11, p.221-227. [2] Solomon, M. M. (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35, p.254-265. [3] Desrosiers, J., J., Dumas, Y., Solomon, M. and SOUMIS, F. (1995) Time constrained routing and scheduling. Network Routing. In: Handbooks in Operations Research and Management Science, eds. M.Ball, T.L.Magnanti, C.L.Monna, G.L.Nemhauser, North Holland, Amsterdam. [4] Kolen, A.W.J., Rinnooy, A.H.G. and Trienekens, H.W.J.M. (1987) Vehicle routing with time windows. Operations Research, 35, p.266-273. [5] Cunha, C.B. and Swait, J.D. (2000) New dominance criteria for the generalized permanent labelling algorithm for the shortest path problem with time windows on dense graphs. International Transactions in Operational Research, v.7, p.139-157.
Agus Purnomo – Jurusan Teknik Industri UNPAS
9
