Sector arc routing-based spatial decision support system for waste collection in Brazil

Abstract

We present a sector arc routing problem-based spatial decision support system technology to develop tactical and operational plans and manage solid waste collection activities including household refuse collection and human and mechanical street sweeping. The proposed technology can also manage solid waste services through optimization (minimizing sector costs, distances and resources). The proposed technology is called optimized planning and integrated logistics management. It can be directly applied to Brazilian municipalities as it contains its major natural features. The system uses advanced technics from sector arc routing and sector scheduling, fleet and staff scheduling and daily plan management using mobile smartphone apps. The technology also allows for waste system inspections that are transparent to all participants in real time. We present the results of cases evaluated in the field for residential refuse collection and human and mechanical street sweeping in two Brazilian cities (Campo Grande and São Paulo). The plan implementations achieved from 12 to 28% actual fixed and variable cost savings for sectors (vehicles and workers) and routes (time and distances) for residential refuse collection and from 7 to 42% savings for human and mechanical street sweeping for the companies.

Keywords

Spatial decision support system sector arc routing residential waste collection street sweeping

Introduction

Significant challenges for solid waste managers include specifying and procuring suitable waste collection and street sweeping vehicles, hiring and training staff, developing routes that optimize resource utilization and monitoring daily operations. In particular, vehicle routing plan development typically entails the geographical division of a municipality into sectors and the subsequent determination of the collection circuit (collection shift or route), that is, the ‘street-to-street’ route to be taken by the drivers of collection vehicles and/or sweepers at designated times and days of the week (frequency of collection) to perform a service.

The collection sector is a geographic region where a vehicle travels to collect waste. A circuit (shift, route or collection trip) is the geographical region where a vehicle travels until it reaches its waste storage capacity. A trip consists of the routes between the garage, collection sector and destination (typically a transfer station or landfill). A collection sector is composed of one or more collection circuits or routes that can be performed during a workday (Mourão et al., 2009).

In Brazil, for human street sweeping, a sector signifies a region defined by a set of segments that can be cleaned by sweepers in the gutters, sidewalks and walkways. The sweeping starting and ending points may be previously defined. In mechanical street sweeping, a sector is also a set of segments, where a piping-sweeping vehicle washes and sweeps gutters and sidewalks. The vehicles may traverse the streets, and the origin and destination of the piping-sweeping may be defined, with the routes typically beginning from and ending at the garage. For both sweeping processes, a maximum staff workload is set (Graphvs and Barufi, 2018).

Currently in Brazil, the majority of waste collection and street sweeping service managers conduct planning manually or by using geo-processors, dividing and redividing the city into collection and sweeping regions in the ‘trial and error’ mode. In addition, route determination (the ordered sequence of streets to be collected or swept) is often delegated to the driver or sweeper.

This work solves these optimization and planning problems by using spatial decision support system (SDSS) technology composed of a software framework that allows users to design and manage human and mechanical collection, sweeping and other service plans. The plans are prepared by SisRot^® LIX, a software developed by Graphvs Ltda. (Graphvs, 2020), which calculates the collection and sweeping sectors and street-by-street routes (in sequence), allowing the services to be performed at reduced fixed and variable costs from the garage through the collection region to discharge at a landfill or transfer station and considering heterogeneous fleets and different origins and destinations (garages, landfills and transfer stations) and various approaches of using personnel to manually and mechanically sweep gutters and sidewalks.

The proposed computer system is part of a framework of computational systems that also contain an application that allows managers or inspectors to monitor service execution on their cell phones in real time. Another mobile application tracks the drivers and indicates the street-by-street route while the vehicle moves, allowing drivers to more easily follow the collection route. This tool disconnects the drivers from depending on route memorization.

This work also utilizes this technology to enhance sector and vehicle collection routes in Brazilian cities. We present the application re-sectored routing results for the Campo Grande municipality, including the fleet, man-hours and overtime reductions. Finally, improvements are also presented for the re-sectorization and optimization of manual and mechanical sweeping sectors and routes in the city of São Paulo for the sub-municipality of Campo Limpo.

To facilitate resolution development for the user, sectoring, routing and scheduling problems were included in the optimization algorithm platform via graphs. The proposed sector arc routing problem (SARP)-based SDSS software framework is called optimized planning and integrated logistics management (OPILM). The software is user-friendly; users can navigate between various algorithms and strategies in the software. OPILM technology can accomplish several tasks, such as information technology and decision-making tasks.

