Help with Optimization and Decision Support Modeling for Business HW4

Interfaces infjU??S. Vol. 35, No. 1, January-February 2005, pp. 24-36 10.1287/inte.l040.0109 issn 0092-21021 eissn 1526-551X1051350110024 @ 2005 INFORMS

Routing Optimization for Waste Management

Surya Sahoo, Seongbae Kim, Byung-In Kim Institute of Information Technology, Inc., 2204 Timberloch, Suite 225, The Woodlands, Texas 77380

[email protected], [email protected], [email protected]}

Bob Kraas, Alexander Popov Jr. Waste Management, Inc., 1001 Fannin Street, Houston, Texas 77002

{[email protected], [email protected]}

Waste Management (WM) obtains one third of its revenue from landfill disposals and two-thirds from waste collection services. As most of the revenue comes from collecting trash, improving efficiency in operating the fleet improves the bottom line. After a flurry of acquisitions and a merger with USA Waste, WM found itself with a large fleet of vehicles whose routing, dispatching, maintenance, and management were decentralized. WM recognized that it could reduce operating costs by improving its use of assets. It contracted with the Institute of Information Technology to develop WasteRoute, a comprehensive route-management system that took into account WM's specific routing concerns and provided broad benefits. Initially, the target audience of the system was the dispatchers and indirectly the drivers. Sales and customer service also benefited because WasteRoute integrated the sales, customer service, and operations departments. The system reduced operating costs, provided better customer service, and determined appropriate prices. WM deployed WasteRoute across the nation beginning in March 2003. By the end of 2003, WM had 984 fewer routes, saving $18 million. It estimated that its savings for 2004 due to the reduction will be $44 million. As it extends the system to additional areas, it expects additional route reductions.

Key words: industries: transportation, shipping; transportation: vehicle routing.

Most US residents consider garbage collection a required service. As a result, there are many waste collection companies in the United States that compete based on price. Waste Management, Inc. (WM) is unusual in focusing on improving customer service to distinguish itself in the market. WM made an enterprise-level investment in im

proving service to address several operational ineffi ciencies. First, after a string of acquisitions in some areas of competing companies, WM had overlapping routes with two trucks serving customers on the same street. It was obvious it needed to improve rout ing in these areas. Second, route planners or drivers sequenced the stops on the routes. When they had enough experience, this method worked fairly well, but it led to a host of problems for Sales and Cus tomer Service. For example, a salesman wanting to offer service to a prospect might have difficulty deter

mining the optimal route for the customer to ensure the best service at the least cost. Drivers were not

required to inform the route planners if they changed

the sequence of stops, which made serving their cus tomers nearly impossible when they were out sick or on vacation. Finally, to reduce information technol ogy (IT) costs, WM sought a Web-based platform to handle routing.

Waste Management With headquarters in Houston, Texas, WM is the lead ing provider of comprehensive waste-management services in North America. Its network of opera tions includes 293 active landfill disposal sites, 16

waste-to-energy plants, 72 landfill gas-to-energy facil ities, 146 recycling plants, 346 transfer stations, and 435 collection operations (depots). Combined, these resources enable WM to offer a full range of envi ronmental services to nearly 20 million residential customers and 2 million commercial customers throughout the US and Canada. WM provides solid-waste collection services for

residential, industrial, and commercial customers in

24

This content downloaded from �������������73.24.246.41 on Sat, 13 Feb 2021 00:39:48 UTC��������������

All use subject to https://about.jstor.org/terms

Sahoo et al.: Routing Optimization for Waste Management Interfaces 35(1), pp. 24-36, ?2005 INFORMS 25

48 states, the District of Columbia, Canada, and Puerto Rico. With nearly 26,000 collection and trans fer vehicles, it operates the largest trucking fleet in the waste industry and collects over 80 million tons of garbage a year. The company provides a wide range of services, from picking up household trash at single-subscription residences to providing com prehensive waste programs for large national com panies with hundreds of locations. For these compa nies, WM's national accounts department develops customized programs, sometimes sending a represen tative to work on site to help them manage specialized and diverse environmental needs.

WM has improved its routing, maintenance, and utilization of labor and equipment in its 435 collec tion operations across the US and Canada. One of the most fundamental changes was the restructuring of the organization around geographic market areas. Before, WM operated as a collection of 1,200 sepa rate business entities; now, these business units have

been consolidated into 66 market areas. This simpler, more streamlined structure aligned the organization with the business strategy. Integrating all the assets in a market area (services, people, resources, and equip ment) enables WM to manage business more effec tively and at a lower cost. As a result, WM now has a

market-based, customer-driven structure resulting in a stronger enterprise and a more competitive force in the market place. Based on 2002 gross revenues, WM's waste-collec

tion business contributed 68 percent of its total rev enue. Within the collection business, commercial col lection, residential collection, and industrial collection

contributed 38, 32, and 29 percent to gross revenues, respectively (Waste Management, Inc. 2003). WM's achievements in IT were recognized by CIO magazine, which awarded it the CIO100 Award for 2001, 2002, and 2003.

The Problem of Routes In changing from a decentralized to a centralized organization, WM recognized that managing the activities of its 19,600 daily routes was not trivial. WM typically operates vehicles six days a week, with a few running on Sundays. With an annual operating cost of nearly $120,000 per vehicle, WM wanted to make every route as profitable and efficient as possible.

WM managers intended to reduce the overall operat ing expenses, whose key components are fixed vehicle costs, variable vehicle costs, and labor expenses. They decided that the best way to evaluate the results of a program to cut costs was to measure the reduction in vehicles. Eliminating one vehicle may eliminate five or even six route days and certainly contributes to reducing assets.

