A Model for the Implementation of a Two-Shift Municipal Solid Waste and Recyclable Material Collection Plan that Offers Greater Convenience to Residents

ABSTRACT

Separating recyclables from municipal solid waste (MSW) before collection reduces not only the quantity of MSW that needs to be treated but also the depletion of resources. However, the participation of residents is essential for a successful recycling program, and the level of participation usually depends on the degree of convenience associated with accessing recycling collection points. The residential accessing convenience (RAC) of a collection plan is determined by the proximity of its collection points to all residents and its temporal flexibility in response to resident requirements. The degree of proximity to all residents is determined by using a coverage radius that represents the maximum distance residents need to travel to access a recycling point. The temporal flexibility is assessed by the availability of proximal recycling points at times suitable to the lifestyles of all residents concerned. In Taiwan, the MSW collection is implemented at fixed locations and at fixed times. Residents must deposit their garbage directly into the collection vehicle. To facilitate the assignment of collection vehicles and to encourage residents to thoroughly separate their recyclables, in Taiwan MSW and recyclable materials are usually collected at the same time by different vehicles. A heuristic procedure including an integer programming (IP) model and ant colony optimization (ACO) is explored in this study to determine an efficient two-shift collection plan that takes into account RAC factors. The IP model has been developed to determine convenient collection points in each shift on the basis of proximity, and then the ACO algorithm is applied to determine the most effective routing plan of each shift. With the use of a case study involving a city in Taiwan, this study has demonstrated that collection plans generated using the above procedure are superior to current collection plans on the basis of proximity and total collection distance.

IMPLICATIONS

RAC is essential to the achievement of a successful tandem MSW and recyclable material collection plan. This study has proposed an optimization model and a metaheuristic tool to determine the routing plan. Through a real case study, a two-shift routing/scheduling plan is obtained by using the proposed procedure, which is to be superior to the existing collection plan. In short, local authorities that propose to determine a two-shift MSW and recyclable material collection plan should consider the proposed model as a basis of their operations.

INTRODUCTION

The traditional treatments of municipal solid waste (MSW), such as landfill and incineration, have become difficult and expensive because of the increasing scarcity of suitable land and associated environmental concerns. Thus, recycling is regarded as one of the major solutions to the challenge of effective waste management. However, the participation of residents is a crucial factor for the achievement of a successful recycling program. Various researchers1,2 have already acknowledged that the success of MSW recycling schemes is highly dependent on the participation of residents, which is itself dependent on convenient access to a recycling collection point. The degree of residential accessing convenience (RAC) to a recycling point can be determined based on proximity (location) and temporal flexibility (timetable). A permanent recycling point, such as a recycling material broker, can provide a sufficient number of alternative time slots to the residents. By contrast, a temporary recycling point, such as the collection points associated with the tandem collection of MSW and recyclables, does not provide any options in terms of collection times. Therefore, it can be seen that the proximity of collection points and a flexible schedule will affect the level of willingness in residents to participate in the recycling program.

In Taiwan, MSW collection is implemented using fixed locations under fixed time slots, and the residents must deposit their garbage into the collection vehicle. To facilitate the assignment of collection vehicles and to encourage residents to separate recyclables properly, in Taiwan MSW and recyclable materials are usually collected at the same time but in different vehicles. It can be seen from this practice that the major goal of MSW collection programs in Taiwan is to “keep trash off the ground.” Such a policy can avoid accumulations of waste on curbsides, which blight the environment, generate bad odors, and attract flies, especially in a tropic area such as Taiwan. Additionally, MSW collection crews can inspect the MSW being disposed of and directly instruct residents, if necessary, to properly separate their recyclables. However, a single fixed collection time is not always convenient to all residents and may require many of them to dispose of their garbage at more distant collection points at a less inconvenient time. Subsequently, such a process of waste collection obviously does not encourage residents to participate fully in any recycling program. Fortunately, this situation has been addressed by the implementation of a night-and-day shift collection schedule, which is designed to improve the RAC. However, the absence of an existing procedure with which to determine the level of RAC associated with a collection plan for recycling makes the identification of superior routing plans difficult.