This work is organized into five sections. The second section illustrates the differences between capacitated arc routing problems (CARPs) and SARPs. The third section presents the OPILM architecture with the SDSS SisRot^® LIX. Section ‘Planning and monitoring execution results’ presents the results of the technology application, and the section ‘Conclusion’ summarizes the conclusions.

Capacitated and sector arc routing

There are three different methods of preparing routes for waste collection and/or street sweeping according to the Brazilian rules: Chinese Postman Problem-based sectoring and routing, CARP-based solutions and SARP-based solutions.

The Chinese Postman Problem-based solutions consider that there are areas of collection that must be covered at certain times and on certain days. These areas can be covered in less than one workday through route design. The goal is to minimize the number of trucks required to cover the areas while joining (sectoring) different coverage areas in multiple trips to the landfill or transfer station. The routes are partially built by the Chinese Postman method, and a truck scheduling problem is performed to join the trips and compose sectors using a given fleet (Simonetto and Borenstein, 2007).

In the CARP-based solutions, the methods used consider a strong connected positive weighted graph G(V, L-L_R, L_R), where V are the vertices, L are the links (L ⊆ E ∪ A, E – not oriented edges and A – oriented arcs and L_R ⊆ E_R ∪ A_R, E_R – required edges and A_R – required oriented arcs) that must be covered for the known garbage offer (q_R > 0). A fleet (homogeneous or heterogeneous) starts and ends at the garage (v₀ ∈ V) and passes through one or more intermediate facilities (v_I ∈ V), that is, a landfill or transfer station. This problem was first proposed as a symmetric graph G(V, E-E_R, E_R) by Golden and Wong (1981).

Using this approach, residential refuse collection applications and software for different cities worldwide were investigated by Ghiani et al. (2014c), and the most recent surveys on methods and their application in garbage collection were conducted by Ghiani et al. (2014a), Han and Ponce-Cueto (2015) and Mourão and Pinto (2017). With CARP solutions, the coverage of the area is not coordinated in a specific region, that is, shift contiguities are not guaranteed or the same vehicle may collect in opposite places in a city, managing the execution and measurement of daily processes complex (Rodrigues and Ferreira, 2015).

The SARP was proposed by Mourão et al. (2009); it is considered an arc routing problem (ARP), although it can be extended to node routing applications for commercial and health waste collection. The SARP is, however, a more general problem than CARP as it includes all the problems of routing in arcs and nodes either with or without intermediate facilities (Rodrigues, 2014). In the SARP, trip contiguity, connectivity and network compactness in a sector are considered objectives to be achieved by the final sector circuits covered by the routes, considering workload and fleet capacity constraints (Negreiros et al. 2016),

The SARP is the basis of our developed platform. The original SARP was proposed as homogeneous, and it was extended by Negreiros et al. (2016) as a heterogeneous problem of sectorization and arc routing for both closed and open routes (Supplemental Figure 1). SARP resolutions are found by using clustering-based heuristic algorithms from generalized heterogeneous group assignments (sectors and circuits), and the Mixed Rural Postman Problem (MRPP) was applied to the circuits by Batista et al. (2015) and Negreiros (2020). CARP heuristic method modifications have also been used by Corberán et al. (2000), Mourão et al. (2009), Rodrigues (2014) and most recently by Cortinhal et al. (2016), and they have been used by Ghiani et al. (2014b) in zoning.

In Supplemental Figure 2, we can observe the different aspects of the sector arc routing solutions, considering the objective function and the capacity constraints. When defining a vehicle fleet, there is a fixed cost to open a new sector using a certain vehicle type and variable costs related to the sector routes, which is minimized. The heterogeneous fleet must also be defined, considering a given number of sectors and the variable costs. Constraints related to staff workload may be present, depending on the available vehicle capacity. In general, this constraint is easily violated because of the uncertain garbage offering. Thus, extra time must be taken into consideration for the maximum workload. Capacity constraints and variability depend on the available vehicles, whose selection is contingent on the capacity necessary to cover the regions while minimizing the number of trips, balancing travel with route cost.

