Reduced-Cost Vogel Method (RVM) Berbasis Reduksi Zero-Point untuk Konstruksi Initial Basic Feasible Solution pada Balanced Transportation Problem

Rakhim, Muhammad Rayyaan Fatikhahur (2026) Reduced-Cost Vogel Method (RVM) Berbasis Reduksi Zero-Point untuk Konstruksi Initial Basic Feasible Solution pada Balanced Transportation Problem. Other thesis, InstitutTeknologi Sepuluh Nopember.

Text 5025221047-Undergraduate_Thesis.pdf - Accepted Version Download (2MB)

Abstract

Transportation Problem (TP) merupakan permasalahan optimisasi fundamental dalam supply chain management yang bertujuan meminimalkan biaya distribusi dengan kendala supply dan demand. Solusi diperoleh melalui dua tahap, yaitu penentuan Initial Basic Feasible Solution (IBFS) menggunakan metode heuristik, kemudian dioptimasi menggunakan Modified Distribution method. Vogel’s Approximation Method (VAM) merupakan metode IBFS klasik terbaik, namun penalty-nya dihitung dari matriks biaya asli sehingga prioritas alokasi dapat menjadi kurang tepat. Penelitian ini mengembangkan Reduced-cost Vogel Method (RVM), yaitu metode konstruksi IBFS satu-langkah yang menghitung penalty Vogel pada matriks hasil reduksi zeropoint. Reduksi tersebut membentuk pasangan dual layak sehingga entri matriks menjadi reduced cost, dan penalty yang dihitung di atasnya menjadi ukuran regret yang berlandaskan teori dualitas, sementara metode tetap deterministik dan berjalan dalam satu lintasan tanpa langkah penyempurnaan. Evaluasi pada 42 kasus benchmark menunjukkan RVM mencapai 38 kasus optimal (90,48%) dengan deviasi rata-rata 0,40%, melampaui tujuh metode pembanding pada kondisi pengujian identik, yaitu VAM (52,38%), TOCM-MT (61,90%), BCE (69,05%), JHMM (73,81%), SSM (73,81%), CSM (78,57%), dan RBSM (80,95%). Studi ablasi terhadap 15 fungsi penalty mengonfirmasi bahwa keunggulan utama berasal dari reduksi zero-point, bukan bentuk fungsi penalty. Pengujian tambahan pada 667 kasus di luar benchmark utama beserta metode pembanding kedelapan (Improved Heuristic Weight, IHW) menunjukkan bahwa keunggulan RVM berkorelasi dengan kepadatan twin cost pada struktur data yang diujikan, sejalan dengan No Free Lunch Theorem. Dengan demikian, RVM menyediakan solusi awal berkualitas tinggi dengan biaya komputasi yang rendah dan landasan matematis yang kuat.
=======================================================================================================================================
The Transportation Problem (TP) is a fundamental optimization problem in supply chain management that aims to minimize distribution costs subject to supply and demand constraints. Solutions are obtained in two stages: determining the Initial Basic Feasible Solution (IBFS) using a heuristic method, then optimizing it using the Modified Distribution method. Vogel's Approximation Method (VAM) is the best classical IBFS method, but its penalty is computed from the original cost matrix, which can make allocation priorities inaccurate. This research develops the Reduced-cost Vogel Method (RVM), a single-pass IBFS construction method that computes the Vogel penalty on a zero-point reduced matrix. The reduction forms a feasible dual pair so that the matrix entries become reduced costs, and the penalty computed on it becomes a regret measure grounded in duality theory, while the method remains deterministic and runs in a single pass without any refinement step. Evaluation on 42 benchmark cases shows that RVM reaches 38 optimal cases (90.48%) with an average deviation of 0.40%, surpassing seven comparison methods under identical testing conditions, namely VAM (52.38%), TOCMMT (61.90%), BCE (69.05%), JHM-M (73.81%), SSM (73.81%), CSM (78.57%), and RBSM (80.95%). An ablation study of 15 penalty functions confirms that the main advantage comes from the zero-point reduction rather than the penalty form. Additional testing on 667 cases beyond the main benchmark, together with an eighth comparison method (Improved Heuristic Weight, IHW), shows that RVM's advantage correlates with the density of tied costs in the tested data structure, consistent with the No Free Lunch Theorem. RVM therefore provides a high-quality initial solution at a low computational cost with a strong mathematical foundation.

Item Type:	Thesis (Other)
Subjects:	T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Muhammad Rayyaan Fatikhahur Rakhim
Date Deposited:	29 Jul 2026 03:10
Last Modified:	29 Jul 2026 03:10
URI:	http://repository.its.ac.id/id/eprint/139456

Actions (login required)

View Item