RAC is mainly determined by the proximity of the collection point and the time of collection. For the determination of recycling collection points, proximity is generally considered and evaluated based on the distance from a residence to the nearest collection point. Several researchers have already proposed alternative approaches for addressing problems concerning proximity. In location studies of emergency facilities, Toregas and ReVelle3 have proposed a coverage distance of a facility and they have developed a mathematical model to find the minimal number of fire stations required to cover the target population. In their definition, the residents within the coverage distance of a facility are regarded as being serviced. Kao and Lin,4 from the viewpoint of a resident, suggest using an acceptable walking distance to evaluate the service level of MSW collection. They have implemented four different walking distances (between 50 and 100 m) using the shortest service location model to assess how each of the four distances influences the number of required collection points. Lin and Chen5 have also proposed a proximity indicator on the basis of coverage and walking distances to determine the locations of permanent recycling depots. In general, the number of required facilities increases as the coverage or walking distance decreases no matter which proximity definition is used. Although proximity is essential for planning a permanent recycling point, it should not be the only factor to consider for planning a temporary one because not all residents are able to handle recyclable materials at the same collection time. The other major factor, temporal flexibility (collection times), should also be considered in the determination of temporary recycling collection points.

In addressing temporal problems, methods with time-window constraints, in which each customer is assigned an acceptable period to be serviced, have been widely explored. For example, Shih and Lin6 applied time-window constraints to develop a routing plan for the collection of infectious waste from several hospitals. Numerous other studies7–9 have also applied a similar approach for vehicle routing problems. However, the application of time-window constraints to a mathematical model designed to evaluate the temporal flexibility of MSW and recyclable material in tandem collection problems is impractical because of the computational effort required to solve even a small-scale problem, as well as the fact that the preferred collection times usually differ among neighboring residents. In reality, only two broad collection time options exist; that is, day or night time. For residences with someone at home most of the day, collection during the daytime is preferred, whereas those working during the day would prefer to dispose of their garbage and recyclable material in the evening. Therefore, a two-shift, day and night collection schedule is proposed because of the increased flexibility that it provides for servicing residences. However, it needs to be stated that because of budgetary constraints, not all collection points can be serviced in both shifts. As a response to this budgetary limitation, this study offers a procedure with which to determine more convenient collection points in each shift on the basis of RAC factors.

Mathematical models such as integer programming (IP) and mixed integer programming (MIP) models are widely applied for various waste management problems, such as in the determination of the route of waste collection services and the locations of recycling depots. In MIP models,10–18 the objective function and constraints incorporated in each differ from model to model and are dependent on the purpose of the model. Badran and El-Haggar19 have summarized some optimization methods in the field of MSW management. In this study, an IP model is developed to determine the collection shift of preannounced collection points.

Once the collection points of a shift have been identified, the routing plan has to be determined. MIP models (e.g., traveling salesman problem models) can also be applied to optimize the routing of such services and they provide the added advantage of ensuring that the obtained solution is the optimal one. However, the length of time required to solve a large MIP model is impractical. Consequently, most heuristic method studies have been devoted to find optimal service routes, such as genetic algorithm,20 tabu search,21 and ant colony optimization (ACO).22 Among these heuristic methods, the ACO algorithm has been widely adopted in studies concerned with traveling salesmen problems because it is capable of finding sound solutions within an acceptable time frame.23,24 Briefly, an ACO is a heuristic algorithm that simulates the behaviors of ants in their search for food. In this study, an ACO is implemented to determine the schedule of a day and night (two-shift) waste collection service.

THE ANALYTICAL PROCESS

Figure 1 presents the procedure to determine a two-shift MSW collection routing plan. First, the data relating to MSW collection points, population distribution, and MSW generation are collected. Then, the regions eligible for a two-shift collection schedule and the coverage radius of each collection point are delineated. Alternative accessible collection points (AACPs) are identified based on the coverage radius. An IP model is then implemented to classify the collection points into day and night shifts. Finally, the collection points of each shift form a typical routing problem that is solved using an ACO algorithm to determine the two-shift MSW collection routing plan. The planner can also adjust the parameters, including the regions for two shifts and the coverage radius, to reconsider other alternative routing plans if desired. Each step of the procedure is described in detail below.

Figure 1. The proposed procedure for developing a two-shift MSW and recycling collection plan.

Regions in Need of a Two-Shift Collection Routing Plan

In contrast to a highly populated region with varied work schedules for different residents that can economically justify a two-shift collection schedule, other regions may not require the same or be cost-effective enough for its provision. For instance, an area with mostly office and commercial buildings may be empty after office hours, and a rural area is not cost-effective enough to justify the implementation of a two-shift MSW collection schedule because its residents are sparsely distributed. Therefore, the suitability of an area to a two-shift collection plan should be evaluated carefully. Generally, there would be no need to implement a two-shift collection plan for commercial and rural areas.