For street sweeping, the literature considers the open ARP as a problem of forming an open Eulerian path in a symmetric, connected and weighted graph, G(V, E-E_R, E_R), such that it is performed at a minimal cost. Selecting the beginning and end of the route is the result of the decision problem. Usberti et al. (2011) proposed a new problem called the ‘open routing problem in arcs on-demand’. The problem considers that, in a connected and symmetric graph G(V, E-E_R, E_R), the required links contain the demand (distances for sweeping). Open circuits passing through all the required links are formed, whose global sum of distances is minimized without any of the circuits exceeding its maximum capacity (maximum sweeping distance). This problem is also an SARP and can be applied in many contexts; it is critical in the delivery of correspondences, sweeping, the control of endemic diseases, the inspection of electric lines and rails, military and police patrols, and other applications (Corberán and Prins, 2009; Mourão and Pinto, 2017; Usberti et al., 2011).

Decision support technology: OPILM

With the growing demand for logistical services, decision support systems (DSSs) are required; they are composed of a series of subsystems and are characterized by the Enterprise Resource Processing model. Computer systems have been developed to manage company sectors (accounting, personnel, marketing, inventory, etc.). However, distribution logistics initiatives still lack tools to support the interdepartmental systemic interoperability, such as wholesale, door-to-door distribution, garbage collection, disease control and other systems (Turban et al., 2005).

Municipalities are responsible for the collection and transportation of solid waste. These expensive services are responsible for 75–80% of the total solid waste management budget (Bhat, 1996). Thus, municipal solid waste management DSSs are necessary to handle the relevant data sources and information for strategic and tactical planning and daily operations.

For tactical planning, Simonetto and Borenstein (2007) proposed a DSS for selective waste collection by generating alternatives to determine the allocation of separate collection vehicles, their routes and the daily amount of solid waste sent to each sorting unit to avoid labour force waste and to reduce the amount of waste sent to landfills. Li et al. (2008) proposed a set of models and a heuristic method for a variation of the single-depot vehicle scheduling problem for reducing the number of trucks covering static trips defined by selective waste collection managers in the city of Porto Alegre, Brazil. Bányai et al. (2019) developed a cyber-physical system for tactical planning with the following model objectives: optimize waste source assignment to garbage trucks, schedule waste collection by routing each garbage truck to minimize the total operation cost and increase reliability while considering comprehensive environmental indicators that greatly impact public health.

A web-based SDSS for tactical and operational routing management in waste collection was developed by Santos et al. (2011) to generate optimized constrained CARP routes. The system was tested for urban trash collection in Coimbra, Portugal, but the results of its application were not published to the best of our knowledge.

A simultaneous routing system that uses traceability data was proposed by Faccio et al. (2011). The rise of new mobile technologies using Global Positioning System (GPS) and general packet radio service (GPRS) for vehicle traceability and telemetry in conjunction with radio frequency identification (RFID) for capturing bin fill states using volumetric sensors. Models applying static and optimal stochastic replenishment bins during routing were evaluated.

Web Geographic Information Systems (GIS) viability has been discussed by Rada et al. (2013) for a solid waste management system based on bin collection. The authors detailed and explored the use of mobile technology (GPS, GPRS and RFID) combined with web-compatible GIS resource analysis support systems for trucks and load traceability for item separation into distinct containers of green waste, food waste, glass/can/hard plastic waste, soft plastic packing waste, paper waste and residual waste.

Over the past 30 years, Negreiros, Palhano and others have developed OPILM systems (Graphvs, 2020), including systems for wholesalers, hospital and commercial waste collection (OPILM SisRot^® FULL) (Negreiros et al., 2013), arbovirus disease control (OPILM WebDengue^®) (Negreiros et al., 2008) and Brazilian regulation implementation in waste collection services (SisRot^® LIX).

The OPILM SisRot^® LIX scheme (Figure 1) presents the operational architecture of a set of computer systems that integrate through the web, allowing for optimized garbage collection planning and management services to be performed. The system architecture is closely related to the conceptual DSS design model proposed by Klashner and Sabet (2007). The core of the framework, corresponding to theory and analysis, includes the SARP system, which composes the algorithms for capacitated sectoring and routing, which are executed either manually or automatically. Heterogeneous sectoring is performed by heterogeneous capacitated centred clustering heuristics, and the routing phase is performed with the mixed rural postman and movement prohibition reduction methods. These algorithms are executed according to the application (residential or selective refuse collection or human/mechanical street sweeping). The sectors and routes are part of the process final decision, and they are visualized through multigraph diagrams with movement/load/time/distance descriptions, multi-scaled vector maps (in PDF and KML file formats), and street-by-street descriptive spreadsheets (in the XLS file format) as detailed in the Supplemental Material.

