4

BAB II

LANDASAN TEORI

2.1 Transportasi

Pengertian transportasi adalah kegiatan pemindahan barang (muatan) dan

penumpang dari suatau tempat lain. Transportasi adalah ilmu yang mempunyai banyak

kaitannya dengan ilmu-ilmu lain seperti, manajemen, pemasaran, pembangunan,

ekonomi, UU dan kebijaksanaan pemerintahan.

Chopra dan meindl (2004) menerangkan bahwa unsur – unsur transportasi

meliputi beberapa unsur yaitu berupa muatan yang diangkat, tersedia kendaraan

sebagai alat angkut, ada jalanan yang dapat dilalui, ada terminal asal serta terminal

tujuan, sumber daya manusia dan organisasi atau manajemen yang menggerakkan

manajemen tersebut. Transportasi menyebabkan nilai barang menjadi lebih tinggi di

tempat tujuan dari pada di tempat asal, dan nilai ini lebih besar dari pada biaya yang

dikeluarkan untuk pengangkutan. Nilai atau kegunaan yang diberikan oleh transportasi

adalah berupa kegunaan tempat (place utility). Kedua kegunaan diperoleh jika barang

telah diangkut ke tempat dimana nilainya lebih tinggi dan dapat dimanfaatkan tepat

pada waktunya.

Menurut Nasution (2004) transportasi diartikan sebagai pemindahan barang

dan manusia dari tempat asal ke tempat tujuan. Proses transportasi merupakan gerakan

dari tempat asal, dari mana kegiatan dimulai, ketempat tujuan kemana kegiatan

pengangkutan diakhiri. Transportasi merupakan kunci utama dalam rantai persediaan

karena produk jarang diproduksi dan dikonsumsi pada tempat/lokasi yang sama.

Transportasi adalah komponen biaya yang signifikan dengan dua unsur yang terpenting

yaitu pemindahan/pergerakan (Movement) dan secara fisik mengubah tempat dari

barang dan penumpang ketempat lain.

2.1.1 Jenis Transportasi

Menurut Abbas (1998) sistem yang digunakan untuk mengangkut barang-

barang dengan menggunakan alat angkut tertentu dinamakan moda transportasi (mode

of transportation). Moda transportasiitu sendiri merupakan istilah yang digunakan

untuk menyatakan alat angkut yang digunakan untuk berpindah tempat dari satu tempat

ketempat lain. Moda yang biasanya digunakan dalam transportasi dapat

dikelompokkan atas moda yang ber jalan didarat, berlayar di perairan laut dan

pedalaman serta moda yang terbang di udara. Moda yang didarat juga masih bisa

dikelompokkan atas moda jalan, moda kereta api dan moda pipa. Jaringan transportasi

5

dapat dibentuk oleh moda transportasi yang terlibat yang salaing berhubungan yang

rangkai dalam Sistem Transportasi Nasional (Sistranas). Masing-masing moda

transportasi memiliki karakteristik teknis yang berbeda dan pemanfaatannya

disesuaikan dengan kondisi geografis daerah layanan.

Heizer dan Render (2006) menyatakan didalam supply chain perlu alat

transportasi dalam suatu distribusi barang atau produk. Lima sarana distribusi yang

utama adalah truk, kereta api, saluran pipa, moda udara, dan moda laut. Berikut

penjelasan mengenai moda transportasi yang bisa digunakan dalam sarana

pendistribusian:

• Moda Darat

Moda darat dapat menggunakan 3 jenis kendaraan, yaitu:

a) Truk

Sebagian besar barang produksi dipindahkan dengan truk. Salah satu

kelebihan yang dimiliki oleh truk adalah fleksibilitas pengirimannya.

Perusahaan sudah menekankan pada pengendara truk untuk mengambil

dan mengirim tepat waktu, tanpa kerusakan, dengan administrasi yang

baik, dan biaya yang rendah. Perusahaan truk terus meningkat pengguna

komputer untuk memonitor cuaca, menemukan rute yang paling efektif,

mengurangi biaya bahan bakar, dan mencari yang paling efisien untuk

membongkar barang.

b) Kereta Api

Merupakan moda yang digunakan pada koridor dengan jumlah

permintaan yang tinggi, dimana alat angkut kereta api yang berjalan

diatas rel. Moda kereta api tidak fleksibel seperti truk namun hanya

dapat digunakan bila didukung oleh jaringan infrastruktur rel kereta api.

Sistem transportasi kereta api dapat dioperasikan dengan biaya operasi

