Title Science and Technology Indonesia e-ISSN:2580-4391 p-ISSN:2580-4405 Vol. 8, No. 1, January 2023 Research Paper Waste Collection Vehicle Routing Problem with Time Windows for Route Optimization of Garbage Transport Vehicles Evi Yuliza1*, Bambang Suprihatin1, Putra Bahtera Jaya Bangun1, Fitri Maya Puspita1, Indrawati1, Sisca Octarina1 1Department of Mathematics, Universitas Sriwijaya, Ogan Ilir, 30662, Indonesia *Corresponding author: eviyuliza@mipa.unsri.ac.id AbstractThe waste collection vehicle routing problem with time windows is an optimization problem on the route of the waste transportvehicle which aims to determine the route of the vehicle by considering the travel time and windows. Garbage transport vehiclestransport garbage in several work areas. This affects the optimal time and distance. The working hours of the garbage collectors aredivided into two parts. The first working hours are 07.00 - 11.00 West Indonesian Time (WIT) and 16.00-20.00 WIT. The cleaningstaff has a break of 5 hours. This study aims to optimize the route of waste transportation vehicles in the problem of transportingwaste so as to minimize travel time and distance. Waste collection vehicle routing problem with time windows on determining theroute of a garbage transport vehicle which is simulated on the problem of transporting garbage in the city of Palembang. The wastecollection vehicle routing problem with the time windows model is solved with an exact approach using LINGO software. The resultsof this study indicate that the proposed optimization model provides optimization of the route of the garbage transport vehicle, thetotal travel time, and break time of the cleaning staff. KeywordsWaste, Transportation, Vehicle Routing Problem, Travel Time, Break Time Received: 9 October 2022, Accepted: 23 December 2022 https://doi.org/10.26554/sti.2023.8.1.66-70 1. INTRODUCTION The problem of vehicle routes in optimization can be discussed in the Vehicle Routing Problem (VRP). Dantzig Ramser in- troduced the Truck Dispatching Problem in 1959 which min- imized the distance traveled from trucks with homogeneous characteristics so that they could serve oil demand from a num- ber of gas stations (Ibrahim et al., 2019; Izar et al., 2016; Jepsen and Pisinger, 2011; Mamat et al., 2016). Furthermore, Clarke and Wright in 1964 generalized this problem in the field of logistics and transportation, hereinafter known as the VRP (Braekers et al., 2016; Lahyani et al., 2015). VRP problems have been widely researched and developed in various fields, such as logistics, transportation, economics, and communica- tions (Gounaris et al., 2013) . Classical VRP aims to determine vehicle routes starting from the depot, ending at the depot for vehicles with the same capacity so that each customer is visited once and each vehicle only has one route (Atefi et al., 2018; Borcinova, 2017; Izar et al., 2016; Nazari et al., 2018). VRP has been widely studied related to optimization problems that aim to identify efficient and optimal vehicle routes for distance or travel costs (Assaf and Saleh, 2017; Azad and Hasin, 2019; Munari et al., 2019). VRP can be related to the problem of garbage collection routes (Wahyukaton and Rochaeni, 2019; Yuliza et al., 2020; Yuliza et al., 2021). Service for each cus- tomer must be started in corresponding time intervals called time windows. The time window can be interpreted as the time interval between departure time and arrival time (Desaulniers et al., 2014; El-Sherbeny, 2010). The problem of waste collection is a problem faced by an area, especially urban areas Lu et al., 2015. In this paper, we study a variant of the Vehicle Routing Problem (VRP) as a waste collection vehicle routing problem with time windows. Rossit et al. (2021) proposed a simulated annealing algorithm to overcome the route of garbage collection vehicles based on mixed integer programming and metaheuristic methods, large neighborhood search, and genetic algorithms. The waste collection vehicle route problem is modeled with a scheduling strategy and an environmentally friendly solution is sought (Ko- rcyl et al., 2019; Lu et al., 2015). Zhou et al. (2022) proposed a model to optimize the solid waste collection and transport routes that have become an issue in China. Markovic et al. (2019) solve the problem of transporting waste in urban areas with a metaheuristic approach based on the waste collection vehicle routing problem on stochastic demand and travel time. https://crossmark.crossref.org/dialog/?doi=10.26554/sti.2023.8.1.66-70&domain=pdf https://doi.org/10.26554/sti.2023.8.1.66-70 Yuliza et. al. Science and Technology Indonesia, 8 (2023) 66-70 Perea et al. (2016) analyzed the problem of transporting waste by considering different types of waste based on heuristics. Bee algorithm was applied to overcome Capacitated Vehicle Rout- ing Problem (CVRP) issues which aim to provide a suggested solution regarding the waste hauling route for the upcoming ITF Sunter project. Based on the CVRP, the capacity of the waste transported will not exceed the capacity of the waste transport vehicles (Natalia et al., 2021) . This study will discuss the optimization model of the waste collection vehicle routing problem with time windows on the waste transportation route in the city of Palembang by consid- ering the rest time parameter. This study aims to optimize the route of waste transportation in the city of Palembang against time windows. More specifically, looking for the optimal route that minimizes the total distance traveled by waste transport vehicles. The problem from this research will be modeled as a waste collection vehicle routing problem with time windows. The mixed integer programming formulation of the waste col- lection vehicle routing problem with time windows was solved using the branch and bound method using LINGO software (Hartono et al., 2018; Puspita et al., 2018; Yuliza et al., 2020). The model will be implemented on the problem of waste trans- portation routes in the Ilir Barat I District I, Palembang city. An efficient procedure is designed to solve the waste collection route problem in the waste collection vehicle routing problem model so as to minimize the distance and travel time. The city of Palembang has a Department of Environment and Hygiene (DEH) which oversees and is responsible for the environment and cleanliness in the city of Palembang. Each DEH officer is responsible for one work area. The officers are assigned to one particular area and serve several Temporary Disposal Sites (TDS) to Final Disposal Sites (FDS) by using waste transport vehicles such as containers, dump trucks, or arm rolls. The process of transporting waste is divided into two periods. The first working hours are from 07.00-11.00 West Indonesian Time (WIT) and 16.00-20.00 WIT. There are a break 5 hours for the officers. This study will also discuss the break time of the officers. The free 5 hours between the working hours of the first session and the second session can be used by officers to rest. Garbage transport vehicles will pick up waste from several TDS and take it to the FDS. Garbage transport routes are carried out randomly so that the time and distance traveled are not optimal. 2. EXPERIMENTAL SECTION 2.1 Materials Data on waste transportation routes were obtained from DEH. The problem of transporting waste can be viewed as a weighted directed graph. The set of all TDS and FDS can be expressed as nodes and the journey from TDS i to TDS j can be expressed as arc, written G= (V,A) where G= 1,2,· · · ,n and V=(i,j)|i= 1,2,· · · ,n, and j= 1,2,· · · ,n. Some assumptions in this study are as follows: Vehicle capacity Some assumptions the average speed of garbage transporting vehicles is 40 km/hour, traffic jams are ignored, traffic lights are ignored, engine damage is neglected, the distance from TDS i to TDS j is considered the same or the matrix is symmetrical, service time about 5 minutes and the capacity of the garbage vehicle is assumed to be 8 tons. 2.2 Methods The waste collection vehicle routing problem with the time windows model is formulated which is implemented on the waste transportation route problem. This model is solved by the branch and bound method with the help of LINGO software. The procedure of this research is shown in Figure 1. Figure 1. Illustration of Research Flow 3. RESULT AND DISCUSSION The mathematical model of the waste collection vehicle routing problem with time windows is formulated as follows: min Z = ∑︁ (i, j)𝜖A di jxi j (1)∑︁ j𝜖V xi j = 1, for i𝜖V (2)∑︁ j𝜖V xji = 1, for i𝜖V (3) qi ≤ yi ≤ Q, for i𝜖V (4) yi − yj + qj ≤ Q(1 − xi j), for (i,j) 𝜖A (5) © 2023 The Authors. Page 67 of 70 Yuliza et. al. Science and Technology Indonesia, 8 (2023) 66-70 ∑︁ ( j,i)𝜖A, j≠i xji − ∑︁ (i, j)𝜖A,i≠j xi j =  −1, for = 0 1, for = d 0, the others (6) ai ≤ ti ≤ bi , for i𝜖V (7) ti − tj + (bi + ti j − aj)xi j ≤ bi − aj , for (i,j) 𝜖A (8)∑︁ ( j,i)𝜖A yi j = 1, for i𝜖V (9) yi j ≤ ii j , for (i,j) 𝜖A (10) xi j𝜖 {0, 1}, for (i,j) 𝜖A (11) yi j𝜖 {0, 1}, for (i,j) 𝜖A (12) The journey from TDS i to TDS j is denoted by xi j. The generation transported at the TDS to i and the generated trans- ported at the TDS to j are denoted by yi and yj. Departure time from TDS to i and travel time from TDS to j are denoted by ti and tj. The officer’s rest time from TDS i to TDS j is denoted by yi j. The distance from TDS i to TDS j is denoted by di j.The departure time of vehicles when transporting waste at TDS to i is denoted by ai.The arrival time of vehicles when transporting waste to TDS j is denoted by bj. Garbage load at TDS to i is denoted by qi. Vehicle capacity is denoted by Q.The travel time from TDS i to TDS j is denoted by ti j. The definitions of each variable and parameter are given in Table 1. Table 1. Variable and Parameter for the Waste Collection Vehi- cle Routing Problem with Time Windows Variable Parameter xi j di j yi ai yj bj ti qi ti ti j yi j Q The waste collection vehicle routing problem with the time window model is implemented on the problem of waste trans- portation routes in Ilir Barat I District, Palembang city. The solution of the waste collection vehicle routing prob- lem with time window model is solved by LINGO software. The solver of LINGO is the branch and bound method. The calculation results are as in Table 3. The calculation results of the waste collection vehicle rout- ing problem with the time window model produce a minimum total distance of 264.05 km and a total travel time of 6.6 hours (Assumption that the average speed of garbage transporting vehicles is 40 km/hour). In the first session, the working hours of officers are 4 hours and in the second session, the working hours of officers are 2.6 hours. The total working hours of the first session and the second session are 8 hours so the officer has a waiting time of 84 minutes. This shows that the waste Table 2. Data on Transportation Type and Amount of TDS in Ilir Barat I District District Vehicle code Transportation type Amount of TDS District 1 20 container 1 District 2 27 dump truck 7 District 3 28 container 2 District 4 29 dump truck 5 District 5 30 dump truck 6 District 6 31 amroll 4 District 7 32 dump truck 7 District 8 33 dump truck 3 District 9 34 dump truck 7 Table 3. Solution of the Waste Collection Vehicle Routing Problem Model with Time Window Vehicle code Minimize distance (km) Transport route 20 0.95 A1-A2 27 21.01 A1-T-B6-B5-B7-B2-B3-B4-T 28 31.4 A1-T-C2-C1 29 26.57 A1-T-D4-D2-D5-D3-T 30 40 A1-T-E6-E2-E4-E3-E5-T 31 34.5 A1-T-F3-F2-T 32 19.68 A1-G3-G2-G5-G4-T-G7-G6-T 33 43.8 A1-T-H3-H2-T 34 46.14 A1-I6-I4-T-I2-I5-I3-T Where node A1: 1st TDS and node T: FDS, The others: another TDS collection vehicle route using the waste collection vehicle rout- ing problem with the time window model produces an optimal total distance and travel time. 4. CONCLUSION The waste collection vehicle routing problem with the time window model can be implemented on the waste transportation route problem. This model observed to time windows and officer rest periods. Solution of the waste collection vehicle routing problem with time window model obtained optimal mileage and travel time. 5. ACKNOWLEDGMENT The research of this article was funded by DIPA of Public Service Agency of Universitas Sriwijaya 2022. SP DIPA- 023.17.2.677515/2022 on December 13, 2021. In accor- dance with the Rector’s Decree Number : 0109/UN9.3.1/SK/ 2022, On April 28, 2022. © 2023 The Authors. Page 68 of 70 Yuliza et. al. Science and Technology Indonesia, 8 (2023) 66-70 REFERENCES Assaf, R. and Y. Saleh (2017). Vehicle-Routing Optimiza- tion for Municipal Solid Waste Collection using Genetic Algorithm: The Case of Southern Nablus city. Civil and Environmental Engineering Reports, 26(3); 43–57 Atefi, R., M. Salari, L. C. Coelho, and J. Renaud (2018). The Open Vehicle Routing Problem with Decoupling Points. European Journal of Operational Research, 265(1); 316–327 Azad, T. and M. A. A. Hasin (2019). Capacitated Vehicle Routing Problem using Genetic Algorithm: A Case of Ce- ment Distribution. International Journal of Logistics Systems and Management, 32(1); 132–146 Borcinova, Z. (2017). Two Models of the Capacitated Vehicle Routing Problem. Croatian Operational Research Review, 8; 463–469 Braekers, K., K. Ramaekers, and I. Van Nieuwenhuyse (2016). The Vehicle Routing Problem: State of the Art Classification and Review. Computers & Industrial Engineering, 99; 300– 313 Desaulniers, G., O. B. Madsen, and S. Ropke (2014). Chapter 5: The Vehicle Routing Problem with Time Windows. In Vehicle Routing: Problems, Methods, and Applications, Second Edition. SIAM; 119–159 El-Sherbeny, N. A. (2010). Vehicle Routing with Time Win- dows: An Overview of Exact, Heuristic and Metaheuristic Methods. JournalofKingSaudUniversity-Science, 22(3); 123– 131 Gounaris, C. E., W. Wiesemann, and C. A. Floudas (2013). The Robust Capacitated Vehicle Routing Problem Under Demand Uncertainty. Operations Research, 61(3); 677–693 Hartono, Y., F. M. Puspita, D. I. Permatasari, and B. Arisha (2018). LINGO-Based on Robust Counterpart Open Ca- pacitated Vehicle Routing Problem (RC-OCVRP) Model of Waste Transportation in Palembang. International Conference onInformationandCommunicationsTechnology (ICOIACT), 18; 429–435 Ibrahim, A. A., N. Lo, R. Abdulaziz, and J. Ishaya (2019). Capacitated Vehicle Routing Problem. International Journal of Research-Granthaalayah, 7(3); 310–327 Izar, S., S. Suwilo, and S. Sutarman (2016). Multi-Depot Vehi- cle Routing Problem with Split Delivery and Time Windows. Bulletin of Mathematics, 8(02); 169–177 Jepsen, M. K. and D. Pisinger (2011). Branch-and-Cut and Branch-and-Cut-and-Price Algorithms for Solving Vehicle Rout- ing Problems. Technical University of Denmark Korcyl, A., R. Książek, and K. Gdowska (2019). A MILP Model for the Municipal Solid Waste Selective Collection Routing Problem. DecisionMaking inManufacturingandServices, 13(1- 2); 17–35 Lahyani, R., M. Khemakhem, and F. Semet (2015). Rich Ve- hicle Routing Problems: From a Taxonomy to a Definition. European Journal of Operational Research, 241(1); 1–14 Lu, J. W., N. B. Chang, L. Liao, and M. Y. Liao (2015). Smart and Green Urban Solid Waste Collection Systems: Advances, Challenges, and Perspectives. IEEE Systems Journal, 11(4); 2804–2817 Mamat, N. J. Z., S. H. Jaaman, and R. R. Ahmad (2016). Vehicle Routing Problem and Capacitated Vehicle Routing Problem Frameworks in Fund Allocation Problem. AIP Conference Proceedings, 1784(1); 050001 Markovic, D., G. Petrovic, Z. Cojbasic, and D. Marinkovic (2019). A Metaheuristic Approach to the Waste Collec- tion Vehicle Routing Problem with Stochastic Demands and Travel Times. Acta Polytechnica Hungarica, 16(7); 45–60 Munari, P., A. Moreno, J. De La Vega, D. Alem, J. Gondzio, and R. Morabito (2019). The Robust Vehicle Routing Problem with Time Windows: Compact Formulation and Branch-Price-and-Cut Method. Transportation Science, 53(4); 1043–1066 Natalia, C., V. Triyanti, G. Setiawan, and M. Haryanto (2021). Completion of Capacitated Vehicle Routing Prob- lem (CVRP) and Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) using Bee Algorithm Approach to Optimize Waste Picking Transportation Problem. Journal of Modern Manufacturing Systems and Technology, 5(2); 69–77 Nazari, M., A. Oroojlooy, L. Snyder, and M. Takác (2018). Reinforcement Learning for Solving the Vehicle Routing Problem. Advances in Neural Information Processing Systems, 31; 1–11 Perea, F., R. Ruiz, K. Katragjini, and G. d. S. de Opti- mización Aplicada (2016). Integer Programming, Clustering, and Local Search Approaches for Grouping Urban Waste Collection Sites. Boletinde Estadisticae InvestigacionOperativa, 32(3); 203–224 Puspita, F. M., Y. Hartono, N. Z. Syaputri, E. Yuliza, and W. D. Pratiwi (2018). Robust Counterpart Open Capaci- tated Vehicle Routing (RC-OCVRP) Model in Optimization of Garbage Transportation in District Sako and Sukarami, Palembang City. International Journal of Electrical and Com- puter Engineerin, 8(6); 4382–4390 Rossit, D. G., A. A. Toncovich, and M. Fermani (2021). Rout- ing in Waste Collection: A Simulated Annealing Algorithm for an Argentinean Case Study. Mathematical Biosciences and Engineering, 18(6); 9579–9605 Wahyukaton and A. Rochaeni (2019). Shortest Route for Waste Transportation in Northern Bandung using Vehicle Routing Problem-Clarke and Wright-Saving Method. Inter- national Journal of Innovative Technology and Exploring Engi- neering, 8(8); 679–686 Yuliza, E., F. M. Puspita, and S. S. Supadi (2020). The Robust CCounterpart Open Capacitated Vehicle Routing Problem with Time Windows on Waste Transport Problems. Bulletin of Electrical Engineering and Informatics, 9(5); 2074–2081 Yuliza, E., F. M. Puspita, and S. S. Supadi (2021). Heuristic Approach for Robust Counterpart Open Capacitated Ve- hicle Routing Problem with Time Windows. Science and Technology Indonesia, 6(2); 53–57 Zhou, J., M. Zhang, and S. Wu (2022). Multi-Objective Vehi- cle Routing Problem for Waste Classification and Collection © 2023 The Authors. Page 69 of 70 Yuliza et. al. Science and Technology Indonesia, 8 (2023) 66-70 with Sustainable Concerns: The Case of Shanghai City. Sus- tainability, 14(18); 11498 © 2023 The Authors. Page 70 of 70 INTRODUCTION EXPERIMENTAL SECTION Materials Methods RESULT AND DISCUSSION CONCLUSION ACKNOWLEDGMENT