Hibridisasi Algoritma Genetika Dengan Variable Neighborhood Search (VNS) Pada Optimasi Biaya Distribusi

Penulis

Asyrofa Rahmi, Wayan Firdaus Mahmudy, Syaiful Anam

Abstrak

Abstrak

Proses distribusi dianggap sangat penting bagi perusahaan karena menjadi salah satu faktor yang mempengaruhi perolehan keuntungan. Besarnya biaya yang dikeluarkan serta kompleksnya permasalahan dalam proses distribusi menjadikan permasalahan distribusi sebagai topik yang perlu diteliti lebih mendalam lagi. Karena algoritma genetika (AG) sudah terbukti mampu memberikan solusi terbaik pada berbagai macam permasalahan optimasi dan kombinatorial, maka algoritma ini digunakan untuk menyelesaikan permasalahan distribusi pada penelitian ini. Namun, penerapan GA klasik memiliki kekurangan yaitu belum mencapai titik optimum global sehingga perlu dihibridisasi menggunakan algoritma variable neighborhood search (VNS). Algoritma ini dipilih karena selain mencari solusi secara global, algoritma ini juga mencari solusi secara lokal sehingga mampu menutupi kekurangan dari GA. Dengan menggunakan hibridisasi GA dengan VNS maka biaya yang diperoleh adalah 32392960 yang dibuktikan dengan penghematan biaya sebesar 323190 jika dibandingkan dengan GA klasik yaitu 32716150. Namun, dilihat dari waktu komputasi, GA-VNS membutuhkan waktu yang relatif sama dengan GA klasik yaitu 279332 ms (milisecond) dan 265091 ms.

Kata kunci: distribusi, algoritma genetika, variable neighborhood search


Abstract

The distribution process is considered importantly for the company as one of the factors that affects profitability. The costs incurred as well as the complexity of the distribution problems makes the distribution problems as a topic that need to be examined more deeply. Since the wide range of combinatorial and optimization problems have been ever solved by using genetic algorithm (GA) well then it is used to resolve the distribution problems in this study. However, the implementation of classical GA has the disadvantage that has not yet reached the global optimum so that needs to be hybridized by using variable neighborhood search (VNS) algorithm. The VNS algorithm has been chosen because its ability either to search the global solutions or local solutions. The local search of VNS algorithm is able to cover the shortage of the GA. By using hibridization of GA with VNS, the cost accrued is 32392960 as evidenced by cost savings of 323190 in comparison with the classical GA is 32716150. However, the computational time of GA-VNS is equal to its classical GA relatively.

Keywords: distribution, genetic algorithm, variable neighborhood search

Teks Lengkap:

PDF (English)

Referensi


ARORA, J.S. & ARORA, J.S., 2012. Chapter 16 – Genetic Algorithms for Optimum Design, Elsevier Inc.

BOUDJELABA, K., ROS, F. & CHIKOUCHE, D., 2014. An efficient hybrid genetic algorithm to design finite impulse response filters. Expert Systems With Applications, 41(13), pp.5917–5937. Available at: http://dx.doi.org/10.1016/j.eswa.2014.03.034.

CASTELLI, M. & VANNESCHI, L., 2014. Genetic algorithm with variable neighborhood search for the optimal allocation of goods in shop shelves. Operations Research Letters, 42(5), pp.355–360. Available at: http://dx.doi.org/10.1016/j.orl.2014.06.002.

CHEIKH, M. DKK., 2015. A variable neighborhood search algorithm for the vehicle routing problem with multiple trips. Electronic Notes In Discrete Mathematics, 47, pp.277–284. Available at: http://dx.doi.org/10.1016/j.endm.2014.11.036.

CHEN, Z.-Q. & WANG, R.-L., 2011. Solving the m-way graph partitioning problem using a genetic algorithm. Ieej Transactions On Electrical And Electronic Engineering, 6(5), pp.483–489. Available at: http://doi.wiley.com/10.1002/tee.20685.

GICQUEL, C. & MINOUX, M., 2015. Multi-product valid inequalities for the discrete lot-sizing and scheduling problem. Computers And Operation Research, 54, pp.12–20. Available at: http://dx.doi.org/10.1016/j.cor.2014.08.022.

