ANALISA LOCAL SEARCH UNTUK PERBAIKAN SOLUSI VARIAN VRP PADA PERMASALAHAN OPTIMASI
Main Article Content
Abstract
Teori graf mempunyai medan aplikasi yang luas khususnya pada permasalahan optimasi. Permasalahan Vehicle Routing Problem (VRP) merupakan kajian dalam teori graf yang dapat diaplikasikan pada permasalahan optimasi. Multi Depot Vehicle Routing Problem (MDVRP), Vehicle Routing Problem with time window (VRPTW) dan gabungannya yaitu MDVRPTW merupakan varian VRP yang akan dianalisa perbaikan solusinya dengan strategi local search. Metode yang digunakan untuk menyelesaikan permasalahan varian VRP ini adalah algoritma self-developed, algoritma interchange descent dan algoritma exchange local search. Strategi penyelesaian varian VRP adalah: tahap inisialisasi, tahap pengembangan dan tahap optimalisasi. Pada tahap pengembangan perbaikan solusi dianalisa dengan local search. Hasil solusi akhir algoritma self developed lebih baik dibandingkan algoritma interchange descent. Algoritma interchange descent melakukan perbaikan inter route dan intra route mengakibatkan proses iterasi yang lama tetapi diperoleh kemungkinan solusi hasil perbaikan lebih banyak jika dibanding exchange local search. Penentuan total waktu tempuh dapat dilihat dari seberapa lama kendaraan melakukan perjalanan. Algoritma self developed menghasilkan total waktu tempuh kendaraan yang minimal dibandingkan dengan algoritma interchange descent. Analisa local search untuk perbaikan solusi MDVRP, VRPTW dan MDVRPTW berguna untuk identifikasi solusi terbaik pada implementasi permasalahan optimasi.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright Notice
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
References
[2] Crevier, B., Jean-Francois Cordeau., & Gilbert Laporte. 2007. The Multi-Depot Vehicle Routing Problem with inter-depot routes ( European Journal of Operational Research 176 (2007) 756-773). Canada: ELSEVIER (online),
[3] En-nahli, L., Afifi, S., Allaoui, H. & Nouaouri, I. 2016. Local Search Analysis for a Vehicle Routing Problem with Synchronization and Time Windows Constraints in Home Health Care Services. International Federation of Automatic Control, France, 2016. (Online), 49(12): 1210-1215
[4] Penna, P.V., Subramanian, A.&Ochi, L.S. 2011. An Iterated Local Search Heuristik for The Heterogeneous Fleet Vehicle Routing Problem, (Online),
[5] Kiran, M, dkk. 2013. A Modified Savings Algorithm Based Approach for Vehicle Routing Problem with Simultaneous Pick-up and Delivery. International Journal of Emerging Technology and Advanced Engineering(Online)
[6] Li, J., Pardalos, P.& Li, Y. 2014. Multi Depot Vehicle Routing Problem With Time Windows Under Shared Depot Resources. College of Engineering, Namjing Agricultur University, Namjing, China. Jounal ofCombinatorial Optimization, (Online),31: 515,
[7] Polacek, M.; Hartl, R.F.; dan Doerner, K. 2005. “A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with TimeWindows.” Journal of Heuristics, 10: 613-627.
[8] Polat,O., Kalayci, C., Kulak, O., Gunther, H. 2015. A Perturbation Based Variable Neighborhood Search Heuristic For SolvingThe Vehicle Routing Problem With Simultaneous Pickup And Delivery With Time Limit. European Journal of Operational Research. S0377-2217(14)00814-5.
[9] Ramalingam, A. dan Vivekanandan, K. 2014. “Genetic Algorithm based Solution Model for Multi-Depot Vehicle Routing Problem with Time Windows.” International Journal of Advanced Research in Computer and Communication Engineering, 3: 8433-8499.
[10] Rostami, Ali S., Mohanna, F., Keshavarz, H. & Hosseinabadi, A.A.R. 2015. Solving Multiple Traveling Salesman Problem using the Gravitational Emulation Local Search Algorithm. Applied Mathematics & Information Sciences, (Online), 9(2): 699-709,
[11] Silva, M.M., Subramanian, A.&Ochi, L.S. 2015. An Iterated Local Search Heuristic for The Split Delivery Vehicle Routing Problem. Computer & Operations Research (Online),
[12] Subramanian, A., Drummond, L.M.A., Bentes, C., Ochi, L.S. & Farias, R. 2010. A Parallel Heuristik for The Vehicle Routing Problem with Simultaneous Pickup and Delivery. Computer & Operations Research (Online), 37: 1899-1911,
[13] Sumathi, S., & Surekha P. 2011. Solution To Multi-Depot Vehicle Routing Problem Using Genetic Algorithms. WAP Journal, (Online), 1(3) : 118-131,
[14] Tamashiro, H.; Nakamura, M.; Okazaki, T.; dan Kang, D. 2007. “A Tabu Search Approach combined with An Extended Saving Method for Multi-depot Vehicle Routing Problems with Time Windows.” Biomedical Soft Computing and Human Sciences, 15(1): 29-37.
[15] Timmermann, T. 2010. An approach to solve the Multi Depot VehicleRouting Problem with Time Windows (MDVRPTW) In Static And Dynamic Scenarios. Proceedings of the 22. Workshop "Planen, Scheduling und Konfigurieren, Entwerfen, (Online)
[16] Wang, Y. 2013. “Research of Multi-Depot Vehicle Routing Problem by Cellular Ant Algorithm.”Journal of Computers, 8(7): 1722-1727.
[17] Wahyuningsih, S dan Satyananda, D (2014 &2015). Pengembangan modul penerapan teori graph berbasis ICT sebagai pedoman PKL mahasiswa jurusan matematika di Industri. LP2M UM: laporan penelitian hibah bersaing.
[18] Xing, W. 2016. An Improved Savings Method for Vehicle Routing Problem. International Conference on Control Science and Systems Engineering (Online)
[19] Yeun, L.C.; Ismail, W.R.; Omar, K.; dan Zirour, M. 2008. ”Vehicle Routing Problem: Models and Solutions.” Journal of Quality Measurement and Analysis, 4(1): 205-218.