The rollon-rolloff waste collection vehicle routing problem (RR-VRPTW) with real-world issues

Full paper: J. Wy, B.-I. Kim, S. Kim, " The rollon-rolloff waste collection vehicle routing problem (RR-VRPTW) with time windows," Working paper

1. Introduction

We study an industrial waste collection problem involving construction sites, downtown areas, and large shopping malls that accumulate generous amounts of garbage. In such a problem, the customers require large-container level services, and thus, tractors are dispatched only one container at a time [1] and collect the garbage container itself. The industrial waste collection problem has been defined as the skip problem [2, 3], and the rollon-rolloff vehicle routing problem (RR-VRP) [4] in previous studies. We also define our problem as the RR-VRP and extend it by including the issue of time windows. Hence, our version is called rollon-rolloff vehicle routing problem with time windows (RR-VRPTW). The problem considered in this research involves complicated constraints, including multiple disposal sites, multiple yards, seven service types (trip types) that can handle all trip types proposed in previous works, time windows for customer demands, a depot, disposal sites and yards, container size, container type, and a lunch break for the tractor drivers. In addition, some customers are allowed to change their service type and may require many services by a single tractor. To the best of our knowledge, no previous works have handled this complicated problem. In addition, time windows of the locations, changing service types, and the varied number of available empty containers at each yard comprise unique issues for the industrial waste collection problem of the this study.

2. Problem Descriptions

2.1. The rollon-rolloff vehicle routing problem with time windows (RR-VRPTW)

In the RR-VRPTW, the customers dump garbage in a container and require waste collection services, which include collecting the full container, ordering an empty container, changing the container, and so on. Tractors transport the container between customer locations and facility locations, such as a depot, disposal sites and yards, to satisfy given customer demands. These tractors carry only a single container at a time, regardless of container sizes and types, have different work schedules, and may require a lunch break for the drivers. The empty containers are stored at yards. However, the number of available containers at each yard may vary because there are multiple yards and tractors transport the containers between customer locations and facility locations. There are different types of wastes that have to be dumped at the proper disposal site. A customer demand is assigned to a disposal site type, and the appropriate disposal site should be used for that customer demand. Table 1 shows the service types derived from a real waste collection company in the U.S.

Table 1. Service types for customer demands

Service types	ID	Descriptions	Patterns
BTY*	1	Bring To Yard - Bring the container from the customer to the yard - Need to arrive at the customer with no container	{D/C/Y}-C-Y-{D/C/Y}
DEL	2	Delivery - Deliver an empty container to the customer - Need to arrive at the customer with an empty container	{L/C/Y}-C-{D/C/Y}
DNR	3	Do Not Return - Remove a full container from the customer to a disposal site - Need to arrive at the customer with no container	{D/C/Y}-C-L-{D/C/Y}
E/R	4	Empty and Return - Pick up a full container, empty it at a disposal site, and return it to the customer - Need to arrive at the customer with no container	{D/C/Y}-C-L-C-{D/C/Y}
FFD*	5	Full From Depot - Pick up a full container from the depot to a disposal site and empty it at the disposal site - Need to arrive at the customer with no container	{D/C/Y}-D(C)-L-{D/C/Y}
REL	6	Relocate - Change the location of the container of the customer - Need to arrive at the customer with no container	{D/C/Y}-C-C’-{D/C/Y}
S/O	7	Switch Out - Exchange container size or container type - Bring an empty container to the customer and exchange it with the full one - Need to arrive at the customer with an empty container	{L/C/Y}-C-L-{D/C/Y}

*: The type which has not been considered in previous studies

D = Depot; L = Disposal site; C, C'= Customer (demand location); Y = Yard

Patterns in Table 1 represent a tractor’s movement for each service type. The bold characters in Patterns represent a fundamental trip, which is a sequence of locations that have to be visited by the tractor to satisfy customer demand with the service type. Locations in braces (e.g., {D/L/C/Y}) mean places that the tractor can visit before and after the fundamental trip. For example, to serve a customer demand with service type BTY, a tractor transports an empty container from the customer location to a yard. Thus, customer-yard (C-Y) is a fundamental trip for the BTY.