dan biaya perawatan yang lebih rendah dari truk, namun biaya investasi

awalnya sangat tinggi sehingga hanya sesuai digunakan untuk angkutan

penumpang yang bersifat massal baik di perkotaan maupun antar kota,

serta angkutan barang. Angkutan barang yang menggunakan kereta api

biasanya dalam bentuk angkutan peti kemas pada kereta flat bed atau

pun untuk mengangkat komoditi curah baik cair maupun padat.

c) Angkutan Pipa

Merupakan moda yang umumnya digunakan untuk bahan berbentuk

cair atau pun gas, pipa digelar diatas tanah, ditanam pada kedalaman

tertentu di tanah atau pun digelar melalui dasar laut. Biaya operasi dan

biaya perawatan rendah, lebih rendah dari biaya moda jalan dan moda

kereta api, namun biaya investasi infrastrukturnya tinggi. Efisien

6

digunakan untuk mengangkut cairan atau gas dalam jumlah barang yang

diangkut tinggi pada jaringan primer. Didaerah perkotaan jaringan pipa

jarak pendek digunakan untuk mengalirkan berbagai keperluan

diantaranya sistem drainase kota untuk mengelola pembuangan air

hujan dan pengendalian banjir, sistem pembuangan air kotor, sistem air

bersih yang biasanya dikelola oleh Perusahaan Air Minum/PAM, Gas

Kota yang digunakan untuk kebutuhan energi untuk masak atau

pemanasan.

• Moda pelayaran

Karena sifat fisik air yang menyangkut daya apung dan gesekan yang terbatas,

maka pelayaran merupakan moda angkutan yang paling efektip untuk angkutan

barang jarak jauh barang dalam jumlah yang besar. Pelayaran dapat berupa

pelayaran paniai, pelayaran antar pulau, pelayaran samudra ataupun pelayaran

pedalaman melalui sungai atau pelayaran di danau. Didalam pelayaran biaya

terminal dan perawatan alur merupakan komponen biaya paling tinggi,

sedangkan biaya pelayarannya rendah. Ukuran kapal cenderung semakin besar

pada koridor-koridor pelayaran utama, dimana pada tahun 1960an ukuran kapal

yang paling besar mencapai 100.000 dwt tetapi sekarang sudah mulai

digunakan kapal tangker MV Knock Nevis 650 ribu ton dengan panjang 458

meter, draft 24,6 meter.

• Moda Udara

Moda transportasi udara mempunyai karakteristik kecepatan yang tinggi dan

dapat melakukan penetrasi sampai keseluruh wilayah yang tidak bisa dijangkau

oleh moda transportasi lain. Di Papua ada beberapa kota yang berada di

pedalaman yang hanya dapat dihubungkan dengan angkutan udara, sehingga

papua merupakan pulau dengan lebih dari 400 buah bandara/landasan

pesawat/air dengan panjang landasan antara 800 sampai 900 meter.

Perkembangan industri angkutan udara nasional, Indonesia sangat dipengaruhi

oleh kondisi geografis wilayah yang ada sebagai suatu negara kepulauan. Oleh

karena itu, Angkutan udara mempunyai peranan penting dalam memperkokoh

kehidupan berpolitik, pengembangan ekonomi, sosial budaya dan keamanan &

pertahanan. Kegiatan transportasi udara terdiri atas: angkutan udara niaga yaitu

angkutan udara untuk umum dengan menarik bayaran, dan angkutan udara

bukan niaga yaitu kegiatan angkutan udara untuk memenuhi kebutuhan sendiri

dan kegiatan pokoknya bukan di bidang angkutan udara. Sebagai tulang

punggung transportasi adalah angkutan udara niaga berjadwal, sebagai

penunjang adalah angkutan niaga tidak berjadwal, sedang pelengkap adalah

angkutan udara bukan niaga.

7

2.1.2 Faktor Yang Mempengaruhi Keputusan Transportasi

Chopra dan meindl (2004) tujuan pengangkutan adalah untuk membuat

keputusan investasi dan di set beroperasi sesuai dengan kebijakan, yaitu

memaksimalkan kembalinya asset yang telah diinvestasikan. Suatu pengangkutan

seperti pada perusahaan penerbangan, jalan kereta api, atau perusahaan truk harus

mempertimbangkan biaya – biaya berikut ini ketika akan menanam modal dalam asset

atau penetapan harga pengaturan dan kebijakan operasional, sebagai berikut:

1. Biaya yang berhubungan dengan kendaraan/sarana angkut

