OPTIMIZING CARTON PRODUCT DELIVERY BY SOLVING TRAVELLING SALESMAN PROBLEM AT PACKAGING COMPANIES
Abstract
Optimization of delivery routes is one form of increasing business productivity to achieve the company's main goal of distributing each product to customers. The Traveling Salesman Problem (TSP) is a combinatorial optimization problem where a salesman goes on a distribution journey that starts from the depot, then visits all customers exactly once, and ends with returning to the depot. This study aims to optimize the distribution route of carton products for packaging companies using the TSP model. The research methodology includes observation, interviews, and document studies to understand the distribution process of carton products at packaging companies. To complete the TSP model, Branch and Bound (BB) and Nearest Neighbor (NN) methods are applied to find the best solution for determining the distribution route of carton products. The way the BB method works is by utilizing branch cuts and boundaries to reduce search space and speed up the resolution process. In the NN method, the nearest point is chosen to get the shortest route distance. Research findings show that the use of the BB method results in a mileage difference from the initial route of 125 km (53% more efficient) and a fuel cost difference of 121,231 IDR (45% cheaper). Meanwhile, the NN method results in a mileage difference from the initial route of 115 km (48.94%) and a fuel cost difference of 109,901 IDR (41.27%). So, the method that produces the best solution is the BB method. The limitations of this study lie in the scale of the model used and the assumptions underlying the analysis. Future research can broaden the scope of the model and consider other factors that may affect the distribution of carton products. The results of this study contribute to improving the efficiency of carton product distribution.
Downloads
References
S. N. Anwar, “Manajemen Rantai Pas Okan (Supply Chain M Anagement) : Konsep Dan Hakikat,” J. Din. Inform., vol. 3, no. 2, pp. 1–7, 2018, [Online]. Available: http://www.unisbank.ac.id/ojs/index.php/fti2/article/view/1315/531
A. Widyarto et al., “Peran Supply Chain Management Dalam Sistem Produksi Dan Operasi Perusahaan,” Peran Supply Chain Manag. dalam ... BENEFIT J. Manaj. dan Bisnis, vol. 16, no. 2, pp. 91–98, 2020.
N. Alam and S. Tui, “Pengaruh Supply Chain Management Terhadap Keunggulan Kompetitif dan Kinerja Pada Perusahaan Manufaktur,” YUME J. Manag., vol. 5, no. 3, pp. 367–382, 2022, doi: 10.37531/yume.vxix.324.
N. P. D. Arwini and I. M. Juniastra, “Peran Transportasi Dalam Dunia Industri,” J. Ilm. Vastuwidya, vol. 6, no. 1, pp. 70–77, 2023, [Online]. Available: https://ejournal.universitasmahendradatta.ac.id/index.php/vastuwidya/article/view/794
A. Rozalina, S. Uslianti, and P. Anggela, “Optimasi Rute Distribusi Dengan Penyelesaian VRP Menggunakan Algoritma Sweep PD. XYZ di Pontianak,” Tin, vol. 4, no. 1, pp. 45–50, 2020.
M. V. Ardiansyah, R. A. Darajatun, and D. N. Rinaldi, “Optimalisasi Pendistribusian Dengan Metode Travelling Salesman Problem Untuk Menentukan Rute Terpendek Di Pt Xyz,” TeKmapro J. Ind. Eng. Manag., vol. 16, no. 2, pp. 84–95, 2021, doi: 10.33005/teKmapro.v16i2.264.
A. Andri, S. Suyandi, and W. Win, “Aplikasi Travelling Salesman Problem dengan Metode Artificial Bee Colony,” J. SIFO Mikroskil, vol. 14, no. 1, pp. 59–68, 2013, doi: 10.55601/jsm.v14i1.92.
N. RN, “Penerapan Metode Branch and Bound Pada Penyelesaian Masalah Traveling Salesman Problem (Tsp),” 2019, [Online]. Available: http://repository.unj.ac.id/id/eprint/29411%0Ahttp://repository.unj.ac.id/29411/1/skripsi.pdf
Suryani, D. Kartika Rahayu Kuncoro, and L. Dianati Fathimahhayati, “1456-3597-1-Sm,” Profisiensi, vol. 6, no. 1, pp. 41–49, 2018.
K. Auliasari, M. Kertaningtyas, and D. W. L. Basuki, “Optimalisasi Rute Distribusi Produk Menggunakan Metode Traveling Salesman Problem,” J. Sains, Teknol. dan Ind., vol. 16, no. 1, p. 15, 2018, doi: 10.24014/sitekin.v16i1.6109.
I. Sutoyo, “Penerapan Algoritma Nearest Neighbour untuk Menyelesaikan Travelling Salesman Problem,” Paradig. - J. Komput. dan Inform., vol. XX, no. 1, pp. 101–106, 2018.
L. Babel, “New heuristic algorithms for the Dubins traveling salesman problem,” J. Heuristics, vol. 26, no. 4, pp. 503–530, 2020, doi: 10.1007/s10732-020-09440-2.
“An Effective Heuristic Algorithm for the Traveling-Salesman Problem Author ( s ): S . Lin and B . W . Kernighan Published by : INFORMS Stable URL : http://www.jstor.org/stable/169020 REFERENCES Linked references are available on JSTOR for this article : You may need to log in to JSTOR to access the linked references .,” vol. 21, no. 2, pp. 498–516, 2017.
F. D. Heraldi, “Penerapan Algoritma Branch and Bound dalam Menyelesaikan Travelling Salesman Problem ( TSP ) untuk Menentukan Rute Perjalanan 11 Kantor Camat di Kota Padang,” 2022.
M. D. Amico, R. Montemanni, and S. Novellani, “This is the final peer-reviewed accepted manuscript of : Dell ’ Amico , M ., Montemanni , R ., Novellani , S . Algorithms based on branch and bound for the flying sidekick traveling salesman problem ( 2021 ) Omega ( United version is Terms of use : Algorithms based on Branch and Bound for the Flying Sidekick Traveling Salesman Problem,” no. 102493, 2021.
Copyright (c) 2024 Fitri Sakinatul Aisyah, Winarno Winarno, Dimas Nurwinata Rinaldi
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this Journal agree to the following terms:
- Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
- Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
- Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.
1.gif)