Figure 1.

Architecture of an OPILM system for garbage collection (Graphvs, 2020).

A Structured Query Language (SQL) database stores the sector, vehicle and crew information (system domain). A graph-based modelling system (GBMS) permits the construction and modification of the service network, extracting and incorporating spatial data from the spatial shapefile and SQL warehouse that is coordinated by an ESRI™ geoprocessor that produces the map visualizations and integrated editing tools (information infrastructure). The GBMS also incorporates tools for simulating the distribution of garbage with different parameters in sectors or circuits by adjusting the required link loads according to the distance, real state unit or population coverage density obtained from the Brazilian sector census (simulation capability).

A frequency assignment module (working days and times) of sectors and routes develops the structure for vehicle and human sweeper assignment. The staff and vehicle assignment module allocates teams to vehicles and then to sectors. The scheduler module schedules vehicles to various sectors for different shifts.

Systems connected to the cloud with continuously operating web services include the mobile CherryTrack^® LIX for drivers/sweepers and managers to track the designed sectors and most recent routes; SisFleet^®, a desktop-based system that manages fleet and the associated cost information (fuel recharge, tire usage, etc.) and TrashControl^®, a system that stores information and reproduces charts and indicators regarding garbage production and productivity per sector/vehicle/team of workers. This information can be easily sent to traceability or telemetry web-based software by other monitoring companies.

The information circulates through a web service via a web virtual private server unit, and tasks are executed based on the plans and information received, and the operating system information release and attribution if the operator is a private (concessionaire) or public (the municipality itself) service. This solution can be incorporated into the garbage collection service operator after replanning the collections service sectors and routes (home, selective, pruning, container, sweeping, etc.), which constantly occurs in the company systemic operational environment.

Planning and monitoring execution results

In this section, we consider the three types of results we obtained by using the OPILM SisRot^® LIX. The residential refuse collection, human street sweeping and mechanical street sweeping results are detailed in the following subsections. For each result, we compare the application characteristics and proposed solution to the currently practised one. The result contexts varied.

Household refuse collection

With a population of 885,000 inhabitants (IBGE, 2018), the city of Campo Grande has 117 collection sectors with an average of two collection circuits per sector. Four sectors were studied for savings verification. The April 2018 data (without optimization) of these sectors were informed by the managers of the local concessionaire as follows:

Sector identification: Sectors 12, 19, 20 and 21 (Supplemental Figure 3).

Collection through 9-t ‘stump’ compactor truck with a maximum collection load of 8.5 t for each sector, and compactors of 12 t or up to 11.5 t/trip can be used.

Collection frequency: night, alternating 3×/week (Monday/Wednesday/Friday).

Each sector required two trips (circuits) per vehicle to be fully covered, with the first trip being garage → sector → landfill and the second trip being landfill → sector → landfill.

Generation of total waste from the four sectors: 68 t/day (sector average of 17 t/day).

Total average daily distance travelled by vehicles: 478 km/day (119.5 km/vehicle/day).

Team: per sector, 4 drivers and 12 collectors operate (1 driver + 3 collectors in each vehicle).

Speeds: empty: 47.0 km/hour, full: 38.0 km/hour, during collection: 6.0 km/hour, deadheading: 25.0 km/hour.

Average daily total team working hours: 39 hours and 43 minutes, with an average of 9 hours 55 minutes for each vehicle/day.

We divided the evaluations into two scenarios. In scenario 1, we review the sectors and routes with 9-t vehicles, and in scenario 2 we re-sector and route using 12-t vehicles.

Comparison between original situation and optimized scenarios

For both optimized scenarios, there is a significant reduction in the total distance travelled by the vehicles compared to that of the original situation. In scenario 1, the current sector geometry was maintained, and SisRot^® LIX only created the optimized vehicle routes (circuits), generating a total distance savings during operation of 13.7%. In scenario 2, both the sectors and circuits were optimized for the 12-t collection vehicle loads, obtaining a total savings in the operation distance of 29.2%. Thus, scenario 2 was selected to be implemented in the field.

