The waste collection vehicle routing problem with time windows

(waste collection VRPTW)

1. Introduction

As with a typical vehicle routing problems with time windows (VRPTW), it is assumed that there is a single depot per site, an operational area (such as a city or county), a finite number of homogeneous vehicles, a set of stops, and dump sites (transfer stations or landfill facilities) in the waste collection VRPTW. The constraints specific to landfills are a major component of the routing model for waste collection companies. 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.

Each stop has a time window, i.e., earliest and latest allowable service starting time, and its pick-up amount or demand. Each vehicle has its capacity and time window, i.e., ready time and due depot return time. Vehicles start from the depot, pick up materials from the stops until they are full, dump them at one of the dump sites, repeat pick up and dumping, and finally return to the depot. The vehicle drivers are assumed to take a one-hour lunch break between 11 a.m. and 1 p.m.

Two main capacity constraints are considered 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. A garbage collection company's business rules set the route capacity constraints and route time. Vehicle capacity dictates when a disposal trip should be made. If the vehicle capacity is larger than the route’s volume capacity, there will be only one disposal trip and it will be the last visit before returning to the depot. If, however, the route’s volume capacity is more than vehicle capacity, multiple disposal trips will be needed in a route. Since there are multiple disposal facilities available, careful selection of the best disposal is critical. Each vehicle is assumed to start from a depot and finish at the depot with zero volume. The typical problem size experienced at Waste Management Inc. ranges between 10,000 and 54,000 commercial stops per depot per week. Thus, the daily problem size ranges between approximately 2,000 and 10,000 per depot.

While minimizing the number of vehicles and total travel time is the major objective of VRPTW in the literature, the route compactness of a solution is very important to WM. The route compactness depends on how the stops are grouped into a route. A solution in which many routes cross over each other is less compact than one in which there are no overlapping routes. Balancing work among the vehicles is also important for implementation of a solution in the field. Our problem is summarized as follows. 

Objectives: 

·        Minimize number of vehicles

·        Minimize travel time

·        Maximize route compactness

·        Balance workload among the vehicles

Constraints:

·        Time windows of stops and the depot

·        Vehicle Capacity (i.e., volume, weight)

·        Route Capacity (i.e., the maximum number of lifts, volume and weight that can be handled per vehicle per day)

·        Routing time limit per vehicle

·        Disposal trips (i.e., when a vehicle is full, it must go to a disposal facility)

·        Driver’s lunch break

2. Benchmark Problem

Since there are no publicly available benchmark problems of the waste collection VRPTW, we extracted several problems from the real world problems and present them here (http://www.e-iit.com/waste-VRPTW/benchmark.html) for other researchers in this area. Each problem has four lines of basic information, one line of stop data header, and multiple lines of stop data. Four lines of basic information include vehicle capacity, total yards allowed for a vehicle per day, total number of stops allowed for a vehicle per day, lunch break time in seconds, default speed in mile per hour, and stop data. A vehicle cannot handle more than the total yards allowed for a vehicle or the total number of stops allowed. The default speed in mile per hour is for origin-destination (OD) matrix construction. Although we apply a shortest-path algorithm to geographic information system (GIS) to obtain OD matrix, i.e., travel time between any two stops, it is hard to publish those ODs on the Internet because of their sizes.  For example, the size of the OD matrix for 1599_stop.txt is about 80 MB. Thus, we recommend readers to use the default speed provided and the Manhattan distance for the calculation of OD matrix. For example, the travel time between stop 0 (x coordinate=1215029, y coordinate=3461398) and stop 1 (1229125, 3460107) in 102_stop.txt is 262.3 seconds. The Manhattan distance between them is 15387 feet and it is 2.914 mile. Since the default speed is 40 MPH, the travel time is 2.914 mile * 3600 seconds / 40 mile, which is 262.3 seconds. Our computational results in this section is also based on this method of OD calculation.

Individual stop has information of stop id, x coordinate in feet, y coordinate in feet, earliest service starting time in HHMM format, latest service starting time in HHMM format, service time in seconds, load in yards, and stop type. In HHMM format, the first two digits show hour and the remaining digits show minute. For example, 1030 stands for 10:30 AM and 1445 stands for 2:45 PM. The depot has stop type of 0, a landfill or transfer station has stop type 2, and a regular stop has stop type 1. Table 1 shows the characteristics of the problems sets.

Table 1. Waste VRPTW benchmark problem sets