The collection business is in three major areas: com mercial, residential, and industrial. Although they are very different, they all produce municipal solid waste and materials for recycling. Commercial cus tomers include strip malls, restaurants, and small office buildings. A commercial route may include 60 to 400 customers and two or three disposal trips to a landfill each day Depending upon the customer base, a driver may visit the same customer multi ple times in one week. The weekly service schedule is fairly static, as most customers seldom change the frequency of service. Commercial routes usually con tain about 20 percent volatility, or unplanned activity, throughout the course of the day. Blocked dump sters or containers, extra services, and new customer

stops alter planned routes. The difficulty in man aging the efficiency and productivity of drivers lies in the details. On one route, a driver may pick up garbage for only 60 customers a day, while on another route in the same city, the driver may serve 300 cus tomers in one day. However, the first driver may drive nearly 400 miles while the second drives only 150 miles. Measuring and comparing driver produc tivity was nearly impossible with WM's existing oper ational systems.

Residential customers are generally people living in private homes. In subscription service areas, where customers call WM individually for service, routes tend to be less dense and costs higher per customer than in contract areas where WM bids for and obtains

the right to serve all homes in an area. In subscrip tion areas, sales and operations staffs work to increase customer density to reduce cost per customer. Munic ipalities and homeowners' associations commonly contract with WM to limit the number of waste vehicles driving through the neighborhoods, thereby increasing the overall safety and appeal of the com

munity. WM had difficulty measuring and comparing productivity within residential routes. Depending on

This content downloaded from �������������73.24.246.41 on Sat, 13 Feb 2021 00:39:48 UTC��������������

All use subject to https://about.jstor.org/terms

Sahoo et al.: Routing Optimization for Waste Management 26 Interfaces 35(1), pp. 24-36, ?2005 INFORMS

(a) Point-to-point routing (b) Arc routing

Figure 1: Because vehicles are permitted to travel and make stops only on the right sides of streets, residential collection requires arc-routing systems.

density, a residential route may serve between 150 and 1,300 homes a day. Compensation plans, geogra phy, unions, and local experience levels all contribute to the productivity of a route. The frequency of service per week will vary based on the climate, geography, competition, and price of service. In northern states, customers commonly expect service once per week. In southern states, they typically expect service twice per week. Once WM determines the weekly frequency for a set of routes, it repeats this schedule every week.

The single largest factor distinguishing residen tial routes from commercial routes is the mandatory adherence to driving on one side of the street. Unlike drivers on commercial routes, those on residential routes are permitted to serve only customers on the right side of the street (Figure 1). Very few exceptions are granted for alleys and one-way streets. This means that solving the residential routing problem is dif ferent from solving the commercial routing problem. Point-to-point solutions are acceptable for commer cial routes but residential routes require arc-routing solutions.

Industrial routes introduce a different routing prob lem. The differentiator between commercial routes and industrial routes is the size of the containers

(dumpsters). A typical commercial container is eight loose yards, while an industrial container may range from 20 to 40 loose yards. Trucks can handle only one industrial container at a time and they commonly haul these large containers to the landfill, empty them, and have them back to the original customers' locations. To complicate the problem, WM uses many different approaches to improve the efficiency of this operation. For example, a truck may first deliver an empty container at the customer location, and then pick up the full container, travel to a disposal facility

and dispose of the contents. It might serve another customer with the same size container. The difficulty arises when a driver is scheduled to perform dif ferent types of services throughout the day for cus tomers with different container sizes and different

service requirements. WM must consider more fac tors, including driver-experience level, vehicle types, container types, material types, and security clear ance, when creating industrial routes.

The Residential and Commercial Routing Problem Characteristics Through WasteRoute, we mainly solved the resi dential routing problem and the commercial routing problem. Both residential and commercial collection problems can be classified as variations of vehicle routing problems with time windows (VRPTW) but with additional constraints. In the literature, a typ ical vehicle routing problem (VRP) comprises a set of vehicles, stops, and a depot. Each vehicle starts from the depot, visits a number of stops, and ends at the depot. Depending on the nature of the applica tion, VRPs may have different characteristics, includ ing types of vehicles (homogeneous or heterogeneous) and number of depots (single or multiple). A VRPTW is defined as a VRP extended by additional time con straints associated with each stop. The depot also has a time window. Each vehicle has a single capacity constraint, such as maximum volume or maximum travel time. The objective function(s) generally mini

mizes total costs or total travel time. The VRPTW is

NP-hard, and finding a feasible solution with a fixed fleet size is an NP-complete problem (Cordeau et al. 2002), and one frequently resorts to approximate or heuristic procedures in solving the problem.

As with a typical VRPTW, at WM, each operation site has a single depot per collection operation, a finite number of homogeneous vehicles, and a set of stops. In addition to those standard components of VRPTW, the routing problems at WM have landfill facilities, the feature unique to the waste-collection business. The constraints specific to landfills are a major compo nent of the routing problem for waste-collection com panies. When a vehicle is full, it needs to go to the closest available disposal facility. Each vehicle can and typically does make multiple disposal trips per day.

This content downloaded from �������������73.24.246.41 on Sat, 13 Feb 2021 00:39:48 UTC��������������

All use subject to https://about.jstor.org/terms

Sahoo et al.: Routing Optimization for Waste Management Interfaces 35(1), pp. 24-36, ?2005 INFORMS 27

WM considers two main capacity constraints when creating a route: vehicle capacity and route capacity. Vehicle capacity is the maximum volume and weight that each vehicle can hold. Route capacity is the daily capacity for each driver: maximum number of stops, maximum number of lifts, maximum volume and weight that a driver can handle per day, and so forth. WM business rules set the route capacity constraints and route time. Vehicle capacity dictates when drivers should make disposal trips. If the vehicle capacity is larger than the route's volume capacity, drivers

