Almost every activity that human do generates waste. To reduce the waste that keeps increasing due to the change of public consumption and lifestyle, a better waste management is needed. Poor waste management lead to health and environment problems, as well as climate change. As a pioneer of community-based establishment that aims to reduce the amount of recyclable house called Waste Bank Program, the performance of waste bank in Yogyakarta city is still underutilized. To increase community participation in depositing their waste to the waste bank, additional home pick-up service believed to increase community participation in depositing their waste to a waste bank. As the result, a routing plan to visit and collect the resident’s waste is needed.
In this research, we introduced a new extension of VRP called Multi-Depot Waste Collection Vehicle Routing Problem with Time Window and Self Delivery Option (MDWCVRPTW-SDO) to address the problem. There are three types of residents considered in this research, i.e. residents who ask for pick-up service to deposit their waste, residents who drop-off their waste by themselves, and residents who are flexible in terms of two aforementioned methods. A simulated annealing (SA) heuristic is developed in this research to solve the MDWCVRPTW-SDO instances and compare the result with the best-known solution from the previous research. The result shows that the algorithm shows its robustness in terms of solution quality. Sensitivity analysis also conducted in this research where the result shows that the selection of the appropriate compensation policy needs to be carefully thought out since it significantly affects the operational cost of MDWCVRPTW-SDO.

Almost every activity that human do generates waste. To reduce the waste that keeps increasing due to the change of public consumption and lifestyle, a better waste management is needed. Poor waste management lead to health and environment problems, as well as climate change. As a pioneer of community-based establishment that aims to reduce the amount of recyclable house called Waste Bank Program, the performance of waste bank in Yogyakarta city is still underutilized. To increase community participation in depositing their waste to the waste bank, additional home pick-up service believed to increase community participation in depositing their waste to a waste bank. As the result, a routing plan to visit and collect the resident’s waste is needed.
In this research, we introduced a new extension of VRP called Multi-Depot Waste Collection Vehicle Routing Problem with Time Window and Self Delivery Option (MDWCVRPTW-SDO) to address the problem. There are three types of residents considered in this research, i.e. residents who ask for pick-up service to deposit their waste, residents who drop-off their waste by themselves, and residents who are flexible in terms of two aforementioned methods. A simulated annealing (SA) heuristic is developed in this research to solve the MDWCVRPTW-SDO instances and compare the result with the best-known solution from the previous research. The result shows that the algorithm shows its robustness in terms of solution quality. Sensitivity analysis also conducted in this research where the result shows that the selection of the appropriate compensation policy needs to be carefully thought out since it significantly affects the operational cost of MDWCVRPTW-SDO.

Aarts, E. H. L., & Laarhoven, P. J. M. v. (1989). Simulated Annealing : An Introduction. Statistica Neerlandica, 43.

Alberdi, E., Urrutia, L., Goti, A., & Oyarbide-Zubillaga, A. (2020). Modeling the Municipal Waste Collection Using Genetic Algorithms. Processes, 8(5). https://doi.org/10.3390/pr8050513

Aliahmadi, S. Z., Barzinpour, F., & Pishvaee, M. S. (2021). A Novel Bi-Objective Credibility-Based Fuzzy Model For Municipal Waste Collection With Hard Time Windows. Journal of Cleaner Production, 296. https://doi.org/10.1016/j.jclepro.2021.126364

Amalia, S. (2020). Faktor Yang Menghambat Partisipasi Masyarakat Pada Program Bank Sampah Di Kota Yogyakarta. Jurnal Ilmu Administrasi, 17(2), 306-323.

Astuti, F. A., Asrifah, D., Widiarti, I. W., Utami, A., & Santoso, D. H. (2018). Identifikasi Persepsi Pola Perlakuan Sampah Oleh Masyarakat Dalam Meningkatkan Efektifitas Pengelolaan Sampah Kota Yogyakarta. Jurnal Science Tech, 4(2).

Beltrami, E. J., & Bodin, L. D. (1974). Networks And Vehicle Routing For Municipal Waste Collection. Networks, 4(1), 65-94.

Benjamin, A. M., & Beasley, J. E. (2010). Metaheuristics For The Waste Collection Vehicle Routing Problem With Time Windows, Driver Rest Period And Multiple Disposal Facilities. Computers & Operations Research, 37(12), 2270-2280. https://doi.org/10.1016/j.cor.2010.03.019