Comparison between original situation, scenario 2 planned and scenario 2 executed

The optimized solution in scenario 2 reduced the number of sectors from four to three, which were named Sector 1, Sector 2 and Sector 3 and put them into operation (Figure 2). The optimized operation in the three sectors with 12-t vehicles included two collection circuits per sector, six collection circuits in total (Supplemental Figure 4).

Figure 2.

Maps indicating the division of operation in downtown Campo Grande/MS, where on the left we see the original four sectors and on the right the optimized re-sectoring (three sectors).

The evaluations were monitored remotely over 60 days and in-loco by the route implementation team using the CherryTrack^® LIX system, whose sectors and routes were generated by SisRot^® LIX and automatically forwarded to the driver via an Android driver monitoring device. Graphvs managed the operations using the web service (Supplemental Figures 5 and 6).

The distance savings of 28.6% on Monday and 28.5% on Friday are nearly the same and expected with the projected savings of 29.2% by SisRot^® LIX; however, Wednesday exhibits a different result (Supplemental Figure 7). On Wednesday, April 20, 2018, after analyzing the circuit execution report, and it was determined that the vehicle did not execute the planned operation, deviating from the optimal routes. Therefore, although the savings was 20.9%, this result should be disregarded.

Working time in Brazil is limited to 44 hours/week (six working days/week) or 7.33 hours/day, and a worker must receive a 50% increase in pay for each extra hour worked in the day (overtime). Thus, for the working hour calculations (Supplemental Figure 7), overtime was adjusted to normal hours using the ratio of 1 overtime hour = 1.5 normal hours. The savings achieved in driver man-hours, above 20%, were primarily due to the ‘withdrawal’ of one driver working day, resulting from the withdrawal of a vehicle from the operation (Supplemental Figure 7).

The savings in man-hours was discreet, as there was no reduction in the number of collectors between the current operation in four sectors and the optimized one in three sectors. For operation with 9-t vehicles, three collectors are used per vehicle. For operation with 12.5-t vehicles, it is necessary to monitor four collectors per vehicle, as there is a greater load to be collected per vehicle and thus greater wear of the street sweepers on the individual routes (Supplemental Figure 7).

During the tests with the CherryTrack^® LIX monitoring system, collection progress and streets still requiring travel can be identified at all times, positively impacting the drivers and collectors who often desire to know ‘how much was left to finish the job’. In addition, decision-making was facilitated (points already covered, routes not yet completed, etc.).

The circuits generated and executed from 23 April 2018 to 27 April 2018 reduced the total distance travelled by the vehicles by 28.5%, which was close to that initially planned by SisRot^® LIX (29.2%) (Supplemental Figure 7), demonstrating that the plans generated by the system are fully executable.

Regarding the cost of collector working hours, the average savings of 5% is important because the same work was performed with nearly the same cost in man-hours while covering 28.5% less distance and increasing productivity. The savings in the driver working hours, above 20%, was considerable, and it was primarily due to the removal of one driver the reduction of one sector, and the consequent removal of one vehicle from the operation.

Public sweeping (human)

Public sweeping is considered indivisible for the Municipality of São Paulo (MSP), where this portion of this study was conducted. It is difficult to organize because its planning depends on the flow of people, vehicles and afforestation in public places (São Paulo is the largest city in South America, with 12.5 million inhabitants). To meet this demand, the city was divided into regions (sub-municipalities) with defined sweeping frequencies and sectors for sweeping groups to service. Circuits are places where each team of sweepers must perform the sweeping task. This service is inspected in sector groups. This service is costly; it demands over 40% of the total cost for urban solid waste, 250 million USD/year (Graphvs and Barufi, 2018).

Sweeping is performed in many manners, manual, mechanized, sidewalk, squares, public installation, etc.; however, this study focused on manual and mechanical sweeping plans. In the manual sweeping of São Paulo, two street sweepers work together on the same gutter side (1.2 m within the sidewalk line), using a ‘lutocar’, typical removal equipment, and appropriate clothing. Each team travels an average of 1.228 km/hour sweeping and walking at a speed between 2.5 and 3.0 km/hour. At this rate, a route of 5.5–7.0 km per working day (7 hours 20 minutes) can be accomplished.