GUO, H., WANG, X. & ZHOU, S., 2015. A Transportation Problem with Uncertain Costs and Random Supplies. International Journal Of E-Navigation And Maritime Economy, 2, pp.1–11. Available at: http://www.sciencedirect.com/science/article/pii/S2405535215000558.

GUPTA, A. DKK., 2012. A Comparative Study of Three Echelon Inventory Optimization using Genetic Algorithm and Particle Swarm Optimization. International Journal Of Trade, Economics And Finance, 3(3), pp.205–208.

JIAO, R. DKK., 2014. A Multistage Multiobjective Substation Siting and Sizing Model Based on Operator-Repair Genetic Algorithm. Ieej Transactions On Electrical And Electronic Engineering, 9, pp.S28--S36.

KIM, S.H. & LEE, Y.H., 2016. Synchronized production planning and scheduling in semiconductor fabrication. Computers & Industrial Engineering, 96, pp.72–85. Available at: http://dx.doi.org/10.1016/j.cie.2016.03.019.

LANGROODI, R.R.P. & AMIRI, M., 2016. A system dynamics modeling approach for a multi-level, multi-product, multi-region supply chain under demand uncertainty. Expert Systems With Applications, 51, pp.231–244. Available at: http://dx.doi.org/10.1016/j.eswa.2015.12.043.

MAHMUDY, W.F., 2015. Optimization of Part Type Selection and Machine Loading Problems in Flexible Manufacturing System Using Variable Neighborhood Search. Iaeng International Journal Of Computer Science, 42(3).

MAHMUDY, W.F., MARIAN, R.M. & LUONG, L.H.S., 2014. Hybrid Genetic Algorithms for Part Type Selection and Machine Loading Problems with Alternative Production Plans in Flexible Manufacturing System. Ecti Transaction On Computer And Information Technology, 8(1), pp.80–93.

MAHMUDY, W.F., MARIAN, R.M. & LUONG, L.H.S., 2013. Modeling and Optimization of Part Type Selection and Loading Problem in Flexible Manufacturing System Using Real Coded Genetic Algorithms. International Journal Of Electrical, Computer, Electronics And Communication Engineering, 7(4), pp.251–260.

MLADENOVIC, N., UROSEVIC, D. & PEREZ-BRIT, D., 2016. Variable Neighborhood Search for Minimum Linear Arrangement Problem. Yugoslav Journal Of Operations Research, 26(1), pp.3–16.

QIONGBING, Z., 2016. A New Crossover Mechanism for Genetic Algorithms with Variable-length Chromosomes for Path Optimization Problems. Expert Systems With Applications, 60, pp.183–189. Available at: http://dx.doi.org/10.1016/j.eswa.2016.04.005.

RAHMI, A., SARWANI, M.Z. & MAHMUDY, W.F., 2017. Genetic Algorithms for Optimization of Multi-Level Product Distribution. Accepted to International Journal Of Intelligent Engineering & Systems.

SARWANI, M.Z., RAHMI, A. & MAHMUDY, W.F., 2017. An Adaptive Genetic Algorithm for Cost Optimization of Multi-Stage Supply Chain. Accepted to Journal Of Telecommunication, Electronic And Computer Engineering.

SITEK, P. & WIKAREK, J., 2012. Mathematical programming model of cost optimization for supply chain from perspective of logistics provider. Management And Production Engineering Review, 3(2), pp.49–61.

SONI, N. & KUMAR, T., 2014. Study of Various Mutation Operators in Genetic Algorithms. International Journal Of Computer Science And Information Technology, 5(3), pp.4519–4521.

THAKUR, M. & KUMAR, A., 2016. Electrical Power and Energy Systems Optimal coordination of directional over current relays using a modified real coded genetic algorithm : A comparative study. International Journal Of Electrical Power And Energy Systems, 82, pp.484–495. Available at: http://dx.doi.org/10.1016/j.ijepes.2016.03.036.

ZIEBUHR, M. & KOPFER, H., 2016. Solving an integrated operational transportation planning problem with forwarding limitations. Transportation Research Part E: Logistics And Transportation Review, 87, pp.149–166. Available at: http://dx.doi.org/10.1016/j.tre.2016.01.006.




DOI: http://dx.doi.org/10.25126/jtiik.201742287