Coverage Radius and AACPs

These recycling collection points in the one-shift collection plan are supposed to be conveniently located for the targeted residents. In the two-shift collection plan, residents unable to access their nearest collection point at the scheduled collection time can dispose of their recyclables at one of the alternative collection points in the other shift. The proximity of an alternative collection point can be evaluated by measuring the distance from the nearest collection point to a potential alternative recycling point. In this study, the coverage radius represents the maximum distance that residents have to walk from the nearest collection point to an alternative collection point. An AACP for a collection point is one for which the distance is less than the coverage radius. Figure 2 illustrates the relationship between a collection point (point 1), coverage radius (R), and the AACPs of the collection point (i.e., points 3 and 4). Residents can access the nearest collection point or its AACPs. The value of R is the indicator to assess the proximity of the AACPs. A numerically small value for R indicates the collection point and its AACPs are close, which implies the expected distances for nearby residents to access the AACPs are short and vice versa.

Figure 2. AACPs.

The Proposed IP Model

An IP model is established to identify the minimal number of collection points required within a predefined coverage radius and areas for a two-shift collection schedule, as formulated below.

(1)

subject to

(2)

(3)

where i and k are the indices of the collection points, M is the total number of collection points, j is the index of a shift, T is the total number of shifts, x _i,j is a binary variable for which the value is equal to 1 if collection point i is part of shift j, and N _i is the set of the AACPs of collection point i.

Equation 1 is the objective function of the proposed IP model that is used to minimize the total sum of the respective number of selected collection points in each shift. Equation 2 ensures that a collection point itself or one of its AACPs is selected in each shift. Equation 3 ensures that all collection points are visited at least once among all shifts. The result after applying the proposed IP model (i.e., the collection points selected for each shift) is analyzed in the next step to find the routing plan of each shift.

An ACO Algorithm-Based Routing Plan

In this stage, a collection routing schedule for each shift is determined using an ACO algorithm. As mentioned previously, the ACO is an algorithm that models the behavior of ants in search of the shortest path from their formicary to the food source.22 In the initial stage, ants move out from their formicary and take random paths to the food source. They also lay down pheromones during their movements to attract other ants to follow their pioneer paths. Because the speed at which ants move is consistent, after a while the shorter paths (from formicary to food source) will accumulate more pheromones than the longer ones. Moreover, because pheromones decay with time, fewer and fewer ants are attracted to follow a path with a lower pheromone concentration (a long distance path), and this also causes a further decrease of pheromones on the longer paths. In short, over time, the ants will consistently follow the shortest path from the formicary to a food source.

The procedure to implement the ACO algorithm is briefly described below, along with a detailed reference to Dorigo and Caro.22 Artificial ants in the ACO algorithm simulate the actions that real ants display in their search for food. In the preliminary application of the ACO algorithm to a collection routing problem, each artificial ant starts at a random collection point and keeps moving to an unvisited collection point according to a probability rule until all points are traversed. The probability rule confines artificial ants to choosing the next point with a higher pheromone level and shorter distance. Additional deposits of pheromones are made after the ant finishes the complete tour or crosses any edge.

CASE STUDY

Study Area

To demonstrate the applicability of the proposed IP model and ACO algorithm, a case study is conducted. Taichung City is the third largest metropolis in Taiwan. Its area is approximately 163 km² with more than 1 million inhabitants. Nantun District is one of its eight major administrative districts. Figure 3 shows the locations of the Nantun District in Taichung City and the city in relationship to the rest of Taiwan. The district itself has a population of approximately 150,000 that generated an average MSW of 141 t/day in 2008.20 In total there are 1289 MSW collection points in the district. All of these points are serviced during the day, whereas 136 points are also serviced during a night shift. Residents can dispose of their garbage and recyclable materials in both shifts. Figure 4 illustrates the distribution of the collection points in the district. Open circles represent day-shift only collection points, and solid circles represent those serviced at both shifts.

Figure 3. Location of the studied case in Taichung City, Taiwan.

Figure 4. The MSW and recycling in tandem collection points of Nantun District.

The Areas in Which a Two-Shift Collection Schedule Operates