The manual sweeping approach in the city of São Paulo is by street axis (Supplemental Figure 8). This approach indicates that a route is taken by the team of sweepers that counts the sector perimeter at the half-time distance of the team workload (7 hours 20 minutes) on a path that begins from a designated starting point and goes to an end-point, which minimizes the route costs. For the streets that must be swept in the first route passage, the sweepers perform the service in the gutters on one side of the road. Upon returning, they perform the service in the gutters on the other side of the road (Figure 3(a)). Another way to perform the same work is by dividing the sweepers to sweep both sides of the road gutters simultaneously. There is only one open route passage, and the sweepers can perform the same service by walking much less and working with a ‘lutocar’. Figure 3(b) displays an example of an open sweep route that is 36.68% shorter than that of the previous case (Figure 3(a)). This solution was proposed to the municipalities of São Paulo to reduce labour fatigue and increase sweeping system coverage. The open SARP using the open RPP was proposed to solve the situation.

Figure 3.

Two different ways of street sweeping: (a) both sweepers at the same side and (b) each sweeper in his own street gutter side walking 36.68% less than in (a).

As seen in Supplemental Figure 9, the route designed for the sweeper covers the set of public places. Once it was determined to include a fixed starting point to allow the sweepers could find a unique place to keep the ‘lutocar’, we observed that the open minimum RPP route can be successfully used. The team of sweepers begins from a support point and concludes their task at a specific point, minimizing the overall cost of the sweeper journey, then returning to the support point. An alternative sweeping service sector formation was considered, where each sector exhibited a capacity that was limited by a maximum sweeping perimeter that cannot exceed half the work shift of each team assigned to it. Thus, the problem becomes an open arc sectorization routing problem because multiple street sweeper teams work in a sector, and no team can overcome their workload, making it necessary to know the path of each team.

The manual sweeping planning and context analysis results are presented in Supplemental Table 2. There are 32 sub-municipalities in the São Paulo municipality, and all of them except for the sub-municipality ‘Sé’ were studied in full. The results were particularly encouraging compared to what was currently in practice by the responsible city halls at the time.

Of the solutions presented in Supplemental Table 2, the perimeter calculated by the SisRot^® LIX sub-municipality sweeping axis was extremely close, in most cases slightly larger, to those by the consortium that served the northwestern area of the city of São Paulo in 2018 and 2019. There were 10 fewer sectors in Butantã, with a savings of 7.63%, and 14 fewer sectors in Vila Maria–Vila Guilherme, with a savings of 20.59%. There was also discrepant information in the Santana sub-municipality regarding the work obtained (50.66% difference). This high difference in the number of sweeping teams is most likely due to an error in the MSP spreadsheets. Supplemental Table 2 also presents the differences in sector number optimization, sweeping perimeter per street axis and the daily sweeping measurement. Each sector is covered by a team of two sweepers with a ‘lutocar’.

Public sweeping (mechanical)

In mechanical street sweeping, the work is directly performed by the concessionaires on the most important roads, margins and avenues. The work is performed by large wash-sweepers containing 1000–5000 L of water, steel sweepers and vacuum cleaners. The sweeping velocity exceeds 7–10 km/hour, and two people work with the machine (driver and auxiliary). Road coverage occurs daily, with certain covered three times per week at night. The frequencies are defined for each place according to their importance. In Supplemental Figure 10, we can see the solution used by the sub-municipality Campo Limpo for mechanical sweeping in this region.

The problem of mechanical sweeping is closely related to that of the human sweeper, although the network is mixed in this case, and the required links become required arcs when the traffic flow must be followed. We can solve the open SARP by using open routes. To design the open routes, we propose the use of open MRPP (OMRPP), where we adapt SisRot^® LIX to perform nearly optimally for all routes. There are many ways to cross the street from the gutters on both sides, where the cleaning may be performed, but a single graph transformation can be performed to solve the OMRPP as an MRPP.

By applying the methods developed for SisRot^® LIX, we achieved superior results than those previously obtained by EcoSampa, as can be seen in Table 1. The results demonstrate that it is possible to reduce the number of sectors and still reduce the total time (49.20%) and distance travelled (10.52%) by the fleet (Supplemental Figure 15).

Table 1.

Recorded gains between SisRot^® LIX – SARPO solution and operational solution by EcoSampa.

