Algoritma Simulated Annealing untuk Menentukan Rute Kendaraan Heterogen (Studi Kasus)

Penulis

Andriansyah Andriansyah, Rizky Novatama, Prima Denny Sentia

Abstrak

Permasalahan transportasi dalam supply chain management sangat penting untuk dikaji karena dapat menimbulkan biaya logistik yang sangat besar. Salah satu cara untuk mengurangi biaya transportasi adalah dengan penentuan rute kendaraan atau dikenal dengan istilah vehicle routing problem. Objek yang menjadi kajian merupakan perusahaan yang bergerak pada bidang distribusi produk untuk area kota Banda Aceh dan sekitarnya. Dalam proses distribusi, perusahaan ini menggunakan dua jenis kendaraan dengan kapasitas dan biaya operasional yang berbeda sehingga permasalahan menjadi heterogeneous fleet vehicle routing problem. Penentuan rute kendaraan dalam penelitian ini dilakukan dengan tiga metode, yaitu metode analitik, algoritma insertion heuristic sebagai metode heuristik, dan algoritma simulated annealing sebagai metode metaheuristik. Berdasarkan hasil yang diperoleh dari data ujicoba, algoritma simulated annealing merupakan algoritma yang paling baik dalam menyelesaikan permasalahan. Secara rata-rata, algoritma simulated annealing dapat menghasilkan kualitas solusi yang sama dengan metode analitik, namun dengan waktu komputasi yang lebih singkat. Selain itu, algoritma simulated annealing menghasilkan kualitas solusi yang lebih baik dibandingkan algoritma insertion heuristic yang dikembangkan dalam penelitian dan dapat meningkatkkan kualitas solusi sebesar 20,18% dari penelitian sebelumnya dengan waktu komputasi 19,27 detik.

 

Abstract

Transportation problems in supply chain are very important to be discussed because they can raises enormous logistic cost. Route determination of the vehicles known as vehicle routing problem is the one of ways to reduce transportation cost. The object discussed in this study is the distribution company for Banda Aceh city and its surroundings. The company uses two types of vehicle to distribute the product for customers. The differences each vehicle are vehicle capacity and operational cost. To cover these differences, the problem becomes heterogenous fleet vehicle routing problem. The study uses three methods to solve the problem. Analitycal method, insertion heuristic algorithm as heuristic method and simulated annealing algorithm as metaheuristic method are the methods used. According to the results, simulated anneling algorithm produces the better solutions than two others. On average, solutions produced by simulated annealing algorithm from dataset have same quality with analitycal method, but with faster computation. Furthermore, simulated anneling algorithm produces better quality of solutions than insertion heuristic algorithm both from this study and previous study. The solution improves 20,18% with computation time 19,27 seconds.

 


 

Teks Lengkap:

PDF

Referensi


AFIFI, S., DANG, D.-C. AND MOUKRIM, A. 2013. A Simulated Annealing Algorithm for the Vehicle Routing Problem with Time Windows and Synchronization Constraints. Regional Council of Picardie and the European Regional Development Fund, pp. 259–265.

ANDRIANSYAH dan SENTIA, P. D., 2018. Penentuan Rute Kendaraan Pada Sistem Distribusi Logistik Pasca Bencana (Studi Kasus). Jurnal Manajemen Industri dan Logistik, 2(1), pp. 75–83.

BIRIM, Ş., 2016. Vehicle Routing Problem with Cross Docking: A Simulated Annealing Approach. Procedia - Social and Behavioral Sciences, 235(October), pp. 149–158.

BORADE, A. B. dan BANSOD, S. V., 2007. Domain Of Supply Chain Management - A State Of Art. Journal of Technology Management & Innovation, 2(4), pp. 109–121.

CAMPBELL, A. M. dan SAVELSBERGH, M., 2004. Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems. Transportation Science, 38(3), pp. 369–378.

CARIC, T. AND GOLD, H., 2008. Vehicle Routing Problem. In-Teh.

DELL’AMICO, M. ET AL., 2007. Heuristic Approaches for the Fleet Size and Mix Vehicle Routing Problem with Time Windows. Transportation Science, 41(4), pp. 516–526.

DULLAERT, W. ET AL., 2002. New heuristics for the Fleet Size and Mix Vehicle Routing Problem with Time Windows. Journal of the Operational Research Society, 53(11), pp. 1232–1238.

ELHADDAD, Y. R., 2012. Combined Simulated Annealing and Genetic Algorithm to Solve Optimization Problems. International Journal of Computer, Electrical, Automation, Control and Information Engineering, 6(8), pp. 1047–1049.

GENDREAU, M. dan POTVIN, J. Y., 2010. Handbook of Metaheuristics. 2nd edn. Springer.

HOFF, A. ET AL., 2010. Industrial aspects and literature survey: Fleet composition and routing. Computers and Operations Research. Elsevier, 37(12), pp. 2041–2061.

IMRAN, A., SALHI, S. AND WASSAN, N. A., 2009. A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem. European Journal of Operational Research. Elsevier B.V., 197(2), pp. 509–518.

KOÇ, Ç. ET AL., 2015. Thirty years of heterogeneous vehicle routing. European Journal of Operational Research, pp. 1–21.

LEUNG, S. C. H. ET AL., 2013. A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints. European Journal of Operational Research. Elsevier B.V., 225(2), pp. 199–210.

PUJAWAN, I. N. dan ER, M., 2017. Supply Chain Management. 3rd edn. ANDI Yogyakarta.

SAPUTRA, N., SENTIA, P. D., ANDRIANSYAH, 2017. Penentuan Rute Kendaraan Heterogen Menggunakan Algoritma Insertion Heuristic. Jurnal Optimasi Sistem Industri.

TALBI, E.-G., 2009. Metaheuristics From Design To Implementatiton. A John Wiley & Sons, Inc.

WIBISONO, E., 2015. Pengembangan heuristik pada kasus heterogeneous vehicle routing problems with time windows and fixed costs. pp. 22–34.

WIRDIANTO, E., JONRINALDI AND SURYA, B., 2007. Penerapan Algoritma Simulated Annealing pada Penjadwalan Distribusi Produk. Jurnal Optimasi Sistem Industri, 7(1), pp. 7–20.

YU, V. F. ET AL., 2017. A simulated annealing heuristic for the hybrid vehicle routing problem. Applied Soft Computing Journal. Elsevier B.V., 53, pp. 119–132.




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