will make only one disposal trip and it will be the last stop before returning to the depot. If, however, the route's volume capacity is more than the vehicle capacity, the driver will make multiple disposal trips. Because multiple disposal facilities are available, we must carefully select the best. We assume that each vehicle starts at a depot and ends up at the depot with zero volume. Each vehicle has a one-hour lunch

break between 11:00 am and 1:00 pm. WM's typical problems range between 25,000 and 120,000 residen tial homes or 10,000 and 54,000 commercial stops per collection operation. While authors of papers on the VRPTW consider

minimizing the number of vehicles and total travel time to be the major objective, WM also considers the visual attractiveness or route compactness of solu tions very important. We borrowed the term "visual attractiveness" from Poot et al. (2002); it depends on how stops are grouped into routes. A solution in which many routes cross over each other is less visu ally attractive than one in which no routes overlap. Balancing work among vehicles is also important in implementing a solution in the field. We summarize our problem as follows:

Objectives ? Minimize the number of vehicles, ? Minimize travel time, ? Maximize visual attractiveness, ? Balance workload among the vehicles. Constraints ? Time windows of stops and the depot, ? Vehicle capacity (volume, weight), ? Route capacity (maximum number of homes

(residential) or lifts (commercial), volume, and weight a vehicle can handle per day), ? Routing time limit per vehicle,

? Disposal trips (when a vehicle is full, it must go to a disposal facility), ? Driver's lunch break.

Before WM adopted WasteRoute, local route plan ners designed routes manually and distributed them to the drivers. Although some route planners had very limited visualization tools, the efficiency of the routes they planned depended greatly upon their experience and knowledge of the area, as well as the timely availability of the information they needed to plan routes to accommodate construction areas,

weather, vehicle availability, and driver availability. Route planners had difficulty constantly taking all of this information into account when planning routes to ensure efficiency. To address disruptions on routes, drivers or dispatchers simply changed routes without reoptimizing the routes, resulting in routes crossing one another, less-than-efficient results, or poor cus tomer service.

WM Selected HT as a Solution Provider WM organized a team of stakeholders and consul tants to evaluate route-management software pack ages. WM was looking for an application that could be integrated into its existing IT infrastructure, prefer ably a Web-based solution. WM decided that the best way to evaluate the ini

tial list of 19 vendors was to put them head-to-head in a competitive situation. It held a competition in

Houston during August 2001. It made its final evalu ation comparing the quality of the routing algorithm engines in February 2002. WM evaluated and com pared the algorithms' functional fit with its business rules. It evaluated the results of the algorithm tests

ba?ed on meeting three objectives; (1) route reduc tion (cost savings), (2) workload balancing (number of routes) across days of the week, and (3) adher ence to business constraints. The solution provided by the Institute of Information Technology, Inc. (IIT) met these requirements. HT's solution also took into consideration turn restrictions or penalties, speed lim its, and adherence to side of street for residential routes. In addition, given a four-hour processing-time restriction, the IIT software solved WM's problem in 35 minutes.

WM contracted with IIT to develop WasteRoute, a comprehensive route-management system that took

This content downloaded from �������������73.24.246.41 on Sat, 13 Feb 2021 00:39:48 UTC��������������

All use subject to https://about.jstor.org/terms

Sahoo et al.: Routing Optimization for Waste Management 28 Interfaces 35(1), pp. 24-36, ?2005 INFORMS

into account WM's specific routing concerns and provided broad benefits. In March 2003, three months after a team of people from both organizations began initial development, WM rolled out the first version of WasteRoute.

GIS and Optimization A geographical information system (GIS) tightly inte grates spatial information to managed data. To illus trate the contrast, consider a customer in a standard relational database. In a standard relational database, the attributes for a customer would typically include name, billing information, and address. The firm typ ically enters the address information manually in a system for managing customer relationships and uses it for mailings. With such a system, the firm could not determine customers' proximity to other customers or routes to support decisions about routing.

Based on a customer's address, a GIS would pro vide spatial information about the customer, includ ing the customer's specific x, y, and z location in a coordinate system and the geometry of the cus tomer's pickup site, usually a point but sometimes a line or a polygon. When it brings this spatial infor

mation together with other information having spa tial components, such as streets, it can display truly unique aspects of the data. For example, it can display customers' locations on a map with the surrounding street network, various landmarks, other customers,

or the collection facility. Although planners can use the GIS component of

WasteRoute to view customer locations on a map and manipulate information, they take advantage of the true power of the GIS when they construct a key component of the optimization engine, an origin destination (OD) matrix. This matrix captures the dis tance and time traversed on a street network between

any two points, taking into account such constraints as speed limits, directional attributes of streets (such as one-way directions or turn penalties and restric tions), and accurate segment distances.

The WasteRoute System WasteRoute is a Web-based Java application, inte grated with WM's other systems (Figure 2). The user interface is managed by applets, is launched from a

Web page, and runs within the Java virtual machine found in nearly all Web browsers. The applet con sists of both tabular data (in forms and reports) and a map displaying customer locations, landfills, and other facilities against a background of streets, land marks, and other geographical boundaries. The coor dination of the navigation tree, customer data, and an interactive map makes the application simple to use. Ease of use is very important to WM, because local route managers, whose computer skills vary widely, use the application.

A given customer can have many stops on many days, each of which represents a location where the vehicle stops. A stop may have one or more orders, each of which represents a trash container or a res idence. This representation models the business to support customer service at the container level but intelligently collapses orders from the same customer into a single stop as appropriate. For example, the optimization engine can view three containers at a strip mall, even though they are at different coor dinates in the real world along a driveway, as one stop for routing purposes. The model is also sophisti cated enough to account for the time taken to handle additional containers at the same location with con