Buhrkal, K., Larsen, A., & Ropke, S. (2012). The Waste Collection Vehicle Routing Problem with Time Windows in a City Logistics Context. Procedia - Social and Behavioral Sciences, 39, 241-254. https://doi.org/10.1016/j.sbspro.2012.03.105

Cordeau, J. F., Laporte, G., & Mercier, A. (2001). A Unified Tabu Search Heuristic For Vehicle Routing Problems With Time Windows. Journal of the Operational Research Society, 52(8), 928-936. https://doi.org/10.1057/palgrave.jors.2601163

Dekker, R., Fleischmann, M., Inderfurth, K., & van Wassenhove, L. N. (2013). Reverse Logistics: Quantitative Models for Closed-loop Supply Chains. Springer Science & Business Media.

Dobiki, J. (2018). Analisis Ketersediaan Prasarana Persampahan di Pulau Kumo dan Pulai Kakara di Kabupaten Halmahera Utara. Jurnal Spasial, 5, 220-228.

Dumez, D., Lehuédé, F., & Péton, O. (2021). A Large Neighborhood Search Approach To The Vehicle Routing Problem With Delivery Options. Transportation Research Part B: Methodological, 144, 103-132. https://doi.org/10.1016/j.trb.2020.11.012

Enthoven, D. L. J. U., Jargalsaikhan, B., Roodbergen, K. J., uit het Broek, M. A. J., & Schrotenboer, A. H. (2020). The Two-Echelon Vehicle Routing Problem With Covering Options: City Logistics With Cargo Bikes And Parcel Lockers. Computers & Operations Research, 118. https://doi.org/10.1016/j.cor.2020.104919

Golden, B. L., Assad, A. A., & A.Wasil, E. (2002). Routing Vehicles in the Real World: Applications in the Solid Waste, Beverage, Food, Dairy, and Newspaper Industries. The Vehicle Routing Problem, pp. 245-286.

Gómez, J. R., Pacheco, J., & Gonzalo-Orden, H. (2015). A Tabu Search Method for a Bi-Objective Urban Waste Collection Problem. Computer-Aided Civil and Infrastructure Engineering, 30(1), 36-53. https://doi.org/10.1111/mice.12031

Grabenschweiger, J., Doerner, K. F., Hartl, R. F., & Savelsbergh, M. W. P. (2021). The Vehicle Routing Problem With Heterogeneous Locker Boxes. Central European Journal of Operations Research, 29(1), 113-142. https://doi.org/10.1007/s10100-020-00725-2

Han, H., & Ponce-Cueto, E. (2015). Waste Collection Vehicle Routing Problem: Literature Review. PROMET - Traffic&Transportation, 27(4), 345-358. https://doi.org/10.7307/ptt.v27i4.1616

Hemmelmayr, V., Doerner, K. F., Hartl, R. F., & Rath, S. (2011). A Heuristic Solution Method For Node Routing Based Solid Waste Collection Problems. Journal of Heuristics, 19(2), 129-156. https://doi.org/10.1007/s10732-011-9188-9

Ho, W., Ho, G. T. S., Ji, P., & Lau, H. C. W. (2008). A Hybrid Genetic Algorithm For The Multi-Depot Vehicle Routing Problem. Engineering Applications of Artificial Intelligence, 21(4), 548-557. https://doi.org/10.1016/j.engappai.2007.06.001

Huang, S.-H., & Lin, P.-C. (2015). Vehicle Routing–Scheduling For Municipal Waste Collection System Under The “Keep Trash Off The Ground” Policy. Omega, 55, 24-37. https://doi.org/10.1016/j.omega.2015.02.004

Kim, B.-I., Kim, S., & Sahoo, S. (2006). Waste Collection Vehicle Routing Problem With Time Windows. Computers & Operations Research, 33(12), 3624-3642. https://doi.org/10.1016/j.cor.2005.02.045

Kirkpatrick, S., D. Gelatt, J., & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220, pp. 671-680.

Liang, Y. C., Minanda, V., & Gunawan, A. (2021). Waste Collection Routing Problem: A Mini-Review Of Recent Heuristic Approaches And Applications. Waste Management and Research, 734242X211003975. https://doi.org/10.1177/0734242X211003975

Lin, S.-W., Yu, V. F., & Chou, S.-Y. (2009). Solving The Truck And Trailer Routing Problem Based On A Simulated Annealing Heuristic. Computers & Operations Research, 36(5), 1683-1692. https://doi.org/10.1016/j.cor.2008.04.005

