Title Science and Technology Indonesia e-ISSN:2580-4391 p-ISSN:2580-4405 Vol. 6, No. 2, April 2021 Research Paper Heuristic Approach For Robust Counterpart Open Capacitated Vehicle Routing Problem With Time Windows Evi Yuliza1, Fitri Maya Puspita1*, Siti Suzlin Supadi2 1Mathematics Department, Faculty of Mathematics and Natural Science, University of Sriwijaya, South Sumatera, Indonesia 2Institute of Mathematical Sciences, Faculty of Science, University of Malaya, Malaysia *Corresponding author: fitrimayapuspita@unsri.ac.id Abstract Garbage is one of the environmental problems. The process of transporting garbage sometimes occurs delays such as congestion and engine failure. Robust optimization model called a robust counterpart open capacitated vehicle routing problem (RCOCVRP) with time windows was formulated to get over this delays. This model has formulated with the limitation of vehicle capacity and time windows with an uncertainty of waste volume and travel time. The RCOCVRP model with time windows is solved by a heuristic approach. The heuristic approach used to solve the RCOCVRP model with time windows uses the nearest neighbor and the cheapest insertion heuristic algorithm. The RCOCVRP with time windows model is implemented on the problem of transporting waste in Sako sub-district. The solutions of these two heuristic approaches are compared and analyzed. The RCOCVRP model with time windows to optimize the route problems of waste transport vehicles that is solved using the cheapest insertion heuristics algorithm is more e�ective than the nearest neighbor method. Keywords Optimization Robust, Counterpart Open Capacitated Vehicle Routing Problem, Time Windows, Nearest Neighbour Algorithm, Cheapest Insertion Heuristic Algorithm Received: 14 November 2020, Accepted: 23 March 2021 https://doi.org/10.26554/sti.2021.6.2.53-57 1. INTRODUCTION Garbage is one of the environmental problems. To solve this environmental problem, the department of cleanliness and the environment carries out waste transportation activities. Garbage transport vehicles carry garbage to a temporary dump site (TDS) and end up at the �nal disposal site (FDS). Classic vehicle routing problem, also known as capacitated vehicle routing problem, has the characteristic that the vehicle departs from the starting point and returns to the starting point for example the route of the vehicle on the distribution of LPG gas (Yuliza and Puspita, 2019). The route of the waste transportation vehicle is an open vehicle routing problem (OVRP) that the garbage transporting vehicle transports waste from the TDS and then takes it to the FDS. The process of transporting garbage sometimes occurs with delay, such as congestion and equipment failure. Robust optimization is an optimization problem approach for data that has uncertainty. De La Vega et al., 2019 formulated an optimization model for the robust vehicle routing problem (RVRP) with time windows and multiple deliverymen. Sungur et al., 2008 and Sun and Wang, 2015 discuss robust optimization of the vehicle route problem with many uncertain requests. Ro- bust optimization research has experienced developments in the problem of vehicle routes, for example in the transportation and logistics sectors The robust capacitated vehicle routing problem (RCVRP) model is a robust optimization that takes into account the uncertainty of demand to minimize the cost of shipping prod- ucts to costumers (Gounaris et al., 2013). Robust vehicle routing problem with time windows (RVRPTW) is a robust optimiza- tion that takes time windows into account. Agra et al., 2013 discussed RVRPTW on transportation problems where delays often occur so that the travel time is uncertain. Braaten et al., 2017 investigated the limit of the maximum amount of delay in the RVRPTW model and this model was solved by a heuristic method based on a large adaptive neighborhood search. Hartono et al., 2018 proposed a robust counterpart vehicle routing prob- lem (RCOCVRP) model for waste transportation by request using the branch and bound algorithm. Puspita et al., 2018a discussed the RCOCVRP model on the problem of waste transportation in Sako and Sukarami Districts. Puspita et al., 2018b discussed the RCOCVRP model with a request on the problem of waste transportation in Sematang Borang District. Research on the problem of solid waste collection and robust https://crossmark.crossref.org/dialog/?doi=10.26554/sti.2021.6.2.53-57&domain=pdf https://doi.org/10.26554/sti.2021.6.2.53-57 Yuliza, E et. al. Science and Technology Indonesia, 6 (2021) 53-57 optimization models has been widely studied (Buhrkal et al., 2012; Campos and Arroyo, 2016; Hannan et al., 2018; Nguyen et al., 2013; Perea et al., 2016 ). Hartono et al., 2018; Puspita et al., 2018b discuss the robust counterpart open capacitated vehicle routing problem (RC-OCVRP) model. Puspita et al., 2018a dis- cussed the robust demand counterpart open capacitated vehicle routing problem (DR-CVRP) model on the problem of waste transportation routes. This research discusses the optimization modeling of robust counterpart open capacitated vehicle routing problem (RCOCVRP) with soft time windows, which means that the arrival time of the vehicle in a TDS (or in FDS) can be equal to or more than the �nal time. Yuliza et al., 2020b has proposed the RCOCVRP model with time windows on the problem of transporting garbage vehicles. This model is solved with an exact approach. The RCOCVRP model with time windows is solved by the cheapest insertion heuristics algorithm then solved using the GAMS soft- ware (Yuliza et al., 2021). RCOCVRP model with time windows produces optimal results solution by considering the volume of waste in each TDS carried by the vehicle does not exceed the vehicle capacity, and travel time does not exceed the time of arrival of the vehicle and solved using the nearest neighbor method (Yuliza et al., 2020a). This model is formulated with the limitation of vehicle capac- ity (Q) and time windows [a,b] with uncertainty of travel time (tij) and volume of waste (qi). In this case, the vehicle arriving at a TDS or FDS may exceed the time windows. The RCOCVRP model with soft time windows is applied to the garbage trans- portation route in Sako District, Palembang. Time windows can be viewed as the time interval from the time the vehicle departs and the time the vehicle arrives at a customer (Agra et al., 2013). This model aims to optimize the route of the waste transport vehicle so as to minimize the distance. This model is solved by a heuristic approach. The heuristic approach used to solve the RCOCVRP model with soft time windows uses the nearest neighbor and the cheapest insertion heuristic algorithm. The nearest neighbor algorithm and the cheapest insertion heuristics algorithm have the same working principle, namely �nding the closest point from the initial point. 2. EXPERIMENTAL SECTION 2.1 Materials Primary data in the form of the names of TDS and FDS, vehicle capacity, time windows and service time were obtained through direct interviews with the environmental and sanitation depart- ment. Secondary data in the form of distance between each TDS to TDS and FDS and travel time are obtained from the google maps application. Each sub-district has a TDS as a temporary dis- posal site for waste transported by the department of cleanliness and the environment waste collection vehicles with uncertain waste volume. The type of vehicle for each work area is a dump truck. The garbage collection vehicle in Sako sub-district has 3 working areas. The garbage collection vehicles serve several TDS in work area 1, work area 2 and work area 3, respectively, Table 1. Time windows and waste volume in working area 1 Time Windows Volume of waste (kg) 07:00, 07:30 q1=800 07:30, 08:00 q2=1500 08:00, 08:30 q3=600 08:30, 09:00 q4=4000 09:00, 09:30 q5=700 09:30, 10:00 q6=2000 10:00, 11:00 q7=6000 as many as 6 TDS, 4 TDS and 11 TDS. Sako district is a densely populated residential area, so the problem of transporting waste is a concern. RCOCVRP model with time windows is simulated on the route of garbage collection vehicles in the working area 1. Time windows and waste volume in working area 1 is shown in Table 1. The distance between TDS i to TDS j and the distance of each TDS to FDS are expressed in the distance matrix as shown in Table 2. It is assumed that the waste transport vehicle has an average speed of 40 km/hour. Based on the results of interviews with o�cers in the environmental and sanitation department, the average service time is around 15 minutes. 2.2 Methods Due to their greedy nature, sometimes the nearest neighbor al- gorithm can skip a shorter route. However, the nearest neighbor is easy to implement and up quickly (Pop et al., 2011). The cheap- est insertion heuristics algorithm is able to solve the problem of vehicle routes. In the case of waste transport routes, each TDS is represented as a point and the travelling from TDS i to TDS j can be represented as an arc. 2.2.1 Nearest Neighbor Algorithm Following are the steps of the nearest neighbor algorithm for the problem of transporting waste: Step 1: Find the closest distance to each TDS from the initial TDS as the starting node. Step 2: Find the closest node from the starting node provided that the garbage volume from each TDS does not exceed vehicle capacity. Step 3: If the garbage volume exceeds the vehicle then start again from Step 1. Step 4: Repeat step 2 until all TDS (included FDS) are visited. 2.2.2 Cheapest Sequential Insertion Algorithm The principle of the cheapest sequential insertion algorithm is to make the initial route �rst. Starting from arc (i, j) from the starting vertex to the destination vertex and try to insert vertex k at a certain position gives the best criteria (Alatartsev et al., 2013; Scutellà, 2015). The arc (i, j) with which node k is inserted is calculated using the formula in the following formula: cik + ckj − cij (1) © 2021 The Authors. Page 54 of 57 Yuliza, E et. al. Science and Technology Indonesia, 6 (2021) 53-57 Table 2. Matrix of distance (km) TDS1 TDS2 TDS3 TDS4 TDS5 TDS6 FDS TDS1 0 0.4 0.35 0.45 1.3 4.5 2.3 TDS2 0 0.55 0.85 1.3 4.8 2.3 TDS3 0 1.1 1.4 5.2 2.2 TDS4 0 1.7 4.1 2.3 TDS5 0 5.8 1.2 TDS6 0 5.6 FDS 0 Table 3. Variables Variables Description xij the vehicle traveling from TDS i to TDS j yi vehicle load when leaving TDS i. ti arrival time to TDS i If none of the arcs provide the best criteria then form a new route. This process is repeated until all nodes are selected. 3. RESULTS AND DISCUSSION Given a directed graph G = (V, A) where V = {1, 2, 3, ..., n + 1} as the set of nodes and A={(i,j) ∣ i=1,2,...,n+1 } dan j = {1, 2, ..., n + 1, i ≠ j} as a set of arcs, where nodes 1, 2, ..., n represent each TDS and node n + 1 represents FDS. Denoted N with N ⊂ V as a set of nodes that do not start from an origin (o) and destination (d) The set T represents the set of all time windows for each node T={ai, bi ∣ i ∈ V} . The set ext(T) represents all the extreme points on T. The variables and parameters proposed is the following: The RCOCVRP with time windows in working area 1 is formulated as follows: Minimize 0.4x12 + 0.35x13 + 0.45x14 + 1.3x15 + 4.5x16 + 2.3x17 + 0.4x21+ 0.55x23 + 0.85x24 + 1.3x25 + 4.8x26 + 2.3x27 + 0.35x31 + 0.55x32+ 1.1x34 + 1.4x35 + 5.2x36 + 2.2x37 + 0.45x41 + 0.85x42 + 1.1x43+ 1.7x45 + 4.1x46 + 2.3x47 + 1.3x51 + 1.3x52 + 1.4x53 + 1.7x54+ 5.8x56 + 1.2x57 + 4.5x61 + 4.8x62 + 4.1x64 + 5.8x65 + 5.6x65+ 5.6x67 + 2.3x71 + 2.3x72 + 2.2x73 + 2.3x74 + 1.2x75 + 5.6x76 (2) Based on the data in Table 1 and Table 2, the RCOCVRP model with time windows aims to minimize the distance traveled by waste transport vehicles so that the objective function is formu- lated as Equation 2. subject to x12 + x13 + x14 + x15 + x16 + x17 = 1, x21 + x23 + x24 + x25 + x26 + x27 = 1, x31 + x32 + x34 + x35 + x36 + x37 = 1, x41 + x42 + x43 + x45 + x46 + x47 = 1, x51 + x52 + x53 + x54 + x56 + x57 = 1, x61 + x62 + x63 + x64 + x65 + x67 = 1, x71 + x72 + x73 + x74 + x75 + x76 = 1 (3) Garbage transport vehicles visit each node only as Constraints (3) is de�ned as at least one trip by a waste transport vehicle from node i to node j and at least one trip by a waste transport vehicle from node j to node i. x21 + x31 + x41 + x51 + x61 + x71 − x12 − x13 − x14 − x15 − x16− x17 = −1; x17 + x27 + x37 + x47 + x57 + x67 − x71 − x72 − x73 − x74− x75 − x76 = 1; x12 + x32 + x42 + x52 + x62 + x72 − x21 − x23 − x24− x25 − x25 − x27 = 0; x13 + x23 + x43 + x53 + x63 + x73 − x31 − x32− x34 − x35 − x36 − x37 = 0; x14 + x24 + x34 + x54 + x64 + x74 − x41− x42 − x43 − x45 − x46 − x47 = 0; x15 + x25 + x35 + x45 + x65 + x75− x51 − x52 − x53 − x54 − x56 − x57 = 0; x16 + x26 + x36 + x46 + x56+ x76 − x61 − x62 − x64 − x64 − x65 − x6767 = 0 (4) Constraints (4) ensure that no sub-tours are cut o� for each node visited by the garbage transport vehicle and the vehicles traveling from TDS i to TDS j are the same as vehicles from TDS j to TDS i. 800 ≤ y1 ≤ 8000, 1500 ≤ y2 ≤ 8000, 600 ≤ y3 ≤ 8000, 4000 ≤ y4 ≤ 8000 700 ≤ y5 ≤ 8000, 2000 ≤ y6 ≤ 8000, 0 ≤ y7 ≤ 8000 (5) Constraint (5) states that the load of waste transport vehicles is limited by the volume of waste and the capacity of the vehicle. y1 − y2 + 8000x12 ≤ 4500, y2 − y3 + 8000x23 ≤ 5400, y3 − y4+ 8000x34 ≤ 2000, y4 − y5 + 8000x45 ≤ 5300, y5 − y6 + 8000x56 ≤ 4000, y6 − y7 + 8000x37 ≤ 0 (6) © 2021 The Authors. Page 55 of 57 Yuliza, E et. al. Science and Technology Indonesia, 6 (2021) 53-57 Table 4. Parameters Parameters Description cij distance between TDS i to TDS j and the distance of each TDS to FDS qi load of waste transport vehicles tij travel time from TDS i to TDS j. ai departure time from TDS i bj vehicle arrival time at TDS j Table 5. The solution of the RCOCVRP model with time windows in working area 1 Route Distance (km) TDS 1 – TDS 3 – TDS 2 – FDS 3.2 Nearest neighbor algorithm TDS 4 – TDS 5 – FDS 2.9 TDS 6 – FDS 5.6 Cheapest insertion Heuristic algorithm TDS 1 – TDS 2 – TDS 3 – FDS 3.15 TDS 4 – TDS 5 – FDS 2.9 TDS 6 – FDS 5.6 The volume of waste is uncertain so that the load of garbage vehicles at each node is formulated as Constraints (6). 7 ≤ t1 ≤ 7.5, 7.5 ≤ t2 ≤ 8, 8 ≤ t3 ≤ 8.5, 8.5 ≤ t4 ≤ 9, 9 ≤ t5 ≤ 9.5, 9.5 ≤ t6 ≤ 10.5, 10.5 ≤ t7 ≤ 11, (7) The vehicle travel time when visiting node i is limited by the time windows formulated by Constraints (7). t1 − t2 + 0.01x12 ≤ 0, t2 − t3 + 0.01375x23 ≤ 0, t3 − t4 + 0.0275x34 ≤ 0, t4 − t5 + 0.0425x45 ≤ 0, t5 − t6 + 0.145x56 ≤ 0, t6 − t7 + 0.14 x67 ≤ 0 (8) Vehicle arrival time at node i is in�uenced by departure time, travel time and vehicle arrival time at node j formulated by Constraints (8). The calculation of the RCOCVRP model with time windows is solved by the Nearest Neighbor algorithm simulated in the working area 1. Furthermore, the calculation of the RCOCVRP model with time windows is solved by the cheapest insertion heuristic algorithm. The route of waste transport vehicles in working area 1 uses the nearest neighbor algorithm and the cheapest insertion heuristics algorithm is shown in Table 5. The total distance of waste transport vehicles in working area 1, respectively, using the nearest neighbor method and the cheapest insertion heuristic algorithm are 11.65 km and 11.7 km. The results of calculations using these two heuristic ap- proaches are almost the same. This is in�uenced by the working principle of these two heuristic approaches is to �nd the closest point. The results for working area 2 and working area 3 use the nearest neighbor algorithm and the cheapest insertion heuristics algorithm as shown in Table 6. Based on Table 5 and Table 6, it is obtained that the total distance of waste transport vehicles in Sako sub-district using the nearest neighbor algorithm is 54.29 km and the total distance traveled using the cheapest insert heuristic algorithm is 54.24 km. The RCOCVRP model with time windows to optimize the route problems of waste transport vehicles that is solved using the cheapest insertion heuristics algorithm is more e�ective than the nearest neighbor method. The basic principle of the nearest neighbor method is to �nd the minimum distance from each arc (i, j). The cheapest insertion heuristic algorithm inserts each node k on arc (i, j). Then �nd the minimum distance between the two insertion arcs so that the node not visited can be avoided. 4. CONCLUSIONS RCOCVRP with time windows can be used to solve waste trans- portation route problems. The results of the calculation of this model using the nearest neighbor method and the cheapest in- sertion heuristics algorithm produce almost the same solution because the principle of these two heuristic approaches is to �nd the closest distance. the cheapest insertion heuristics al- gorithm is more e�cient than the nearest neighbor algorithm for determining the route of the waste transport vehicle. From the calculation results, it is found that the cheapest insertion heuristic algorithm is more e�cient than the nearest neighbor algorithm for determining the route of the waste transport vehi- cle. REFERENCES Agra, A., M. Christiansen, R. Figueiredo, L. M. Hvattum, M. Poss, and C. Requejo (2013). The robust vehicle routing problem with time windows. Computers & operations research, 40(3); 856–866 Alatartsev, S., M. Augustine, and F. Ortmeier (2013). Constrict- © 2021 The Authors. Page 56 of 57 Yuliza, E et. al. Science and Technology Indonesia, 6 (2021) 53-57 Table 6. The solution of the RCOCVRP model with time windows in working area 2 and working area 3 Route Distance (km) Working Area 2 TDS 1 – TDS 2 – TDS 3 – FDS 5.8 TDS 4 – FDS 6.2 Working Area 3 TDS 1 – TDS 2 – TDS 3 – FDS 5.86 TDS 4 – TDS 5 – TDS 6 – FDS 5.75 TDS 7 – TDS 8 – FDS 6.18 TDS 9 – TDS 11 – FDS 6.4 TDS 10 – FDS 6.4 ing insertion heuristic for traveling salesman problem with neighborhoods. Twenty-Third International Conference on Au- tomated Planning and Scheduling, 23(1); 2–9 Braaten, S., O. Gjønnes, L. M. Hvattum, and G. Tirado (2017). Heuristics for the robust vehicle routing problem with time windows. Expert Systems with Applications, 77; 136–147 Buhrkal, K., A. Larsen, and S. Ropke (2012). The waste collection vehicle routing problem with time windows in a city logistics context. Procedia-Social and Behavioral Sciences, 39; 241–254 Campos, A. A. and J. E. C. Arroyo (2016). An ILS Heuristic for the Waste Collection Vehicle Routing Problem with Time Windows. Advances in Intelligent Systems and Computing, 557; 889–899 De La Vega, J., P. Munari, and R. Morabito (2019). Robust op- timization for the vehicle routing problem with multiple de- liverymen. Central European Journal of Operations Research, 27(4); 905–936 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 Hannan, M., M. Akhtar, R. Begum, H. Basri, A. Hussain, and E. Scavino (2018). Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm. Waste management, 71; 31–41 Hartono, Y., F. M. Puspita, D. I. Permatasari, and B. Arisha (2018). LINGO-based on robust counterpart open capacitated vehicle routing problem (RC-OCVRP) model of waste transportation in Palembang. International Conference on Information and Communications Technology (ICOIACT), 18; 429–435 Nguyen, P. K., T. G. Crainic, and M. Toulouse (2013). A tabu search for time-dependent multi-zone multi-trip vehicle rout- ing problem with time windows. European Journal of Opera- tional Research, 231(1); 43–56 Perea, F., R. Ruiz, K. Katragjini, and G. d. S. de Optimización Apli- cada (2016). Integer programming, clustering, and local search approaches for grouping urban waste collection sites. Boletin de Estadistica E Investigacion Operativa, 32(3); 203–224 Pop, P. C., I. Zelina, V. Lupşe, C. P. Sitar, and C. Chira (2011). Heuristic algorithms for solving the generalized vehicle rout- ing problem. International Journal of Computers Communica- tions & Control, 6(1); 158–165 Puspita, F. M., E. S. Cahyono, S. Rahayu, and B. L. Sintia (2018a). Model of Demand Robust Counterpart Open Capacitated Ve- hicle Routing Problem (DRC-OCVRP) Simpli�cation by Ap- plying Preprocessing Techniques in Rubbish Controlling in Sematang Borang District, Palembang. E3S Web of Conferences, 68; 1–6 Puspita, F. M., Y. Hartono, N. Z. Syaputri, E. Yuliza, and W. D. Pratiwi (2018b). Robust counterpart open capacitated vehi- cle routing (RC-OCVRP) model in optimization of garbage transportation in District Sako and Sukarami, Palembang City. International Journal of Electrical and Computer Engineering, 8(6); 4382–4390 Scutellà, M. G. (2015). Logistics. In Lecture Note; 91–103 Sun, L. and B. Wang (2015). Robust optimisation approach for vehicle routing problems with uncertainty. Mathematical Problems in Engineering, 2015; 1–8 Sungur, I., F. Ordónez, and M. Dessouky (2008). A robust opti- mization approach for the capacitated vehicle routing problem with demand uncertainty. Iie Transactions, 40(5); 509–523 Yuliza, E. and F. Puspita (2019). The Branch and Cut Method for Solving Capacitated Vehicle Routing Problem (CVRP) Model of LPG Gas Distribution Routes. Science and Technology Indonesia, 4(4); 105–108 Yuliza, E., F. Puspita, S. Supadi, and S. Octarina (2020a). The robust counterpart open capacitated vehicle routing problem with time windows. Journal of Physics: Conference Series, 1663(1); 1–7 Yuliza, E., F. M. Puspita, and S. S. Supadi (2020b). The robust coun- terpart 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). Robust Optimiza- tion for the Counterpart Open Capacitated Vehicle Routing Problem With Time Windows. Advances in Social Science, Education and Humanities Research, 513; 556–560 © 2021 The Authors. Page 57 of 57 INTRODUCTION EXPERIMENTAL SECTION Materials Methods Nearest Neighbor Algorithm Cheapest Sequential Insertion Algorithm RESULTS AND DISCUSSION CONCLUSIONS