figuration parameters. This database is automatically synchronized with the existing AS/400 infrastructure.

Deployment From the beginning, WM understood that deploying an application like WasteRoute would fundamentally change the way it served its customers. Getting peo ple to change for any reason is difficult, and fail ing to orchestrate the change risks failure. A team of two project managers (IT and business) and a group of four organizational-change-management personnel developed a plan to roll out WasteRoute to the orga

nization. They designed the initial deployment plan with two tiers: tier one has 36 market areas consisting of larger collection operations, and tier two, 30 mar ket areas consisting of smaller, more rural collection operations. They set the completion time line for tier one at the end of 2003 and for tier two at the end of

2004. They further decided to break tier one into three waves of 12 market areas for systematic rollout of WasteRoute. We conducted the first classroom train

ing class in March 2003 for wave-one participants.

This content downloaded from �������������73.24.246.41 on Sat, 13 Feb 2021 00:39:48 UTC��������������

All use subject to https://about.jstor.org/terms

Sahoo et al.: Routing Optimization for Waste Management Interfaces 35(1), pp. 24-36, ?2005 INFORMS 29

GPS PDA

Call Center/ Customer Service

GPS Data Hosting

JMS queue

Figure 2: WasteRoute is a Java application which is integrated with various other enterprise systems at WM through Web services/HTTP protocol. The various applications provide data to WasteRoute and consume the services it generates. Customer and billing data for sites in the US reside in an AS400 system called MAS and for sites in Canada, reside in InfoPro. Contract residential customer data collected through GPS systems is also integrated. WasteRoute uses SiteMinder as a directory server for user authentication and authorization in accordance with WM's corporate standards. WasteRoute is also integrated with other systems, such as analysis and modeling for profitability (AMP) and customer-service applications.

To help us with training and expand our knowledge base, we had some of the route planners from the wave-two operation sites participate in the deploy ment of wave-one operations. Our objective was to train many people simultaneously while they gained on-the-job experience. This procedure worked very weU. The training class consisted of two components: standard operating procedures and application train ing. After taking the initial class, the planners also took a series of self-paced Web-based courses that covered each of the two topics individually. While the exact savings in the various areas vary, Elgin, Illinois, for example, went from 10 routes to nine routes using

WasteRoute. It improved the average productivity of the routes from 57.06 cubic yards of garbage per hour to 63.41 cubic yards per hour (Figure 3). When companies adopt software, such as Waste

Route, the employees who must use it tend to be defensive and resist changing the way they do

their jobs. To maintain morale and build trust between employees and managers, WM drew up a proac tive communication plan and included the employ ees at every step during the rollout. WM reduced the number of routes with the full support of the drivers because it did not lay off any drivers; it reduced staff through normal attrition. In Baltimore, Fleet Optimization Manager Renee Huff says, "Driver involvement has been a crucial success factor in implementing WasteRoute at our site." Huff projected the new routes that WasteRoute created on a screen and received valuable feedback from drivers on route

density and capacity limitations. Giving the drivers ownership made them willing to adopt the new sys tem and help to improve their routes. We broke the deployment for each operation site

into four steps: service-boundary analysis (SBA), weekly balancing, clustering stops, and optimizing routes. Market area managers and route planners use

This content downloaded from �������������73.24.246.41 on Sat, 13 Feb 2021 00:39:48 UTC��������������

All use subject to https://about.jstor.org/terms

Sahoo et al.: Routing Optimization for Waste Management 30 Interfaces 35(1), pp. 24-36, ? 2005 INFORMS

(a) Before

(b) After

Figure 3: In the Elgin, Illinois area, WM reduced routes by one, a reduc tion of 10 percent. Before WasteRoute, that area required 10 nine-hour routes, and its productivity was 57.06 yards per hour. With the solution of WasteRoute, that area now requires nine nine-hour routes, and its pro ductivity is 63.40 yards per hour. Each polygon shows an individual route.

WasteRoute extensively during these steps. During SBA, area staff could remove any overlaps between neighboring WM operations. In conducting weekly balancing, route planners try to move customers to different days to equalize workloads on the five days of the week. This step includes a review of customers' container sizes and frequencies. For a customer with a small container and service three or more times

a week, WM can substitute a larger container and reduce the frequency of service, thus reducing WfM's cost of serving that customer. This step can add time

to the deployment because such changes require per sonal phone calls by WM representatives to confirm them. In the clustering step, users look at the geogra phies of the routes without creating individual route sequences. During the optimization step, route plan ners sequence the daily routes using WasteRoute. After WasteRoute creates the routes, drivers and man

agers review them. Once the drivers approved of the new routes, the managers set a go-live date for the operation site, and WM notified the customers as nec essary by phone, mail, or door hangers (notices hung on door knobs).

Impact and Business Benefits After four years of emphasizing growth through acquisitions, WM needed to optimize its routes. WM strives for operational excellence. Corporate leaders identified WasteRoute as one of the building blocks it needed to achieve operational excellence. To sell this program to stakeholders and key personnel, we designated four key objectives: profitability, customer service, route optimization, and safety.

Profitability In February 2003, CEO Maurice Myers remarked, "Over the past year, in pilots at 27 different hauling locations, we've reduced drivers and trucks by up to 17 percent and on average 10 percent. The company operates 15,000 commercial and residential routes. Our goal is to achieve the average pilot reduction of 10 percent. Each route is estimated to cost $120,000 annually, so our potential cost savings are meaningful to our bottom line."

