Abstract

In cities and towns, municipal waste collection is observably expensive, fuel-inefficient, and congestive towards traffic, desiring improvements in all facets. In this project, the routes of garbage trucks are explored through a novel algorithmic system of garbage collection, which could be applied to current waste collection trucks as well as smaller, less obtrusive vehicles. An algorithm is designed in JAVA that works over a stack of 2-dimensional matrices meant to emulate the intricacies of the road network of a city or town- from the roads, to the waste bins, to the flow of traffic. The algorithm, based off of the shortest-path algorithm known as A-Star Search, considers heuristic, or estimation functions which measure factors including distance, estimated time of travel, probable impact on traffic, as well as others. With the combination of these heuristic functions, the algorithm generates possible routes for garbage trucks to take to collect traffic, and scores these routes based on the factors mentioned previously in a combined percentage. From these scores, the best route can be saved and fed back to the user through a Graphical User Interface. Through extensive testing, it was determined that on average the algorithm was able to generate routes with an average 93.45% waste bin coverage rate. These results indicate that the algorithm is effective at improving the routes of garbage trucks and thus waste management as a whole, as shown by consistent improvement in data. Thus, the algorithm can be used in practical applications to assist in waste collection.

Phrase 1

How do the routes of Garbage Trucks and their size affect traffic in the local area?

Phrase 2

The goal of this project is to engineer a new system for garbage collection, which would be applied to the current routes of trucks used as well as smaller, less obtrusive vehicles.

Background

Out of all of the common municipal services, waste management stands out as an industry lacking in efficiency as well as cost, with many towns requiring its citizens to pay for the services on top of normal taxes. While the service has been around for countless years, dating back to the 1950s, no major improvements seem to be made, especially in terms of cost and traffic efficiency. With 60-80% of the spending going towards it, the collection phase particularly is historically unoptimized (Karadimas, Papatzelou, & Loumos, 2007). On top of this, the vehicles themselves act as a bottleneck for collection, featuring an astonishingly-low fuel economy averaging just 3 miles per gallon (Zeng & Church, 2009). While these trucks feature technologies, such as automatic collection arms, that are valuable and sometimes necessary for collection, the presence of these vehicles generates a traffic congestion issue, due to their frequent stops along the road during potentially busy hours. Thus, it can be hypothesized that with less time on busy roads, congestion can be relieved by some factor. Routing is a more complicated issue, as it varies widely from town to town or city to city. While it may be true that each routing network is tailored towards its respective town or city, a universal standard is yet to exist, making it difficult to know how much room there can be for improvement. Thus, a method of routing garbage trucks that is applicable for all areas can be designed. Existing work has looked into the waste collection, package delivery, etc. of specific areas with set data and roads for testing (Gunawan et al, 2018). This kind of research, while beneficial to the industry as a whole, suffers from the same problem of overly-specific planning for waste collection. Each area has its own laws, systems of collection, quirks, and desires, making generalization as an extension of these studies very difficult. Furthermore, thousands of these studies cannot be funded and conducted in order to optimize each and every area individually. However, the key concepts and research from a collection of these existing studies can be generalized into a catch-all algorithm that can be used as a base for any future algorithms specific to certain areas.

Procedure

To simulate a road network, a matrix, known as a 2D Array in JAVA, was used to turn roads into grids, with 1 corresponding to a road and 0 filling the empty space. Thus, roads are represented as long strings of connected 1’s in the matrix. A beginning sample space of 10x10 was used, and testing began with a hard-coded environment. Adapting the imported A-Star algorithm to the matrix format was trivial, with individual coordinates being extracted from the grid and turned into Node objects for A-Star to interpret. Many proof of concepts were created during the development phase, with the first being a test of routing between two points on a hard-coded environment. Now, by manipulating a binary matrix, road environments could be created at will and any two points could be routed with A-Star, which will find the shortest path along the road between the two points.

The Random Environment

For testing, a hard-coded, 10x10 grid was not suitable for collecting data and testing the strength of the algorithm, so larger, pseudo-random environments were created. First, routing space was increased from 10x10 to 100x100. The random road network consists of a series of randomly generated roads which all start and end on opposite edges of the map. (FIGURE for showing the directions and stuff that the roads can take). The road is then made up of randomly-placed continuous points from the starting edge to the finishing edge, moving in weighted random directions, with the True Direction being obviously the most likely direction. These random roads are combined into what is known as a Board, and boards are tested on what is known as a Spread Factor. Four quadrants are measured for their number of road points, and the mean absolute deviation is taken over the four quadrants to produce a Spread Score. Only boards that meet a maximum Spread Score threshold are accepted for testing. This process helps prevent boards that have many condensed roads and large amounts of empty space.

