Optimization of Inspection Routes Using Linear Programming & Nearest Neighbour at KJPP ANA & Rekan Gianyar
DOI:
https://doi.org/10.51278/bse.v4i1.1155Keywords:
Linear programming, Nearest neighbor, Route optimization, Traveling salesman problemAbstract
Inspection is the activity procedures of an appraiser identical with survey to the location of the object of assessment. Considering efficient KJPP ANA & Rekan Gianyar is important for determining the best route in order to reduce overtime. This research focused in optimizing the inspection case route to the location using Linear Programming (LP) and Nearest Neighbor (NN) for Traveling Salesman Problem cases. In addition, analyzing the comparison of the initial route and the new route with both methods after optimizing travel time to reduce overtime. This research combined set theory and distribution & transportation concepts in the optimization. The data in this research used primary data including initial route along with the coordinates and secondary includes company profiles, LP and NN algorithms collected through interviews, documentation and literature study. The collected data were processed with Microsoft Excel and Google Colaboratory software. The results found that the LP method minimized travel time savings by an average of 12%, while the NN method is 8%. The LP method minimized the average overtime and costs by 16 minutes (Rp. 13,000, -) while the NN method is 11 minutes (Rp. 9,000, -).
Keywords: Linear programming, Nearest neighbor, Route optimization, Traveling salesman problem
References
Andriansyah, M. V., Darajatun, R. A., & Rinaldi, D. N. (2021). Optimalisasi Pendistribusian Dengan Metode Travelling Salesman Problem Untuk Menentukan Rute Terpendek Di Pt Xyz. Tekmapro: Journal of Industrial Engineering and Management, 16(02), 84–95.
Baik, H., & Valenzuela, J. (2020). An optimization drone routing model for inspecting wind farms. Soft Computing, 6(1), 1–16. https://doi.org/10.1007/s00500-020-05316-6
Bulut, F., & Erol, M. H. (2018). A Real-Time Dynamic Route Control Approach on Google Maps using Integer Programming Methods. International Journal of Next-Generation Computing, 9(3), 190–200.
Chowdhury, S., Shahvari, O., Marufuzzaman, M., & Li, X. (2021). Computers & Industrial Engineering Drone routing and optimization for post-disaster inspection. Computers & Industrial Engineering, 159(October 2020), 107495. https://doi.org/10.1016/j.cie.2021.107495
Dio, R., & Dermawan, A. A. (2023). Optimalisasi Jumlah Permintaan dan Produksi CV. XYZ Menggunakan Software Simulasi Flexsim. Journal of Industrial and Manufacture Engineering, 7(1), 59–68.
Dyah, K. (2014). Peranan Manajemen Logistik dalam Organisasi Publik. In Modul 1 (pp. 1–50).
Fadhlurrahman, M. G., & Binatari, N. (2019). Masalah Transshipment untuk Penentuan Rute Distribusi BBM di Kabupaten Klaten. Seminar Matematika Dan Pendidikan Matematika Uny 2019.
Fauzi, A. A., & Sulistyono, E. (2022). Traveling Salesman Problem Dalam Menyelesaikan Rute Optimal Pengiriman Air Minum Isi Ulang. Jurnal Sintak, 1(1), 31–38.
Junaidi, A., Sasono, E., Wanuri, W., & Emiyati, D. W. (2020). The effect of overtime, job stress, and workload on turnover intention. Management Science Letters, 10(16), 3873–3878. https://doi.org/10.5267/j.msl.2020.7.024
Katagiri, H., Guo, Q., Wu, H., & Hamori, H. (2016). A Route Optimization Problem in Electrical PCB Inspections?: Pickup and Delivery TSP-Based Formulation. Transactions on Engineering Technologies, 3(1), 193–205. https://doi.org/10.1007/978-981-10-0551-0
Lusiani, A., Purwaningsih, S. S., Sartika, E., Bandung, P. N., & Bandung, P. N. (2023). TSP METHOD USING NEAREST NEIGHBOR ALGORITHM AT PT. J & T EXPRESS IN BANDUNG. Lebesgue: JurnalIlmiahPendidikan Matematika, Matematika Dan Statistika, 4(3), 1560–1568. https://doi.org/0.46306/lb.v4i3.449
Mandagi, M. S., & Ilat, V. (2015). Evaluasi penerapan sistem akuntansi penggajian pada kantor jasa penilaian publik benedictus darmapuspita dan rekan di Jakarta. Jurnal EMBA, 3(2), 840–851.
Mazin, A., Mohammed, A., Abd, M. K., Hamed, R. I., Mostafa, S. A., Ibrahim, A., Jameel, H. K., Hamed, A., Hamed, R. I., Mostafa, S. A., & Ibrahim, D. A. (2017). Solving Vehicle Routing Problem by Using Improved K-Nearest Neighbor Algorithm for Best. Journal of Computational Science, 10(1), 1–21. https://doi.org/10.1016/j.jocs.2017.04.012
Negara, R. M., Mayasari, R., & Syambas, N. R. (2023). Performance Comparison of SOM and ACO for Travelling Salesman Problem-Case Study on the Indonesia Palapa Ring Network. Journal of Communications, 18(2), 109–115. https://doi.org/10.12720/jcm.18.2.109-115
Paillin, D. B., & Tupan, J. M. (2020). Model Integer Liniear Programming (Ilp) Dalam Pemecahan Traveling Salesman Problem (Tsp) (Studi Kasus?: Pt. Paris Jaya Mandiri – Ambon). ALE Proceeding, 3, 40–47. https://doi.org/10.30598/ale.3.2020.40-47
Paillin, D. B., Tupan, J. M., & Lasamahu, I. (2020). Optimasi Rute Pendistribusian Bahan Bakar Minyak (BBM) Pada PT. Pertamina Region IVc UPMS VIII -Ambon. Seminar Dan Konferensi Nasional IDEC 2020, 0(November), 1–9.
Peker, M., ?en, B., & Kumru, P. Y. (2013). An efficient solving of the traveling salesman problem: The ant colony system having parameters optimized by the Taguchi method. Turkish Journal of Electrical Engineering and Computer Sciences, 21(SUPPL. 1), 2015–2036. https://doi.org/10.3906/elk-1109-44
Ruffinelli, D., & Barán, B. (2017). Linear nearest neighbor optimization in quantum circuits?: a multiobjective perspective. Quantum Information Processing, 16(1), 1–26. https://doi.org/10.1007/s11128-017-1662-3
Septo, D., Suparji, & Rifai, A. (2022). Kepastian hukum jasa penilai publik di Indonesia. Jurnal Hukum Dan Kesejahteraan Universitas Al Azhar Indonesia, 7(2), 14–29.
Setiyawan, Y. (2017). Penentuan rute optimal distribusi produk dengan metode traveling salesman problem (tsp) (studi kasus?: pt. ppi surakarta). universitas muhammadiyah surakarta, 01, 1–7.
Taiwo, O. S., Josiah, O., Taiwo, A., Dkhrullahi, S., & Sade, O. K. (2013). Implementation of heuristics for solving travelling salesman problem using nearest neighbour and nearest insertation approaches. International Journal of Advnce Research, 1(3), 140–154.
Waskito, M., & Sari, N. K. (2022). Pengaruh lingkungan kerja dan kompensasi terhadap loyalitas karyawan. KINERJA: Jurnal Ekonomi Dan Bisnis, 4(2), 123–136.
Wibisono, E. (2018). Logika Logistik; Teknik dan Metode Pemrograman dalam Problem-problem Pengaturan Rute (1st ed.). Graha Ilmu.
Windyatri, H., & Rayendra, R. (2023). Optimasi rute pengiriman BBM dengan Heterogeneous Vehicle Routing Problem With Multi-Trips. G-Tech: Jurnal Teknologi Terapan, 7(3), 1100–1109.
Yu, D., Tao, Y., & Ma, Y. (2022). Solving TSP Problems with Integer Programming. Journal of Physics: Conference Series, 2381(1). https://doi.org/10.1088/1742-6596/2381/1/012045
Zhou, Y., Luo, Q., Chen, H., He, A., & Wu, J. (2015). A discrete invasive weed optimization algorithm for solving traveling salesman problem. Neurocomputing, 151(P3), 1227–1236. https://doi.org/10.1016/j.neucom.2014.01.078
Baik, H., & Valenzuela, J. (2020). An optimization drone routing model for inspecting wind farms. Soft Computing, 6(1), 1–16. https://doi.org/10.1007/s00500-020-05316-6
Bulut, F., & Erol, M. H. (2018). A Real-Time Dynamic Route Control Approach on Google Maps using Integer Programming Methods. International Journal of Next-Generation Computing, 9(3), 190–200.
Chowdhury, S., Shahvari, O., Marufuzzaman, M., & Li, X. (2021). Computers & Industrial Engineering Drone routing and optimization for post-disaster inspection. Computers & Industrial Engineering, 159(October 2020), 107495. https://doi.org/10.1016/j.cie.2021.107495
Dio, R., & Dermawan, A. A. (2023). Optimalisasi Jumlah Permintaan dan Produksi CV. XYZ Menggunakan Software Simulasi Flexsim. Journal of Industrial and Manufacture Engineering, 7(1), 59–68.
Dyah, K. (2014). Peranan Manajemen Logistik dalam Organisasi Publik. In Modul 1 (pp. 1–50).
Fadhlurrahman, M. G., & Binatari, N. (2019). Masalah Transshipment untuk Penentuan Rute Distribusi BBM di Kabupaten Klaten. Seminar Matematika Dan Pendidikan Matematika Uny 2019.
Fauzi, A. A., & Sulistyono, E. (2022). Traveling Salesman Problem Dalam Menyelesaikan Rute Optimal Pengiriman Air Minum Isi Ulang. Jurnal Sintak, 1(1), 31–38.
Junaidi, A., Sasono, E., Wanuri, W., & Emiyati, D. W. (2020). The effect of overtime, job stress, and workload on turnover intention. Management Science Letters, 10(16), 3873–3878. https://doi.org/10.5267/j.msl.2020.7.024
Katagiri, H., Guo, Q., Wu, H., & Hamori, H. (2016). A Route Optimization Problem in Electrical PCB Inspections?: Pickup and Delivery TSP-Based Formulation. Transactions on Engineering Technologies, 3(1), 193–205. https://doi.org/10.1007/978-981-10-0551-0
Lusiani, A., Purwaningsih, S. S., Sartika, E., Bandung, P. N., & Bandung, P. N. (2023). TSP METHOD USING NEAREST NEIGHBOR ALGORITHM AT PT. J & T EXPRESS IN BANDUNG. Lebesgue: JurnalIlmiahPendidikan Matematika, Matematika Dan Statistika, 4(3), 1560–1568. https://doi.org/0.46306/lb.v4i3.449
Mandagi, M. S., & Ilat, V. (2015). Evaluasi penerapan sistem akuntansi penggajian pada kantor jasa penilaian publik benedictus darmapuspita dan rekan di Jakarta. Jurnal EMBA, 3(2), 840–851.
Mazin, A., Mohammed, A., Abd, M. K., Hamed, R. I., Mostafa, S. A., Ibrahim, A., Jameel, H. K., Hamed, A., Hamed, R. I., Mostafa, S. A., & Ibrahim, D. A. (2017). Solving Vehicle Routing Problem by Using Improved K-Nearest Neighbor Algorithm for Best. Journal of Computational Science, 10(1), 1–21. https://doi.org/10.1016/j.jocs.2017.04.012
Negara, R. M., Mayasari, R., & Syambas, N. R. (2023). Performance Comparison of SOM and ACO for Travelling Salesman Problem-Case Study on the Indonesia Palapa Ring Network. Journal of Communications, 18(2), 109–115. https://doi.org/10.12720/jcm.18.2.109-115
Paillin, D. B., & Tupan, J. M. (2020). Model Integer Liniear Programming (Ilp) Dalam Pemecahan Traveling Salesman Problem (Tsp) (Studi Kasus?: Pt. Paris Jaya Mandiri – Ambon). ALE Proceeding, 3, 40–47. https://doi.org/10.30598/ale.3.2020.40-47
Paillin, D. B., Tupan, J. M., & Lasamahu, I. (2020). Optimasi Rute Pendistribusian Bahan Bakar Minyak (BBM) Pada PT. Pertamina Region IVc UPMS VIII -Ambon. Seminar Dan Konferensi Nasional IDEC 2020, 0(November), 1–9.
Peker, M., ?en, B., & Kumru, P. Y. (2013). An efficient solving of the traveling salesman problem: The ant colony system having parameters optimized by the Taguchi method. Turkish Journal of Electrical Engineering and Computer Sciences, 21(SUPPL. 1), 2015–2036. https://doi.org/10.3906/elk-1109-44
Ruffinelli, D., & Barán, B. (2017). Linear nearest neighbor optimization in quantum circuits?: a multiobjective perspective. Quantum Information Processing, 16(1), 1–26. https://doi.org/10.1007/s11128-017-1662-3
Septo, D., Suparji, & Rifai, A. (2022). Kepastian hukum jasa penilai publik di Indonesia. Jurnal Hukum Dan Kesejahteraan Universitas Al Azhar Indonesia, 7(2), 14–29.
Setiyawan, Y. (2017). Penentuan rute optimal distribusi produk dengan metode traveling salesman problem (tsp) (studi kasus?: pt. ppi surakarta). universitas muhammadiyah surakarta, 01, 1–7.
Taiwo, O. S., Josiah, O., Taiwo, A., Dkhrullahi, S., & Sade, O. K. (2013). Implementation of heuristics for solving travelling salesman problem using nearest neighbour and nearest insertation approaches. International Journal of Advnce Research, 1(3), 140–154.
Waskito, M., & Sari, N. K. (2022). Pengaruh lingkungan kerja dan kompensasi terhadap loyalitas karyawan. KINERJA: Jurnal Ekonomi Dan Bisnis, 4(2), 123–136.
Wibisono, E. (2018). Logika Logistik; Teknik dan Metode Pemrograman dalam Problem-problem Pengaturan Rute (1st ed.). Graha Ilmu.
Windyatri, H., & Rayendra, R. (2023). Optimasi rute pengiriman BBM dengan Heterogeneous Vehicle Routing Problem With Multi-Trips. G-Tech: Jurnal Teknologi Terapan, 7(3), 1100–1109.
Yu, D., Tao, Y., & Ma, Y. (2022). Solving TSP Problems with Integer Programming. Journal of Physics: Conference Series, 2381(1). https://doi.org/10.1088/1742-6596/2381/1/012045
Zhou, Y., Luo, Q., Chen, H., He, A., & Wu, J. (2015). A discrete invasive weed optimization algorithm for solving traveling salesman problem. Neurocomputing, 151(P3), 1227–1236. https://doi.org/10.1016/j.neucom.2014.01.078
Downloads
Published
2024-05-17
How to Cite
Canigia Susila, N. M. A., Penindra, I. M. D. B., Utami, N. M. C., Ariyani, N. W. S., Juliana, M., & Sitanggang, B. E. I. (2024). Optimization of Inspection Routes Using Linear Programming & Nearest Neighbour at KJPP ANA & Rekan Gianyar. Bulletin of Science Education, 4(1), 364–378. https://doi.org/10.51278/bse.v4i1.1155
Issue
Section
Articles
