Algoritma Branch-and-Cut untuk Permasalahan Dial-a-Ride

Hanifa Reygina Fajrin, Dr. Irwan Endrayanto A., S.Si., M.Sc.

2025 | Skripsi | MATEMATIKA

Dial-a-Ride Problem (DARP) merupakan permasalahan transportasi yang bertujuan untuk merancang rute perjalanan dengan biaya minimal dengan memperhatikan kenyamanan penumpang. Skripsi ini menyajikan penerapan algoritma Branch-and-Cut untuk menyelesaikan DARP yang diformulasikan dalam bentuk Mixed-Integer Linear Programming (MILP). Algoritma Branch-and-Cut diperkuat dengan teknik pengurangan ukuran masalah serta penambahan berbagai cuts yang disebut pertidaksamaan valid untuk mempercepat pencarian solusi. Sebagai implementasinya, disajikan penyelesaian studi kasus DARP dengan algoritma Branch-and-Cut menggunakan bahasa pemrograman Python dan solver Gurobi. Hasil penelitian menunjukkan bahwa algoritma Branch-and-Cut mampu memberikan solusi yang optimal pada DARP, yaitu rute perjalanan dengan biaya dan waktu tempuh minimal.

The Dial-a-Ride Problem (DARP) is a transportation optimization problem that aims to design vehicle routes at a minimal cost while adhering to passenger convenience constraints. This thesis presents the application of the Branch-and-Cut algorithm to solve the DARP, which is formulated as a Mixed-Integer Linear Programming (MILP) model. The Branch-and-Cut algorithm is enhanced with problem size reduction techniques and the addition of various cuts, known as valid inequalities, to accelerate the solution search. For the implementation, the algorithm is used to solve a DARP case study utilizing the Python programming language and the Gurobi solver. The results demonstrate that the Branch-and-Cut algorithm successfully provides an optimal solution for the DARP, yielding routes with minimal cost and travel time.

Kata Kunci : algoritma, branch-and-cut, dial-a-ride, DARP, transportasi