Routing Optimization for Garbage Collection
Introduction
Waste management refers to the activities and actions required to manage waste from the inception of garbage to its final disposal. This includes the collection of waste, transportation to the landfill site, treatment and safe disposal. This project deals with routing optimization for garbage collection in waste management.
The transportation of waste to landfill sites is carried out by government agencies and/or private companies, depending on the laws of the country. Domestic waste collection services are often provided by local government authorities, and industrial and commercial waste is collected by private companies. Both the government and companies rely on the use of trucks to transport waste to the landfill sites. These agencies aim to minimize the cost associated with fuel consumption, schedule of the driver of the trucks and optimize the route of trucks to reduce the time taken to collect waste. They also need to conform to the labor laws of the country, the capacity of trucks and the traffic rules.
This project helps to understand the problem of routing optimization for Waste Management. The discussion starts with a description of the problem and then delves into its formulation in mathematical form. An actual solution to the simplified version of the problem will be provided using dynamic programming.
An actual company that benefits a lot from garbage routing optimization is Waste Management Inc. It is a Fortune 500 company based in the US and operates across North America. In 2002, the company felt the need to work on routing optimization of garbage trucks and finally solved this problem which ultimately saved millions of dollars through cost reduction. Our project takes some ideas from the way Waste Management attempted to understand and solve the problem and discusses a few ideas on the extension of the problem.
We also interviewed people in the city of Montreal to listen to their perspective of daily garbage collection. We found that the need for optimization by considering factors is not coming from the end customers rather waste management companies.
Problem Description and Formulation
Generally, garbage collection companies have to manage routes varies from hundreds to thousands in daily operation. Taking an example of Waste Management company in North America, they manage 19,600 daily routes on average and have 20 million customers in the residential areas and 2 million in the commercial areas. In total, Waste Management owns 2,6000 garbage trucks and the operational costs related to each garbage truck is around $120,000 (Sahoo, Kim, Kim, Kraas, & Jr., 2004). Therefore, they need to make every route operation efficient and profitable. In this case, the number of vehicles becomes the key component that routing optimization must consider since operation costs account for fixed vehicle costs, variable vehicle costs and labor expenses. Minimizing the number of vehicles is considered as an objective of the problem.
Garbage collection also contains three major areas which are residential, commercial and industrial. In this case study, our group mainly focuses on how garbage collection works in residential areas. Residential customers are generally people who live in their private homes and subscribe to the service from a garbage collection company. For private companies, routes for collection really depend on the density of service points. For example, if the area has few residences subscribing to the service, the routes of this area tend to be more expensive and time-consuming. Whereas in contrast, if all residence in an area subscribing to the service, the route will be more efficient and time-saving. Meanwhile, one unique feature of residential garbage collection is the mandatory adherence to driving on one side of the street. Figure 1 (below) illustrates the meaning of one-sided routes. Therefore, travel time for trucks is also an important objective playing in this optimization problem. In this report, we will emphasize minimizing the travel time of each truck.
Formulation
The objective is to minimize travel time. Some assumptions have to be made to simplify the problem:
● There is no lunch break for drivers for each route
● We aren’t considering the total number of trips for disposal
● Consequently, we do not formulate the constraint that the number of trips from regular stops to disposal facilities for a vehicle should be equal to disposal constraints
● Number of trips from disposal facilities to regular stops should be one less than disposal trips but since we aren’t tracking visits to disposal facility we do not have this constraint
The description of the variables are shown below:
● regular stops are represented by nodes 1 to N
● the landfills are represented by nodes N + 1 to N + M, the lunch break is represented by N + M + 1, and the depot is represented by 0 in the vertex set V = {0,1,2…N, N + 1,… N + M + 1}, and A is the arc set.
● si: service time at node i
● di: demand at node d
● The depot and the landfills have 0 demand
● The depot has 0 service time
● tij (non-negative) is associated with arc (i,j) belongs to A
● K: available vehicle set
● Nk: actual number of disposal trips for vehicle k
● C: vehicle capacity
● X i,j,k: where (i,j) belongs to A, k belongs to K. It’s equal to 1 if arc (i, j) is used by vehicle k and 0 otherwise.
● Wi,k is the time variable where i belongs to V, k belongs to K, be the start service time at node i when it’s serviced by vehicle k.
● Di,k where i belongs to V, k belongs to K
Objective Function (minimize travel time):
Decision Variables: Xi,j,k, Di,k, dj
Constraints:
- Every regular stop should be serviced by exactly one vehicle
2. Ensure that every route starts from the depot
3. Keeping the waste collected at each stop within the capacity of the truck
4. Garbage collected should reset to 0 after a visit to the landfill
5. To ensure collected garbage represents the correct incremental volume of a particular stop
6. The last trip should be to the depot
7. The equations below are there for imposing binary and integer constraints and non-negativity constraints on our decision variables
Dynamic Programming or Garbage Routing Optimization
Simplifying Garbage Truck Routing to TSP
The problem of Garbage truck Routing optimization can be thought of like a traveling salesman problem with some additional complexities such as multiple agents, with capacity constraints, time window constraints, arc routing, etc. and for the sake of simplifying the problem to actually solve it for optimal route, we ignore the additional constraints essentially determining the optimal route for 1 truck that is assumed to have large enough capacity for all the stops it is scheduled to visit and without time window constraints.
We explored the topic of Dynamic Programming and implemented a dynamic programming approach to solve the traveling salesman problem.
Dynamic Programming
Dynamic programming concerns itself with a class of functional relations that rise from multi-stage decision processes possessing certain definite structural characteristics. The characteristic properties are exploited to achieve a reduction in the dimensionality of the mathematical problem, thereby making some processes amenable to analytic or computational techniques.
Every Dynamic Programming can be expressed as a recurrence relation and is therefore suited to processes that occur over a sequence of time or stages. But DP does not necessarily involve processes that change over time, often-times the stages are introduced by considering the component activities individually although they occur simultaneously in time
A multi-stage process that is easily formulated in these terms is usually in the form of an allocation problem where at each stage resources are reinvested in such a way to maximize a total payoff. Linear programs can be expanded to include several time periods as opposed to the static picture they usually represent by adding additional constraints reflecting constraints felt at each time interval.
Problems that DP solves have optimal substructure since there is a recurrence relation that models the problem, it is clear that the optimal solution to an overall problem will use the optimal solution to its simpler sub-problems that the main problem can be broken down into and it is observed that the same sub-problem is encountered again and again multiple times so whenever we obtain a solution, we should store that solution to save time by not solving a problem more than once and this is why DP problems are said to have overlapping subproblems (Dreyfus).
Dynamic Programming approach to solve TSP: Bellman/Held-Karp Algorithm
The Held–Karp algorithm, also called Bellman–Held–Karp algorithm, is a dynamic programming algorithm proposed in 1962 independently by Bellman and by Held and Karp to solve the Traveling Salesman Problem (TSP)
Optimal Substructure of TSP that is exploited to formulate it as a Dynamic Programming Problem
Every subpath of a path of minimum distance is itself of minimum distance. Using this logic optimal tour of a TSP can be recursively formulated as:
M = min c∈{2,…,N} (D({2, . . . , N}, c) + dc,1 ),
where the cities are numbered from 1, 2, . . . , N and assume we start at city 1, and the distance between city i and city j is di,j.
Consider subsets S ⊆ {2, . . . , N} of cities and, for c ∈ S, let D(S, c) be the minimum distance, starting at city 1, visiting all cities in S and finishing at city c. If S = {c}, then D(S, c) = d1,c. Otherwise: D(S, c) = min x∈S−c (D(S − c, x) + dx,c ). The minimum distance for a complete tour of all cities is:
M = min c∈{2,…,N} (D({2, . . . , N}, c) + dc,1)
A tour n1 , . . ., nN is of minimum distance just when it satisfies M = D({2, . . . , N}, nN ) + dnN,1 (Cormen, 2009)
Comparison with the brute force approach to solving TSP
The brute force approach wastes a lot of time by generating every possible tour including the ones that have sub-paths that can never possibly lead to an optimal tour and since the DP approach, on the other hand, figures out which sub-path cannot possibly lead to optimal solution as soon as it finds a better sub-path and does not waste any time from then on to try tours with that suboptimal sub-path.
The time complexity of the force solution is O(n!) while for DP solution, it is O( ). It is worth mentioning here that even the dynamic programming solution is not a polynomial-time solution.
Comparison of brute force Vs dynamic programming approach shown below:
Problem Extension
- Types of garbage and multiple trucks: Usually, there are 3 types of garbage bins: plastic, organic and glass/metal. Some items are banned from going into any of these bins. There are specific rules for each of these bins. For example, the color of the garbage bag and the garbage bin size. These provide an extra constraint to the optimization problem. There are designated sections in the landfill area for each type of waste, and often the companies dedicated trucks to a certain type of waste. For instance, a truck that collects the majority of organic waste cannot be used to collect glass/metal waste as the latter goes to a different landfill site for the recycling process.
- Modeling the problem to a different city: The problem cannot be easily modeled to another city. It may be easy to map the problem to a neighboring city, or in the same province, but as soon as it is tried in a different province, it becomes difficult to find a feasible solution due to the difference in the layout of the cities. For example, there are different traffic laws across different provinces in a country and across continents. There are certain laws related to the location of landfill sites in the city as well. While some provinces limit the location of a landfill site to be in the suburban areas, others do not impose such restrictions. The capacity of the truck is also one of the constraints which change as the permissible size of vehicles is also different in certain areas of the city.
- Street Layout: Sometimes the layout of the city also provides an extension of the problem. While some areas allow the trucks to cross the street, some limit this and hence the problem comes under the arc routing process. Contrary to normal routing problems, which usually involve mapping a route between nodes, arc routing focuses more heavily on the route itself. The goal of many arc routing
- Unpredictable factors: Additionally, unpredictable factors such as traffic patterns and last-minute changes can wreak havoc on the route planning efforts. Some small businesses spend hours every morning mapping out their delivery routes by hand or using inappropriate tools for the job like Google Maps — only to find that these plans need to be adjusted throughout the day.
Recommendations
We have experienced a tough but interesting process in learning a garbage collection routing optimization case study. We summarize some ideas related to recommendations and future improvements.
1. We learned that the garbage collection optimization problem is a wide range optimization problem so that a simple linear or non-linear regression model is hard to solve. The bottleneck of this problem is that there are too many objectives and constraints. Therefore, we propose the Dynamic Programing method. In terms of this, we suggest that before formulating a multistage problem into a Linear Programming problem, check if it can be formulated as a Dynamic programming problem as it is much faster and elegant to formulate a problem as a recurrence relationships are much more succinct than an LP with multitude of decision variables required to model constraints that present themselves at various stages of the problem.
2. The solution to simplified TSP can be thought of as a benchmark to compare with the approximate solutions obtained by other approaches.
3. In this report, we only consider part of the problems and we assume lots of constraints and objectives holding constant. As future work, if we have enough working time on this project, we will incorporate additional constraints that would be applied such as problem extensions we described in the early part of the report.
References
- Cormen, T. H. et al. (2009). Introduction to algorithms. Cambridge, MA: MIT Press.
- Dreyfus, S. E. (n.d.). A COMPARISON OF LINEAR PROGRAMMING AND DYNAMIC PROGRAMMING.
- Sahoo, S. P., Kim, S. P., Kim, B.-I. P., Kraas, B. P., & Jr., A. P. (2004). Routing Optimization for Waste Management. Franz Edelman Award for Achievement in Operations Research and the Management Sciences, 35, 24–36. Retrieved from http://www.jstor.org/stable/27651734