Sector	EcoSampa	SisRot^© LIX	Gain (%)
CL001
Perimeter (axis) (km)	No indication	18.25
Distance (km)	92.67	100.03
Time (hh:mm)	07:00	06:26
CL002
Perimeter (axis)(km)	No indication	17.15
Distance (km)	36.65	48.31
Time (hh:mm)	07:00	04:14
CL003
Perimeter (axis) (km)	No indication	–
Distance (km)	37.58	–
Time (hh:mm)	07:00	–
Result
Total distance (km)	166.90	149.34	10.52%
Total time (hh:mm)	21:00	10:40	49.20%
Total sectors	3	2	33.33%

Conclusion

The circuits generated and executed from 23 April 2018 to 25 April 2018, in Campo Grande provided a reduction of over 28% in the total distance travelled by the vehicles, which was extremely close to that initially planned by SisRot^® LIX (29.3%), demonstrating that the plans generated by the framework can be executed with minimal differences between the planned and the executed results.

Regarding the cost of collector working hours, the average savings of 5% is relevant because the same work was performed with nearly the same amount of man-hours while covering 28.5% less distance, therefore increasing productivity. The savings with fixed and variable costs of over 20% were considerable, primarily because one driver and vehicle were removed from the operation, eliminating their associated costs.

Another important aspect of the framework was the use of the CherryTrack^® LIX Driver and CherryTrack^® LIX Manager applications. The CherryTrack^® LIX Driver, installed on a mobile device inside the load packer, assisted in navigation by indicating to the driver the sequence of roads he should follow to comply with the optimized route. Drivers were thought to have to ‘decorate’ the route as the service execution relies on them. Embellish, CherryTrack^® LIX broke this paradigm, which has dominated the medium for years. CherryTrack^® LIX Manager allowed researchers, managers and inspectors to monitor the service execution for each vehicle or the entire operation in real time.

The savings in manual and mechanical sweeping obtained in São Paulo exceeded expectations. The new methodology can reduce the operating costs of sweeping services for the city by millions of reals in comparison to those of other operational solutions.

Based on the results, OPILM SisRot^® LIX, through its algorithms and software, can be implemented by a team to reduce operational costs. Economical solutions were determined for home collection plans and human/mechanical sweeping plans, which were then consolidated through sector optimization and home collection and manual sweeping scripts, respectively. The proposed SARP-based solution can be used for favourable tactical, operational and strategic planning in waste management.

Supplemental Material

sj-pdf-1-wmr-10.1177_0734242X221104366 – Supplemental material for Sector arc routing-based spatial decision support system for waste collection in Brazil

Supplemental material, sj-pdf-1-wmr-10.1177_0734242X221104366 for Sector arc routing-based spatial decision support system for waste collection in Brazil by Marcos José Negreiros Gomes, Augusto Wagner de Castro Palhano and Eduardo César Rodrigues Reis in Waste Management & Research

Footnotes

Acknowledgements

We would like to thank SELETA, SOLURB, SELLIX, São Paulo Parcerias/AMLURB and Consortium EcoSampa for helping to facilitate this work. We would also like to thank the Graphvs Ltda. team for facilitating this research.

Declaration of conflicting interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The authors received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Marcos José Negreiros Gomes

Supplemental material

Supplemental material for this article is available online.

References

Batista

Negreiros

Muritiba

, et al. (2015) New framework of metaheuristics for the Capacitated Centred Clustering Problem. In: The XI Metaheuristics International Conference, Agadir-Marrocos, 7–10 June.

Bányai

Tamás

Illés

, et al. (2019) Optimization of municipal waste collection routing: Impact of Industry 4.0 technologies on environmental awareness and sustainability. International Journal of Environmental Research and Public Health 16: 634.

Bhat

(1996) A model for the optimal allocation of trucks for the solid waste management. Waste Management & Research 14: 87–96.

Corberán

Martí

Romero

(2000) Heuristics for the mixed rural postman problem. Computers & Operations Research 27: 183–203.

Corberán

Prins

(2009) Recent results on arc routing problems: An annotated bibliography. Networks. 56: 50–69. DOI: 10.1002/net.20347

Cortinhal

Mourão

Nunes

(2016) Local search heuristics for sectoring routing in a household waste collection. European Journal of Operational Research 1–12. 255: 68–79. DOI: 10.1016/j.ejor.2016.04.013

Faccio

Persona

Zanin

(2011) Waste collection multi objective model with real time traceability data. Waste Management 31: 2391–2405.