Biaya untuk pembelian atau menyewa sarana angkut barang – barang atau

biaya yang berhubungan dengan kendaraan yang terjadi apabila sarana

angkut digunakan, perbaikan sarana angkut untuk membuat keputusan

jangka panjang.

2. Biaya tetap

Biaya yang berhubungan dengan terminal, gerbang pelabuhan udara

meskipun sarana tersebut digunakan atau tidak. Sebagai contoh biaya tetap

suatu fasilitas terminal perusahaan pengiriman truk dan pelabuhan udara

tidak terkait pada banyaknya truk yang dikunjungi.

3. Biaya yang berhubungan dengan transportasi

Biaya ini terjadi setiap kali sarana angkut meninggalkan suatu tempat untuk

melakukan perjalanan dan meliputi biaya tenaga kerja serta bahan bakar.

Biaya transportasi tergantung pada jangka waktu dan panjangnya perjalanan,

tetapi tidak terikat pada kuantitas pengiriman. Biaya ini dianggap variabel

tergantung dari pembuat keputusan strategis atau keputusan perencanaannya

tergantung pada jangka waktu dan panjangnya suatu perjalanan.

4. Biaya yang berhubungan dengan kualitas

Biaya ini meliputi biaya loading/unloading dan sebagian dari biaya bahan

bakar yang bervariasi dengan jumlah barang yang diangkut. Biaya ini biasa

termasuk dalam biaya variabel dalam semua keputusan transportasi kecuali

jika menggunakan tenaga kerja tetap untuk memuat atau membongkar

barang.

5. Biaya umum/Overhead

Kategori ini meliputi biaya perencanaan dan penjadwalan suatu jaringan

transportasi seperti halnya investasi didalam teknologi informasi serta biaya

yang masuk dalam biaya tak langsung.

2.2 Distribusi

8

Pada aktivitas pendistribusian Toth dan Vigo (2004) hal terpenting yang harus

diperhatikan adalah pemilihan jalur rute yang dikunjungi, jumlah kendaraan yang

digunakan pada saat pengiriman, penyeimbangan rute dan meminimalkan keluhan

pelanggan sangatlah penting dilakukan oleh perusahaan dengan tujuan agar dapat

meminimalkan ongkos perjalanan. Biaya transportasi / ongkos perjalan merupakan

salah satu komponen utama dalam struktur biaya logistik total, Stock dan Lambert

(2001) menyatakan bahwa 60% dari biaya logistik total adalah biaya transportasi,

penerapan efisiensi transportasi dapat memberikan kontribusi pada penurunan biaya

logistik total.

2.2.1 Jenis saluran distribusi

• Saluran distribusi langsung

Produsen → Konsumen

Contoh: petani sayur menjual sayuran di pasar.

• Saluran distribusi semi langsung

Produsen → Perantara → Konsumen

Contoh: Penerbit buku menjual bukunya melalui sales.

• Saluran distribusi tidak langsung

Produsen → Pedagang Besar → Pedagang Kecil → Pedagang

Eceran → Konsumen

Contoh: Pabrik televisi menjual televisi kepada konsumen melalui

pedagang barang elektronik yang mengambil/membeli dari agen atau

perwakilan dagang pabrik televisi tersebut.

2.2.2 Tujuan Distribusi

Tujuan Kegiatan distribusi yang dilakukan oleh individu atau lembaga sebagai

berikut:

• Kelangsungan hidup kegiatan produksi terjamin. Produsen atau

perusahaan membuat barang dengan tujuan dijual untuk memperoleh

keuntungan. Dari hasil penjualan tersebut dapat digunakan untuk

melakukan proses produksi kembali sehingga kelangsungan hidup

perusahaan tetap terjamin.

• Barang atau jasa Hasil produksi dapat bermanfaat bagi konsumen.

Barang atau jasa produksi tidak akan ada artinya bila tetap berada di

tempat produsen. Barang atau jasa tersebut akan bermanfaat bagi

konsumen yang membutuhkan setelah ada kegiatan distribusi.

• Konsumen dapat memperoleh Barang dengan mudah. Tidak semua

barang atau jasa yang dibutuhkan konsumen dapat dibeli secara

langsung dari produsen. Ada barang barang atau jasa jasa tertentu yang

9

memerlukan kegiatan penyaluran atau distribusi dari produsen ke

konsumen agar konsumen mudah untuk mendapatkanya.

2.2.3 Fungsi Distribusi

Menurut Kotler (1991) menyatakan tentang distribusi adalah sekelompok