Liu, R., Jiang, Z., & Geng, N. (2012). A Hybrid Genetic Algorithm For The Multi-Depot Open Vehicle Routing Problem. OR Spectrum, 36(2), 401-421. https://doi.org/10.1007/s00291-012-0289-0

Mancini, S., & Gansterer, M. (2021). Vehicle Routing With Private And Shared Delivery Locations. Computers & Operations Research, 133. https://doi.org/10.1016/j.cor.2021.105361

Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., & Teller, A. H. (1953). Equation of State Calculation by Fast Computing Machine. The Journal of Chemical Physics, 21.

Nurprihatin, F., & Lestari, A. (2020). Waste Collection Vehicle Routing Problem Model with Multiple Trips, Time Windows, Split Delivery, Heterogeneous Fleet and Intermediate Facility. Engineering Journal, 24(5), 55-64. https://doi.org/10.4186/ej.2020.24.5.55

Posmaningsih, D. A. (2016). Faktor-Faktor yang Mempengaruhi Partisipasi Masyarakat dalam Pengelolaan Sampah Pada di Denpasar Timur. Jurnal Skala Husada Volume 13, pp. 59 - 71.

Purkayastha, D., Majumder, M., & Chakrabarti, S. (2015). Collection And Recycle Bin Location-Allocation Problem In Solid Waste Management: A Review. Pollution, 1(2), 175-191.

Sahoo, S., Kim, S., Kim, B.-I., Kraas, B., & Popov, A. (2005). Routing Optimization for Waste Management. Interfaces, 35(1), 24-36. https://doi.org/10.1287/inte.1040.0109

Taillard, É., Badeau, P., Gendreau, M., Guertin, F., & Potvin, J.-Y. (1997). A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows. Transportation Science, 31(2), 170-186. https://doi.org/10.1287/trsc.31.2.170

Tilk, C., Olkis, K., & Irnich, S. (2021). The Last-Mile Vehicle Routing Problem With Delivery Options. OR Spectrum, 43(4), 877-904. https://doi.org/10.1007/s00291-021-00633-0

Tirkolaee, E. B., & Alinaghian, M. (2016). Solving A Robust Capacitated Arc Routing Problem Using A Hybrid Simulated Annealing Algorithm: A Waste Collection Application. Journal of Industrial Engineering and Management Studies, 3(1), 61-76.

Tirkolaee, E. B., Alinaghian, M., Sasi, M. B., & Esfahani, M. M. S. (2016). Solving A Robust Capacitated Arc Routing Problem Using A Hybrid Simulated Annealing Algorithm: A Waste Collection Application. Journal of Industrial Engineering and Management Studies, Vol. 3, pp. 61 - 76.

Tirkolaee, E. B., Mahdavi, I., & Mehdi Seyyed Esfahani, M. (2018, Jun). A Robust Periodic Capacitated Arc Routing Problem For Urban Waste Collection Considering Drivers And Crew's Working Time. Waste Manag, 76, 138-146. https://doi.org/10.1016/j.wasman.2018.03.015

Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2013). A Hybrid Genetic Algorithm With Adaptive Diversity Management For A Large Class Of Vehicle Routing Problems With Time-Windows. Computers & Operations Research, 40(1), 475-489. https://doi.org/10.1016/j.cor.2012.07.018

Wulandari, S., & Alam, P. F. (2018). The Use Of Online Waste Management System In Bank Sampah Induk Bantul. ECOTROPHIC 12(2).

Yuliana, I., & Wijayanti, Y. (2019). Partisipasi Masyarakat pada Program Bank Sampah. HIGEIA Journal Of Public Health Research And Development, Vol. 3, pp. 545-555.

Zhang, S. Z., & Lee, C. K. M. (2016, 4-7 Dec. 2016). Flexible vehicle scheduling for Urban Last Mile Logistics: The emerging technology of Shared Reception Box International Conference on Industrial Engineering and Engineering Management (IEEM), Bali, Indonesia.

Zhou, L., Baldacci, R., Vigo, D., & Wang, X. (2018). A Multi-Depot Two-Echelon Vehicle Routing Problem with Delivery Options Arising in the Last Mile Distribution. European Journal of Operational Research, 265(2), 765-778. https://doi.org/10.1016/j.ejor.2017.08.011