With a graduating deployment schedule, financial benefits increased on a nonlinear scale. WM began to realize benefits in the second quarter of 2003. Deployment to 36 market areas in 2003 realized sav ings at approximately $18 million and costs at roughly $10 million. WM estimated that its saving for the year of 2004 due to the route reduction of 2003 will be $44 million. WM anticipates the savings to come in the long term. As each market area's employees become more familiar with the software and the soft

ware becomes institutionalized across WM, it will yield additional savings. The firm expects to make additional route reductions and thus cost savings as it extends WasteRoute to 30 market areas throughout

This content downloaded from �������������73.24.246.41 on Sat, 13 Feb 2021 00:39:48 UTC��������������

All use subject to https://about.jstor.org/terms

Sahoo et al.: Routing Optimization for Waste Management Interfaces 35(1), pp. 24-36, ?2005 INFORMS 31

North America in 2004. WM expects its cash flow to increase by $648 million over a five-year period. Over the same period, it estimates its savings in operational expenses will be $498 million. Early in the deploy ment, WM realized that WasteRoute had impacts beyond saving costs. As routes increased in capac ity, they could increase in revenue. Managers able to understand daily vehicle activities and sales could focus on targeted areas to increase route density.

Customer Service

As WM stabilized its routes, the dispatchers, cus tomer representatives, and drivers communicated

more effectively and can now produce more consis tant and reliable service. Sales agents able to see the location of facilities or the area covered by a route can judge which customers to target. They can also close deals by offering those customers appropriate pricing options.

Route Optimization Tom Derieg, vice present of fleet services and logistics and executive sponsor of WasteRoute, states, "This past year was one of patience and persistence for our team members and the many employees around the company who helped us analyze the efficiency of our routes. I am very pleased to report to you that we exceeded the goal Maury Myers set out for us in December 2002. We were asked to reduce 750

routes, and our 2003 cumulative accomplishment was a reduction of 984 routes (goals exceeded quarter over quarter in 2003). It is tough to admit that we had an efficiency issue, but based on our results, I am very proud to see how much this work has strengthened the company already/' The most significant improve

ments were made by the Oregon market area, which reduced 46 routes against a goal of reducing 12, and their optimization efforts continue in 2004.

In a short span of four years, WM has transformed itself from a fragmented organization headed in many directions to a centralized corporation with a uni fied goal of operational excellence. The success of

WasteRoute has brought WM close to realizing the benefits of its size and scale. This Fortune 100 com

pany is now delivering on its promise of operational excellence and differentiated service as an example to the waste industry. Applying optimization to reduce

routes has made WM receptive to increasing the role for operations research techniques in other opera tional areas, such as locating facilities and delineating service boundaries.

Safety Reducing routes continues to improve WM's opera tional efficiency and cost savings, and it has a positive impact on the environment and employees. Fewer trucks on the road noticeably reduce emissions and noise. Reducing travel during busy times of the day and traffic in the communities in which WM is a member are also noticeable benefits.

"Safety and WasteRoute are inextricably linked," ex plained Jim Schultz, vice president of safety. "The Was teRoute team recognized from the outset their respon sibility to employees, customers, and people in the communities we serve to ensure safety is the founda tion," he added. To do this, WM has made operational safety a cornerstone element in the WasteRoute imple

mentation.

Conclusion In 1999, Waste Management acquired businesses at the rate of one per day, so it was imperative that it searched for a way to manage this growth simply to ensure survival. During that same year, WM set the goal of achieving some business benefits by opti

mizing routes, and, with the help of the Institute of Information Technology, it realized this goal using

WasteRoute. This GIS-based route-management appli cation reduced WM's operational costs by (1) orga nizing routes to minimize overlap and thereby reduce the number of vehicles WM needed to serve its cus

tomers, and (2) sequencing the stops along a route to make the best use of fuel, driver schedules, and disposal trips. Integrating WM's existing systems with WasteRoute allows customer-service personnel to resolve service issues quickly because they have access to information about the customers. Market

ing and sales personnel also use WasteRoute to offer appropriate pricing to prospects and to select areas to serve based on existing routes and facility locations.

The financial results from the initial deployment of WasteRoute are very positive. With the rollout of Was teRoute in 2003 and 2004, WM expects to reduce the number of collection routes by 10 percent. WM began

This content downloaded from �������������73.24.246.41 on Sat, 13 Feb 2021 00:39:48 UTC��������������

All use subject to https://about.jstor.org/terms

Sahoo et al.: Routing Optimization for Waste Management 32 Interfaces 35(1), pp. 24-36, ?2005 INFORMS

deploying WasteRoute in March 2003 with a net effect of 984 fewer routes at the end of the year, exceeding its goal of dropping 750 routes, and achieving sav ings of $18 million. WM estimated that its savings for the year of 2004 due to the route reduction of 2003 will be $44 million. The firm expects to make additional route reductions and thus cost savings as it extends WasteRoute throughout North America in 2004. WM expects its cash flow to increase by $648 million over a five-year period. Over the same period, it estimates its savings in operational expenses will be $498 million.

Appendix The Optimization Problem To explain the problem clearly, we present a mathe matical programming model for a simplified version of our problem here. We simplified the problem by minimizing only travel time. In the real-world prob lem, we also try to minimize the number of vehi cles, maximize the visual attractiveness, and balance the workload. This simplified model also considers single-vehicle capacity alone. In the simplified prob lem, we assume that the number of vehicles is given and consider a single objective function: minimize the travel time. We adopted the notation and basic VRPTW model of Cordeau et al. (2002) and changed them to incorporate the disposal operations and the drivers' lunch breaks.

