4
II TINJAUAN PUSTAKA Untuk memahami permasalahan yang berhubungan dengan penentuan rute optimal kendaraan dalam mendistribusikan barang serta menentukan solusinya maka diperlukan beberapa konsep teori berikut:
2.1 Graf Definisi 1 (Graf , Graf Berarah dan Graf Takberarah) Suatu graf G adalah pasangan terurut (V,A) dengan V merupakan himpunan takkosong dan berhingga yang anggota-anggotanya disebut simpul (node/vertex) dan A merupakan himpunan berhingga garis yang menghubungkan simpul-simpul anggota V yang disebut dengan sisi (arc atau edge). Sisi yang menghubungkan simpul i dengan simpul j dinyatakan dengan {i,j}. Dalam suatu graf, jika sisi yang menghubungkan simpul-simpulnya berarah maka graf tersebut dinamakan graf berarah (directed graph/digraf). Jika semua sisi yang menghubungkan simpulsimpulnya tidak berarah maka dinamakan graf takberarah (undirected graph) (Foulds 1992).
2.2 Linear Programming Linear programming (LP) atau pemrograman linear adalah suatu masalah optimasi yang memenuhi ketentuan-ketentuan: 1) tujuan
dari
masalah
tersebut
adalah
untuk
memaksimumkan
atau
meminimumkan suatu fungsi linear dari sejumlah variabel keputusan. Fungsi yang akan dimaksimumkan atau diminimumkan itu disebut fungsi objektif, 2) nilai-nilai variabel keputusannya harus memenuhi semua himpunan kendala; setiap kendala harus berupa persamaan linear atau pertidaksamaan linear, 3) ada pembatasan tanda untuk setiap variabel. Untuk sembarang variabel pembatasan tanda menentukan tidak dibatasi.
harus taknegatif
,
atau tandanya (Winston 2004)
5
Definisi 2 (Bentuk standar suatu LP) Suatu linear programming didefinisikan mempunyai bentuk standar sebagai berikut: Minimumkan terhadap (2.1) dengan x dan c merupakan vektor yang berukuran n, vektor b berukuran m; sedangkan A merupakan matriks yang berukuran m × n yang disebut juga dengan matriks kendala. ( Nash & Sofer 1996) Model linear programming (LP) menyajikan bentuk matematis dari fungsi objektif dan pembatasnya yang berupa fungsi linear. Pada tulisan ini suatu linear programming (LP) memiliki bentuk standar sebagai berikut (Taha 2003):
dengan cj, aij dan bi merupakan konstanta yang nilainya diketahui.
2.2.1 Solusi Suatu Linear Programming (LP) Untuk menyelesaikan suatu masalah linear programming (LP) agar diperoleh solusi yang optimum dapat dilakukan dengan banyak metode. Salah
6
satu metode yang paling umum digunakan adalah metode simpleks yang mulai dikembangkan oleh Dantzig tahun 1947. Metode ini merupakan metode iteratif untuk menyelesaikan masalah linear programming dalam bentuk standar. Pada linear programming (2.1), vektor x yang memenuhi kendala Ax = b disebut sebagai solusi dari linear programming (2.1). Misalkan matriks A dapat dinyatakan sebagai A = (B N), dengan B adalah matriks berukuran m × m yang merupakan matriks yang elemennya berupa koefisien variabel basis dan N merupakan matriks yang elemennya berupa koefisien variabel nonbasis pada matriks kendala. Matriks B disebut matriks basis untuk linear programming.
2.3 Integer Linear Programming Sebuah model pengoptimalan disebut model integer linear programming (ILP) atau disebut juga integer programming (IP) jika variabel-variabel keputusan yang digunakan berupa bilangan bulat (integer). Jika semua variabel keputusan harus berupa integer maka model tersebut dinamakan pure integer programming, tetapi jika hanya sebagian yang harus integer maka disebut mixed integer programming. Sedangkan integer programming yang semua variabelnya harus bernilai 0 atau 1 disebut 0-1 integer programming. (Rardin 1998) Secara sederhana model linear programming (LP) dengan pembatas tambahan
berupa
variabelnya
bernilai
integer
disebut
sebagai
integer
programming (IP). Dalam tulisan ini suatu integer programming (IP) memiliki bentuk standar sebagai berikut:
dengan cj, aij dan bi merupakan konstanta yang nilainya diketahui (Taha 1975).
7
Definisi 3 (Linear Programming Relaksasi) Linear programming relaksasi dari suatu integer programming merupakan linear programming yang diperoleh dari integer programming tersebut dengan menghilangkan kendala bilangan bulat atau kendala 0-1 pada variabelnya. (Winston 1995) 2.4 Metode Branch and Bound Untuk memperoleh solusi optimal dari masalah integer programming dapat dipecahkan dengan metode branch and bound. Prinsip dasar dari metode branch and bound adalah memecah daerah fisibel dari masalah LP-relaksasi dengan cara membuat subproblem baru sehingga masalah IP dapat terpecahkan. Daerah fisibel suatu LP adalah daerah yang memuat titik-titik yang dapat memenuhi semua kendala linear masalah LP (Taha 2003). Setiap subproblem diukur dengan tiga cara sebagai berikut: 1. Batas dari subproblem ≤ solusi optimum yang didapat saat ini (z*) 2. LP-relaksasi tidak memiliki solusi fisibel. 3. Solusi optimum dari LP-relaksasi berupa integer. Jika solusi ini lebih baik dari solusi optimum yang didapat sebelumnya maka solusi ini menjadi solusi optimum yang baru dan cara pertama digunakan kembali untuk semua subproblem dengan nilai z* baru yang lebih besar. Adapun langkah-langkah metode branch and bound untuk masalah pemaksimuman, menurut Taha (2003) adalah sebagai berikut: Ditetapkan batas bawah awal z =
untuk nilai optimum dari fungsi objektif ILP
dan tetapkan i = 0. Langkah 1 (pem-fathom-an dan pembatasan) Dipilih LPi sebagai subproblem untuk diteliti. Kemudian LPi diselesaikan dan LPi di-fathom-kan jika memenuhi salah satu dari ketiga kondisi berikut: 1. Nilai optimum z dari LPi tidak dapat menghasilkan nilai objektif yang lebih baik daripada batas bawah sekarang. 2. LPi menghasilkan solusi integer fisibel yang lebih baik daripada batas bawah sekarang. 3. LPi tidak memiliki solusi yang fisibel.
8
Dalam hal ini akan muncul dua kasus yaitu: 1. Jika LPi di-fathom-kan dan solusi yang diperoleh lebih baik daripada batas bawah sekarang, maka batas bawah z diperbaharui. Jika semua subproblem di-fathom-kan maka proses dihentikan. ILP optimum dihubungkan dengan batas bawah sekarang, bila ada. Jika sebaliknya, dipilih i = i + 1, dan ulangi Langkah 1. 2. Jika LPi tidak di-fathom-kan, proses dilanjutkan ke Langkah 2 untuk melakukan pencabangan pada LPi. Langkah 2 (pencabangan) Dipilih sebarang variabel xj yang nilai optimumnya adalah xj* yang tidak memenuhi batasan integer dalam solusi LPi. Bidang [xj*] < xj < [xj*] + 1 (dengan [v] sebagai integer terbesar yang ≤ v) dieliminasi dengan membuat dua subproblem LP yang sesuai dengan xj ≤ [xj*] dan xj ≥ [xj*] + 1. Kemudian ditentukan i = i + 1 , dan kembali pada Langkah 1. Untuk memudahkan pemahaman tentang metode branch and bound diberikan contoh sebagai berikut: Contoh: Misalkan diberikan masalah integer sebagai berikut:
Solusi optimum dari LP-relaksasi contoh tersebut (LP0) adalah z = 4.85, x1 = 2.75, dan x2 = 2.1 (lihat Lampiran 1a). Daerah fisibel LP-relaksasi dari masalah di atas dapat dilihat pada Gambar 1. Menurut metode branch and bound, karena solusi optimum LP-relaksasi tersebut tidak memenuhi syarat integer, maka harus dibuat subproblem baru. Dipilih sembarang variabel xi optimum yang tidak memenuhi syarat integer, misalnya x1 = 2.75, sehingga bidang 2 < x1 < 3 bukan daerah fisibel bagi masalah IP dan harus dipisahkan. Ruang LP0 semula diganti dengan dua ruang LP yakni LP1 dan LP2 dengan ruang solusi yang didefinisikan sebagai berikut: -
Ruang LP1= ruang LP0 + kendala (x1 ≤ 2)
9
-
Ruang LP2= ruang LP0 + kendala (x1 ≥ 3)
Ruang solusi dari LP1 dan LP2 dapat dilihat pada Gambar 2. X2
5• 4•
Solusi optimum LP0 z=4.85, x1=2.75, x2=2.1
3• 2• 1•1 -2•
• -1
•1
0
•2
•
•
3
4
•5
•
6
•7
•8
X1
Gambar 1 Daerah fisibel LP. X2
5•
LP1
LP2
4• 3• 2• 1•
•
-2
•
-1
0
•
• 1
2•
•
3
• 4
• 5
•
6
•7
•
8
X1
Gambar 2 Grafik ruang LP1 dan LP2. Dari gambar di atas terlihat bahwa batasan baru LP1 dan LP2 tidak dapat dipenuhi secara bersamaan, sehingga LP1 dan LP2 harus dibuat menjadi dua buah LP yang berbeda. Kemudian masalah LP1 dan LP2 diselesaikan satu per satu. Misalkan LP1 dipilih pertama kali untuk diselesaikan, sehingga permasalahannya menjadi:
10
Diperoleh solusi optimum untuk masalah LP di atas, yaitu z = 4.4 , x1 = 2, dan x2 = 2.4 (lihat Lampiran 1b). Karena solusi optimum LP1 bukan solusi optimum integer, maka LP1 tidak di-fathom-kan, sehingga dilakukan pencabangan di LP1 menjadi 2 subproblem, yakni LP3 dan LP4. Ruang solusi LP3 dan LP4 didefinisikan sebagai berikut: - Ruang LP3 = ruang LP0 + kendala (x1 ≤ 2) + kendala (x2 ≤ 2) = ruang LP1 + kendala (x2 ≤ 2) - Ruang LP4 = ruang LP0 + kendala (x1 ≤ 2) + kendala (x2 ≥ 3) = ruang LP1 + kendala (x2 ≥ 3) Solusi optimum dari LP3 adalah z = 4 dengan x1 = 2 dan x2 = 2 (lihat Lampiran 1d). Karena solusi LP3 integer, maka LP3 di-fathom-kan. Nilai z = 4 sebagai calon batas bawah solusi optimum IP. Solusi optimum dari LP4 adalah z = 3.5 dengan x1 = 0.5 dan x2 = 3 (lihat Lampiran 1e). Karena solusi LP4 (z = 3.5 dengan x1 = 0.5 dan x2 = 3) tidak memenuhi syarat integer maka semestinya LP4 tidak di-fathom-kan. Namun karena nilai z = 3.5 tidak lebih baik dari batas bawah sebelumnya (z = 4 dengan x1 = 2 dan x2 = 2) maka LP4 di-fathom-kan, sehingga solusi LP4 bukan solusi optimum IP. Calon batas bawah untuk solusi optimum IP adalah z = 4. Selanjutnya diselesaikan LP2, dan dari penghitungan diperoleh solusi optimum LP2 adalah z = 4.80 dengan x1 = 3 dan x2 = 1.8 (lihat Lampiran 1c). Seperti yang diketahui bahwa dari penyelesaian LP0 sudah diperoleh nilai optimum yaitu z = 4.85 artinya nilai z tidak mungkin akan lebih besar dari 4.85 dan tidak mungkin akan lebih baik dari calon batas bawah sebelumnya (z = 4). Karena semua variabel dari fungsi objektif pada LP3 telah memenuhi syarat integer yaitu z = 4 dengan x1 = 2 dan x2 = 2 maka tidak mungkin LP2 akan menghasilkan solusi integer yang lebih baik, sehingga LP2 di-fathom-kan dan tidak perlu dilakukan pencabangan. Karena semua subproblem sudah di-fathomkan, maka pencabangan berhenti, sehingga diperoleh solusi optimumnya dari penyelesaian LP3 yaitu z = 4 dengan x1 = 2 dan x2 = 2.
11
Penggunaan metode branch and bound untuk menyelesaikan masalah IP pada contoh di atas dapat dilihat pada Gambar 3. Penghitungan nilai-nilai variabel dilakukan dengan bantuan software LINGO 8.0. LP0 z = 4.85, x1 =2.75, dan x2 =2.1
x1 ≤ 2
x1 ≥ 3
LP1
LP2 z = 4.8, x1 =3, dan x2 =1.8
z = 4.4, x1 =2, dan x2 =2.4 x2 ≤ 2
x2 ≥ 3
LP3
LP4
z = 4, x1 =2, dan x2 =2 batas bawah (optimal)
z = 3.5, x1 =0.5, dan x2 =3
Gambar 3 Pencabangan dengan metode branch and bound untuk menemukan solusi IP. 2.5 Traveling Salesman Problem (TSP) Traveling Salesman Problem (TSP) merupakan suatu masalah optimasi untuk mencari rute terpendek bagi seorang salesman yang menjajakan produknya dengan melakukan tour yang dimulai dari tempat asalnya menuju n kota tepat satu kali
kemudian
kembali
ke
tempat
asalnya.
Tujuannya
adalah
untuk
meminimumkan biaya operasional salesman yang dikeluarkan oleh perusahaan. Rute kendaraan pada masalah TSP merupakan cycle Hamilton yaitu path tertutup yang memuat semua node pada graf yang mempresentasikan jaringan jalan yang menghubungkan tiap kota. Tujuannya adalah menentukan rute perjalanan yang fisibel sedemikian sehingga jarak tempuh yang melalui rute tersebut minimum. Menurut Garfinkel dan Nemhauser (1972) secara matematis TSP dapat dinyatakan sebagai suatu graf berarah G=(V,A) dengan V={0,1, ..., n} menyatakan himpunan node yang menunjukkan lokasi kota dan A={(i, j) | i, j V, i ≠ j} merupakan himpunan sisi berarah (arc) yang menyatakan jalan penghubung tiap kota.
Node 0 menyatakan kota asal/depot yang merupakan tempat seorang
12
salesman memulai perjalanan. Misalkan
adalah jarak tempuh (biaya
perjalanan) dari kota i ke kota j dan jika variabel keputusannya adalah:
maka TSP dapat diformulasikan secara matematis sebagai berikut:
dengan kendala:
Persamaan (2.21) merupakan fungsi tujuannya yaitu meminimumkan total jarak tempuh (biaya perjalanan).
Kendala (2.22) dan (2.23) menggambarkan
bahwa salesman mendatangi dan meninggalkan setiap kota tepat satu kali, sedangkan kendala (2.24) memastikan bahwa tidak terdapat subrute dan kendala (2.25) menjamin bahwa xij merupakan integer biner. Contoh solusi dari TSP dapat dilihat pada Gambar 4.
Rute Kota Depot
Gambar 4 Contoh penyelesaian TSP.
13
2.6 Vehicle Routing Problem (VRP) Kallehauge et al. (2001) mendefinisikan permasalahan m-TSP sebagai salah satu variasi dari TSP, di mana terdapat m salesman yang mengunjungi sejumlah kota dan tiap kota hanya dapat dikunjungi oleh tepat satu salesman saja. Tiap salesman berawal dari suatu depot dan pada akhir perjalanannya juga harus kembali ke depot tersebut. Permasalahan m-TSP ini dikenal sebagai Vehicle Routing Problem (VRP). Jadi VRP berkaitan dengan penentuan rute optimal untuk permasalahan yang melibatkan lebih dari satu kendaraan (vehicle) dengan kapasitas tertentu untuk melayani sejumlah konsumen sesuai dengan permintaannya masing-masing. Dalam masalah VRP ini, setiap kota diasosiasikan sebagai lokasi konsumen dan tiap kendaraan yang digunakan untuk mengunjungi sejumlah konsumen memiliki kapasitas tertentu. Total jumlah permintaan pelanggan dalam suatu rute tidak melebihi kapasitas kendaraan yang ditugasi melayani rute tersebut dan setiap pelanggan dikunjungi hanya satu kali oleh satu kendaraan. Pada masalah VRP juga terdapat suatu depot di mana tiap kendaraan harus berangkat dan kembali ke depot itu. Permasalahan VRP bertujuan meminimalkan total jarak tempuh kendaraan atau total biaya dari setiap rute perjalanan, selain itu bisa juga bertujuan meminimalkan banyaknya kendaraan yang digunakan (m). Sebagai contoh, penyelesaian masalah VRP dengan satu depot ditunjukkan dalam gambar berikut:
Pelanggan
Depot
Rute
Gambar 5 Contoh penyelesaian VRP satu depot dengan 3 rute.
14
Permasalahan VRP yang dituliskan oleh Toth and Vigo (2002) menjelaskan bahwa VRP adalah masalah penentuan rute kendaraan dalam mendistribusikan barang dari tempat produksi yang dinamakan depot ke konsumen dengan tujuan meminimumkankan total jarak tempuh kendaraan. Untuk mencapai tujuan tersebut perlu diperhatikan beberapa batasan yang harus dipenuhi yaitu setiap kendaraan yang akan mendistribusikan barang ke konsumen harus memulai rute perjalanan dari tempat produksi (depot), setiap pelanggan hanya boleh dilayani satu kali oleh satu kendaraan, setiap pelanggan mempunyai permintaan yang harus dipenuhi dan diasumsikan permintaaan tersebut sudah diketahui sebelumnya. Setiap kendaraan memiliki batasan kapasitas tertentu artinya setiap kendaraan akan melayani pelanggan sesuai dengan kapasitasnya. Selanjutnya juga harus dipenuhi bahwa tidak terdapat subrute untuk setiap kendaraan. Menurut Toth and Vigo (2002), secara matematis VRP dapat dinyatakan sebagai suatu digraf G=(V, A) dengan V={0,1,..., n} adalah himpunan simpul yang menunjukkan lokasi pelanggan dan A={(i, j) | i, j V, i ≠ j} yaitu himpunan sisi berarah yang menyatakan jalan penghubung antarlokasi pelanggan. Simpul 0 menunjukkan depot, yaitu tempat menyimpan kendaraan yang digunakan untuk distribusi dan merupakan tempat dimulainya suatu rute kendaraan. Banyaknya kendaraan yang tersedia di depot adalah K dengan kapasitas kendaraan ke-k adalah Ck. Setiap pelanggan i memiliki permintaan sebanyak di. Toth and Vigo (2002) memformulasikan VRP dalam bentuk pemrograman linear integer dengan tujuan meminimalkan total biaya atau total jarak tempuh dari rute perjalanan pendistribusian barang/jasa adalah sebagai berikut:
dengan kendala:
Kendala ini untuk memastikan bahwa setiap konsumen dikunjungi tepat satu kali oleh satu kendaraan.
15
Batasan tersebut untuk menjamin bahwa terdapat K kendaraan yang beroperasi yang memulai rute dari depot.
Batasan ini memastikan bahwa setiap konsumen akan dikunjungi oleh kendaraan yang sudah dijadwalkan untuk konsumen tersebut.
Kendala tersebut menjamin bahwa total permintaan konsumen dalam setiap rute tidak melebihi kapasitas kendaraan.
Kendala ini memastikan bahwa tidak terdapat subrute pada formulasi yang ada.
Batasan ini memastikan bahwa variabel keputusan
merupakan integer
biner.
Batasan ini menjamin variabel keputusan
merupakan integer biner.
Dengan variabel keputusan:
dengan: V = himpunan node A = himpunan sisi berarah (arc), cij = jarak/biaya perjalanan dari konsumen i ke konsumen j di = jumlah permintaan konsumen i Ck = kapasitas kendaraan ke- k K = banyaknya kendaraan yang tersedia
16
Permasalahan VRP yang dikemukakan oleh Kallehauge et al. (2001) adalah menyangkut masalah distribusi barang dari tempat produksi (depot) ke sejumlah konsumen yang tersebar di sejumlah tempat. Tujuannya adalah untuk meminimalkan total jarak tempuh (total biaya) dari rute perjalanan kendaraan dalam mendistribusikan barang. Rute yang dibentuk harus memenuhi batasanbatasan yaitu setiap pelanggan hanya dikunjungi satu kali oleh satu kendaraan, semua pelanggan harus dilayani sesuai dengan permintaannya masing-masing yang diketahui sebelumnya. Kendaraan yang digunakan adalah homogen dan memiliki batasan kapasitas tertentu sehingga rute yang dilalui tidak melebihi kapasitasnya. Setiap rute kendaraan berawal dari depot dan pada akhirnya juga harus kembali ke depot. Secara matematis Kallehauge et al. (2001) mendefinisikan VRP sebagai suatu digraf G=(N,A), dengan N merupakan simpul yang terdiri atas gabungan himpunan pelanggan C dan depot. Himpunan C berupa simpul 1 sampai n sedangkan simpul depot adalah 0 dan n+1. A adalah himpunan sisi berarah yaitu penghubung antarsimpul yang merupakan jaringan jalan yang digunakan oleh kendaraan. Semua rute berawal dari simpul 0 dan berakhir di impul n+1. Himpunan kendaraan V merupakan kumpulan kendaraan yang homogen dengan kapasitas q. Setiap pelanggan atau simpul i untuk setiap i anggota C memiliki permintaan sebesar di, sehingga panjang rute yang dilalui oleh setiap kendaraan dibatasi oleh kapasitas kendaraan. Setiap sisi (i,j) pada graf memiliki jarak tempuh cij yaitu jarak dari simpul i ke simpul j dan diasumsikan jarak tempuh cij=cji. Tujuannya adalah menentukan himpunan rute dengan total jarak tempuh atau biaya perjalanan yang minimum dengan syarat setiap rute berawal di simpul 0 dan berakhir di simpul n+1, setiap pelanggan dilayani tepat satu kali oleh satu kendaraan dan memenuhi kendala kapasitas kendaraan. Kallehauge et al. (2001) memodelkan masalah VRP tersebut ke dalam model matematis sebagai berikut:
dengan kendala-kendala:
17
Batasan ini menjamin bahwa tiap pelanggan hanya dapat dikunjungi tepat satu kali oleh satu kendaraan.
Batasan tersebut untuk memastikan bahwa total jumlah permintaan pelanggan dalam satu rute tidak melebihi kapasitas kendaraan.
Batasan tersebut menjamin bahwa setiap kendaraan memulai rute perjalanan dari depot.
Batasan ini memastikan bahwa setiap kendaraan yang mengunjungi suatu pelanggan, setelah selesai melayani akan meninggalkan pelanggan tersebut.
Kendala tersebut memastikan bahwa setiap rute perjalanan kendaraan berakhir di depot.
Batasan variabel keputusan
merupakan integer biner
Dengan variabel keputusan:
dengan: V = himpunan kendaraan dengan kapasitas yang identik C = himpunan konsumen/pelanggan N = himpunan node/vertex (simpul), {0,1,...,n+1} A = himpunan sisi berarah (arc), cij = jarak/biaya perjalanan dari konsumen i ke konsumen j di = total jumlah permintaan konsumen i q = kapasitas kendaraan Formulasi model matematis yang dibuat oleh Kallehauge et al. dan Toth &Vigo mempunyai tujuan yang sama yaitu meminimumkan total jarak
18
tempuh/biaya dari setiap rute perjalanan. Perbedaannya adalah Toth &Vigo hanya memperhitungkan biaya perjalanan untuk perjalanan awal dari depot, kemudian mengunjungi semua konsumen, tanpa memperhitungkan perjalanan kembali ke depot
pada
akhir
perjalanan
tersebut;
sedangkan
Kallehauge
et
al.
memperhitungkan biaya perjalanan untuk perjalanan awal dari depot, kemudian mengunjungi semua konsumen dan perjalanan kembali ke depot. 2.7 Capacitated Vehicle Routing Problem (CVRP) Capacitated Vehicle Routing Problem (CVRP) merupakan salah satu variasi dari masalah VRP dengan penambahan kendala kapasitas kendaraan yang identik. Setiap kendaraan yang melayani konsumen disyaratkan memiliki batasan kapasitas sehingga banyaknya konsumen yang dilayani oleh setiap kendaraan dalam satu rute bergantung pada kapasitas kendaraan. Permasalahan CVRP bertujuan meminimumkan total jarak tempuh rute perjalanan kendaraan dalam mendistribusikan barang dari tempat produksi yang dinamakan dengan depot ke sejumlah konsumen. Menurut Kara et al. (2004) masalah CVRP adalah masalah pengoptimalan jarak tempuh perjalanan kendaraan dalam pendistribusian barang dari tempat poduksi (depot) ke sejumlah agen pelanggan sehingga menghasilkan rute dengan total jarak tempuh yang minimum. Penentuan rute kendaraan tersebut harus memperhatikan beberapa batasan yaitu setiap kendaraan harus memulai rute perjalanan dari depot
dan setelah melayani sejumlah konsumen juga harus
kembali ke depot. Setiap konsumen hanya dilayani tepat satu kali oleh satu kendaraan. Terdapat sejumlah kendaraan di depot dengan kapasitas yang identik yang digunakan untuk melayani konsumen. Kendaraan-kendaraan tersebut memiliki kapasitas tertentu sehingga panjang rute yang dilalui oleh setiap kendaraan dalam melayani setiap konsumen sesuai dengan kapasitasnya. Setiap rute kendaraan tidak memiliki subrute sehingga rute yang terbentuk adalah sebanyak kendaraan yang dioperasikan. Kara et al. (2004) mendefinisikan Capacitated Vehicle Routing Problem (CVRP) sebagai suatu graf berarah G=(N,A) dengan himpunan simpul (vertex),
adalah
menyatakan depot yaitu tempat kendaraan memulai
dan mengakhiri rute perjalanan dan
menyatakan konsumen (C).
19
Sedangkan
adalah himpunan sisi berarah (arc)
yang merupakan himpunan sisi yang menghubungkan antarsimpul. Setiap simpul memiliki permintaan (demand) sebesar
dengan
adalah integer
positif. Himpunan V={1,2,...,K} merupakan kumpulan kendaraan yang homogen dengan kapasitas yang identik yaitu Q, sehingga panjang setiap rute dibatasi oleh kapasitas kendaraan. Setiap arc
memiliki jarak tempuh
yaitu jarak dari
simpul i ke simpul j. Jarak perjalanan ini diasumsikan simetrik yaitu
dan
. Permasalahan dari CVRP adalah menentukan himpunan dari K rute kendaraan yang memenuhi kondisi berikut: (1) setiap rute berawal dan berakhir di depot, (2) setiap konsumen harus dilayani tepat satu kali oleh satu kendaraan, (3) total permintaan konsumen dari setip rute tidak melebihi kapasitas kendaraan, dan (4) total jarak dari semua rute diminimumkan. Permasalahan
tersebut
kemudian
diformulasikan
ke
dalam
model
matematika dengan tujuan meminimumkan total jarak tempuh perjalanan kendaraan. Variabel
adalah variabel keputusan yang bernilai 1 jika arc
merupakan solusi dari masalah CVRP dan bernilai 0 jika bukan solusi, dan variabel
merupakan integer yang dihubungkan dengan setiap konsumen
. Variabel keputusan
hanya akan terdefinisi jika
.
Adapun formulasinya adalah sebagai berikut:
dengan kendala
Batasan ini memastikan bahwa tiap pelanggan hanya dikunjungi tepat satu kali oleh satu kendaraan.
Batasan tersebut menjamin bahwa setiap rute perjalanan kendaraan berawal dari depot.
20
Batasan bahwa setiap rute perjalanan kendaraan berakhir di depot.
Batasan ini memastikan bahwa tidak terdapat subrute pada setiap rute yang terbentuk. Variabel keputusan
hanya akan terdefinisi jika
Jika
maka kendala (2.46) tidak mengikat, sehingga
dan
Sedangkan jika
maka kendala tersebut menunjukkan bahwa
sehingga
batasan subtour elimination terpenuhi.
Variabel keputusan
merupakan integer biner
Variabel keputusannya adalah:
dengan: V = {1,...,K} = himpunan kendaraan dengan kapasitas yang identik K = banyaknya kendaraan yang digunakan N = himpunan node (simpul) C = himpunan konsumen/pelanggan A = himpunan sisi berarah (arc), cij = jarak/biaya perjalanan dari konsumen i ke konsumen j di = total jumlah permintaan konsumen i = kapasitas kendaraan uik = muatan kendaraan ke- k setelah mengunjungi konsumen ke- i Formulasi model matematis CVRP Kara et al. (2004) tersebut pada intinya menekankan pada batasan subtour elimination yaitu mengeliminasi subtour supaya tidak terdapat subrute pada rute-rute yang terbentuk yang dikaitkan
21
dengan batasan kapasitas kendaraan. Variabel keputusan hanya akan terdefinisi jika jumlah permintaan konsumen i dan konsumen j tidak melebihi kapasitas kendaraan.