In accordance with the procedure shown in Figure 1, the required data are collected first. To identify appropriate areas in which to implement a two-shift collection schedule, the population distribution of each area is established. Figure 5a represents the population density of Nantun District, which is determined from census data and the geographical information map layers of household address locations. Figure 5b illustrates five groups, A to E, which are ranked in order of descending population densities. For example, group A is the highest populated group of subareas in Nantun District with 50% of the total population, group B has 13% of the total population of the district, and so on. Five scenarios are analyzed in this study. Table 1 lists the area groups included in each scenario, indexed from I to V. Each scenario includes different subareas for which a two-shift collection schedule is being considered.

Table 1. Populations of subarea groups in Nantun District

Scenario Index	Subarea Groups	Percentage of Total Population (%)	Number of Collection Points	Area (m^2)
I	A	50	615	195,811
II	A, B	63	792	414,825
III	A, B, C	75	1091	744,507
IV	A, B, C, D	88	1176	1,338,863
V	A, B, C, D, E	100	1289	58,042,577

Figure 5. (a) The population density distribution of Nantun District, and (b) the subareas classified by percentage of population from high to low population density.

Coverage Radius and Respective AACPs

Kao and Lin4 have suggested that for residents the appropriate walking distance to a collection point is less than 100 m. For a comparison using the coverage radius of an existing two-shift collection plan, an extraordinary long distance of 500 m is also evaluated. Thereby, the coverage radii analyzed in this study are 50, 75, 100, and 500 m. The AACPs under different coverage radii are determined and the proposed IP model is applied to generate the collection points for each shift of a two-shift collection routing plan for each scenario.

Determination of ACO Parameters

A two-stage test was conducted to ensure the applicability of ACO in the identification of the optimal solution and to determine the parameters for applying the ACO algorithm. The ACO tool used in this study is ACOTSP.25 In the first stage, several hypothetical cases with 30, 40, 50, and 60 collection points were randomly created and they were resolved using CPLEX26 (an optimization tool) and ACOTSP separately. The test results indicate that the best solution of the five ACOTSP test runs is identical to the solution gained from CPLEX for all tested cases, which establishes the superiority of ACO algorithms in the identification of the optimal routes. In the second stage, the ACO parameters for the case study were determined, including the number of ants (m), the pheromone decay coefficient (α), and the relative importance of exploitation versus exploration on the movements of the ants (q ₀). Table 2 lists the tested values of the parameters. Each combination of parameter values (e.g., 2 for m, 0.1 for α, and the 0.85 for q ₀) is tested five times in this case study using ACOTSP. For comparison, the average performance of a parameter value is to calculate all combinations with the identical parameter value by using the following equation:

Table 2. The results for testing ACO parameters

Parameter Value	P (%)
m
2	99.49
3	99.76
5	99.75
10	99.64
15	99.63
α
0.1	99.65
0.3	99.66
0.5	99.66
0.9	99.65
q 0
0.85	99.60
0.9	99.66
0.95	99.72
0.99	99.70
1	99.58

(4)

where P is the average performance of a parameter value, C is the number of combinations with the identical parameter value, D _t is the average solution of the tth combination for the parameter value, and D* is the global optimal solution of all of the tested runs. For instance, the average performance percentage of α= 0.3 is 99.66%, where m and q ₀ of combinations of this group varies from 2 to 15 and 0.85 to 1, respectively. As listed in Table 2, the minimal and maximal values of P are 99.49% for m = 2 and 99.76% for m = 3. This study found ACO to be highly effective in identifying the best solution to the problem set. The numerals underlined in Table 2 are the parameter values used in the following scenario analysis.

RESULTS AND DISCUSSION

The scenarios analyzed with different coverage radii are denoted by Sy.x, where y is the scenario index, as indicated in Figure 5b and Table 1, and x represents the value of a coverage radius, as listed in Table 3. The coverage radius implies the maximal distance for a resident to walk to access the AACP. The current collection plan is denoted by R.now. In addition, a scenario denoted by R.aco that optimizes the routing plan in each shift of R.now by the ACO algorithm is also implemented.

Table 3. The results for analyzed scenarios