perusahaan dan perorangan yang dimiliki hak kepemilikan produk atau jasa ketika

dipindahkan dari produsen ke konsumen. Sedangkan fungsi distribusi sendiri adalah:

1) Mengumpulkan informasi mengenai langganan, pesaing serta pelaku dan

kekuatan lain yang ada saat ini maupun yang potensial dalam lingkungan

pemasaran.

2) Mengembangkan dan menyebarkan komunikasi persuasif untuk merangsang

pembeli.

3) Mencapai persetujuan akhir mengenai harga dan syarat lain sehingga transfer

kepemilikan dapat dilakukan.

4) Melakukan pemesanan ke perusahaan manufaktur.

5) Memperoleh dana untuk membiayai persediaan pada berbagai level saluran

pemasaran.

6) Menanggung resiko yang berhubungan dengan pelaksanaan fungsi saluran

pemasaran tersebut.

7) Mengatur kesinambungan penyimpanan dan pergerakan produk fisik dari

bahan mentah sampai kekonsumen akhir.

8) Mengatur perlunasan tagihan pembeli melalui bank dan institusi keuangan

lainnya.

9) Mengawasi transfer kepemilikan actual dari organisasi atau orang kepada

organisasi atau orang lain.

2.2.4 Saluran Distribusi

Muhyidin dan Abdurahman (2007) menyatakan saluran distribusi adalah

saluran yang digunakan untuk menyalurkan suatu produk dari produsen ke konsumen,

dengan fungsi saluran distribusi sebagai berikut:

a) Melakukan pencarian dan berkomunikasi dengan pembeli.

b) Mengusahakan perundingan untuk mencapai persetujuan akhir atas harga dan

ketentuan lainnya mengenai tawaran agar perpindahan pemilikan dapat terjadi.

c) Melaksanakan pengangkutan dan penyimpanan produk.

d) Mengatur distribusi dana untuk menutup biaya saluran distribusi.

e) Menerima resiko dalam hubungan dengan pelaksanaan pekerjaan saluran

pemasaran.

10

Menurut Mohyi dan Hikmawati (2000) Saluran distribusi atau perantara

distribusi adalah orang atau lembaga yang kegiatannya menyalurkan barang dari

produsen sampai ke tangan konsumen dengan tujuan untuk memperoleh keuntungan.

Didalam saluran distribusi yang paling berperan penting adalah pedagang. Pengertian

pedagang itu sendiri adalah seseorang atau lembaga yang membeli dan menjual barang

kembali tanpa mengubah bentuk dan tanggung jawab sendiri dengan tujuan untuk

mendapatkan keuntungan.

Pedagang dibedakan menjadi:

o Pedagang Besar (Grosir atau Wholesaler) adalah pedagang yang

membeli barang dan menjualnya kembali kepada pedagang yang lain.

Pedagang besar selalu membeli dan menjual barang dalam partai besar.

o Pedagang Eceran (Retailer) adalah pedagang yang membeli barang dan

menjualnya kembali langsung kepada konsumen. Untuk membeli biasa

partai besar, tetapi menjualnya biasanya dalam partai kecil atau

persatuan.

2.2.5 Faktor Yang Mempengaruhi Distribusi

Faktor-faktor yang mempengaruhi kegiatan distribusi ialah:

1. Faktor Pasar

Dalam lingkup faktor ini, saluran distribusi dipengaruhi oleh pola pembelian

konsumen, yaitu jumlah konsumen, letak geografis konsumen, jumlah pesanan

dan kebiasaan dalam pembelian.

2. Faktor Barang

Pertimbangan dari segi barang bersangkut-paut dengan nilai unit, besar dan

berat barang, mudah rusaknya barang, standar barang dan pengemasan.

3. Faktor Perusahaan

Pertimbangan yang diperlukan di sini adalah sumber dana, pengalaman dan

kemampuan manajemen serta pengawasan dan pelayanan yang diberikan.

4. Faktor kebiasaan dalam pembelian

Pertimbangan yang diperlukan dalam kebiasaan pembelian adalah kegunaan

perantara, sikap perantara terhadap kebijaksanaan produsen, volume penjualan

dan ongkos penyaluran barang.

2.3 Vehicle Routing Problem (VRP)

2.3.1. Definisi Vehicle Routing Problem

Vehicle Routing Problem merupakan salah satu bentuk permasalahan

transportasi yang melibatkan pendistribusian barang maupun orang kepada pelanggan

dengan menggunakan kendaraan dan bertujuan untuk meminimasi beberapa tujuan