Determining Strategies

In the current model developed, garbage collection is simulated over 5 days (Monday - Friday) of routing, with the first goal being to cover as much area of a given road map as possible. The first strategy to accomplish this will be known as Edge Routing, wherein 5 random combinations of edges are chosen and 5 paths are routed between them. An edge is a point of road on the matrix that is touching the border. While this strategy does well at maximizing coverage, it would imply multiple off-site dump locations with many entries(edges) into the modeled environment. Each day of routing is designated with a Route ID, which ranges from 2-6. These can be placed on top of the road matrix to create a matrix with values from 0-6 (0 being empty space, 1 being unrouted road). The advantage of Route ID is in the visuals of the board, showing each route as a unique color. This is accomplished with a simple color-choosing method, which assigns a color to each ID and colors the board according to its composition of IDs.

Edge Routing

To optimize the simplest form of the 5-day Edge Routing algorithm, all edge points are collected into a list and all possible combinations of two edge points are created and stored into another master list. In one iteration, 5 random combinations of edges are chosen from the master list and A-Star routes between them. The algorithm collects the percentage of rode points covered as a score and saves the pairs of edges used for routing, known as an Edge Code. After a specified number of iterations (Say, 1000), the Edge Code with the highest score is taken as the optimized route, and is fed back to the user.

Base Routing

The second version of the algorithm, known as Base Routing, improves on the previous version with the inclusion of a Base Point, or starting point for the trucks. Thus, each day of routing begins and ends at the Base Point, which would represent either a dump or a parking spot for the truck. The Base Routing algorithm still uses one of the two edge points found for the Edge Routing algorithm, leaving the other point in memory. Base Routing improves on the applicability of Edge Routing and also gives potential users the opportunity to plant down their source location. Improvements on Strategies

House Mapping

The first main improvement on the algorithms can be achieved by mapping out the actual homes that need their waste collected, so that coverage of the map can be more accurately measured. Each generated road comes with a randomly-generated House Factor from 0-9, which determines the density of houses along a road. The higher the House Factor, the more dense the road will be with houses. This is achieved by generating a second random number for each point on the road and only placing a house (and waste bin) on the point if the House Factor exceeds the random number. Rather than measuring for total road coverage to compare routes, the algorithm can measure House Coverage (total routes points less than or equal to 1 unit away from a house) to compare possible routes. To store the locations of the houses, a House Matrix is layered on top of the road matrix, so as to prevent loss of data through routing.

Turn Around

Since the Base Routing approach only utilized one of the two randomly generated edges for each route, it is expected that it performs poorly in comparison to Edge Routing. This can be attributed to the truck taking the same route to and from the Base Point. A simple fix was made wherein the algorithm utilizes the second, unused coordinates of an edge point. With the Turn Around method, the truck is routed from the base station to one edge to another edge each day. This significantly increases the route coverage and allows for non-repetitive routes.

Accounting for Traffic

To account for traffic, many variables must be considered, with the ultimate measurable being the Traffic Flow. Running alongside the main algorithm is the TrafficModel object, which monitors the traffic on every road in the environment. Contained in this object are multiple Road objects that are created alongside the randomly generated board. Each road has its own unique identifier (not to be confused with Route ID) and corresponding house density, which was generated during the board creation. Using a simple linear model, and assuming speed limit ranges from 20mph to 60mph, a correlation between house density and speed limit was created. Next, the Number of Vehicles on a given road can either be manually entered or randomly generated within the TrafficModel. These values vary from road to road and from day to day, allowing for variation in traffic patterns each day. The estimated length of each cell can be inputted, and thus the Length of each road can be found. Traffic density is calculated as the Number of Vehicles / Length, and to find Traffic Flow the Vehicle Speed is multiplied by the Traffic Density. By estimating the reduction in average speed caused by the truck, the Change in Traffic Flow can be found for each road by taking the difference between the Traffic Flow with and without the presence of the truck. With this Change in Traffic Flow, A-Star can be modified to consider this variable when routing between points, resulting in the truck taking routes that reduce the track’s impact on traffic as a whole.

Figures