BAB I PENDAHULUAN
1.1. Latar Belakang dan Permasalahan Kereta api merupakan salah satu angkutan darat yang banyak diminati masyarakat, hal ini dikarenakan biaya yang relatif murah dan waktu tempuh yang cepat dibandingkan angkutan darat lainnya. Selain itu, kelebihan kereta api lainnya adalah ramah lingkungan dan relatif aman. Oleh karena itu, diperlukan solusi yang tepat agar dapat mengoptimalkan perjalanan kereta api. Masalah optimasi jalur kereta api identik dengan persoalan rute terpendek. Masalah ini menjadi masalah yang penting karena berkaitan dengan masalah meminimumkan biaya dan efisiensi waktu yang dibutuhkan. Masalah rute terpendek untuk semua pasangan vertek (jalur kereta api pada suatu stasiun) adalah masalah menentukan lintasan terpendek untuk setiap vertek yang ada, dengan mengoptimalkan fungsi tujuan (objektif) tertentu. Persoalan rute terpendek merupakan suatu jaringan pengarahan rute perjalanan dimana seorang pengarah jalan ingin menentukan rute terpendek antara dua kota berdasarkan rute alternatif yang tesedia yang biasanya terdiri dari satu atau beberapa kota tujuan. Masalah ini umumnya menggunakan representasi graf untuk memodelkan persoalan yang diwakili sehingga lebih memudahkan penyelesainnya. Masalahnya adalah bagaimana cara mengunjungi vertek pada graf dari vertek awal ke vertek akhir dengan bobot minimum, dalam hal ini bobot yang digunakan adalah jarak kota-kota yang dikunjungi diasumsikan sebagai graf yang saling terhubung antar suatu kota dengan kota-kota yang lainnya. Salah satu contoh permasalahan rute terpendek dalam bidang tarnsportasi adalah masalah optimasi jalur kereta api. Ketersediaan kereta api lebih dari satu untuk melayani stasiun-stasiun yang akan dituju berarti menambah permasalahan dalam pendistribusian penumpang
karena mungkin ada beberapa kendaraan pengangkut yang digunakan secara bersama untuk melayani tempat-tempat tersebut. H. Whitney dan M. Flood mengenalkan pendistribusian barang yang terdiri dari satu kendaraan, dikenal dengan metode Traveling Salesman Problem atau disebut dengan TSP. TSP dinyatakan sebagai permasalahan dalam mencari jarak minimal sebuah tur tertutup terhadap sejumlah n kota dimana kota-kota yang ada hanya dikunjungi sekali dengan kota awal juga merupakan kota akhir (tujuan). Permasalahan optimasi jalur kereta api disebut juga dengan Railway Traveling Salesman Problem (RTSP), permasalahan ini diperkenalkan oleh Hadjicharalambous dkk (2007), Hu dan Raidl (2008) dan buku Pop (2012). Permasalahan RTSP memiliki keterkaitan dengan Traveling Generalized Salesman Problem atau biasa disebut GTSP. GTSP diperkenalkan oleh Henry dan Lapordere pada tahun 1969. GTSP merupakan perluasan dari TSP dimana vertek (konsumen) dari graf tersebut dikelompokkan ke dalam kluster dan masalahnya adalah untuk menemukan biaya minimum Tour Hamiltonian setiap kluster yang dikunjungi tepat satu kali, yaitu mengunjungi satu vertek yang mewakili sebuah kluster. Permasalahan RTSP yang akan dibahas dalam penulisan ini merupakan permasalahan
dimana
seorang
salesman
melakukan
perjalanan
dengan
menggunakan transportasi kereta api dari stasiun awal, dimana ia memulainya tidak lebih awal dari waktu yang ditentukan menuju ke setiap stasiun di ℬ dan akhirnya kembali ke stasiun awal dengan kendala ia harus menghabikan total
waktu yang dibutuhkan di setiap stasiun di ℬ untuk menjalankan bisnisnya dan tujuannya adalah bagaimana meminimalisir keseluruhan waktu perjalanan. Contohnya adalah perusahaan pertamina yang melakukan pendistribusian minyak dengan menggunakan armada kereta api, begitu juga dengan pendistribusian semen Holcim dan semen Gresik yang menggunakan armada kereta api . Pemecahan masalah RTSP yang dilakukan secara manual dengan mencari dan memeriksa waktu perjalanan yang terpendek tidaklah efisien, hanya akan menghabiskan waktu dan tenaga saja. Apalagi cara tersebut hanya akan efektif jika jumlah kota atau konsumennya sedikit. Jika cara tersebut diterapkan pada
jumlah kota atau jumlah konsumen yang banyak maka cara tersebut tidak tepat untuk digunakan. Oleh karena itu, diperlukan algoritma yang dapat memecahkan permasalahan tersebut. Untuk menghasilkan rute yang efisien dalam mengoptimalkan perjalanan kereta api dapat digunakan metode heuristik. Metode heuristik cenderung sulit dipahami tetapi sangat handal dalam menyelesaikan masalah ini. Metode ini sulit dipahami karena banyak step yang harus dikerjakan untuk mendapatkan solusi yang optimal, metode ini dikatakan handal karena dalam algoritma ini ada prosedur pencarian solusi optimal yang dilakukan berulang-ulang sampai didapatkan solusi yang optimal. Metode heuristik terdiri dari beberapa macam algoritma yang biasa digunakan, salah satunya adalah algoritma Branch-and-Cut. Selanjutnya dalam penelitian ini akan dibahas penyelesaian masalah RTSP dengan pendekatan Integer Linear Programming (ILP). Integer Linear Programming atau Integer Programming (IP) adalah optimasi matematika untuk menemukan solusi diamana solusinya berupa bilangan bulat. Dalam hal ini akan dibentuk sebuah model matematika untuk meminimalisir waktu keseluruhan yang diperlukan salesman dalam melakukan perjalanan bisnisnya. Selanjutnya untuk menyelesaikan model Integer Programming yang telah dibuat digunakan algoritma Branch-and-Cut. Menurut John E. Mitchell (1999) dalam makalahnya yang berjudul ”Branch and Cut Algorithms for Combinatorial Optimization Problems” menjelaskan bahwa algoritma branch and cut memodifikasi branch
and
bound
dengan
mencoba
menguatkan
strategi
dasar
linear programming
relaxation (LPR) dari permasalahan IP dengan pertidaksaman baru sebelum melakukan pencabangan solusi bagian. Branch and Bound murni dapat dipercepat dengan menggunakan cutting planes baik di awal diagram pohon Branch Bound
maupun
mengurangi
di
tiap-tiap
nodenya,
banyak
diagram
pohon
karena
tersebut.
Cutting Branch
Planes and
Cut
and
mampu dapat
digunakan dalam penyambungan dengan heuristic untuk memperoleh batas
yang lebih rendah pada nilai optimal dengan menggunakan algoritma branch and bound. Menurut Shon
Albert (2006)
dalam
makalahnya
yang
berjudul
“Solving Mixed Integer Linear Programs using Branch and Cut Algorithm” menerangkan bahwa metode branch and cut menggabungkan keuntungan dari skema Branch and Bound murni dan skema Gomory Cutting Plane. Menyelesaikan masalah dengan metode branch and cut akan lebih cepat dibandingkan dengan branch and bound saja. Gomory Cutting Plane cepat, tetapi tidak dapat diandalkan. Branch and Bound dapat diandalkan, tetapi lambat. Akibatnya kedua metode dapat digabung menjadi satu yaitu dinamakan Branch And Cut. Pertama ditambahkan beberapa cut dari menggunakan
skema
Gomory
kemudian mengaplikasikan
sisanya menggunakan branch and bound. Algoritma tersebut tidak hanya dapat diandalkan hasilnya, tetapi juga lebih cepat. Pada prakteknya tidak semua algoritma ini efektif untuk diterapkan atau diimplementasikan pada suatu masalah tertentu. Hal ini disebabkan karena setiap algoritma mempunyai penampilan yang bebeda dalam penyelesaian suatu masalah. Suatu algoritma dikatakan baik jika lagoritma tersebut efektif dan efisien. Algoritma yang efektif dan efisien diukur dari berapa jumlah waktu dan ruang memori yang digunakan untuk menjalankannya. Berdasarkan hal ini, maka dalam penelitian ini akan dibahas tentang penyelesaian masalah RTSP pada kasus pendistribusian barang dengan menggunakan algoritma Branch-and-Cut dan menggunakan bantuan software, salah satunya ILOG CPLEX versi 12.5.
1.2. Perumusan dan Batasan Masalah Rumusan permasalahan dalam dalam penelitian ini adalah bagaimana metode Program Linear Bilangan Bulat dalam menyelesaikan permasalahan RTSP. Selanjutnya pembentukan model matematika untuk masalah RTSP dengan
menggunakan software ILOG CPLEX versi 12.5. Hal ini terkait cara meminimalkan keseluruhan waktu sebuah perjalanan. Batasan masalah dalam penelitian ini, penulis hanya membahas mengenai satu rute perjalanan kereta api pada masing-masing stasiun dan stasiun lain yang tidak dilewati kereta api diabaikan.
1.3. Tujuan dan Manfaat Penelitian Secara umum Tujuan yang ingin dicapai dalam penelitian ini adalah sebagai berikut: 1.
Penyusunan model matematika dari masalah RTSP.
2.
Menerapkan metode program linear bilangan bulat dalam masalah rute perjalanan kereta api.
3.
Mendapatkan solusi optimal rute perjalanan kereta api dalam bentuk graf.
Manfaat dari penelitian ini adalah sebagai berikut: 1.
Secara umum penelitian ini diharapkan dapat meberikan sumbangan terhadap ilmu pengetahuan dan menambah pengetahuan alam bidang matematika terapan terutama optimasi pada masalah RTSP untuk mencari waktu tersingkat.
2.
Secara khusus manfaat penelitian ini diharapkan dapat memberikan gambaran tentang penyelesaian masalah RTSP dengan menggunakan algoritma branch and cut sehingga dapat menemukan rute perjalanan kereta api optimal yang dapat meminimalisir keseluruhan waktu perjalanan.
3.
Metode penyelesaian dari masalah masalah RTSP yang digunakan dalam penelitian ini diharapkan dapat membantu pembaca untuk menyelesaikan masalah dalam kehidupan sehari-hari yang mempunyai prinsip yang sama dengan model yang dirumuskan dalam penelitian ini.
1.4. Tinjauan Pustaka Penelitian dalam tesis ini adalah mengkaji kembali paper yang ditulis oleh Hadjicharalambous, dkk (2007), Hu dan Raidl (2008) dan buku Pop (2012) yang
membahas tentang metode penyelesaian masalah RTSP dengan menggunakan algoritma Branch and Cut dan menggunakan bantuan software, salah satunya ILOG CPLEX versi 12.5 sehingga dapat menemukan rute perjalanan kereta api optimal yang dapat meminimalisir keseluruhan waktu perjalanan. Sebelum menentukan penyelesaian dari masalah optimisasi jalur kereta api, terlebih dahulu dipahami tentang definisi kereta api, jenis-jenis kereta api, jalur kereta api, stasiun kereta api, dan operasional perjalanan kereta api. Informasi mengenai hal tersebut diambil dari Undang-Undang Nomor 23 Tahun 2007 tentang perkeretaapian, reglemen 19 Bab I pasal 1 ayat 4a, dan operasional kereta api yang dinyatakan dalam peraturan-peraturan PT. Kereta Api Indonesia (DPR, 2007). Selanjutnya mempelajari teori-teori yang berkaitan dengan masalah RTSP. Masalah RTSP disini merupakan persoalan optimasi jalur kereta api. Diasumsikan diberikan sebuah himpunan stasiun, sebuah jadwal terkait kereta api yang menghubungkan antar stasiun, stasiun awal tempat memulai perjalanan, sebuah himpunan bagian ℬ dari stasiun, dan waktu awal memulai perjalanan. Seorang salesman akan melakukan perjalanan dari stasiun awal dan memulainya
tidak lebih awal dari waktu yang telah ditentukan menuju setiap stasiun di ℬ, dan akhirnya kembali menuju stasiun awal tempat ia memulai perjalanan dengan
kendala ia harus menghabiskan total waktu yang dibutuhkan di setiap stasiun pada ℬ untuk melakukan kegiatan bisnisnya. Tujuannya adalah menemukan sirkuit
Hamilton terpendek yang dilalui salesman yang meminimalkan fungsi tujuan, dalam hal ini meminimalkan waktu perjalanan. Persoalan ini direpresentasikan dalam bentuk graf dan membentuk formula matematisnya sehingga lebih memudahkan penyelesaiannya. Beberapa konsep dasar mengenai graf dalam hal ini yakni definisi graf, jenis-jenis graf, sirkuit Hamilton, representasi graf, dan beberapa definisi pendukung terkait dengan teori graf diambil dari buku Wilson (1998), buku Bondy dan Murty (1976), buku Setiadji dan buku Munir (2003). Formulasi masalah TSP merupakan formulasi program liniear bilangan bulat yang teorinya dirujuk dalam Winston (1994). Selanjutnya formulasi bilangan bulat untuk TSP dibagi atas dua yaitu: formulasi bilangan bulat untuk
Symmetric TSP (STSP) dan formulasi bilangan bulat untuk Asymmetric TSP (ATSP) yang dirujuk pada Dantzig et al (1954). Selanjutnya mempelajari keterkaitan antara RTSP dengan Generalized Asymetric Traveling Salesman Problem (GATSP) dan mempelajari formulasi umum pada kasus RTSP yang diambil dari paper yang ditulis oleh Hadjicharalambous, dkk (2007), Hu dan Raidl (2008) dan buku Pop (2012). Formulasi umum dari RTSP didasarkan pada time-expanded-digraph yang diperkenalkan oleh Hadjicharalambous, dkk (2007). Karena time-expandeddigraph bisa saja memiliki ukuran yang besar, maka diberikan metode yang dapat mereduksi ukuran graf tersebut. Kemudian masalah RTSP yang sudah direduksi tersebut disajikan dalam bentuk Integer Linear Programming (ILP) yang sederhana. Masalah ILP dipelajari di dalam buku Winston (1994). Algoritma yang digunakan untuk menyelesaikan masalah tersebut adalah algoritma Branch and Cut dan menggunakan bantuan software, salah satunya ILOG CPLEX versi 12.5 sehingga dapat menemukan rute optimal yang dapat meminimalisir keseluruhan waktu perjalanan yang diambil dari paper Hu dan Raidl (2008).
1.5. Metedologi Penelitian Metode penelitian yang digunakan dalam penulisan tesis ini adalah studi literatur. Penelitian ini dibagi menjadi tiga tahap. Tahap pertama, mempelajari formulasi umum dari kasus RTSP yang didasarkan pada time-expanded-digraph, selanjutnya mempelajari bentuk RTSP yang akan direduksi dalam bentuk ILP yang sederhana. Tahap kedua, mempelajari salah satu algoritma yang digunakan untuk menyelesaikan masalah RTSP, yaitu Algoritma Branch and Cut dan menggunakan bantuan software, salah satunya ILOG CPLEX versi 12.5 sehingga dapat menemukan rute optimal yang dapat meminimalisir keseluruhan waktu perjalanan. Tahap ketiga, menerapkan algoritma Branch and Cut pada contoh numerik dan menyelesaikannya dengan menggunakan bantuan software, salah satunya ILOG CPLEX versi 12.5.
1.6. Sistematika Penulisan Tesis ini dibagi menjadi 4 (empat) Bab. Di dalam Bab I berisi tentang latar belakang dan permasalahan, perumusan dan batasan masalah, tujuan dan manfaat penelitian, tinjauan pustaka, metode penelitian dan sistematika penulisan. Selanjutnya, pada Bab II peneliti menguraikan landasan teori yang dijadikan materi pendukung dalam penelitian ini. Teori yang dimuat dalam bab ini hanya yang berkaitan dengan penelitian yang akan dikaji. Pada Bab III berisi tentang model matematika masalah RTSP. Terakhir, dalam Bab IV memuat tentang simulasi model matematika maslah RTSP.