11

distribusi. Hal ini dapat dilakukan dengan cara menentukan secara optimal jumlah

kendaraan yang digunakan serta rute yang harus ditempuh untuk masing-masing

kendaraan dalam memenuhi permintaan pelanggan. Banyak metode yang dapat dipakai

untuk mencari solusi yang baik, tetapi untuk lingkup yang lebih besar, fungsi biaya

untuk mencari nilai minimum global sangatlah kompleks.

Kallehauge & Larsen 2001 menerangkan bahwa Vehicle Routing Problem

(VRP) merupakan salah satu variasi dari Travel Salesman Problem (TSP) yaitu m-TSP,

dimana terdapat m salesman yang mengunjungi sejumlah kota dan tiap kota hanya

dapat dikunjungi tepat satu salesman saja. Tiap salesman berawal dan berakhir ke

depot yang sama.

Toth & vigo (2004) VRP merupakan sebuah masalah pemograman interger

yang masuk kategori masalah polinomial sukar, yang berarti usaha komputasi yang

digunakan akan semakin sulit dan banyak, seiring dengan meningkatnya ruang lingkup

masalah yang terjadi dengan tujuan yang dicapai diantaranya:

a. Meminimalkan ongkos perjalanan secara keseluruhan yang dipengaruhi

keseluruhan jarak yang ditempuh dan jumlah kendaraan yang digunakan.

b. Meminimalkan jumlah kendaraan yang digunakan untuk melayani semua

konsumen.

c. Menyeimbangkan rute.

d. Meminimalkan keluhan pelanggan.

VRP terdiri dari penentuan rute kendaraan yang melayani beberapa pelanggan.

Setiap kendaraan memiliki kapasitas angkut, dan setiap pelanggan memiliki demand.

Tiap pelanggan dikunjungi tepat satu kali dan total demand tiap rute tidak boleh

melebihi kapasitas angkut kendaraan. Dalam VRP sendiri dikenal pula istilah depot,

dimana tiap kendaraan harus berangkat dan kembali ke depot itu. Hal tersebutlah yang

menyebabkan VRP sering disebut sebagai permasalahan m-TSP. Golden & Raghaven

(2008) disebutkan bahwa VRP adalah sebuah problem yang terletak pada irisan dua

masalah yang sudah dikenal, yaitu TSP dan BPP. Dimana kedua masalah tersebut

termasuk dalam kategori NP-Hard Problem, yang berarti waktu komputasi yang

digunakan akan semakin sulit dan banyak seiring dengan meningkatnya ruang lingkup

masalah. Tujuan yang ingin dicapai adalah meminimalkan total jarak tempuh dan

meminimalkan jumlah kendaraan yang digunakan. VRP sendiri memiliki beberapa

faktor-faktor penentu dalam implementasinya pada dunia nyata.

Permasalahan VRP biasanya digambarkan dalam sebuah grafik. Grafik tersebut

menggambarkan permasalahan yang terjadi, yaitu berupa penyebaran konsumen yang

harus dilayani dan posisi depot yang merupakan pusat pendistribusian berlangsung.

Vertex (V0, …, Vn) merupakan titik yang menunjukkan posisi depot dan konsumen

berada. Vertex depot ditunjukkan oleh dan yang lainnya menunjukkan konsumen yang

berjumlah n. Garis yang menghubungkan antar vertex disebut arc. Arc menunjukkan

12

waktu, ongkos perjalanan dan jarak yang digunakan untuk perjalanan dari satu titik ke

titik yang lain. Solusi dianggap layak jika memenuhi beberapa syarat, yaitu rute yang

terbentuk harus dapat melayani semua konsumen, semua konsumen hanya bisa

dikunjungi satu kali dan semua rute harus dimulai dan selesai di home depot (Haksever

,2000). VRP memiliki karakteristik berupa demand yang berada pada setiap konsumen,

memiliki satu depot, dan memiliki lebih dari satu kendaraan dengan kapasitas yang

terbatas. Gambar 2.1. menunjukkan contoh penyelesaian VRP dengan menghasilkan 2

rute dan masing-masing rute kembali ke titik awal (depot). Rute 1 melayani 5

konsumen dan rute 2 melayani 6 konsumen dengan jumlah permintaannya masing-

masing tanpa melanggar load maksimum yang mampu dibawa oleh setiap kendaraan.

VRP diklasifikasikan dalam NP-hard problem, oleh karena itu metode exact

