Optimasi Penjadwalan KRL Commuter Line Jabodetabek Berbasis Quadratic Multiple Knapsack Problem Menggunakan Algoritma Branch And Bound

Putra, Rama Darmawan (2026) Optimasi Penjadwalan KRL Commuter Line Jabodetabek Berbasis Quadratic Multiple Knapsack Problem Menggunakan Algoritma Branch And Bound. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5002221047-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (96MB) | Request a copy

Abstract

KRL Commuter Line Jabodetabek merupakan moda transportasi massal utama yang membutuhkan pengelolaan trainset secara efisien agar jadwal perjalanan dapat dilayani dengan pemanfaatan armada yang optimal. Penjadwalan KRL merupakan masalah optimasi yang kompleks karena sejumlah besar perjalanan harus dialokasikan kepada trainset yang terbatas sekaligus disusun menjadi urutan perjalanan yang layak secara operasional. Permasalahan penjadwalan tidak cukup dimodelkan sebagai penugasan kapasitas biasa karena kelayakan suatu jadwal juga dipengaruhi oleh hubungan antarperjalanan, terutama kesinambungan stasiun dan waktu tunggu antarjadwal. Oleh karena itu, penelitian ini memodelkan optimasi penjadwalan KRL sebagai Quadratic Multiple Knapsack Problem (QMKP), karena model ini mampu mengakomodasi keuntungan individu sekaligus keuntungan berpasangan yang merepresentasikan efisiensi lokasi dan waktu antara dua perjalanan yang dilayani secara berurutan oleh satu rangkaian. Model diselesaikan menggunakan algoritma Branch and Bound karena metode ini dapat menelusuri ruang solusi secara sistematis dan memberikan dasar pencarian solusi terbaik melalui mekanisme pembatasan dan pemangkasan cabang. Data penelitian terdiri atas 396 perjalanan dan 37 trainset, dengan parameter utama berupa durasi perjalanan, prioritas perjalanan, serta nilai interaksi antarperjalanan. Beberapa studi kasus diuji, meliputi QMKP konvensional, QMKP dengan trainset sebagai sequence perjalanan, serta QMKP berbasis Branch and Bound dengan dan tanpa pembatasan beam width. Hasil implementasi menunjukkan bahwa QMKP konvensional belum menjamin kelayakan operasional karena perjalanan dalam satu knapsack tidak diwajibkan membentuk urutan yang sesuai. Sebaliknya, model berbasis sequence mampu menghasilkan susunan perjalanan yang lebih realistis karena mempertimbangkan kesinambungan stasiun dan waktu. Pada Studi Kasus 4, yaitu Branch and Bound tanpa pembatasan beam width, diperoleh nilai objektif 81.741 dengan 276.144.886 nodes dalam 3600 detik. Studi Kasus 5, yaitu Branch and Bound dengan beam width 5000, menghasilkan nilai objektif yang sama, tetapi waktu komputasi turun menjadi 286,50 detik dengan 1.796.446 nodes. Dengan demikian, model QMKP berbasis sequence yang diselesaikan menggunakan Branch and Bound mampu menghasilkan penjadwalan yang lebih representatif secara operasional, sedangkan pembatasan beam width terbukti mempercepat komputasi tanpa menurunkan kualitas solusi pada data penelitian ini.
=========================================================================================================================================
The Jabodetabek KRL Commuter Line is a major mass transportation mode that requires efficient trainset management so that scheduled trips can be served with optimal fleet utilization. KRL scheduling is a complex optimization problem because a large number of trips must be assigned to a limited number of trainsets while simultaneously being arranged into operationally feasible trip sequences. The scheduling problem cannot be represented merely as a conventional capacity assignment problem because schedule feasibility is also influenced by the relationships between trips, particularly station continuity and waiting time between consecutive trips. Therefore, this study formulates the KRL scheduling optimization problem as a Quadratic Multiple Knapsack Problem (QMKP), since this model can accommodate both individual profits and pairwise profits that represent spatial and temporal efficiency between two trips served consecutively by the same trainset. The model is solved using the Branch and Bound algorithm because this method systematically explores the solution space and searches for the best solution through bounding and branch-pruning mechanisms. The research data consist of 396 trips and 37 trainsets, with the main parameters comprising trip duration, trip priority, and interaction values between trips. Several case studies are examined, including conventional QMKP, QMKP with trainsets treated as trip sequences, and Branch and Bound-based QMKP with and without a beam width restriction. The implementation results indicate that conventional QMKP does not guarantee operational feasibility because trips assigned to the same knapsack are not required to form a feasible sequence. In contrast, the sequence-based model produces a more realistic trip arrangement by considering station and temporal continuity. In Case Study 4, which applies Branch and Bound without a beam width restriction, an objective value of 81,741 is obtained by exploring 276,144,886 nodes within 3,600 seconds. Case Study 5, which uses a beam width of 5,000, produces the same objective value, while reducing the computational time to 286.50 seconds and the number of explored nodes to 1,796,446. Therefore, the sequence-based QMKP model solved using Branch and Bound provides a more operationally representative scheduling solution while the beam width restriction accelerates the computation without reducing the solution quality for the data used in this study.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Algoritma Branch and Bound, beam width, KRL Commuter Line, Quadratic Multiple Knapsack Problem, penjadwalan trainset. Branch and Bound algorithm, beam width, KRL Commuter Line, Quadratic Multiple Knapsack Problem, trainset scheduling.
Subjects:	Q Science Q Science > QA Mathematics > QA401 Mathematical models. Q Science > QA Mathematics > QA402.6 Transportation problems (Programming) Q Science > QA Mathematics > QA76.9 Computer algorithms. Virtual Reality. Computer simulation. Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Science and Data Analytics (SCIENTICS) > Mathematics > 44201-(S1) Undergraduate Thesis
Depositing User:	Rama Darmawan Putra
Date Deposited:	29 Jul 2026 07:37
Last Modified:	29 Jul 2026 07:37
URI:	http://repository.its.ac.id/id/eprint/139892

Actions (login required)

View Item