Tractors should visit a yard to load/unload an empty container according to the relationship between container status of the tractors and the next customer demand (Figure 1). If a tractor does not have a container and the next customer demand requires an empty container, the tractor should visit a yard to bring the required container (Figure 1(a)). If a tractor has an empty container and the next customer demand does not need a container, the tractor should unload the container at a yard before visiting the next customer (Figure 1(b)). Even if the tractor has an empty container and the next customer demand needs a container, the tractor should visit a yard to bring an appropriate container when the type and size of the empty container on the tractor are different from the required container. If there is no appropriate container at the closest yard from the current location of the tractor, the closest yard cannot be used and another yard should be considered.

Figure 1. Relationship between container status of the tractor and the next customer demand

In addition, tractors should visit customers and facility locations within their respective time windows. The tractors may wait until the opening of the time windows of a location, but they cannot visit them after the time windows. For instance, as shown in Figure 2, a tractor departs at 9:10 from its depot after preparing for 10 minutes. The tractor conducts service for the DNR customer demand and then moves to a yard to bring an empty container for the S/O customer demand. However, the arrival time at customer location with service type S/O is before the earliest time of the customer demand’s time windows. Thus, the tractor should wait for 22 minutes (until 11:30).

Figure 2. Example of a simple route

The problem also considers additional real-world issues and constraints on various container sizes and types, and a lunch break for tractor drivers.

2.2. Some real-world issues

The additional actual issues are described in the sub-sections below.

2.2.1. Unfinished state service issue

Customer demands with service type FFY prefer to be served at the beginning of a route because the service type for the previous day has not been completed. The location of the customer demands are the same as the yard location.

2.2.2. Changing service type issue

Some denoted customer demands with service type E/R may be changed to service type S/O. Service type E/R requires the transportation of a full container from customer location to a disposal site and then returning back the container to customer location after dumping the garbage at the disposal site. However, if the customer demand with service type E/R merely requires a container with the same type and not necessarily the same container, the customer demand may be served as service type S/O, in which the tractor conveys an empty container with required characteristics at customer location and exchanges the two containers. However, not all customers with service type E/R allow the changing of their service type. Moreover, changing service type E/R does not always guarantee better solutions. For example, if service type E/R is changed to service type S/O in a route, the route may visit more locations and may travel longer distances than E/R (Figure 3).

Figure 3. Example of changing service type

2.2.3. Customer-disposal site eligibility

A customer demand may be eligible for multiple disposal sites; as such, the disposal site should be determined for the customer. However, some customer demands use a fixed disposal site. If a route involves a customer demand with a fixed disposal site, the total route time of the route may increase because the fixed disposal site may not be the disposal site with minimum cost.

2.2.4. Multiple demands at a single customer location issue

A customer location may request many waste collection services, that is, several customer demands are made in a single customer location. In the real cases, some customers prefer one tractor driver for their multiple demands due to security concerns and for convenience of management.

The objective of this study is to minimize the number of required tractors and total route time of the tractors to serve all of given customer demands. Our problem can be summarized below.

Objective: Minimize the number of required tractors and total travel time of the tractors Constraints:
§ Facility locations ž A depot, multiple disposal sites, multiple yards ž Time windows of the locations ž Disposal site types ž Various container types and sizes § Tractors ž Different work times ž A lunch break for tractor drivers ž Time windows of the lunch break	§ Customer demands ž Service types ž Disposal site types ž Time windows of customer demands § Additional issues ž Unfinished state service type: FFY ž Changing service type E/R to service type S/O ž Customer-disposal site eligibility ž Multiple demands at a single customer location

3. Benchmark Data

3.1. Descriptions

Fourteen problem instances of type A were derived from a real waste collection company in the U.S. and twenty instances of type B were artificially generated. Table 2 shows the summary of the data sets. The third column presents the number of given customer demands, whereas the fourth and fifth columns are the number of yards and disposal sites, respectively. The problem instances include various constraints such as lunch breaks, different work times of tractors, various container sizes and types, seven customer service types, and time windows. ER_no# involves E/R customer demands that allow service type change, whereas FL_no# includes customer demands with the fixed disposal site constraint. All_no# has both service code changeable E/R customer demands and customer demands with fixed disposal site constraint. ER_no1 in type A data has the same data as Nor_no1 except that the former has E/R customer demands that allow service type change. For type B data, all instances of Nor_no#, ER_no#, FL_no#, and ALL_no# with the same # have the same data set but have different constraints as the names imply.