optimization sulit untuk menyelesaikan kasus VRP. Untuk mendapatkan solusi

yang relevan dengan kondisi real dan sangat dekat dengan solusi yang optimal 5 maka

digunakanlah metode heuristic dan meta-heuristic.

13

Gambar 2.1 Penyelesaian Vehicle Routing Problem (Haksever.,2000)

Perkembangan kasus distribusi di dunia nyata dengan berbagai macam

karakteristik membuat banyaknya varian VRP yang merupakan pengembangan dari

varian VRP yang sudah ada. Mulai dari VRP dengan single objective hingga multi

objective. Hal ini yang membuat banyak peneliti yang merasa tertantang untuk

menyelesaikan kasus VRP yang mulai beragam dan lebih up to date seperti yang

dilakukan oleh Hempsch dan Irnich (2008) atau mengembangkan metode baru untuk

mencari solusi yang lebih baik. Hempsch dan Irnich (2008) menyebutkan bahwa kasus

distribusi pada dunia nyata memiliki kendala baru berupa Inter-tour constrains. Inter-

tour constrains adalah kendala yang melihat bahwa terdapat banyak sifat dalam

distribusi yang mempengaruhi solusi yang dihasilkan, seperti proses sorting pada

depot, lama maksimum rute, dan terbatasnya kapasitas untuk memproses barang yang

datang. Hempsch dan Irnich menggunakan local-search algorithms dalam

menyelesaikan kasus tersebut. Sedangkan penelitian lain mengembangkan metode

heuristik dalam menyelesaikan varian kasus Heterogeneous Fleet VRP (HFVRP).

Tujuan dari penelitian tersebut adalah membandingkan hasil komputasi dan

performansi algoritma heuristik miliknya dengan penelitian terdahulu. Kasus VRP

yang bersifat multi objective pernah dilakukan dengan mencoba membawa beban kerja

supir taksi sebagai faktor yang diperhitungkan dan mengembangkan model VRP yang

tidak hanya mencari jarak terpendek tetapi juga mempertimbangkan keseimbangan

beban kerja yang dibebankan ke supir.

2.3.2. Jenis-jenis VRP

Menurut Yunita (2013) batasan-batasan yang harus dipenuhi dalam

menyelesaikan permasalahan VRP antara lain sebagai berikut:

1. Setiap permintaan barang dari customer dapat terpenuhi.

2. Setiap customer dikunjungi hanya satu kali dan hanya oleh satu kendaraan

saja.

3. Setiap rute kendaraan berawal dan berakhir di depot.

4. Jumlah total permintaan yang dapat dilayani dalam satu rute oleh sebuah

kendaraan tidak melebihi kapasitas kendaraan tersebut.

Dalam menggunakan VRP untuk dunia nyata, banyak faktor sampingan yang

muncul. Faktor-faktor tersebut berpengaruh pada munculnya variasi dari VRP menurut

(Fajarwati, 2012), antara lain :

1. Capacitated VRP (VRP)

Faktor: setiap kendaraan mempunyai kapasitas yang terbatas.

2. VRP With Time Windows (VRPTW)

Faktor: pelanggan harus dilayani dengan waktu tertentu.

14

3. Multiple Depot VRP (MDVRP)

Faktor: distributor memiliki banyak depot.

4. VRP With Pick-Up and Delivering (VRPPD)

Faktor: pelanggan diperbolehkan mengembalikan barang ke depot asal.

5. Split Delivery VRP (SDVRP)

Faktor: pelanggan dilayani dengan kendaraan berbeda.

6. Stochastic VRP (SVRP)

Faktor: munculnya random values (seperti jumlah pelanggan, jumlah

permintaan, waktu perjalanan atau waktu pelayanan).

7. Periodic VRP

Faktor: pengantaran hanya dilakukan di hari tertentu.

Menurut Yunita (2013) formulasi VRP dengan tujuan meminimalkan total biaya

atau total jarak tempuh dari rute perjalanan pendistribusian barang atau jasa adalah

sebagai berikut:

Fungsi Tujuan

∑ ∑ ∑ 𝐶𝑖𝑗 𝑋𝑖𝑗𝑘

𝑗∈𝑉𝑖∈𝑉𝑘∈𝐾

Dimana