Scenario ID	Number of Collection Points by Day Shift (number of points)	Number of Collection Points by Night Shift (number of points)	Total Collection Distance of Two Shifts (m)
R.now	1,289	136	178,431
R.aco	1,289	136	131,280
S.I.50	1,097	394	133,676
S.I.75	1,042	295	126,840
S.I.100	1,034	264	123,027
S.I.500	1,244	36	112,927
S.II.50	1,041	514	140,827
S.II.75	977	397	133,181
S.II.100	981	343	129,169
S.II.500	1,231	56	115,139
S.III.50	948	714	158,840
S.III.75	878	546	148,440
S.III.100	885	463	143,146
S.III.500	1,213	76	121,235
S.IV.50	934	782	164,841
S.IV.75	857	595	153,532
S.IV.100	861	508	148,303
S.IV.500	1,186	103	122,909
S.V.50	844	898	175,996
S.V.75	756	697	163,689
S.V.100	765	604	155,580
S.V.500	1,179	110	127,389

Table 3 summarizes the results obtained for all of the analyzed scenarios using the proposed method, including the number of collection points in day and night shifts and the total collection distance of each scenario. Figure 6 compares the results for total collection distances versus coverage radii. For comparison, the values of the coverage radius are expressed by their logarithmic values. Obviously, the total collection distance decreases as the coverage radius increases, or as the number of subregions with a two-shift collection schedule decreases. As shown in this figure, the influence of a coverage radius on the total collection distance is less sensitive as it increases because for any given collection point it is easier to find AACPs with a large coverage radius than those with a small one.

Figure 6. The results of the analyzed scenarios.

Figure 6 also compares the results with the current collection plan, R.now, with its enhanced routing plan, R.aco. The coverage radius (786 m) of these two plans is identical, which can be computed by a max-minimal procedure; that is, by calculating the distance between each collection point of one shift and its nearest AACP in the other shift and then by finding the maximum among these distances. The R.now and R.aco plans implement the two-shift collection schedule for the entire area, as for scenario V. To improve the readability of Figure 6, two horizontal lines and one vertical line have been added to highlight the total collection distances and coverage radii of both plans. The gap between the two horizontal lines indicates the improvement in the total collection distance after modifying the routing plan of R.now to R.aco. The modification has reduced the original total collection distance by 26% through the use of the ACO algorithm. In addition, the horizontal lines also provide references for the decision-makers during the evaluation of a new routing plan with various coverage radii, regions with two-shift collection schedules, and collection distances. The vertical line in Figure 6 highlights the coverage radius of 786 m for R.now and R.aco, which is greater than the maximal coverage radius of 500 m for S.# scenarios. This also means all of the routing plans of S.# scenarios offer the residents better proximity than R.now under two-shift collection. In addition, the total collection distances of all of the scenarios are less than that for R.now, which indicates these scenarios can be alternatives to replace R.now, the current collection plan. If the collection points in each shift remain unchanged, R.aco is recommended. Alternatively, the collection authority or manager may evaluate the coverage radius, the total collection distance, and the areas eligible for a two-shift collection schedule to find a preferred alternative. For example, if the decision-maker desires to improve the convenience of resident access to recycling as much as possible and the total collection distance of the alternative is less than that of the current collection plan, then S.V.50 is recommended. If a total collection distance of less than S.V.50 is desired, S.IV.50 or S.V.75 is the recommended alternative. S.IV.50 has the most convenient coverage radius (50 m) and offers 88% of the population convenient access to a two-shift collection point schedule, whereas S.V.75 offers a moderately convenient walking distance of 75 m and the entire area can be covered by a two-shift collection point schedule.

CONCLUSIONS

In this study, a heuristic procedure has been proposed to evaluate the RAC level for recyclable material collection points serviced by a two-shift collection plan. The implementation of a two-shift collection schedule and coverage radius of collection points can greatly affect the RAC level to these services. The proposed IP model is used to classify the collection points into two shifts and to satisfy the requirements of AACPs in two-shift collection areas. The ACO is capable of efficiently determining the routing plans. The case study presented demonstrates how the proposed method can be applied to a real problem. On the basis of various coverage radii and areas for two-shift collections, different routing plans were analyzed. The results are expected to assist the local authority in determining a proper two-shift collection plan. In short, the proposed methodology has been demonstrated to be flexible and efficient in the analyses of various scenarios and for the implementation of an improved routing plan.

ACKNOWLEDGMENTS

The authors thank the National Science Council of Taiwan of the Republic of China for financially supporting this research under contract no. NSC 98-2211-E-324-001-MY2. The authors also express special thanks to Dr. Thomas Stützle for his development of ACOTSP and assistance in helping the authors use the program in this study.