ANALISA PERBANDINGAN METODE SIMULATED ANNEALING DAN LARGE NEIGHBORHOOD SEARCH UNTUK MEMECAHKAN MASALAH LOKASI DAN RUTE KENDARAAN DUA ESELON
Downloads
Abstract
Two-echelon location routing problem (2E-LRP) is a problem that considers distribution problem in a two-level / echelon transport system. The first echelon considers trips from a main depot to a set of selected satellite. The second echelon considers routes to serve customers from the selected satellite. This study proposes two metaheuristics algorithms to solve 2E-LRP: Simulated Annealing (SA) and Large Neighborhood Search (LNS) heuristics. The neighborhood / operator moves of both algorithms are modified specifically to solve 2E-LRP. The proposed SA uses swap, insert, and reverse operators. Meanwhile the proposed LNS uses four destructive operator (random route removal, worst removal, route removal, related node removal, not related node removal) and two constructive operator (greedy insertion and modived greedy insertion). Previously known dataset is used to test the performance of the both algorithms. Numerical experiment results show that SA performs better than LNS. The objective function value for SA and LNS are 176.125 and 181.478, respectively. Besides, the average computational time of SA and LNS are 119.02s and 352.17s, respectively.
Abstrak
Permasalahan penentuan lokasi fasilitas sekaligus rute kendaraan dengan mempertimbangkan sistem transportasi dua eselon juga dikenal dengan two-echelon location routing problem (2E-LRP) atau masalah lokasi dan rute kendaraan dua eselon (MLRKDE). Pada eselon pertama keputusan yang perlu diambil adalah penentuan lokasi fasilitas (diistilahkan satelit) dan rute kendaraan dari depo ke lokasi satelit terpilih. Pada eselon kedua dilakukan penentuan rute kendaraan dari satelit ke masing-masing pelanggan mempertimbangan jumlah permintaan dan kapasitas kendaraan. Dalam penelitian ini dikembangkan dua algoritma metaheuristik yaitu Simulated Annealing (SA) dan Large Neighborhood Search (LNS). Operator yang digunakan kedua algoritma tersebut didesain khusus untuk permasalahan MLRKDE. Algoritma SA menggunakan operator swap, insert, dan reverse. Algoritma LNS menggunakan operator perusakan (random route removal, worst removal, route removal, related node removal, dan not related node removal) dan perbaikan (greedy insertion dan modified greedy insertion). Benchmark data dari penelitian sebelumnya digunakan untuk menguji performa kedua algoritma tersebut. Hasil eksperimen menunjukkan bahwa performa algoritma SA lebih baik daripada LNS. Rata-rata nilai fungsi objektif dari SA dan LNS adalah 176.125 dan 181.478. Waktu rata-rata komputasi algoritma SA and LNS pada permasalahan ini adalah 119.02 dan 352.17 detik.
A. A. N. Perwira Redi (Universitas Pertamina), Universitas Pertamina
SCOPUS ID = 56436570600
Scholar ID = Anak Agung Ngurah Perwira Redi Ph.D, CSCA
Reviewing interest : Metaheuristic, Logistic
Downloads
D. Abramson, "Constructing school timetables using simulated annealing: sequential and parallel algorithms," Management science, vol. 37, pp. 98-113, 1991. https://doi.org/10.1287/mnsc.37.1.98
V. Jayaraman and A. Ross, "A simulated annealing methodology to distribution network design and management," European Journal of Operational Research, vol. 144, pp. 629-645, 2003. https://doi.org/10.1016/S0377-2217(02)00153-4
S.-W. Lin, S.-Y. Chou, and S.-C. Chen, "Meta-heuristic approaches for minimizing total earliness and tardiness penalties of single-machine scheduling with a common due date," Journal of Heuristics, vol. 13, pp. 151-165, 2007. https://doi.org/10.1007/s10732-006-9002-2
A. R. McKendall, J. Shang, and S. Kuppusamy, "Simulated annealing heuristics for the dynamic facility layout problem," Computers & operations research, vol. 33, pp. 2431-2444, 2006. https://doi.org/10.1016/j.cor.2005.02.021
A. Van Breedam, "Comparing descent heuristics and metaheuristics for the vehicle routing problem," Computers & Operations Research, vol. 28, pp. 289-315, 2001. https://doi.org/10.1016/S0305-0548(99)00101-X
H. Asefi, S. Lim, M. Maghrebi, and S. Shahparvari, "Mathematical modelling and heuristic approaches to the location-routing problem of a cost-effective integrated solid waste management," Annals of Operations Research, vol. 273, pp. 75-110, 2019. https://doi.org/10.1007/s10479-018-2912-1
R. Cuda, G. Guastaroba, and M. G. Speranza, "A survey on two-echelon routing problems," Computers & Operations Research, vol. 55, pp. 185-199, 2015. https://doi.org/10.1016/j.cor.2014.06.008
S. K. Jacobsen and O. B. Madsen, "A comparative study of heuristics for a two-level routing-location problem," European Journal of Operational Research, vol. 5, pp. 378-387, 1980. https://doi.org/10.1016/0377-2217(80)90124-1
M. Boccia, T. G. Crainic, A. Sforza, and C. Sterle, "A metaheuristic for a two echelon location-routing problem," in International Symposium on Experimental Algorithms, 2010, pp. 288-301. https://doi.org/10.1007/978-3-642-13193-6_25
M. Schwengerer, S. Pirkwieser, and G. R. Raidl, "A Variable Neighborhood Search Approach for the Two-Echelon Location-Routing Problem," in EvoCOP, 2012, pp. 13-24. https://doi.org/10.1007/978-3-642-29124-1_2
V.-P. Nguyen, C. Prins, and C. Prodhon, "Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking," European Journal of Operational Research, vol. 216, pp. 113-126, 2012 https://doi.org/10.1016/j.ejor.2011.07.030
V.-P. Nguyen, C. Prins, and C. Prodhon, "A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem," Engineering Applications of Artificial Intelligence, vol. 25, pp. 56-71, 2012. https://doi.org/10.1016/j.engappai.2011.09.012
U. Breunig, V. Schmid, R. Hartl, and T. Vidal, "A large neighbourhood based heuristic for two-echelon routing problems," Computers & Operations Research, vol. 76, pp. 208-225, 2016. https://doi.org/10.1016/j.cor.2016.06.014
V. C. Hemmelmayr, J.-F. Cordeau, and T. G. Crainic, "An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics," Computers & operations research, vol. 39, pp. 3215-3228, 2012. https://doi.org/10.1016/j.cor.2012.04.007
L. Chwif, M. R. P. Barretto, and L. A. Moscato, "A solution to the facility layout problem using simulated annealing," Computers in industry, vol. 36, pp. 125-132, 1998.
A. Lim, B. Rodrigues, and X. Zhang, "A simulated annealing and hill-climbing algorithm for the traveling tournament problem," European Journal of Operational Research, vol. 174, pp. 1459-1478, 2006. https://doi.org/10.1016/S0166-3615(97)00106-1
A. Van Breedam, "Improvement heuristics for the vehicle routing problem based on simulated annealing," European Journal of Operational Research, vol. 86, pp. 480-490, 1995. https://doi.org/10.1016/0377-2217(94)00064-J
S.-W. Lin, F. Y. Vincent, and S.-Y. Chou, "Solving the truck and trailer routing problem based on a simulated annealing heuristic," Computers & Operations Research, vol. 36, pp. 1683-1692, 2009. https://doi.org/10.1016/j.cor.2008.04.005
N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, "Equation of state calculations by fast computing machines," The journal of chemical physics, vol. 21, pp. 1087-1092, 1953. https://doi.org/10.1063/1.1699114
S. Kirkpatrick, J. C. Gelatt, and M. P. Vecchi, "Optimization by simmulated annealing," science, vol. 220, pp. 671-680, 1983. https://doi.org/10.1126/science.220.4598.671
R. Eglese, "Simulated annealing: a tool for operational research," European journal of operational research, vol. 46, pp. 271-281, 1990. https://doi.org/10.1016/0377-2217(90)90001-R
V. Yu, F., S.-W. Lin, W. Lee, and C.-J. Ting, "A simulated annealing heuristic for the capacitated location routing problem," Computers & Industrial Engineering, vol. 58, pp. 288-299, 2010. https://doi.org/10.1016/j.cie.2009.10.007
V. F. Yu and S.-Y. Lin, "A simulated annealing heuristic for the open location-routing problem," Computers & Operations Research, vol. 62, pp. 184-196, 2015. https://doi.org/10.1016/j.cor.2014.10.009
S. Ropke and D. Pisinger, "An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows," Transportation science, vol. 40, pp. 455-472, 2006. https://doi.org/10.1287/trsc.1050.0135
C. Prodhon. (2016, 11 January 2020). LRP-2E instances. Available: http://prodhonc.free.fr/Instances/instances0_us.htm
K. Pichka, A. H. Bajgiran, M. E. Petering, J. Jang, and X. Yue, "The two echelon open location routing problem: Mathematical model and hybrid heuristic," Computers & Industrial Engineering, vol. 121, pp. 97-112, 2018. https://doi.org/10.1016/j.cie.2018.05.010
JMIL Jurnal Manajemen Industri dan Logistik (Journal of Industrial and Logistics Management) is an Open Access Journal. The authors who publish the manuscript in JMIL Jurnal Manajemen Industri dan Logistik agree to the following terms:
JMIL Jurnal Manajemen Industri dan Logistik is licensed under a Creative Commons Attribution 4.0 International License. This permits anyone to copy, redistribute, remix, transmit and adapt the work provided the original work and source is appropriately cited.
This means:
(1) Under the CC-BY license, authors retain ownership of the copyright for their article, but authors grant others permission to use the content of publications in JMIL Jurnal Manajemen Industri dan Logistik in whole or in part provided that the original work is properly cited. Users (redistributors) of JMIL Jurnal Manajemen Industri dan Logistik are required to cite the original source, including the author's names, JMIL Jurnal Manajemen Industri dan Logistik as the initial source of publication, year of publication, volume number, issue, and Digital Object Identifier (DOI); (2) Authors grant JMIL Jurnal Manajemen Industri dan Logistik the right of first publication. Although authors remain the copyright owner.
