Pengembangan Algoritma Hybrid Restart Simulated Annealing with Variable Neighborhood Search (HRSA-VNS) untuk penyelesaian kasus Vehicle Routing Problem with Time Windows (VRPTW)
DOI:
https://doi.org/10.26593/jrsi.v6i1.2427.49-56Abstrak
Determining the vehicle routing is one of the important components in existing logistics systems. It is because the vehicle route problem has some effect on transportation costs and time required in the logistics system. In determining the vehicle routes, there are some restrictions faced, such as the maximum capacity of the vehicle and a time limit in which depot or customer has a limited or spesific opening hours (time windows). This problem referred to Vehicle Routing Problem with Time Windows (VRPTW). To solve the VRPTW, this study developed a meta-heuristic method called Hybrid Restart Simulated Annealing with Variable Neighborhood Search (HRSA-VNS). HRSA-VNS algorithm is a modification of Simulated Annealing algorithm by adding a restart strategy and using the VNS algorithm scheme in the stage of finding neighborhood solutions (neighborhood search phase). Testing the performance of HRSA-VNS algorithm is done by comparing the results of the algorithm to the Best Known Solution (BKS) and the usual SA algorithm without modification. From the results obtained, it is known that the algorithm perform well enough in resolving the VRPTW case with the average differences are -2.0% with BKS from Solomon website, 1.83% with BKS from Alvarenga, and -2.2% with usual SA algorithm without any modifications.
Keywords : vehicle routing problem, time windows, simulated annealing, VNS, restart
Referensi
Alfa, A. S., S. S. Heragu dan M. Chen (1991). A 3-opt based simulated annealing algorithm for vehicle routing problems. Computers & Industrial Engineering 21(1): 635-639.
Alvarenga, G. B., G. R. Mateus dan G. de Tomi (2007). A genetic and set partitioning two-phase approach for the Vehicle Routing Problem with Time Windows. Computers & Operations Research, 34(6), 1561-1584.
Breedam, A. V. (1995). Improvement heuristics for the Vehicle Routing Problem based on Simulated annealing. European Journal of Operational Research, 86, 480-490.
Dantzig, G. B. dan J. H. Ramser (1959). The Truck Dispatching Problem.Management Science, 6(1): 80-91.
Halim, C. dan Yu, V. F. (2016). Minimum Cost Vertex-Disjoint Path Cover Problem. Electronic Thesis and Dissertation (ETD) National Taiwan University of Science and Technology. Diakses dari : http://pc01. lib.ntust.edu.tw/ETD-db/ETD-search/view etd?URN=etd-0115116-143744 [2017, 1 Maret]
Homberger, J. (2000). Verteilt-parallele Metaheuristiken zur Tourenplanung, Gaber, Wiesbaden
Homberger, J. dan Gehring, H. (1999). Two Evolutionary Metaheuristics for the Vehicle Routing Problem with Time Windows. INFOR, 37, 297-318
Iswari, T., Yu, V.F., dan Asih, A.M.S. (2016). A Simulated Anealing Heuristic for Blood Pick-Up Routing Problem. Electronic Thesis and Dissertation (ETD) National Taiwan University of Science and Technology. Diakses dari: https://pc01.lib.ntust.edu.tw/ ETD-db/ETD-search/view_etd?URN=etd-0620116-133237 [2017, 1 Maret].
Kumar,S.N., dan Paneerselvam, R., (2012), A Survey on The Vehicle Routing Problem and Its Variants, Intelligent Information Management, 4, 66-74.
Laporte, G. (1992). The Vehicle Routing Problem: An overview of exact and approximate algorithms. European Journal of Operational Research 59(3), 345-358.
Lin, S.-W., K.-C. Ying, Z.-J. Lee dan F.-H. Hsi (2006). Applying Simulated annealing Approach for Capacitated Vehicle Routing Problems. 2006 IEEE International Conference on Systems, Man, and Cybernetics, 639-644.
Lin, S.-W., V. F. Yu dan S. Y. Chou (2011). A simulated annealing heuristic for the truck and trailer routing problem with time windows. Expert Systems with Applications, 38(12), 15244-15252.
Mester, D. (2002). An Evolutionary Strategies Algorithm for Large Scale Vehicle Routing Problem with Capacitate and Time Windows Restrictions, Working Paper Institute of Evolution, University of Haifa, Israel.
Metropolis, N., A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller dan E. Teller (1953). Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics, 21(6), 1087.
Oliviera, H. C. B., G. C. Vasconcelos dan G. B. Alvarenga. (2006). A Multi-Start Simulated Annealing Algorithm for the Vehicle Routing Problem with Time Windows. Proceedings of the Ninth Brazilian Symposium on Neural Networks.
Rochat, Y. dan Taillard, E.D. (1995). Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. Journal of Heuristics, 1, 147-167.
Solomon, M. M. dan J. Desrosiers. (1988). Survey Paper—Time Window Constrained Routing and Scheduling Problems.Transportation Science, 22(1), 1-13.
Solomon. M. M (2005). Best Known Solution Identified by Heuristic. Diunduh dari : http://web.cba.neu.edu/~msolomon/heuristi.htm
Taillard,E., Badeau, P., Gendreau, M., Geurtin, F. dan Potvin, J.Y. (1997). A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows. Transportation Science, 31, 170-186
Xiao, Y., Zhao, Q., Kaku I., dan Xu, Y. (2012). Development of a fuel consumption optimization model for the capacitated vehicle routing problem. Computers & Operations Research,39(7), 1419-1431.
Xie F., Ji, S., Liu Y., dan Huang, X., 2008, Research of Coupling Relation between City Logistics and Economy based on Artificial Neural Network, Institute of Electrical and Electronics Engineers (IEEE) Journal.
Yu, V. F. dan S.-W. Lin (2014). Multi-start simulated annealing heuristic for the location routing problem with simultaneous pickup and delivery. Applied Soft Computing 24: 284-290.
Yu, V. F., S.-W. Lin, W. Lee dan C.-J. Ting (2010). A simulated annealing heuristic for the capacitated location routing problem.Computers & Industrial Engineering, 58(2) 288-299.