The simplified waste VRPTW is defined on the net work G = (V, A), where the regular stops are rep resented by nodes 1 to N, the landfills are repre sented by nodes N + 1 to N + M, the lunch break is represented by N + M + 1, and the depot is rep resented by 0 in the vertex set V = {0,1,2...N, N + 1,... N + M + 1}, and A is the arc set. For mod eling purposes, the landfills are duplicated such that a vehicle visits a landfill at most once in a route. For

example, if a vehicle visits a specific landfill three times in a route, we duplicate the landfill three times so that the vehicle virtually visits a landfill at most once. The maximum number of disposal trips for a vehicle can determine the number of duplications in a day because, in extreme cases, the vehicle visits the same landfill every time. Each node in V has a time window [aif bt] representing the earliest possible

service starting time and the latest possible starting time. The depot's time window [?, L] has the special

meaning of the earliest possible departure from the depot and the latest possible arrival at the depot. Each node has a service time s? and demand d{. The lunch break, the depot, and the landfills have zero demand. The depot has zero service time. A nonnegative travel time, t{-, is associated with each arc (/', ;*) e A. Travel time between the lunch break stop, N + M + 1, and any stop is set to zero.

Let K be the available vehicle set, Nk be the actual number of disposal trips for vehicle k, and C be the vehicle capacity. Let xit-]ik, where (/, /) e A,k eK, equal 1 if arc (/,;) is used by vehicle k and 0 oth erwise. Let time variable wifk/ where i eV,k e K, be the start service time at node / when it is serviced

by vehicle k. Let also Difk, where ieV,keK, be the cumulative demand at node i for vehicle k. A route

represents the travel path of a vehicle, and a subroute represents a sub-travel path that starts from the depot or a disposal facility and ends at a disposal location or the depot.

Simplified Waste-VRPTW Model

min E E ti,}*,}* keK{i,j)eA

subject to

E E *. ./,* = ! V/el,2,...,N, (1) keK(i,j)eA

?*?,/,* = 1 V/ceK, (2)

Dik<C VkeK, iel,2,...,N,N+M+l, (3) D?a = 0 VkeK, meO,N + l,N+2,...,N+M, (4)

Dhk+drDjik<(l-xhjik)BigM VfceK, ieO,l,2,...,N+M + l,jeO,l,2,...,N,N+M+l, (5)

N N+M+l

E?, E *,,/,*<C*Nt V^gK, (6) ;=1 ?=1

N+M

E E aw = N* VfceK, (7) i'el^.^N^+M+l m=N+l

N+M

E E *?,/.* = ^-1 V?re?C, (8) m=N+l;'el/.../N,N+M+l

This content downloaded from �������������73.24.246.41 on Sat, 13 Feb 2021 00:39:48 UTC��������������

All use subject to https://about.jstor.org/terms

Sahoo et al.: Routing Optimization for Waste Management Interfaces 35(1), pp. 24-36, ?2005 INFORMS 33

N+M

? xnfiik = \ VfceK, (9) m=N+l

N+M

?*,,n+m+i,* = 1 v^eK, (10) i=l

N+M

EXN+M+1,;,^1 VfceK, (11) 7=0

N+M+l N+M+l

/ , %i,j,k 2^ j,i,k 1=0 2=0

V/ceK, ;gO,1,...,N + M + 1, (12) wf/jt + sf + ii#;- ? w^ fc < (1 - Jff//^)Big M

VkeK, (z,/)gA, (13)

wi,k + Si + SN+M+1 + U,j ~ Wj,k

