i i “A3-1519” — 2022/8/4 — 21:20 — page 439 — #1 i i i i i i in Computational and Applied Mathematics Trends Trends in Computational and Applied Mathematics, 23, N. 3 (2022), 439-469 Sociedade Brasileira de Matemática Aplicada e Computacional Online version ISSN 2676-0029 www.scielo.br/tcam doi: 10.5540/tcam.2022.023.03.00439 Capacited Vehicle Routing Problem with CO2 Emission Minimization Considering Path Slopes L. A. P. CANTÃO1*, A. YAMAKAMI2 and R. F. CANTÃO3 Received on November 12, 2020 / Accepted on February 7, 2022 ABSTRACT. This work presents the application of a CO2 emission estimation function for cargo vehicles on a Capacited Vehicle Routing Problems (CVRP) setting, considering route’s slopes variation. Compar- isons were established with functions minimizing fuel consumption and route length in a case study about selective collection of recyclable waste at Sorocaba, state of São Paulo, Brazil. Routes with lower emissions have been achieved without significantly increasing fuel consumption or distance traveled. Keywords: CO2 emission, vehicle routing problem, path slope. 1 INTRODUCTION Carbon dioxide (CO2) emissions from fossil fuel powered vehicles are an environmental problem because they contribute directly to the greenhouse gases (GHG) effect. Thus, minimization of such emissions can result in an overall decrease of pollution levels. Green Vehicle Routing Problems (G-VRP) are VRP aimed for environmental problems such as fossil fuel emissions and consumption reduction or traffic jam prevention, to name but a few. Specifically about GHG emissions, [10] compiles data about the influence of driving patterns over emission factors for heavy duty vehicles. This methodology has been applied for VRPs in [11], [8], [7] and [13]. The aforementioned driving patterns are relaxed in the form of a Pollution-Routing Problem (PRP) as explored by [2], [5] and [4]. They assume that the instantaneous emission rate E (g/s) at *Corresponding author: Luiza Amalia Pinto Cantão – E-mail: luiza.amalia@unesp.br 1UNESP, Instituto de Ciências e Tecnologia de Sorocaba, Campus de Sorocaba, Av. Três de Março, 511, Alto da Boa Vista, 18085-180, Sorocaba, SP, Brazil – E-mail: luiza.amalia@unesp.br https://orcid.org/0000-0002-0610-0737 2Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação (FEEC), Departamento de Sis- temas e Energia (DSE), Av. Albert Einstein, 400, 13083-852, Campinas, SP, Brazil – E-mail: ayamakami66@gmail.com https://orcid.org/0000-0003-3537-4638 3Universidade Federal de São Carlos, Departamento de Fı́sica, Quı́mica e Matemática (DFQM), Rodovia João Leme dos Santos (SP-264), km 110, 18052-780, Sorocaba, SP, Brazil – E-mail: rfcantao@ufscar.br https://orcid.org/0000-0003- 2308-3833 i i “A3-1519” — 2022/8/4 — 21:20 — page 440 — #2 i i i i i i 440 CVRP GREEN CONSIDERING PATH SLOPES the exhaust is directly related to fuel consumption rate F (g/s) through the relation E = δ1F +δ2 where δ1 and δ2 are GHC specific parameters. The exact same formulation is used by [17] on a VRP with backhauling. In [22] a bi-objective Green Vehicle Routing and Scheduling Problem (G-VRSP) is presented. The main objective is the minimization of CO2 emissions, depending on the types both of the vehicle and the fuel. The secondary objective is a penalty function accounting for delays at clients. COPERT – Computer programme to calculate emissions from road transport [15] – is a software financed by the European Environment Agency, designed to estimate pollutant emission from road transport and urban traffic. The estimates are based on vehicle model, type of fuel, circula- tion area and speed limits. The fifth version of COPERT for Windows can be freely downloaded from https://copert.emisia.com/installing/. In [19] and [20] a geoprocessing tool, ArcGIS 3D, was used to map geographical information along the routes, taking into account elevation. COPERT [15] was used to fit fuel consumption parameters. Both papers have shown that the use of geographical information (mainly elevation) can bring significant improvements in the solution when compared with “flat” models, where the effects of inclination is disregarded. Amongst all the works presented here, these two are the only ones making use of geographical information in their models. Unfortunately, ArcGIS 3D and its optimization extension ArcGIS Network Analyst are closed source commercial software, thus hiding the details about the VRP used. The present work builds upon [21] where the authors propose to minimize CO2 emissions asso- ciating them with the physical work resulting from the forces the vehicle is subjected to. Even though the authors include the slope in the equations, all results were obtained disregarding in- clination (null slope). So, our contribution consists in effectively incorporating the slopes – and their corresponding effect onto CO2 emissions – into the objective function. A case study regarding selective collection of recyclable waste in the city of Sorocaba, state of São Paulo, Brazil, provides the common ground to compare the proposed objective function with the ones presented by [23] and applied by [18], in addition to the classical distance (symmetrical distances from the origin to depot). The mathematical model for the Capacited Vehicle Routing Problem (CVRP) is given by (1.1), as described in [23] and [12], which in turn is an Integer Linear Programming Problem (ILPP). Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 441 — #3 i i i i i i L. A. P. CANTÃO, A. YAMAKAMI and R. F. CANTÃO 441 Different options for the objective function (1.1a) will be examined in Section 2, so we opted to introduce the model with a generic one. min n ∑ i=1 n ∑ j=1 ci jxi j (1.1a) Subject to n ∑ j=0 i 6= j xi j = 1 ∀i ∈ N? (1.1b) n ∑ j=0 i 6= j xi j− n ∑ j=0 i6= j x ji = 0 ∀i ∈ N (1.1c) n ∑ j=0 i 6= j y ji− n ∑ j=0 i6= j yi j = Di ∀i ∈ N? (1.1d) yi j ≤ Qxi j, ∀i, j ∈ N (1.1e) n ∑ j=0 x0 j = |K| (1.1f) xi j ∈ {0,1} ∀i, j ∈ N?, (1.1g) where • n is the number of nodes other than node 0, that represents the depot. • N = {0,1,2, . . . ,n} and N? = {1,2, . . . ,n}. • xi j is a binary variable evaluating to 1 if the vehicle goes from i to j, 0 otherwise. • yi j is the truck load from i to j. • ci j is the cost to go from i to j. • Di is the demand associated with node i. • Q is the maximum vehicle capacity. • |K| is the fleet size and also the number of routes. Meaning of the equations in the model: • (1.1a) Minimization of the cost to carry out the routes. • (1.1b) Each customer can only be visited once. • (1.1c) Vehicles must enter and leave a node right away. • (1.1d) Represents the load increase after visiting a node. The added weight is equal to the demand of the visited node. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 442 — #4 i i i i i i 442 CVRP GREEN CONSIDERING PATH SLOPES • (1.1e) Loads must not exceed the vehicle capacity Q. Vehicles must return to the depot when they reach or are close to its maximum capacity. • (1.1f) Each vehicle in the fleet must follow one of the |K| routes, ensuring that no cycles are formed [12]. • (1.1g) xi j is a binary variable, evaluating to 1 if the vehicle goes from i to j, 0 otherwise. Different objective functions will be plugged to the Problem (1.1), as presented below. 2 THE CVRP COST FUNCTIONS Three cost functions for the CVRP were used, each one modeling a separate feature, namely the amount of CO2 emission considering the slope of the streets, fuel consumption (with no slope) and distance traveled by each vehicle. 2.1 Calculation of fuel consumption and total emission Toro et al. [21] present a Green Capacitated Location-Routing Problem (G-CLRP), where fuel consumption between nodes i and j is obtained based on the forces acting on the vehicle, as shown in Figure 1. Note that in the description of forces it is assumed that the vehicle is going up. Figure 1: Forces acting on a truck moving upwards. Source: Adapted from [21]. Defining • βi j: slope of the path between i and j. • ~FM: force generated by the engine and transmitted to the tires of the vehicle. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 443 — #5 i i i i i i L. A. P. CANTÃO, A. YAMAKAMI and R. F. CANTÃO 443 • m~g: vehicle weight (mass × gravity). • ~N: normal force of the inclined plane on the vehicle. • vi j: vehicle speed between i and j. • di j: distance between nodes i and j. • ~FR: forces opposing to the vehicle movement (friction, wind and internal). Force balancing equations Assuming the same constant speed along all sections of all routes (vi j = v = constant,∀i, j ∈ N), the balance of forces is given as follows: ∑~Fx = m~ax⇒ ~FM−~FR−m~gsinβi j = 0 ∑~Fy = m~ay⇒ ~N−m~gcosβi j = 0 where ~FR = ~FR,tires +~FR,w +~FR,i + mv2 2di j and • ~FR,tires represents the frictional force between tires and terrain that opposes the movement of the vehicle. • ~FR,w is the air resistance. • ~FR,i represents the equivalent force of the internal forces that oppose the movement of the vehicle. • mv2 i j 2di j is the force necessary for the vehicle to reach the permanent kinetic energy regime (constant speed). • m is the mass of the vehicle which is given by the mass of the empty vehicle m0 plus the load t carried between nodes i and j (ti j), that is, m = m0 + ti j. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 444 — #6 i i i i i i 444 CVRP GREEN CONSIDERING PATH SLOPES By definition ~FR,tires = ~Nb, where b is a terrain-dependent constant1. So, ~FM = ~FR +m~gsinβi j = ~FR,tires +~FR,w +~FR,i + mv2 2di j +m~gsinβi j = ~Nb+~FR,w +~FR,i + mv2 2di j +m~gsinβi j = (m~gcosβi j)b+~FR,w +~FR,i + mv2 2di j +m~gsinβi j. Taking the magnitude of ~FM , we have FM = (mgcosβi j)b+FR,w +FR,i + mv2 2di j +mgsinβi j. (2.1) The work Ui j = FMdi j from i to j is then given by: Ui j = [ (mgcosβi j)b+FR,w +FR,i + mv2 2di j +mgsinβi j ] di j = [ (m0 + ti j)gbcosβi j +FR,w +FR,i + (m0 + ti j)v2 2di j +(m0 + ti j)gsinβi j ] di j = [ m0g ( bcosβi j + v2 i j 2gdi j + sinβi j ) +FR,w +FR,i ] di j + [ g ( bcosβi j + v2 i j 2gdi j + sinβi j )] ti jdi j. (2.2) Downward force balancing equation What if the vehicle is going down? The forces ~FM and ~FR will be reversed. Consequently: ∑~Fx = m~ax⇒ ~FM−~FR +m~gsinβi j = 0 ∑~Fy = m~ay⇒ ~N−m~gcosβi j = 0 1According to https://www.ctborracha.com/borracha-sintese-historica/propriedades-das- borrachas-vulcanizadas/propriedades-tribologicas/ the coefficient of kinetic friction between the tire and the asphalt is b = 0.72 N. Accessed in 08/21/2019. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 445 — #7 i i i i i i L. A. P. CANTÃO, A. YAMAKAMI and R. F. CANTÃO 445 Similarly, we have: Ui j = [ m0g ( bcosβi j + v2 i j 2gdi j − sinβi j ) +FR,w +FR,i ] di j + [ g ( bcosβi j + v2 i j 2gdi j − sinβi j )] ti jdi j. General Case Assuming constant speed, we get Ui j = αi jdi j + γi jti jdi j, (2.3) where the constants αi j depend on the mean slope between i and j, the unloaded vehicle weight, the energy to achieve the steady state speed, the resistance on the tires, the air resistance and the internal vehicle losses. Some of these quantities, in turn, depend on the speed of the vehicle. Constants γi j depend on the slope of the path between i and j and the resistance of the tires. The work required between i and j has a component that is related to the unloaded vehicle, αi jdi j and another component that is related to the carried load, that is, γi jti jdi j. The work required for the vehicle to complete a route is given by the sum of the work of each arc. Associating it to a binary variable xi j, we have: ∑ i, j∈V Ui j = ∑ i, j∈V αi jdi jxi j + ∑ i, j∈V γi jdi jti j, (2.4) where xi j is 1 if the arc between i and j is used, 0 otherwise. Note that it is possible to obtain the average slope of (i, j) thus allowing the estimation of αi j and γi j for each arc, and so the objective function is linear. The amount of fuel used to perform the total work ∑i, j∈V Ui j is obtained with a conversion factor E1 (gallons/J). The emitted amount per unit of fuel is given by another conversion factor, E2 (kg of CO2/gallon). These factors depend on the type of vehicle and the fuel used, see [3] and [6]. Finally, the total emission can be calculated as: E1×E2× ∑ i, j∈V Ui j = E× ∑ i, j∈V Ui j. (2.5) Some dimensional analysis shows that gallon J︸ ︷︷ ︸ E1 × CO2 gallon︸ ︷︷ ︸ E2 × J︸︷︷︸ ∑Ui j =CO2. 2.2 Fuel consumption rate – FCR In [23], an attempt is made to solve a capacitated vehicle routing problem using a function that estimates the fuel consumption rate (FCR), where the distance traveled per unit volume of fuel Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 446 — #8 i i i i i i 446 CVRP GREEN CONSIDERING PATH SLOPES is inversely proportional to the vehicle weight. Since Q0 corresponds to the weight of the empty vehicle and Q1 to the transported load, FCR is formulated as a linear function depending on Q1: ρ(Q1) = α(Q0 +Q1)+b, (2.6) with b being constant. Let Q be the maximum capacity of the vehicle, ρ∗ and ρ0 as the fuel consumption rate for the full-loaded and empty truck, respectively. It can be seen from (2.6) that ρ∗(Q) = α(Q0 +Q)+b and ρ0 = αQ0 +b. Then: ρ ∗−ρ0 = α(Q0 +Q)+b− (αQ0 +b) = αQ0 +αQ+b−αQ0−b = αQ. Isolating α , we have: α = ρ∗−ρ0 Q (2.7) which is the slope of the line given by Equation (2.6). Rewriting it: ρ(Q1) = αQ0 +b+αQ1 = ρ0 +αQ1 = ρ0 + ρ∗−ρ0 Q Q1 (2.8) where ρ0 = αQ0 +b⇒ ρ0 = ρ∗−ρ0 Q Q0 +b is the empty truck weight. For any arc between i and j, where j is the next customer to be served after leaving i, fuel cost is given by: Ci j f uel = c0ρi jdi j, (2.9) where • c0 is the unit cost of fuel. • ρi j FCR along the route from i to j. • di j distance traveled between i and j. Denoting n as the number of customers on the route, we have: C f uel = n ∑ i=1 n ∑ j=1 Ci j f uel = n ∑ i=1 n ∑ j=1 c0ρi jdi jxi j, (2.10) where xi j is binary, assuming value 1 if the vehicle goes from node i to j, and 0 otherwise. Denoting yi j as the load weight carried between i and j, Equation (2.8) becomes ρi j = ρ0 + ρ∗−ρ0 Q yi j = ρ0 +αyi j. (2.11) Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 447 — #9 i i i i i i L. A. P. CANTÃO, A. YAMAKAMI and R. F. CANTÃO 447 Considering that vehicles have a fixed operational cost F and 0 represents the depot, the objective function becomes: min n ∑ j=1 Fx0 j + n ∑ i=0 n ∑ j=0 c0di jxi j(ρ0 +αyi j), (2.12) which is nonlinear. Constraint (1.1e), however, guarantees that yi j = 0 when xi j = 0 [23], thus allowing us to rewrite (2.12) as min n ∑ j=1 Fx0 j + n ∑ i=0 n ∑ j=0 c0di j(ρ0xi j +αyi j). (2.13) This function was used with a CVRP by [18] in a case study applied to selective recyclable waste collection. 3 COMPUTATIONAL TESTS Tests were performed on an Intel Core i7-2600 desktop, with 3.4 GHz, 8.0 GB of RAM and Microsoft Windows 7 Home Premium operating system. Instances were solved with CPLEX version 23.7. Data were taken from [18] which presents a CVRP for the garbage collection of a cooperative in the city of Sorocaba, state of São Paulo, Brazil. At each node, in addition to its geographical coordinates (latitude and longitude), we add its altitude obtained with Google Earth Pro software, version 7.3.2.5776, for Debian GNU/Linux operating system. Distances between locations were calculated using the Haversine distance di j = 2 ·6371 arcsin [ sin ( Lat j−Lati 2 )2 + cos(Lati)cos(Lat j)sin ( Lon j−Loni 2 )2 ]1/2 (3.1) where Lat and Lon represent latitude and longitude, respectively [1]. Each instance was tested with the constraints presented in (1.1) and three different objective functions: 1. Distance ∑di jxi j. 2. FCR (2.13) without the first part of the function (fixed cost of the vehicle), with the same data as modeled in [18], that is, ρ(Q) = 1×105Q+0.1111, with an estimated fuel cost of R$ 2,999 per liter (R$: Brazilian Real). 3. Function (2.4). Description of the data follows. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 448 — #10 i i i i i i 448 CVRP GREEN CONSIDERING PATH SLOPES Function (2.4) In order to use (2.4), we need to determine the parameters of (2.2). We have chosen a IVECO Tector truck, 4 × 2, of 9 tonnes2. As the FR,i value is not available in the literature and we are not able to properly define a value for it, we are assuming FR,i = 0. For FR,w (aerodynamic drag coefficient), we have: FR,w = 1 2 ρCxAv2 being: • ρ = 1.184 kg/m3, air density with a temperature around 25◦C. • Cx = 0.9, aerodynamic coefficient for a truck. • A = 2.491×1.890 = 4.70799 m2, estimated cross-sectional area for a 9-ton Tector truck. • v = 20×(1000/3600) m/s, constant speed between nodes. Other function parameters: • m0 = 3025 kg, empty truck weight. • g = 9.81 m/s2, gravitational constant. • b = 0.72 N, friction of the tire with the asphalt. The angle βi j can be obtained with the help of Figure 2. Figure 2: Right triangle used to calculate βi j. Given the distances we estimate the difference in height between two nodes: ∆Alti j = Alt j−Alti, 2https://www.iveco.com/brasil/produtos/pages/tector\_carac\_bene.aspx Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 449 — #11 i i i i i i L. A. P. CANTÃO, A. YAMAKAMI and R. F. CANTÃO 449 where Alti and Alt j are the heights at nodes i and j, respectively, on the opposite side to βi j. The adjacent side to βi j is given by: xi j = √ d2 i j−∆Alt2 i j. Finally, βi j = arctan ( ∆Alti j xi j ) . For the Emission Factor, we assume E = 694 CO2 (g/KWh)3, for medium-sized trucks. 3.1 Validation problem For model validation, five points were chosen in the city of Sorocaba, state of São Paulo, Brazil, corresponding to recyclable waste generators of reasonable size (three universities, one shopping mall and one residential building playing depot). All points have different heights, as can be seen in Table 1. Table 1: Test data. Height (m) Latitude (◦) Longitude (◦) Demand (kg) 0 601 −23.50874 −47.46598 3700 1 609 −23.50325 −47.46365 3700 2 613 −23.47935 −47.41724 3700 3 667 −23.58126 −47.52405 3700 4 646 −23.53465 −47.46277 3700 Inclinations can be seen on (3.2), where we assign index 0 (origin/depot) to the first row and first column.  0 0.0122 0.0020 0.0066 0.0155 −0.0122 0 0.0007 0.0055 0.0106 −0.0020 −0.0007 0 0.0034 0.0043 −0.0066 −0.0055 −0.0034 0 −0.0026 −0.0155 −0.0106 −0.0043 0.0026 0  (3.2) Results are shown in Tables 2, 3 and 4. For each objective function (minimization of CO2, FCR and minimum distance), the solution is evaluated in the other two. Table 2: Result when minimizing CO2. CO2 (kg) FCR (R$) Distance (m) 344.884 15.339 31906.361 Route 0 – 3 – 4 – 2 – 1 – 0 3https://cetesb.sp.gov.br/veicular/relatorios-e-publicacoes/ Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 450 — #12 i i i i i i 450 CVRP GREEN CONSIDERING PATH SLOPES Table 3: Result when minimizing FCR. CO2 (kg) FCR (R$) Distance (m) 344.884 15.339 31906.361 Route 0 – 3 – 4 – 2 – 1 – 0 Table 4: Results when minimizing distance. CO2 (kg) FCR (R$) Distance (m) 560.355 20.085 31906.361 Route 0 – 1 – 2 – 4 – 3 – 0 Looking at Tables 2, 3 and 4, we note that two different routes were found for the three objective functions. Problems minimizing CO2 and fuel consumption (FCR) provided the same solution, while for the minimum distance problem we have a different route, with the same optimal value in distance for all cases. To better understand these results, Tables 5 and 6 show the cost of each arc for both routes, rounded to three decimals. Table 5: Route 0 – 3 – 4 – 2 – 1 – 0. Arc Distance (m) FCR (R$) CO2 (kg) 0 – 3 10003.242 3.332 41.738 3 – 4 8116.461 3.605 74.196 4 – 2 7704.099 4.277 108.854 2 – 1 5427.043 3.615 104.394 1 – 0 655.515 0.510 15.702 31906.361 15.339 344.884 The distance traveled on both routes is equal because the arcs traversed are symmetrical, for example (0 – 3) and (3 – 0), on routes 1 and 2 respectively. However, when we calculate the arc cost (1 – 2) and (2 – 1) for the other functions, these have different costs, and consequently, the route on Table 5 minimizes the costs of the other functions discussed here. If we only consider distance tough, both routes provide a minimal cost. Looking at Table 6 it can be seen that routes start with smaller distances and end with greater ones, making both the FCR cost and CO2 emissions higher, since they are proportional to truck weight. The route on Table 5 reverses the case: the longest path is traveled with less load. In this small validation example, solutions for the FCR function and emission of CO2 resulted in the same path, due to the size of the problem; in other cases, as seen next, different solutions were obtained. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 451 — #13 i i i i i i L. A. P. CANTÃO, A. YAMAKAMI and R. F. CANTÃO 451 Table 6: Route 0 – 1 – 2 – 4 – 3 – 0. Arc Distance (m) FCR (R$) CO2 (kg) 0 – 1 655.515 0.219 2.765 1 – 2 5427.043 2.410 49.847 2 – 4 7704.099 4.277 110.155 4 – 3 8116.461 5.406 156.827 3 – 0 10003.242 7.773 240.761 31906.361 20.085 560.355 3.2 Case Study: CORESO Cooperative CORESO cooperative collects recyclable materials from some selected neighborhoods in the city of Sorocaba, state of São Paulo, Brazil, predominantly on the eastern part of the city. In 2016, it covered 230 streets (nodes) from Monday to Friday, comprising around 9000 collection points (door-to-door collection and collective generators). The collection points are illustrated4 in Figure 3. Routes were separated by weekdays, as requested by the cooperative administrative board, and demand requires two daily routes, for trucks with a capacity of 4000 kg. Tables 7, 8 and 9 present in bold the results obtained with the three objective functions previously described (CO2, FCR and distance) respectively, and the number of nodes of each route, including the depot. The remaining columns show the values of the other two objective functions when calculated on the optimal route. The number of nodes sums up to 235 because some streets are visited more than once a week. Table 7: Results for the cooperative when minimizing emissions of CO2. For the sake of com- parison, numbers in italics represent the solution when all slopes are considered zero. Although seemingly small, there are differences in four of five days. Distance FCR CO2 CO2 Number m R$ kg kg (no slopes) of nodes Monday 17932.364 6.694 104.993 106.945 60 Tuesday 10576.397 3.903 61.394 61.394 49 Wednesday 9606.025 3.516 54.400 57.269 46 Thursday 13257.440 4.920 77.865 77.889 39 Friday 9273.732 3.416 53.613 53.561 41 Totals 60645.958 22.449 352.265 357.058 235 Table 7 brings, for comparison purposes, the solution for the CO2 emissions minimization prob- lem, when all slopes are made zero (numbers in italics). For Monday, Wednesday and Thursday 4Figures 3 to 18 were made with a Python [9] script created by the authors. The script uses the GeoPandas library [14] with maps provided by OpenStreetMap [16]. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 452 — #14 i i i i i i 452 CVRP GREEN CONSIDERING PATH SLOPES Figure 3: Collection points for recyclable materials at Sorocaba, state of São Paulo, Brazil. In the upper picture the points and the city boundaries can be seen. In the lower picture, there is a zoom comprising all points. results considering the inclination are smaller, and thus better, than the zero slope ones. Although counterintuitive, that is one of the main results of this work. Clearly, larger slopes must result in larger CO2 emissions, when sections of the route are taken individually. Equations (2.2) and (2.4) show that, when considering the whole route, inclination and weight (truck plus cargo) play to- gether, resulting in sections with larger slopes coming first in the route, when the truck is almost empty, thus effectively reducing the emission. Tuesday reaches a match and Friday is a little worse. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 453 — #15 i i i i i i L. A. P. CANTÃO, A. YAMAKAMI and R. F. CANTÃO 453 Table 8: Results for the cooperative when minimizing consumption of fuel (FCR). Distance FCR CO2 Number m R$ kg of nodes Monday 17932.364 6.644 104.993 60 Tuesday 10572.502 3.903 61.407 49 Wednesday 9568.617 3.510 54.544 46 Thursday 13180.610 4.902 77.889 39 Friday 9148.581 3.388 53.723 41 Totals 60402.674 22.347 352.556 235 Table 9: Results for the cooperative when minimizing distance. Distance FCR CO2 Number m R$ kg of nodes Monday 17932.364 6.721 108.493 60 Tuesday 10560.528 4.069 69.564 49 Wednesday 9490.884 3.755 66.614 46 Thursday 13094.096 4.923 79.846 39 Friday 9148.581 3.388 53.723 41 Totals 60226.453 22.856 378.240 235 Table 7 (minimization of emissions) shows that the net reduction on the CO2 emission is 4.793 kg per week, totaling almost 250 kg a year when slopes are taken into account. In the case of the fuel minimization function (results in Table 8), the decrease on the CO2 emission is smaller (4.502 kg per week, 234.104 kg a year) when compared with the minimization of emissions with zero slope, as expected. Minimization of emissions (Table 7) with slopes in play and minimization of fuel consumption (Table 8) have very close weekly emissions – a difference of 0.291 kg per week – with an added bonus of an economy of roughly R$ 5.30 a year. Of course the decision is up to the managerial board, but an extra reduction of emissions seems to be worth this extra cost. Distance minimization (Table 9) can short the routes in 419 m per week or 21 km a year, with an expressive increase in CO2 emissions (about 1350 kg a year). One can argue that shorter travels can extend the lifespan of the trucks and save time, but these savings are negligible: 21 km corresponds to only 0.67 % of the total distance traveled during a year. To summarize, the minimization of CO2 emissions can prevent 250 kg of pollutant reaching the atmosphere a year, while increasing fuel costs and distance traveled by a negligible amount of R$ 5.30 and 21 km, also per year respectively, a very small price to pay for the reduction of greenhouse gases and thus the overall improvement of environmental conditions. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 454 — #16 i i i i i i 454 CVRP GREEN CONSIDERING PATH SLOPES 3.3 Results for Monday Table 10 and Figures 4, 5 and 6 illustrate for Monday, results and the routes minimizing CO2 emissions, FCR cost and distance, respectively. Table A.1 presents the streets and their respective indices. Table 10: Summary of results for Monday. Numbers in bold are the minimum for that objective function. Objective Distance FCR CO2 Number Function m R$ kg of nodes CO2 emission 17932.364 6.644 104.993 60 FCR 17932.364 6.644 104.993 60 Distance 17932.364 6.721 108.493 60 As it can be seen, routes for the minimization of CO2 emissions and FCR cost are exactly the same, showing that inclinations probably were not big enough to make a difference. For distance minimization we have the same collection points, but in opposite directions, hence the same distance in all cases, but with an increase of 3.5 kg in emissions due to heavier loads close to the end of the route. 0 33 29 32 38 28 37 35 34 1 27 39 36 30 2 31 44 43 56 54 41 40 45 42 57 55 53 52 58 50 49 48 59 51 47 46 0 23 9 21 8 10 6 20 14 22 12 11 7 5 4 3 19 18 25 24 13 15 16 17 26 Figure 4: Routes minimizing CO2 emissions for Monday. 60 collection points are covered, total- ing a distance of 17932.364 m, 104.993 kg of emitted CO2 and a FCR cost of R$ 6.694. Numbers in routes refer to Table A.1. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 455 — #17 i i i i i i L. A. P. CANTÃO, A. YAMAKAMI and R. F. CANTÃO 455 0 33 29 32 38 28 37 35 34 1 27 39 36 30 2 31 44 43 56 54 41 40 45 42 57 55 53 52 58 50 49 48 59 51 47 46 0 23 9 21 8 10 6 20 14 22 12 11 7 5 4 3 19 18 25 24 13 15 16 17 26 Figure 5: Routes minimizing FCR for Monday. 60 collection points are covered, totaling a dis- tance of 17932.364 m, 104.993 kg of emitted CO2 and a FCR cost of R$ 6.644. Numbers in nodes refer to Table A.1. 0 49 48 59 51 47 55 53 52 58 50 46 57 56 54 41 40 45 30 2 31 44 43 42 36 37 35 34 1 27 33 29 32 38 28 39 0 26 25 24 13 15 4 3 19 18 17 16 5 7 6 20 14 22 9 21 8 10 11 12 23 Figure 6: Routes minimizing distance for Monday. 60 collection points are covered, totaling a distance of 17932.364 m, 108.493 kg of emitted CO2 and a FCR cost of R$ 6.721. Numbers in nodes refer to Table A.1. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 456 — #18 i i i i i i 456 CVRP GREEN CONSIDERING PATH SLOPES 3.4 Results for Tuesday Table 11 and Figures 7, 8 and 9 illustrate for Tuesday, results and routes minimizing CO2 emis- sions, FCR cost and distance, respectively. Table A.2 presents the streets and their respective indices. Table 11: Summary of results for Tuesday. Numbers in bold are the minimum for that objective function. Objective Distance FCR CO2 Number Function m R$ kg of nodes CO2 emission 10576.397 3.903 61.394 49 FCR 10572.502 3.903 61.407 49 Distance 10560.528 4.069 69.564 49 For Tuesday results for emission and FCR minimization are very close, as well as their respec- tive routes (only a few streets in different places along the route). On the other hand, distance minimization was able to cut off only 15.869 m with a corresponding increase of 8.17 kg of CO2, clearly showing that a few tweaks in the routes can have a big impact on the amount of emission, with minimal effect on the distance. It is interesting to notice that on the distance minimization problem, there is a clear unbalance on the route size, as if the solution is built by trying to travel as much as possible in one route (possibly through shorter sections), leaving a few streets for the second. 0 46 14 13 38 34 32 33 1 36 37 39 35 17 18 19 20 21 25 26 24 27 23 22 30 40 29 28 41 31 47 45 48 7 0 43 2 8 5 3 15 11 10 9 4 6 12 16 42 44 Figure 7: Routes minimizing CO2 emissions for Tuesday. 49 collection points are covered, total- ing a distance of 10576.397 m, 61.394 kg of emitted CO2 and a FCR cost of R$ 3.903. Numbers in nodes refer to Table A.2. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 457 — #19 i i i i i i L. A. P. CANTÃO, A. YAMAKAMI and R. F. CANTÃO 457 0 46 14 13 38 34 32 33 1 36 39 37 35 17 18 19 20 21 25 26 24 27 23 22 30 40 29 28 41 31 47 45 48 7 0 43 6 3 2 8 15 11 10 9 4 5 12 16 42 44 Figure 8: Routes minimizing FCR for Tuesday. 49 collection points are covered, totaling a dis- tance of 10572.502 m, 61.407 kg of emitted CO2 and a FCR cost of R$ 3.903. Numbers in nodes refer to Table A.2. 0 45 42 16 12 15 44 46 11 0 47 48 7 31 41 26 25 30 40 29 28 24 27 23 22 21 20 33 32 35 17 18 19 1 36 39 37 34 38 5 4 9 10 14 13 8 2 3 6 43 Figure 9: Routes minimizing distance for Tuesday. 49 collection points are covered, totaling a distance of 10560.528 m, 69.564 kg of emitted CO2 and a FCR cost of R$ 4.069. Numbers in nodes refer to Table A.2. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 458 — #20 i i i i i i 458 CVRP GREEN CONSIDERING PATH SLOPES 3.5 Results for Wednesday Table 12 and Figures 10, 11 and 12 illustrate for Wednesday, results and routes minimizing CO2 emissions, FCR cost and distance, respectively. Table A.3 presents the streets and their respective indices. Table 12: Summary of results for Wednesday. Numbers in bold are the minimum for that objec- tive function. Objective Distance FCR CO2 Number Function m R$ kg of nodes CO2 emission 9606.025 3.516 54.400 46 FCR 9568.617 3.510 54.544 46 Distance 9490.884 3.755 66.614 46 Once more minimization of emissions and FCR have very similar routes, with a negligible dif- ference on the CO2 emission: only 0.144 kg. On the other hand, Wednesday has the biggest dif- ference in emission when comparing with the distance minimization function, 12.214 kg, for a route 115.141 m shorter. Environmental-wise, it makes much more sense to choose the minimum emission route. 0 41 28 42 30 27 44 38 35 40 39 29 0 31 21 9 20 10 13 19 17 14 15 16 12 18 11 7 6 8 25 24 1 4 22 5 26 23 2 3 32 33 43 45 37 36 34 Figure 10: Routes minimizing CO2 emissions for Wednesday. 46 collection points are covered, totaling a distance of 9606.025 m, 54.400 kg of emitted CO2 and a FCR cost of R$ 3.516. Numbers in nodes refer to Table A.3. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 459 — #21 i i i i i i L. A. P. CANTÃO, A. YAMAKAMI and R. F. CANTÃO 459 0 41 28 42 30 27 44 38 35 40 39 29 0 31 21 9 20 10 14 17 19 13 12 16 15 18 11 7 6 8 25 24 1 4 22 5 26 23 2 3 32 33 43 45 37 36 34 Figure 11: Routes minimizing FCR for Wednesday. 46 collection points are covered, totaling a distance of 9568.617 m, 54.544 kg of emitted CO2 and a FCR cost of R$ 3.510. Numbers in nodes refer to Table A.3. 0 44 38 37 36 45 43 0 35 34 40 39 28 33 29 27 30 42 41 32 3 2 23 26 25 8 5 22 4 1 24 6 7 11 18 15 14 10 16 12 13 19 17 20 9 21 31 Figure 12: Routes minimizing distance for Wednesday. 46 collection points are covered, totaling a distance of 9490.884 m, 66.614 kg of emitted CO2 and a FCR cost of R$ 3.755. Numbers in nodes refer to Table A.3. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 460 — #22 i i i i i i 460 CVRP GREEN CONSIDERING PATH SLOPES 3.6 Results for Thursday Table 13 and Figures 13, 14 and 15 illustrate for Thursday, results and routes minimizing CO2 emissions, FCR cost and distance, respectively. Table A.4 presents the streets and their respective indices. Table 13: Summary of results for Thursday. Numbers in bold are the minimum for that objective function. Objective Distance FCR CO2 Number Function m R$ kg of nodes CO2 emission 13257.440 4.920 77.865 39 FCR 13180.610 4.902 77.889 39 Distance 13094.096 4.923 79.846 39 Thursday is perhaps the most uniform day, with very close results for all objective functions, maybe because it has the smallest number of streets in the week. Despite that, emissions and FCR minimization have very different routes when compared to the previous days. Emissions and distance are not that different either, with a reduction of 1.981 kg of CO2 for an extra 163.344 m. 0 36 26 11 7 10 1 2 3 4 6 9 5 8 12 13 14 15 38 21 22 17 16 0 34 35 30 32 31 25 27 18 28 29 33 24 20 19 23 37 Figure 13: Routes minimizing CO2 emissions for Thursday. 46 collection points are covered, totaling a distance of 9606.025 m, 54.400 kg of emitted CO2 and a FCR cost of R$ 3.516. Numbers in nodes refer to Table A.4. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 461 — #23 i i i i i i L. A. P. CANTÃO, A. YAMAKAMI and R. F. CANTÃO 461 0 34 35 30 32 31 24 25 27 28 29 33 20 19 23 37 0 38 21 22 17 16 5 8 12 13 14 15 1 2 3 4 6 9 36 26 18 11 7 10 Figure 14: Routes minimizing FCR for Thursday. 46 collection points are covered, totaling a distance of 9568.617 m, 54.544 kg of emitted CO2 and a FCR cost of R$ 3.510. Numbers in nodes refer to Table A.4. 0 34 35 30 32 31 11 18 27 28 29 33 7 10 9 6 4 3 13 12 8 5 1 2 14 15 16 17 22 21 38 0 36 26 25 24 20 37 23 19 Figure 15: Routes minimizing distance for Thursday. 46 collection points are covered, totaling a distance of 9490.884 m, 66.614 kg of emitted CO2 and a FCR cost of R$ 3.755. Numbers in nodes refer to Table A.4. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 462 — #24 i i i i i i 462 CVRP GREEN CONSIDERING PATH SLOPES 3.7 Results for Friday Table 14 and Figures 16, 17 and 18 illustrate for Friday, the routes minimizing CO2 emissions, FCR cost and distance, respectively. Table A.5 presents the streets and their respective indices. Table 14: Summary of results for Friday. Numbers in bold are the minimum for that objective function. Objective Distance FCR CO2 Number Function m R$ kg of nodes CO2 emission 9273.732 3.416 53.613 41 FCR 9148.581 3.388 53.723 41 Distance 9148.581 3.388 53.723 41 Finally, Friday also has very uniform results, with FCR and distance minimization giving the same routes, with little gain when compared to CO2 emission minimization (only 0.110 kg, the smallest amongst all days). 0 18 21 15 22 17 35 16 23 19 38 20 27 26 25 24 28 30 36 29 34 32 33 31 37 39 40 0 2 3 7 8 6 11 12 4 13 14 10 1 9 5 Figure 16: Routes minimizing CO2 emissions for Friday. 46 collection points are covered, total- ing a distance of 9606.025 m, 54.400 kg of emitted CO2 and a FCR cost of R$ 3.516. Numbers in nodes refer to Table A.5. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 463 — #25 i i i i i i L. A. P. CANTÃO, A. YAMAKAMI and R. F. CANTÃO 463 0 18 21 15 22 17 35 16 23 19 38 20 27 26 25 24 28 30 34 32 33 13 14 31 29 36 37 39 40 0 2 3 7 8 6 9 1 11 12 4 10 5 Figure 17: Routes minimizing FCR for Friday. 46 collection points are covered, totaling a dis- tance of 9568.617 m, 54.544 kg of emitted CO2 and a FCR cost of R$ 3.510. Numbers in nodes refer to Table A.5. 0 18 21 15 22 17 35 16 23 19 38 20 27 26 25 24 28 30 34 32 33 13 14 31 29 36 37 39 40 0 2 3 7 8 6 9 1 11 12 4 10 5 Figure 18: Routes minimizing distance for Friday. 46 collection points are covered, totaling a distance of 9490.884 m, 66.614 kg of emitted CO2 and a FCR cost of R$ 3.755. Numbers in nodes refer to Table A.5. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 464 — #26 i i i i i i 464 CVRP GREEN CONSIDERING PATH SLOPES The biggest challenge was to implement and test Function (2.4). The inclusion of Function (2.13) and distance was used to compare results. We note that, with the routes obtained, the results are quite satisfactory in the sense that, even running paths with greater distances, still we have gained in the reduction of emission CO2 and fuel consumption, which benefits the environment in addition to generating a smaller workforce for the vehicle, increasing its useful life. 4 FINAL CONSIDERATIONS In this work we have presented the application of a Capacited Vehicle Routing Problem (CVRP) for a recycling cooperative at Sorocaba, state of São Paulo, Brazil, comparing three different and independent objectives: minimization of either distance, or fuel consumption rate or CO2 emissions. For the latter the inclination of each section of the route is considered, which affects the emission rate. The streets were previously chosen by the cooperative managerial board and grouped by business days. Two trucks perform the collection during the week simultaneously, meaning that for each objective two routes are obtained. Results have shown that is possible, with minor changes in the routes already in practice by the cooperative, emit a considerable smaller amount of CO2 in the atmosphere in the course of a year, with negligible increase either in traveled distance or fuel cost. It should be stressed that these minor adjustments are more easily adopted by both the board and the workers because they are associated with smaller business logic distress. Giving the competing nature of the objectives here addressed, CO2 emission, distance and fuel consumption rate, further research points to multiobjective formulations. A bi-objective problem – minimization of both CO2 and distance – is being prospectively addressed by the authors. Investment in green routes is necessary since environmental problems caused by pollutant emis- sions from motor vehicles is one of the biggest factors of air pollution and consequently of cli- mate change. With the increase in the fleet of vehicles, alternative fuels are increasingly becoming the focus of research. However, they cannot replace fossil fuels yet as they are energetically less efficient, thus proactively seeking better routes while keeping costs in check presents itself as a very viable option. Acknowledgments To the Department of Systems and Energy (DSE) of the Faculty of Electric Engineering and Computing (FEEC) of the State University of Campinas (UNICAMP) for the opportunity to carry out a Post-Doctorate internship and complete the present work. To the reviewers, whose invaluable remarks and suggestions helped a lot to improve this paper. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 465 — #27 i i i i i i L. A. P. CANTÃO, A. YAMAKAMI and R. F. CANTÃO 465 REFERENCES [1] M. Basyir, M. Nasir, Suryati & W. Mellyssa. Determination of Nearest Emergency Service Office using Haversine Formula Based on Android Platform. EMITTER International Journal of Engineering Technology, 5(2) (2017). [2] T. Bektaş & G. Laporte. The Pollution-Routing Problem. Transportation Research Part B: Methodological, 45(8) (2011), 1232 – 1250. doi:https://doi.org/10.1016/j.trb.2011.02.004. URL http://www.sciencedirect.com/science/article/pii/S019126151100018X. Supply chain disruption and risk management. [3] CETESB. Emissões veiculares no estado de São Paulo 2017. https://cetesb.sp.gov.br/ veicular/relatorios-e-publicacoes/ (2017). Acesso em 21/08/2019. [4] E. Demir, T. Bektaş & G. Laporte. An adaptive large neighborhood search heuristic for the Pollution- Routing Problem. European Journal of Operational Research, 223(2) (2012), 346 – 359. doi:https:// doi.org/10.1016/j.ejor.2012.06.044. URL http://www.sciencedirect.com/science/article/ pii/S0377221712004997. [5] E. Demir, T. Bektaş & G. Laporte. The bi-objective Pollution-Routing Problem. European Journal of Operational Research, 232(3) (2014), 464 – 478. doi:https://doi.org/10.1016/j.ejor.2013.08.002. URL http://www.sciencedirect.com/science/article/pii/S0377221713006486. [6] M. do Meio Ambiente. Primeiro Inventário Nacional de Emissões Atmosféricas por Veı́culos Au- tomotores Rodoviários – Relatório Final. http://antigo.antt.gov.br/index.php/content/ view/5632/1__Inventario_Nacional_de_Emissoes_Atmosfericas_por_Veiculos_ Automotores_Rodoviarios.html. Acesso em 21/08/2019. [7] M. Figliozzi. Vehicle Routing Problem for Emissions Minimization. Transportation Research Record, 2197(1) (2010), 1–7. doi:10.3141/2197-01. URL https://doi.org/10.3141/2197-01. [8] M.A. Figliozzi. The impacts of congestion on time-definitive urban freight distribution networks CO2 emission levels: Results from a case study in Portland, Oregon. Transportation Research Part C: Emerging Technologies, 19(5) (2011), 766 – 778. doi:https://doi.org/10.1016/j.trc.2010.11.002. URL http://www.sciencedirect.com/science/article/pii/S0968090X10001634. Freight Transportation and Logistics (selected papers from ODYSSEUS 2009 – the 4th International Workshop on Freight Transportation and Logistics). [9] P.S. Foundation. Python Programming Language (2021). URL https://www.python.org. [10] J. Hickman, D. Hassel, R. Joumard, Z. Samaras & S. Sorenson. Methodology for calculating transport emissions and energy consumption. Technical report, Transportation Research Laboratory (1999). [11] M. Çimen & M. Soysal. Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm. Transportation Research Part D: Trans- port and Environment, 54 (2017), 82 – 98. doi:https://doi.org/10.1016/j.trd.2017.04.016. URL http: //www.sciencedirect.com/science/article/pii/S1361920916305284. [12] S. Irnich, P. Toth & D. Vigo. The family of vehicle routing problems. In P. Toth & D. Vigo (editors), “Vehicle Routing: problems methods, and applications”. SIAM, second edition ed. (2014). Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 466 — #28 i i i i i i 466 CVRP GREEN CONSIDERING PATH SLOPES [13] O. Jabali, T. Van Woensel & A. De Kok. Analysis of travel times and CO2 emissions in time-dependent vehicle routing. Production and Operations Management, 21(6) (2012), 1060–1074. [14] K. Jordahl, J.V. den Bossche, M. Fleischmann, J. Wasserman, J. McBride, J. Gerard, J. Tratner, M. Perry, A.G. Badaracco, C. Farmer, G.A. Hjelle, A.D. Snow, M. Cochran, S. Gillies, L. Culbert- son, M. Bartos, N. Eubank, maxalbert, A. Bilogur, S. Rey, C. Ren, D. Arribas-Bel, L. Wasser, L.J. Wolf, M. Journois, J. Wilson, A. Greenhall, C. Holdgraf, Filipe & F. Leblanc. geopandas/geopandas: v0.8.1. Zenodo (2020). doi:10.5281/zenodo.3946761. URL https://doi.org/10.5281/zenodo. 3946761. [15] L. Ntziachristos & Z. Samaras. COPERT III Computer programme to calculate emissions from road transport – metodology and emission factors (version 2.1) (2000). URL https://www.eea.europa. eu/publications/Technical_report_No_49/at_download/file. Acesso em 31/07/2019. [16] OpenStreetMap contributors. Planet dump retrieved from https://planet.osm.org (2017). URL https: //www.openstreetmap.org. [17] L. Pradenas, B. Oportus & V. Parada. Mitigation of greenhouse gas emissions in vehicle routing problems with backhauling. Expert Systems with Applications, 40(8) (2013), 2985 – 2991. doi:https://doi.org/10.1016/j.eswa.2012.12.014. URL http://www.sciencedirect.com/ science/article/pii/S0957417412012559. [18] G.T. Santos, L.A.P. Cantão & R.F. Cantão. An ant colony system metaheuristics applied to a coopera- tive of recyclable materials of Sorocaba: a case of study. In V.N. Coelho, I.M. Coelho, T.A. de Oliveira & L.S. Ochi (editors), “Smart and Digital Cities”. Springer International Publishing (2019), p. 79–97. [19] G. Tavares, Z. Zsigraiova, V. Semiao & M. Carvalho. Optimisation of MSW collection routes for minimum fuel consumption using 3D GIS modelling. Waste Management, 29(3) (2009), 1176 – 1185. doi:https://doi.org/10.1016/j.wasman.2008.07.013. [20] G. Tavares, Z. Zsigraiova, V. Semiao & M.d.G. Carvalho. A case study of fuel savings through op- timisation of MSW transportation routes. Management of Environmental Quality: An International Journal, 19(4) (2008), 444–454. [21] E.M. Toro, J.F. Franco, M.G. Echeverri & F.G. Guimarães. A multi-objective model for the green ca- pacitated location-routing problem considering environmental impact. Computers and Industrial En- gineering, 110 (2017), 114 – 125. doi:https://doi.org/10.1016/j.cie.2017.05.013. URL http://www. sciencedirect.com/science/article/pii/S0360835217302176. [22] Y. Xiao & A. Konak. A simulating annealing algorithm to solve the green vehicle routing and schedul- ing problem with hierarchical objectives and weighted tardiness. Applied Soft Computing, 34 (2015), 372 – 388. doi:https://doi.org/10.1016/j.asoc.2015.04.054. URL http://www.sciencedirect. com/science/article/pii/S1568494615002811. [23] Y. Xiao, Q. Zhao, I. Kaku & Y. Xu. Development of a fuel consumption optimization model for the capacitated vehicle routing problem. Computers and Operations Research, 39(7) (2012), 1419 – 1431. doi:https://doi.org/10.1016/j.cor.2011.08.013. URL http://www.sciencedirect.com/science/ article/pii/S0305054811002450. Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 467 — #29 i i i i i i L. A. P. CANTÃO, A. YAMAKAMI and R. F. CANTÃO 467 APPENDIX A: COLLECTION POINTS TABLES Table A.1: Collection points for Monday. Index Address Index Address 1 Condomı́nio Cruzeiro do Sul 31 Rua Cruz e Souza 2 Condomı́nio Torre de Vicenza 32 Rua Gonçalo Vecina de la Vina 3 Rua João Tiburcio dos Santos 33 Rua João Ferreira da Silva 4 Rua Miguel Sayeg 34 Rua Antonio Gomes Morgado 5 Rua Celina Stela Corradi Beu 35 Rua São Miguel Arcanjo 6 Rua Adone Sotovia 36 Rua Ana Nery 7 Rua Nagib Jorge Murad 37 Rua Martins França 8 Rua José Maria Christ 38 Rua João Frederico Hingst 9 Rua Ismael Estanislau de Arruda 39 Rua Doutor Nicolau Alonso Martins 10 Rua Josephina Rodrigues Colo 40 Rua Pedro Jacob 11 Rua João Martinez 41 Rua Tobias Barreto 12 Rua Florencio Vieira da Rocha 42 Rua Francisco de Paula Aquino 13 Rua Agripino Guedes 43 Rua D’Abreu Medeiros 14 Rua Luiz Celestino Bertanha 44 Rua Rafael Laino 15 Rua Guido Mencacci 45 Rua General Antunes Gurjão 16 Rua Epaminondas Neves 46 Rua Claudio Furquim 17 Rua Antonio Martins Caixeiro Soriano 47 Rua Doutor Ruy Barbosa 18 Rua Laila Gallep Sacker 48 Rua Coronel Jose Tavares 19 Rua Milton Ribeiro Pinto 49 Rua Pericles Pilar 20 Rua Fernando Silva 50 Rua Constantino Senger 21 Rua Irineu Momesso 51 Rua Isaac Pacheco 22 Rua Benedito Barbosa 52 Rua Ataliba Borges 23 Rua Antonio Guilherme da Silva 53 Rua Luiz Paes de Almeida 24 Rua Sargento Paulino Claro dos Santos 54 Rua Felipe Betti 25 Rua Dom Paulo Rolim Loureiro 55 Rua Visconde de Mauá 26 Rua Amalia Fernandes Rodrigues 56 Rua Joaquim Bastos 27 Rua dos Expedicionarios 57 Rua Vital Brasil 28 Rua Maria Garcia Alcolea 58 Rua Voluntario Altino 29 Rua Doutor Delfim Moreira 59 Rua Gustavo Schrepel 30 Rua Padre Lessa Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 468 — #30 i i i i i i 468 CVRP GREEN CONSIDERING PATH SLOPES Table A.2: Collection points for Tuesday. Index Address Index Address 1 Rua Luigi Brunetti 25 Rua Cesario de Aguiar 2 Rua Afonso Gabriotti 26 Rua Gioto Pannunzio 3 Rua Jornalista Hernani Pereira 27 Rua Almeida Falcão 4 Rua Jorge Caracante 28 Rua Paulo Eiro 5 Avenida Dom Pedro I 29 Rua Frei Eugênio Becker 6 Rua Pindorama 30 Rua Professor Eneas Proença de Arruda 7 Rua Pedro José Senger 31 Rua Maria Aparecida Brunetti 8 Rua Ramon Haro Martini 32 Rua Estacio de Sa 9 Rua Gastão Vidigal 33 Rua Doutor Alfredo Maia 10 Rua Olı́mpio Loureiro 34 Rua Teotonio de Araujo 11 Rua Pedro Nolasco de Campos 35 Rua Benjamin dos Santos 12 Rua Aristide da Silva Lobo 36 Rua Antonio Monteiro 13 Rua General Argolo 37 Rua Rodrigues do Prado 14 Rua Rodrigues de Mello 38 Rua Margarida Izar 15 Rua João Nobrega de Almeida 39 Avenida José Benedito de Lima 16 Rua Hipólito José da Costa 40 Rua Wilson Fusco 17 Rua José do Patrocı́nio 41 Rua Jorge Courbassier 18 Rua Doutor Emı́lio Ribas 42 Rua Guilherme Marconi 19 Rua Lopes Trovão 43 Rua Thadeu Grembecki 20 Rua Joaquim Pires 44 Rua Padre Pedro Domingos Paes 21 Rua Conselheiro Antonio Prado 45 Rua Tiburcio Gabriel Torres Monteiro 22 Rua Martins de Oliveira 46 Rua Pedro Acacio de Marcos 23 Rua Professor Fonseca Junior 47 Rua Fernando Luiz Grohman 24 Rua Americo Brasiliense 48 Rua Antonia Lopes Bravo Table A.3: Collection points for Wednesday. Index Address Index Address 1 Rua Joana Decaria Tota 24 Rua Pedro Geremias Alves 2 Rua Ramon Haro Martini 25 Rua Vicente Celestino 3 Rua Pedro Jose Senger 26 Rua Joana Decaria Totta 4 Rua Hosmar Dahir 27 Rua Agostinho Decaria 5 Rua Antonio Aidar 28 Rua Vicente Decaria 6 Rua Antonio Arrojo Peres 29 Rua Robina Cacielo Decaria 7 Rua Joao Delgado Hidalgo 30 Rua Coronel Paulo Foot Guimarães 8 Rua Dirceu D’Almeida 31 Rua João Valentino Joel 9 Rua Carmem Galan Archilla 32 Rua Mario Piccini 10 Rua Pedro Sunica Neto 33 Rua Paschoal Bernal Vecina 11 Rua Agustinho de Vito 34 Rua Jose Prestes de Barros 12 Rua Doutor Gabriel Rezende Passos 35 Rua Jose Bonadia 13 Rua Adolfo Grizzi Santos 36 Rua Ivan Santos Albuquerque 14 Rua Pedro Peres 37 Rua Hortencio Piaya Martinez 15 Rua Jose Balera 38 Rua Antonio Antunes de Almeida 16 Rua Umberto Ferro 39 Rua Ambrosina do Amaral Marchetti 17 Rua Luiz Vicente Verlangieri 40 Rua Manuel Ribeiro de Andrade 18 Rua Sizina Azevedo Schrepel 41 Rua Pedro Teodoro de Almeida 19 Rua Pedro de Goes 42 Rua Wilma Tavares Simoni 20 Rua Professor Dorival Dias de Carvalho 43 Avenida Carlos Sonetti 21 Rua Renato Swensson 44 Rua Bayard Nobrega de Almeida 22 Rua Domenico Matteis 45 Rua Emerenciano Prestes de Barros 23 Rua Joaquim Scherepel Trends Comput. Appl. Math., 23, N. 3 (2022) i i “A3-1519” — 2022/8/4 — 21:20 — page 469 — #31 i i i i i i L. A. P. CANTÃO, A. YAMAKAMI and R. F. CANTÃO 469 Table A.4: Collection points for Thursday. Index Address Index Address 1 Rua Dionisio Reis dos Santos 20 Rua Jose Roberto Moncayo 2 Rua Jose de Oliveira 21 Rua Plinio de Almeida 3 Rua Benedito de Campos 22 Rua Professor Nelson Guedes 4 Rua Fernando Martins Costa 23 Rua Bernardo Martins Junior 5 Rua Dorothy de Oliveira 24 Rua Lucimara Godoy Zambonini 6 Rua Jose Rosa 25 Rua Carmem Ruiz Moncayo 7 Rua Eugenio Leite 26 Rua Lauro Alves Lima 8 Rua Eduardo Sandano 27 Rua Jose Martinez Y. Martinez 9 Rua Solange Victoretti 28 Rua Luigi Lava Melapague 10 Rua Antonio Rodrigues Sanches 29 Rua Artur Tarsitani 11 Rua Mario Guilherme Notari 30 Rua Santos Severo Scapol 12 Rua Major Barros França 31 Rua Francisco Mucciolo 13 Rua João Batista de Moraes 32 Rua Humberto Notari 14 Rua Renato Lucci 33 Euclides Medeiros 15 Rua Antonia Camargo Nunes 34 Belmira Loireiro de Almeida 16 Rua Florencio Antonio Pires 35 Rua Demercindo Alves da Silva 17 Rua Joao Moncayo 36 Rua Plı́nio Miguel 18 Alameda Professor Horácio Ribeiro 37 Rua Joao Augusto Gomes 19 Rua Jose Del Cistia 38 Rua Rubesval Luiz Jose Table A.5: Collection points for Friday. Index Address Index Address 1 Rua Comandante Salgado 21 Rua Capitao Padilha de Camargo 2 Rua Andre Matiello 22 Rua Doutor Alvaro Guião 3 Rua Aristeu Prestes de Barros 23 Rua Vidal de Negreiros 4 Rua Fernao Salles 24 Rua Doutor Ruy Barbosa 5 Rua Joaquim Rodrigues de Barros 25 Rua Jose Martins 6 Rua Jeronimo Antonio Fiuza 26 Rua Duarte da Costa 7 Rua Joao Valentino Joel 27 Rua Newton Prado 8 Rua Fernando Luiz Grohman 28 Rua Santa Maria 9 Rua Proessor Luiz de Campos 29 Rua Manoel Lopes 10 Rua Teodoro Kaizel 30 Rua Doutor Oliverio Pilar 11 Rua Nhozinho Prestes 31 Rua Francisco Glicerio 12 Rua Marquesa de Santos 32 Rua Tereza Lopes 13 Rua Assis Machado 33 Rua Barcelona 14 Rua Quinzinho de Barros 34 Rua Sa Fleury 15 Rua Doutor Campos Salles 35 Rua Sargento Antônio Remio Ribeiro 16 Rua Felipe Camarão 36 Rua Sevilha 17 Rua Raposo Tavares 37 Rua Madrid 18 Rua Augusto de Assis 38 Rua Thome de Souza 19 Rua Doutor Moreira Salles 39 Rua Catalunha 20 Rua Ricardo Severo 40 Rua Granada Trends Comput. Appl. Math., 23, N. 3 (2022)