Table 2. Benchmark data

No.	Data ID	The number of demand	The number of yard	The number of disposal site	Descriptions
A1	Nor_no1	25	2	15	━
A2	Nor_no2	20	2	15
A3	Nor_no3	16	2	15
A4	Nor_no4	6	2	15
A5	Nor_no5	20	2	15
A6	Nor_no6	21	2	14
A7	Nor_no7	30	2	15
A8	Nor_no8	291	1	23
A9	ER_no1	25	2	15	Changing service type E/R
A10	ER_no2	20	2	15
A11	ER_no3	20	2	15
A12	ER_no4	26	2	19
A13	FL_no1	6	2	16	Fixed disposal site
A14	FL_no2	30	2	15
B1	Nor_50	35	3	11	━
B5	Nor_75	58	5	11
B9	Nor_100	85	3	11
B13	Nor_150	132	5	12
B17	Nor_200	185	3	11
B2	ER_50	35	3	11	Changing service type E/R
B6	ER_75	58	5	11
B10	ER_100	85	3	11
B14	ER_150	132	5	12
B18	ER_200	185	3	11
B3	FL_50	35	3	11	Fixed disposal site
B7	FL_75	58	5	11
B11	FL_100	85	3	11
B15	FL_150	132	5	12
B19	FL_200	185	3	11
B4	All_50	35	3	11	Changing service type E/R Fixed disposal site
B8	All_75	58	5	11
B12	All_100	85	3	11
B16	All_150	132	5	12
B20	All_200	185	3	11

3.2. Format

3.2.1. Stops

Stop_ID	Identity index of the stop (= stop ID)
X, Y	Coordinate of the stop
Stop_type	0=depot; 1=customer demand; 2=yard; 3~=disposal site
Current_size	Container size that the stop has
Current_type	Container type that the stop has
Future_size	Container size that the stop will order
Future_type	Container type that the stop will order
Disposal site_type	The eligible disposal site type for the stop
Service_type	Service type of the stop (Refer to Table 1)
Service_time	Loading/unloading time at the stop (second)
Start_time	The earliest time of time windows
End_time	The latest time of time windows
Facility_id	If the stop has a fixed disposal site, the value is stop ID of the disposal site
Flag_er_so	If the value is 1, the stop can change service type from E/R to S/O. It is only for the stops with service type E/R.

** If service type of the stop is BTY, DNR, FFY, REL, Future_size and Future_type are not meaningful because they do not need a new container.

** If service type of the stop is DEL, Current_size and Current_type are not meaningful because it just wants to have a new container.

3.2.2. OD (Origin-Destination)

Origin	Stop ID of origin
Destination	Stop ID of destination
Time	Travel time from origin to destination (second)
Distance	Travel distances from origin to destination (mile)

** For data type B, travel distances are the same with travel times and the travel distances is not meaningful.

3.2.3. Vehicles

Tractor_ID	Identity index of the tractor
Start_time	The beginning time of the tractor' work schedule
End_time	The ending time of the tractor' work schedule
Start_location	Location where the tractor begins (=stop ID of depot)
Lunch_duration	Lunch time (second)
Lunch_early	The earliest time of time windows for lunch break
Lunch_late	The latest time of time windows for lunch break
Flag_reference	If tractors are insufficient to serve all customer demands, the tractor that the value is 1 can be copied and used.

3.2.4. Containers

Location	Location where the containers are stored (=stop ID of yard)
Container_size	Size of the container
Container_type	Type of the container
Available_num	The number of available container at the point of beginning

You may download the zip file here.

References

[1] Kim B-I, Kim S, Sahoo S. Waste collection vehicle routing problem with time windows. Computers and Operations Research 2006; 33:3624-42.

[2] Meulemeester LD, Laporte G, Louveaux FV, Semet F. Optimal sequencing of skip collections and deliveries. Journal of the Operational Research Society 1997; 48:57-64.

[3] Archetti C, Speranza MG. Vehicle routing in the 1-skip collection problem. Journal of the Operational Research Society 2004; 55:717-27.

[4] Bodin L, Mingozzi A, Baldacci R, Ball M. The Rollon-Rolloff Vehicle Routing Problem. Transportation science 2000;34(3):271-88.