<(2 ?x//N+M+1//c ?xN+M+1/j-//c)BigM,

V/cgK, (i,j)eA (14) N+M+l N+M+l

fl* E xi,j,k^y>i,k<bi E **,,,* ,=i ;=i

V/cgK, zg0,1,...,N + M + 1, (15) E<wlk<L VkeK, ie0,l,...,N + M + l, (16)

*, ,,,* e {0,1} V/cgK, (?,;)gA, (17)

N^>0, Integer VkeK, (18) Du>0 VfcGK, zg0,1,...,N + M + l. (19)

Constraints (1) impose the rule that each regular stop should be served by exactly one vehicle. Con straints (2) ensure that each route starts from the depot. Constraints (3) keep the amount of garbage collected at each stop within the vehicle capacity constraint. Constraints (4) ensure that the collected garbage volume is reset to zero once the vehicle has visited a landfill, as well as in the particular instance when the vehicle leaves the depot. Constraints (5) are in place to make sure that the collected garbage reflects the correct incremental volume of a particular stop when a truck visits that stop. By constraints (6), the actual number of disposal trips is calculated. Con straints (7) impose the condition that the number of trips from the regular stops to disposal facilities for a vehicle is equal to the number of actual disposal trips. Constraints (8) impose the condition that the num ber of trips from the disposal facilities to the regu lar stops should be one less than the number of dis posal trips. The last trip from a disposal facility in

that route should be to the depot, and this will be achieved by constraints (9). Constraints (10) and (11) are introduced to add the lunch break for each route.

Constraints (12) ensure that if the vehicle arrives at a stop, it must leave the stop. Constraints (13) through (16) make sure that the time constraints on both the route and vehicle are satisfied. Constraints (14) make sure that the travel time between before-lunch-break

stop and after-lunch-break stop is included. Finally, constraints (17) through (19) impose binary condi tions, nonnegative integer constraints, and nonnega tive conditions on the variable set. As observed in

the simplified waste-VRPTW model, the disposal trips and the lunch break make the problem much more complicated.

The Solution Approach We developed and implemented an iterative two phase algorithm in which the first phase generates an initial solution and the second improves it. First, we estimate the number of routes for a given site by considering the total workload and the maximum vol ume, yardage, number of lifts (commercial) or homes (residential), and allowable routing time of routes. Then, we initially (roughly) route the stops based on their locations and time-window constraints in the

first step, which we call Phase 1. For the first ini tial route-building phase, we apply a hybrid method of balanced clustering and a greedy-insertion algo rithm to enhance visual attractiveness. In this stage, we also balance the routes in terms of the workload

so that a single vehicle can serve each route. The sec ond phase of the algorithm accomplishes optimized route building using an extended traveling-salesman problem (TSP) and extended-insertion VRPTW and by applying metaheuristic algorithms. In this step, if any stops are not routed in a given route, it assigns those stops to their closest available routes. If after all the routes are optimized, there are stops remain ing that have not been routed, the algorithm increases the number of routes and repeats the two steps from the beginning. We discuss the main algorithms of the procedure in the next sections.

Initial Route Construction Using Balanced Clustering Algorithms with Greedy Insertion The first phase of the solution approach utilizes a fc-means-variant-balanced-clustering algorithm (Kim

This content downloaded from �������������73.24.246.41 on Sat, 13 Feb 2021 00:39:48 UTC��������������

All use subject to https://about.jstor.org/terms

Sahoo et al.: Routing Optimization for Waste Management

34_ Interfaces 35(1), pp. 24-36, ?2005 INFORMS

et al. 2004). Like the fc-means algorithm, it selects an initial centroid seed stop for each route randomly as the first step and assigns the remaining stops to their nearest route. Then, it calculates a new centroid for each route. It clusters the stops based on the distances between the stops and the centroids. In other words, it assigns a stop to the route whose centroid is the closest to the stop. Each time it assigns a stop to a route, it considers the capacity of the route. The capac ity of the route is defined by the maximum number of stops that the vehicle is allowed to visit, the vol ume or weight that the vehicle is allowed to handle,

and the allowable routing time. The algorithm esti mates the routing time for each route each time it adds a stop to the route by using a fast TSP heuristic algorithm, which is a greedy insertion. When a route

whose centroid is the nearest to the stop being pro cessed has already reached its capacity, it assigns the stop to the next closest route whose capacity is not full.

We also developed and applied a simple improve ment algorithm for enhancing visual attractiveness. The basic idea of the improvement is as follows: if a stop's current route is not the same as the stop's

Problem set

Best-known solution HT algorithm

Vehicle i Distance Vehicle # Distance Problem

set Vehicle # Distance Vehicle ? Distance

C101 C102 C103 C104 C105 C106 C107 C108 C109 R101 R102 R103 R104 R105 R106 R107 R108 R109 R110 R111 R112 RC101 RC102 RC103 RC104 RC105 RC106 RC107 RC108

10 10 10 10 10 10 10 10 10 19 17 13 9 14 12 10 9

11 10 10 9 14 12 11 10 13 11 11 10

828.94 828.94 828.06 824.78 828.94 828.94 828.94 828.94 828.94

1,645.79 1,486.12 1,292.68 1,007.24 1,377.11 1,251.98 1,104.66 960.88

1,194.73 1,118.59 1,096.72 982.14

1,696.94 1,554.75 1,261.67 1,135.48 1,629.44 1,424.73 1,230.48 1,139.82

10 10 10 10 10 10 10 10 10 19 18 14 10 14 12 11 10 12 11 11 10 16 13 11 10 14 12 11 11

828.94 828.94 828.94 827.95 828.94 828.94 828.94 828.94 828.94

1,703.69 1,479.37 1,226.05 1,020.62 1,446.35 1,310.08 1,132.39 980.55

1,196.61 1,106.65 1,146.41 994.16

1,705.72 1,537.24 1,324.17 1,173.91 1,577.90 1,450.65 1,248.44 1,162.47

C201 C202 C203 C204 C205 C206 C207 C208 R201 R202 R203 R204 R205 R206 R207 R208 R209 R210 R211 RC201 RC202 RC203 RC204 RC205 RC206 RC207 RC208

591.56 591.56 591.17 590.60 588.88 588.49 588.29 588.32

1,252.37 1,191.70 939.54 825.52 994.42 906.14 893.33 726.75 909.16 939.34 892.71

1,406.91 1,367.09 1,049.62 798.41

1,297.19 1,146.32 1,061.14 828.14

591.56 591.56 603.37 601.11 588.88 588.49 588.32 588.32

1,279.98 1,105.65 1,000.33 774.41

1,099.99 971.85 854.01 743.27

1,019.73 1,000.26 848.92

1,461.31 1,224.31 1,134.20 853.45

1,362.71 1,135.19 1,204.67 897.29

Table 1: Because we could not find a publicly available benchmark problem set for waste collection, we used Solomon's (1987) well-known data set for VRPTW, which is much simpler than our problem, to evaluate our algo rithms. The problem sets and their best-known solutions are available at http://web.cba.neu.edu/-msolomon/. The best-known solutions have been updated for the last 17 years after the problem sets were presented, and the current best-known solutions as of August 2004 came from 16 different works from all over the world. No single solution algorithm can generate the best-known solutions for all the problems. Most of the works are laboratory-level research experiments. Considering these facts, the results in this table, and the fact that ours has been successfully embedded in a real-world enterprise routing system and is being used, we can claim that our approach is highly competitive.

This content downloaded from �������������73.24.246.41 on Sat, 13 Feb 2021 00:39:48 UTC��������������

All use subject to https://about.jstor.org/terms

Sahoo et al.: Routing Optimization for Waste Management Interfaces 35(1), pp. 24-36, ?2005 INFORMS 35

nearest route, move the stop to the nearest route when its move does not violate the capacity constraints of the routes and when its move improves the overall route quality.

Route Improvement by Extended-Insertion Algorithm and Metaheuristic Algorithm We use an extended version of Solomon's (1987) insertion algorithm to improve a route generated in the first phase, and a combined simulated-annealing

metaheuristic with the CROSS exchange local-search method of Taillard et al. (1997) for further improve ment. While Solomon's insertion algorithm assumes that each vehicle departs from the depot, serves only one route, and returns to the depot, the extended insertion algorithm considers multiple disposal facility operations and the driver's lunch break for each route.

We treated the lunch break as a special stop with a time window between 11:00 am and 1:00 pm and with a one-hour service time. We assume that the

travel distance and time between the lunch break stop and a regular stop is zero. Each time a vehicle is full, it must visit a landfill facility to empty its load. To handle this, we applied an iterative process of splitting a route to Solomon's insertion algorithm. In the following description, a route represents the travel path of a vehicle and a subroute represents a sub-travel path that starts from the depot or a disposal facility and ends at a disposal location or the depot.

All stops are marked as not routed at the begin ning of the algorithm. The algorithm creates an empty route for a vehicle and marks its lunch check as not

yet. It initializes a subroute with a seed stop chosen as the farthest stop from the depot. While a route is ini tialized with a sequence (depot, the seed stop, depot) in Solomon's algorithm, a subroute is initialized with a sequence (depot, the seed stop, lunch break, the closest disposal to the depot, depot) in the extended insertion algorithm. Because the route finally returns to the depot, the disposal facility closest to the depot is selected in an initial subroute.

After initialization, we insert repeatedly all stops that can be inserted without violating the time win dows using Solomon's insertion method. Note that we do not consider vehicle capacity at this stage. Instead,

we consider only the time window constraints of the vehicle and stops. A simulated-annealing metaheuris tic using the CROSS exchange local search method proposed by Taillard et al. (1997) improves the sub route constructed.

After the algorithm constructs a feasible subroute, it considers the vehicle capacity and splits the sub route. If the current subroute is within the vehicle

capacity, it does not need to split the subroute and it adds the subroute directly to the current route. Oth erwise, it adds a landfill facility in the sequence, splits the current subroute, and sets the rest of the stops after the splitting point to not routed. For the rest of the stops, it initializes a new subroute now

with a sequence (landfill facility, new seed stop, the

(a) Best-known solution for RC205

(b) Our solution for RC205

Figure 4: We compare the visual attractiveness of our solution and a best-known solution. Although our solution for the problem set RC205 of Solomon's (1987) data set requires a longer travel distance than Bent and Van Hentenryck's (2001) solution, it has much less overlap between routes and so is much more visually attractive. The polygons represent the boundaries of routes, and the different shapes show the stops that belong to the different routes.

This content downloaded from �������������73.24.246.41 on Sat, 13 Feb 2021 00:39:48 UTC��������������

All use subject to https://about.jstor.org/terms

Sahoo et al.: Routing Optimization for Waste Management 36 _ Interfaces 35(1), pp. 24-36, ?2005 INFORMS

dosest disposal to the depot, depot) and applies Solomon's insertion-heuristic algorithm to construct a subroute. It repeats this process until all the stops are routed.

Computational Experiments Because we could not find a publicly available bench mark problem set for waste collection, we used Solomon's well-known data set for VRPTW to evalu

ate our algorithms. Note that Solomon's problem set does not require any disposal trips or a lunch break. The problem sets and their best-known solutions are available at http://web.cba.neu.edu/^msolomon/ (Solomon 1987). Our method was able to generate competitive solutions compared with the best-known solutions (Table 1). Although our solutions are not as favorable when compared to the best-known solu tions (in terms of the number of vehicles required and travel distance for some problem sets), our method usually generated more visually attractive solutions (Figure 4).

Acknowledgments We could not have done the work reported in this paper without the committed hard work of many people from WM and IIT. We also appreciated invaluable help from

Anthony Brigandi, Sudhansu K. Baksi, Thomas Spencer III, Stephen C. Graves, and Mary F. Haight.

References Bent, Russell, Pascal Van Hentenryck. 2001. A two-stage hybrid

local search for the vehicle routing problem with time win dows. Technical report CS-01-06, Department of Computer Science, Brown University, Providence, RI. http://citeseer. ist.psu.edu/454901.html.

Cordeau, Jean-Francois, Guy Desaulniers, Jacques Desrosiers, Marius M. Solomon, Francois Soumis. 2002. VRP with time windows. P. Toth, D. Vigo, eds. The Vehicle Routing Problem. SIAM, Philadelphia, PA, 157-193.

Kim, Byung-In, Seongbae Kim, Surya Shaoo. 2004. Balanced clustering algorithms for vehicle routing problems. Insti tute of Industrial Engineers Annual Conference, May 15-19,

Houston, Texas. Retrieved October 18, 2004 http://www.x cd.com/iie/research/finalpapers/283.doc.

Poot, Alexander, Goos Kant, Albert P. M. Wagelmans. 2002. A sav ings based method for real-life vehicle routing problems. /. Oper. Res. Soc. 53(1) 57-68.

Solomon, Marius M. 1987. Algorithm for the vehicle routing and scheduling problem with time window constraints. Oper. Res. 35(2) 254-265.

Taillard, Eric, Philippe Badeau, Michel Gendreau, Francois Guertin, Jean-Yves Potvin. 1997. A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Sei. 31(1) 170-186.

Waste Management, Inc. 2003. Investor Meetings, Boston, MA. http://www.wm.com/newwm/investor/presentations/may20. ppt.

This content downloaded from �������������73.24.246.41 on Sat, 13 Feb 2021 00:39:48 UTC��������������

All use subject to https://about.jstor.org/terms