Ghiani

Guerriero

Manni

, et al. (2013) Simultaneous personnel and vehicle shift scheduling in the waste management sector. Waste Management 33: 1589–1594.

Ghiani

Laganà

Manni

, et al. (2014a) Operations research in solid waste management: A survey of strategic and tactical issues. Computers & Operations Research 44: 22–32.

10.

Ghiani

Manni

, et al. (2014b) The impact of an efficient collection sites location on the zoning phase in municipal solid waste management. Waste Management 34: 1949–1956.

11.

Ghiani

Mourão

Pinto

, et al. (2014c) Routing in waste collection applications. In: Corberán

Laporte

(eds) Arc Routing Methods and Applications, Chapter 15. MOS-SIAM Series in Optimization, pp 351–370. DOI: 10.1137/1.9781611973679.ch15

12.

Golden

Wong

(1981) Capacitated arc routing problems. Networks 11: 305–315.

13.

Graphvs (2020) SisRot Lix. Available at: http://www.graphvs.com.br/?p=65 (accessed October 2020).

14.

Graphvs and Barufi (2018) Modelos e Planos de Otimização para a Integração do Sistema Logístico de RSU da Cidade de São Paulo. PMISP-2018. São Paulo: São Paulo Parcerias/PMSP.

15.

Han

Ponce-Cueto

(2015) Waste collection vehicle routing problem: Literature review. Traffic & Transportation 27: 345–358.

16.

Instituto Brasileiro de Geografia e Estatística (IBGE) (2018) Available at: https://cidades.ibge.gov.br/brasil/access (accessed December 2018).

17.

Klashner

Sabet

(2007) A DSS design model for complex problems: Lessons from mission critical infrastructure. Decision Support Systems 43: 990–1013.

18.

J-Q

Borenstein

Mirchandani

(2008) Truck scheduling for solid waste collection in the City of Porto Alegre, Brazil. Omega 36: 1133–1149.

19.

Mourão

Nunes

Prins

(2009) Heuristic methods for the sectoring arc routing problem. European Journal of Operational Research 196: 856–868.

20.

Mourão

Pinto

(2017) An updated annotated bibliography on arc routing problems. Networks 70: 144–194.

21.

Negreiros

(2020) Generalized travelling salesman based procedures for the mixed rural postman problem. Submitted to Transportation Science – in Review.

22.

Negreiros

Palhano

Batista

(2016) The heterogeneous sector routing problem. In: Workshop in arc routing problems (WARP II), Lisbon. Lisbon/PT: ISEG.

23.

Negreiros

Palhano

Rodrigues

, et al. (2013) Integrated DSS tools for routing, tracking and drivers assistance in wholesale – SisRot^®, Cherry/Zeus-Track^®. In: Proceedings of the MCLP. , IFAC Proceedings Volumes, Volume 46, pp. 523–526. DOI: 10.3182/20130911-3-BR-3021.00123

24.

Negreiros

Xavier

AFS

Lima

JWO

, et al. (2008) Integração de sistemas computacionais e modelos logísticos de otimização para prevenção e combate à dengue. Pesquisa Operacional 28: 1–27.

25.

Rada

Ragazzi

Fedrizzi

(2013) Web-GIS oriented systems viability for municipal solid waste selective collection optimization in developed and transient economies. Waste Management 33: 785–792.

26.

Rodrigues

AMM

(2014) Sectores e Rotas na Recolha de Resíduos Sólidos Urbanos. PhD Thesis, University of Porto, Porto.

27.

Rodrigues

AMM

Ferreira

(2015) Waste collection routing—limited multiple landfills and heterogeneous fleet. Networks. 65: 155–165. DOI: 10.1002/net.21597

28.

Santos

Coutinho-Rodrigues

Antunes

(2011) A web spatial decision support system for vehicle routing using Google Maps. Decision Support Systems 51: 1–9.

29.

Simonetto

Borenstein

(2007) A decision support system for the operational planning of solid waste collection. Waste Management 27: 1286–1297.

30.

Turban

Rainer

Potter

(2005) Administracao de tecnologia da informação: teoria e prática, 3 edn. Rio de Janeiro: Elsevier.

31.

Usberti

França

(2011) The open capacitated arc routing problem. Computers & Operations Research 38: 1543–1555.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

3.17 MB