Extracting input data for residential waste collection capacitated arc routing problems

Abstract

Residential waste collection is an essential but expensive public service provided by governments throughout the world. A key contributor to the cost of waste management is collection cost, making the potential for cost savings on waste collection an area of focus. One way to reduce collection cost is through the use of vehicle routing to improve collection routes. While various vehicle routing problem definitions exist for waste vehicle routing, the most compelling is the Mixed Capacitated Arc Routing Problem with Time Restrictions and Intermediate Facilities (MCARPTIF). A challenge facing the MCARPTIF however is that the input parameters necessary to solve real world instances of the problem are difficult to estimate. These include the time taken to drop off waste, the collection and traversal time per street segment and the waste generation rate per street segment. Global Positioning System (GPS) devices and publicly available data sets offer an opportunity to provide insight into some of these parameters and to develop more realistic MCARPTIF instances and subsequently collection routes. This dissertation aims to demonstrate how these parameters can be efficiently estimated. Using GPS data and known landfill locations, landfill visit durations are estimated at a landfill in a metropolitan area. Landfill visit durations are estimated to average 16 minutes. In addition, landfill durations are shown to increase with congestion within the facility. Using GPS data and publicly available street network data from the same metropolitan area, the average vehicle velocity when collecting waste over seven case study areas was found to be 3.857 km/h. The vehicle velocity when traversing street segments within the case study areas was found to average 6.843 km/h. A synthetic population based on census data and per capita waste generation estimates was used to estimate waste generation rates per street segment for a number of case study areas. All of the above mentioned variables were compared to known parameter assumptions used in literature and differ considerably. Lastly the parameter estimates were used to solve a number of real world instances of the MCARPTIF and were compared to instances using parameters from literature. Differences between instances solved using parameters estimated in this dissertation and those based on assumptions from literature illustrate the importance of using accurate input data for waste collection routing applications.