Metode Pengembangan Pendekatan Metaheuristik dalam Menyelesaikan Optimisasi Kombinatorial

Abstract

Combinatorial optimization problems arise, in many forms, in various aspects of everyday life. Nowadays, a lot of services are driven by optimization algorithms, enabling us to make the best use of the available resources while guaranteeing a level of service. Examples of such services are public transportation, vehicle routing problems for goods delivery, university time-tabling, and patient scheduling.Metaheuristic approcah to solve combinatorial optimization problem is a rapidly developing field of research. This is due to the completeness of the Non Polinomial condition of many combinatorial optimization problems and the increasing importance of combinatorial optimization problems in industrial world. Combinatorial problems are so challenging because they are easy to state however very difficult to solve New approaches, and new mathematical insights, on combinatorial optimization have been developed in this disertation. The proposed algorithm starts with obtaining feasible areas to solve combinatorial optimization problems, i.e. areas that are constrained by problem constraints after relaxation. Then we explore the feasible area to identify an area which contain an optimal feasible integer solution.The exploration for finding a feasible integer solution is based on the movement of nonbasic variables from their bounds. The proposed approach is further tested in the model examples and optimization tests for Vehicle Routing Problems. The results show that the proposed method can be used to solve a large scale combinatorial optimization problems efficiently.

Masalah optimisasi kombinatorial muncul, dalam banyak bentuk, dalam berbagai aspek kehidupan sehari-hari. Saat ini, banyak layanan didorong oleh algoritma pengoptimalan, memungkinkan penulis untuk memanfaatkan sumber daya yang tersedia dengan sebaik-baiknya sambil menjamin tingkat layanan. Contoh layanan tersebut adalah transportasi umum, masalah perutean kendaraan untuk pengiriman barang, jadwal dan waktu universitas, dan penjadwalan pasien. Pendekatan mistereuristik untuk menyelesaikan masalah optimisasi kombinatorial adalah bidang penelitian yang berkembang pesat. Hal ini disebabkan oleh kelengkapan kondisi Non Polinomial dari banyak masalah optimisasi kombinatorial dan semakin pentingnya masalah optimisasi kombinatorial dalam dunia industri. Masalah kombinatorial sangat menantang karena mudah dinyatakan tetapi sangat sulit untuk menyelesaikan pendekatan baru, dan wawasan matematis baru, pada optimasi kombinatorial telah dikembangkan dalam disertasi ini. Algoritma yang diusulkan dimulai dengan memperoleh area yang layak untuk menyelesaikan masalah optimisasi kombinatorial, yaitu area yang dibatasi oleh kendala masalah setelah relaksasi. Kemudian penulis menjelajahi area yang layak untuk mengidentifikasi area yang berisi solusi integer layak yang optimal. Eksplorasi untuk menemukan solusi integer yang layak didasarkan pada pergerakan variabel non-dasar dari batas-batasnya. Pendekatan yang diusulkan diuji lebih lanjut dalam contoh model dan tes optimisasi untuk Masalah Rute Kendaraan. Hasil menunjukkan bahwa metode yang diusulkan dapat digunakan untuk menyelesaikan masalah optimasi kombinatorial skala besar secara efisien.