𝑋𝑖𝑗𝑘 = {

1, 𝑗𝑖𝑘𝑎 𝑘𝑒𝑛𝑑𝑎𝑟𝑎𝑎𝑛 𝑘 𝑑𝑖𝑗𝑎𝑙𝑎𝑛𝑘𝑎𝑛 𝑑𝑎𝑟𝑖 𝑡𝑖𝑡𝑖𝑘 𝑖 𝑘𝑒 𝑖, 𝑖 ≠ 𝑖0, 𝑢𝑛𝑡𝑢𝑘 𝑦𝑎𝑛𝑔 𝑙𝑎𝑖𝑛

Adapun batasan –batasan yang digunakan sebagai berikut:

Batasan 1: Setiap customer hanya dikunjungi tepat satu kali dan hanya oleh satu

kendaraan.

∑ ∑ 𝑋𝑖𝑗𝑘 = 1

𝑖∈𝑉𝑘∈𝐾

, ∀𝑖 ∈ 𝑉 {0}

Batasan 2: Total permintaan dari setiap customer dalam satu rute tidak boleh melebihi

tiap kendaraan.

∑ 𝑞𝑖

𝑖∈𝑉/{0}

∑ 𝑋𝑖𝑗𝑘 ≤ 𝑄 , ∀𝑘 ∈ 𝐾

𝑗∈𝑉

Batasan 3: Setiap kendaraan harus meninggalkan customer yang telah dikunjungi.

∑ 𝑋𝑖𝑗𝑘 −

𝑖∈𝑉

∑ 𝑋ℎ𝑗𝑘

𝑗∈𝑉

= 0 , 𝑉ℎ ∈ 𝑣/{0}, ∀𝑘 ∈ 𝐾

15

Batasan 4: Setiap kendaraan yang meninggalkan depot harus kembali ke depot.

∑ 𝑋0𝑗𝑘 = 1

𝑗∈𝑉/{0}

, ∀𝑘 ∈ 𝐾

∑ 𝑋𝑗0𝑘 = 1

𝑗∈𝑉/{0}

, ∀𝑘 ∈ 𝐾

Batasan 5: Batasan nilai.

𝑋𝑖𝑗𝑘 ∈ {0,1} , ∀𝑘 ∈ 𝐾, 𝑗 ∈ 𝑉, 𝑘 ∈ 𝐾

Formulasi VRP yang bisa digunakan menurut Yunita dkk (2013) guna

meminimalkan total biaya atau total jarak tempuh dari rute perjalanan pendistribusian

barang sebagai berikut:

a.

Kendala ini untuk meminimalisasi biaya biaya transportasi total dari rute.

b. ∀𝑖 ∈ 𝑁

Batasan tersebut untuk menjamin bahwa seluruh customer dapat dilayani.

c. ∑ 𝑌 𝐾𝑘=1 ik= 1 ∀𝑖 ∈ 𝑉 {0}

Batasan ini untuk memastikan bahwa setiap customer dikunjungi tepat satu kali

oleh satu kendaraan.

d. ∑𝑘𝑘=1 y0k = k

Kendala ini memastikan bahwa terdapat K kendaraan yang beroperasi memulai

rute dari depot.

e. ∑𝑖∈𝑣 di yik ≤ 𝐶k ∀𝑘 = 1,2, … , 𝐾

Kendala tersebut menjamin bahwa total permintaan konsumen dalam setiap

rute tidak melebihi kapasitas kendaraan.

f. ∀𝑘 ∈ 𝐾

Batasan ini memastikan bahwa total waktu rute suatu kendaraan tidak melebihi

waktu maksimum.

g. ∑ 𝑋 ≥ 1𝑟𝐾 ∀𝑘 ∈ 𝐾

Kendala ini menjamin bahwa tiap kendaraan minimal melewati 1 jalur.

h. 𝑋𝑟𝑘 ∈ {0,1} ∀𝑘 ∈ 𝐾, ∀𝑟 ∈ 𝑅k

Batasan tersebut menjamin variable keputusan 𝑋𝑟𝑘 merupakan interger biner,

dengan variable keputusan:

𝑋𝑟𝑘= {

1,0, 𝑗𝑖𝑘𝑎 𝑠𝑒𝑙𝑎𝑖𝑛𝑛𝑦𝑎

𝑗𝑖𝑘𝑎 𝑘𝑒𝑛𝑑𝑎𝑟𝑎𝑎𝑛 𝑘 𝑚𝑒𝑛𝑔𝑔𝑢𝑛𝑎𝑘𝑎𝑛 𝑟𝑢𝑡𝑒 𝑟

16

Keterangan formulasi:

K = Himpunan kendaraan pada depot, dengan K = {1, 2, … , K}

Rk = Himpunan rute yang ditempuh kendaraan k, dengan R = {R1, R1, … ,

RK}

V = Himpunan titik

di = Jumlah permintaan customer i

r = Indeks rute

𝐶𝑟𝑘 = biaya operasional kendaraan k yang menempuh rute r.

𝐴𝑟𝑖𝑘 = Konstanta yang bernilai 1 jika kendaraan k dengan rute r yang

menuju, custumer i, dan bernilai 0 untuk kondisi lain.

𝑇𝑟𝑘 = Waktu perjalanan kendaraan untuk menempuh rute r.

𝑇𝑀𝐴𝑋 = Waktu perjalanan maksimum untuk suatu kendaraan.

𝑋𝑟𝑘 = Variabel biner, bernilai 1 jika kendaraan k menggunakan rute r, dan

bernilai 0 untuk kondisi lainnya

2.4 Algoritma Sequential Insertion

Penyelesaian masalah rute kendaraan atau Vehicle Routing Problem (VRP)

memiliki banyak metode untuk memecahkannya. Salah satu metode yang dapat

diterapkan untuk menyelesaikan VRP dan variasinya adalah Metode Heuristik. Metode

Heuristik merupakan teknik untuk menyelesaikan permasalahan dengan lebih

menekankan pada performa komputasi sederhana. Menurut Laporte (1983) metode

Heuristik mudah diimplementasikan pada formulasi matematis yang diketahui dapat

menjamin suatu solusi optimal, dan salah satu contoh Metode Heuristik antara lain

Metode Insertion.

Gambar 2.2. Ilustrasi Penyisipan dengan Metode Sequential Insertion

Pada Gambar 2.2, Menurut Abadi (2014) Prinsip dasar dari algoritma sequential

insertion adalah mencoba menyisipkan pelanggan di antara semua busur (edge) yang

ada pada rute saat ini. busur ini didefinisikan sebagai lintasan yang menghubungkan

secara langsung satu lokasi dengan lokasi yang lain.

Menurut Yunita (2013) Algoritma sequential insertion diawali dengan memilih

suatu pelanggan untuk menduduki posisi sebagai pelanggan awal (seed customer) pada

rute dan tur pertama. Selanjutnya, tiap pelanggan akan dicoba disisipkan pada suatu

busur (edge) tertentu yang memberikan kriteria terbaik bagi rute saat ini, batasan time

17

window terpenuhi, dan total muatan kendaraan bagi rute saat ini tidak melebihi

kapasitas kendaraan. Pada penerapan algoritma sequential insertion terdapat beberapa

kriteria dalam pemilihan konsumen pertama. Adapun kriteria pemilihan konsumen

pertama yang dapat digunakan yaitu earliest deadline, earliest ready time, shortest time

window, dan longest travel time.

Adapun menurut Abadi (2014) langkah-langkah pemecahan masalah sequential

Insertion adalah sebagai berikut:

• Langkah 1

Pilih satu titik awal sebagai titik awal (0) yang dipilih berdasarkan aturan yang

telah ditentukan sebelumnya, lanjut ke langkah 2.

• Langkah 2

Hitung jarak tempuh yang dilalui distributor ke tiap pelanggan dan hitung

waktu tempuh yang dibutuhkan dalam mengirimkan barang ke tiap pelanggan,

lanjut ke langkah 3.

• Langkah 3

Hitung sisa kapasitas motor, jika sisa kapasitas motor memenuhi untuk

mengirimkan barang sesuai permintaan pelanggan maka lanjut ke langkah 4,

jika tidak lanjut ke langkah 9.

• Langkah 4

Jika telah memasuki pelanggan ke-2 atau seterusnya maka lanjut ke langkah 5,

jika tidak lanjut ke langkah 6.

• Langkah 5

Sisipkan pelanggan berikutnya ke dalam urutan rute yang telah terbentuk, lanjut

ke langkah 6.

• Langkah 6

Pilih pelanggan yang memiliki jarak paling pendek, lanjut langkah 7.

• Langkah 7

Hitung jarak tur, waktu penyelesaian tur dan list rute pelanggan yang telah

dilayani. Lanjut ke langkah 8.

• Langkah 8

Jika permintaan barang yang akan dikirimkan ke pelanggan belum semua

terpenuhi maka lanjut ke kembali 2, jika sudah lanjut ke langkah 10.

• Langkah 9

Kembali ke depot, buat tur baru, t = t+1, kembali ke langkah 2.

• Langkah 10

Semua permintaan barang yang dikirimkan ke pelanggan telah terpenuhi,

hentikan prosedur ini.