WASTE COLLECTION VEHICLE ROUTING PROBLEMCONSIDERING SIMILARITY PATTERNOFTRASHCAN ANDGARBAGE UNLOADING
SOMAYEH FOOLADI1, HAMED FAZLOLLAHTABAR2*
1Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran
2* Faculty of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran
ABSTRACT
Rapid urbanization poses a serious environmental threat of solid waste management (SWM) and reverse supply chain. In this paper, a mathematical model is proposed in order to reduce the cost of waste collection and transporting for recycling process. First a mixed-integer nonlinear programming model is provided including a waste collection routing problem and the following processes after garbage unloading, so that, there is a balance between the distance between trashcans, and the similarity of the trashcans in terms of the types of waste which is in the trashcans, in order to select the optimal route for each garbage transport vehicles. For this purpose, a similarity pattern is designed. By following the similarity pattern for route selection, recovery rate of waste will be increased being shown in the model. Then, we solved the model by using LINGO 0.9 software and analyze the output results of solved model.
KEYWORDS: Reverse supply chain; Recycling; Vehicle Routing Problem; Mathematical modeling.
1. INTRODUCTION
In general a waste collection system involves the collection and transportation of solid waste to disposal facilities. This essential service is receiving increasing attention from many researchers due to its impact on the public concern for the environment and population growth, especially in urban areas. Because this service involves a very high operational cost, researchers are trying to reduce the cost by improving the routing of waste collection vehicles, finding the most suitable location of disposal facilities and the location of collection waste bins as well as minimizing the number of vehicles used.
We address a waste collection VRP with consideration of similarity of the trashcans in terms of the types of waste which is in the trashcans and the following processes after garbage unloading. The waste collection problem consists of routing vehicles to collect customers waste while minimizing travel cost. This problem is known as the Waste Collection Vehicle Routing Problem (WCVRP). WCVRP differs from the traditional VRP by that the waste collecting vehicles must empty their load at disposal sites. The vehicles must be empty when returning to the depot.
The structure of the present paper is the following: Section 2 discusses the literature which has previously studied WCVRP or other similar and relevant problems. The WCVRP is then formulated with consideration of similarity of the trashcans in terms of the types of waste which is in the trashcans and the following processes after garbage unloading and modeled in section 3. The subsequent section 4 discusses the results obtained from LINGO software. Finally, our concluding remarks are given in section 5.
2. LITERATURE REVIEW
Weigel and Cao (1999) presented a case study of application of VRPTW algorithms for Sears home delivery problem and technician dispatching problem. They follow a cluster-first-route-second method and discuss three main routines: origin-destination (OD) matrix construction, route assignment, and route improvement routines. They apply a shortest-path algorithm to a geographic information system (GIS) to obtain OD matrix, i.e., travel time between any two stops. For the route assignment routine (clustering), an algorithm called multiple-insertion, which is similar to the parallel insertion algorithm of Potvin and Rousseau (1993) was developed. As an objective function, the weighted combination of travel time, wait time, and time window violation is used. They propose an intra-route improvement algorithm and a neighborhood inter-route improvement algorithm that improves the solution quality by transferring and exchanging stops between two routes. In order to enhance the improvement performance, tabu search is applied to the improvement algorithms.
Chang and Wang (1997) used a fuzzy goal MIP model for vehicle routing and scheduling in a solid waste collection system. Shih and Lin (1999) reported an approach to resolve the collection, vehicle scheduling, and routing problems for infectious waste management by using DP and IP methods for the periodic vehicle routing problem in cost only.
Tung and Pinnoi(2000) modified Solomon’s insertion algorithm and apply it to a waste collection problem in Hanoi, Vietnam. In addition to the considerations of the standard VRPTW, they consider a landfill operation that is the dumping of the collected garbage at the landfill, and inter-arrival time constraints between two consecutive visits at a stop. They incorporate the landfill operation by assuming that a vehicle starts a new route from the depot after landfill. Or-opt and 2-opt algorithms are adopted to improve the solution quality.
Angelelli and Speranza(2002) addressed the periodic vehicle routing problem with intermediate facilities (PVRP–IF). When a vehicle visits an intermediate facility, its capacity will be renewed. They propose a tabu search algorithm with four move operators: move a customer in the same day, change the visiting schedule, redistribution of customers, and simplification of intersection. Initial solutions are built by choosing a visiting schedule randomly to each customer and constructing vehicle routes on each day using iterative insertion procedure. Angelelli and Speranza(2002) applied their algorithm for estimating the operating costs of different waste-collection systems: traditional system with three-man crew, side-loader system, and side-loader system with demountable body. The differentiator between their problem and ours is the time windows of the stops and the facilities. Our problem requires explicit consideration of time windows.
Eisenstein and Iyer(1997) used a Markov decision process to model the residential waste collection problem in the city of Chicago. They model the weight and time required to collect waste from a city block as normally distributed random variables. Action in their Markov decision process is the choice of route that visits the dumpsite once or twice. Teixeira et al. (2004) applied a heuristic approach for a PVRP for the separate collection of three types of waste: glass, paper, and plastic/metal. The approach has three phases: define a zone for each vehicle, define waste type to collect on each day, and select the sites to visit and sequence them. Mourao and Almeida (2000) modeled the residential garbage collection problem in a quarter of Lisbon, Portugal as a capacitated arc routing problem, and propose two lower-bounding methods and a route-first, cluster-second heuristic method. Chang et al. (1997) discussed how combining GIS functions with analytical models can help analyzing alternative solid waste collection strategies for a metropolitan city in Taiwan.
A real life waste collection vehicle routing problem with time windows assuming multiple disposal trips and drivers’ lunch breaks was addressed by Kim et al. (2006). They assumed a weekly predetermined schedule and presented a route construction algorithm that was an extension of Solomon’s insertion algorithm (Solomon, 1987) and address a real life waste collection VRPTW with consideration of multiple disposal trips and drivers' lunch breaks. Ombuki-Berman et al. (2007) addressed the same problem by using a multi-objective genetic algorithm on a set of benchmark data from real-world problems obtained by Kim et al. (2006).
Benjamin and Beasley (2010) improved the results when minimizing travel distance using a tabu search and variable neighborhood search and a combination of these. A very similar problem, with only one disposal site, is addressed by Tung andPinnoi(2000), where they modify Solomon's insertion algorithm and apply it to a waste collection problem in Hanoi, Vietnam. Nuortio et al. (2006) presented a guided variable neighborhood thresholdingmetaheuristic for the problem of optimizing the vehicle routes and schedules for collecting municipal solid waste in Eastern Finland. Solid waste collection is furthermore considered by Li et al. (2008) for the City of Porto Alegre, Brazil. Their problem consists of designing daily truck schedules over a set of previously defined collection trips, on which the trucks collect solid waste in fixed routes and empty loads in one of several operational recycling facilities in the system. They use a heuristic approach to solve the problem. Buhrkal et al. (2012) studied the Waste Collection Vehicle Routing Problem with Time Window which is concerned with finding cost optimal routes for garbage trucks such that all garbage bins are emptied and the waste is driven to disposal sites while respecting customer time windows and ensuring that drivers are given the breaks that the law requires. they propose an adaptive large neighborhood search algorithm for solving the problem and illustrate the usefulness of the algorithm by showing that the algorithm can improve the objective of a set of instances from the literature as well as for instances provided by a Danish garbage collection company.
3. PROBLEM FORMULATION
In this section, A mixed-integer nonlinear programming model is provided including a waste collection vehicle routing problem (WCVRP) and the following processes after garbage unloading, so that, there is a balance between the distance between trashcans, and the similarity of the trashcans in terms of the types of waste which is in the trashcans, in order to select the optimal route for each garbage transport vehicles. For this purpose, a similarity pattern is designed. Fig. 1 presents a general diagram of our model.
FIG. 1.GENERAL DIAGRAM OF THE PROBLEM.
The problem is defined on a graph where the set of nodes N={1,…,n} consists of a depot and a disposal site which are consider as one node {1}?N, n-1 customers {2,…,n}?N and the set of arcs is G={(i,j)|i,j?N,i?j}. Let M be the set of vehicles in VRP network and let K be the set of types of waste and the types of centers that we will transport the classified waste after unloading them. It is assumed that all vehicles in VRP network can have different capacity O_m. The objective of the WCVRP is to find a set of routes for the vehicles, minimizing total travel cost and satisfying vehicle capacity, such that all customers are visited exactly once and rout of each vehicles, is chosen so that the similar trashcan be placed in one rout. For this purpose, similar pattern was designed based on the probability of presence of the type of waste in trashcan P_ki, and dissimilarity is shown as a penalty in the objective function.
The problem can then be modeled using three types of variables: r_ijm is one if and only if vehicle m?M uses arc (i,j)?G, VC_k represents the total volume of transmitted kth type of waste from collection site to kth center, U_k represents the number of trips required to transport VC_k and x_k represents the number of vehicles required to satisfy the x_k. A mathematical model for the present WCVRP is:
The objective function minimizes the travel cost under the restriction of the following constraints. All m vehicles must leave (1) and return (2) to the depot. Constraint (3) ensures that all customers are serviced exactly once. Inflow and outflow must be equal except for the depot nodes (4). Vehicle capacity is given by (5) and (6). Constraints (7) and (8) are for the amount of binary variables. How to calculate the parameters of the similarity and proximity of trashcans (z_ijand d_ij) is shown in the Constraints (9), (10), (11) and (12). Constraint (13) shows the balance between similarity and proximity of trashcans for routing. Calculation of VC_k is shown in constraints (14) and (15).these two constraints shows that in contrast of disposal volume (VC_1), the rate of recovery has a direct relationship with following the similarity pattern. Constraints (16) and (17) calculate U_kand x_k, respectively. Constraint (18) shows that P_ki is a possibility. Finally (19) imposes non-negativity and binary variables.
4. COMPUTATIONAL RESULTS
In this section, we solved the model by using LINGO 0.9 software and analyze the output results of solved model. Table 1 and Table 2 show the results of solved model for large size in which the value of index is: M=7, K=7 and n=11. Objective function value is equal to 915086 which have obtained after 37 minutes.
TABLE 1.RESULTS OF SOLVED MODEL BY LINGO 9.0
TABLE 2.RESULTS OF SOLVED MODEL BY LINGO 9.0
k VC_k U_k x_k
1 14.2 7 7
2 11.3 5 5
3 3.666667 4 4
4 0.8666667 0 0
5 1.266667 0 0
6 0.4 0 0
7 0.8 1 1
In this example, we assume that there are 10 trashcans and one depot in an area. The presence of 7 types of waste in the trashcan is clear .Also there are 7 different vehicles for collecting wastes. These vehicles should service the trashcans so that where possible, similar trashcans have serviced by one vehicle to the quality of wastes not diminished because of waste combination. As a result, rate of recovery will have increased. According to output results in table 1, Let us consider the nonzero decision variable corresponding to the third vehicle: R(1, 3, 3), R(3, 6, 3), R(6, 8, 3), R(8, 7, 3) and R(7, 1, 3). These variables indicates that the third vehicle began to move from node 1 (depot) to node 3 in order to service it. And then move to node 6, node 8, node 7, respectively and finally, it returns to node 1 (depot) after giving service to those nodes. Now look at Table 2, Total volume of recyclable waste that should be transferred to recycle center is equal to 3.66 (VC_3=3.66) and for transferring this volume we need 4 trips (U_3=4) and 4 vehicles (x_3=4). Finally we have the minimal cost for maximal volume of recycle. We can see the route of third vehicle in these VRP network in Fig. 2.
FIG. 2. ROUTE OF 3th VEHICLE in VRP NETWORK
5. CONCLUSIONS
In this paper, a mixed-integer nonlinear programming model has been provided including a waste collection vehicle routing problem (WCVRP) and the following processes after garbage unloading. A mathematical modeling formulation is given for the general WCVRP with consideration of similarity of the trashcans in terms of the types of waste which is in the trashcans in order to maintain the quality of wastes and to increase the recovery rate and to decrease the disposal rate. The vehicles should service the trashcans so that where possible, similar trashcans have serviced by one vehicle to the quality of wastes not diminished because of waste combination. Finally the WCVRP has been solved using the LINGO software and the output results, has been analyzed.
REFERENCES
Angelelli, E. &Speranza, MG. (2002). The application of a vehicle routing model to a waste-collection problem: two case studies. Journal of the Operational Research Society, 53, 944–952.
Angelelli, E. &Speranza, MG. (2002).The periodic vehicle routing problem with intermediate facilities. European Journal of Operational Research, Vol. 137, 233–247.
Benjamin, AM. & Beasley, JE. (2010). Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities. Computers & Operations Research, Vol. 37, 2270-2280.
Buhrkal, K., Larsen, A.&Ropke, S. (2012). The Waste Collection Vehicle Routing Problem with Time Windows in a City Logistics Context.Procedia-Social and Behavioral Sciences, Vol. 39, 241-254.
Chang, N.B.& Wang, S.F. (1997).A fuzzy goal programming approach for the optimal planning of metropolitan solid waste management systems. Eur. J. Oper. Res. Vol. 99, 287–303.
Chang, N-B., Lu, HY.&Wei, YL.(1997). GIS technology for vehicle routing and scheduling in solid waste collection systems. Journal of Environmental Engineering, Vol. 123, 901–933.
Eisenstein, DD.Iyer, AV. (1997). Garbage collection in Chicago: a dynamic scheduling model. Management Science, Vol.43, Issue 7, 922–933.
Kim,BI., Kim, S. &Sahoo, S. (2006). Waste collection vehicle routing problem with time windows. Computers & Operations Research, Vol. 33, 3624–3642.
Li, J-Q.,Borenstein, D. &Mirchandani, PB.(2008). Truck scheduling for solid waste collection in the city of Porto Alegre, Brazil. Omega, Vol. 36, 1133-1149.
Mourao, MC. &Almeida, MT. (2000).Lower-bounding and heuristic methods for a refuse collection vehicle routing problem. European Journal of Operational Research, Vol. 121, 420–434.
Nuortio, T., Kyt?joki, J., Niska, H. &Br?ysy, O. (2006).Improved route planning and scheduling of waste collection and transport. Expert Systems with Applications, Vol.30, 223-232.
Ombuki-Berman, BM., Runka, A. & Hanshar, FT. (2007).Waste collection vehicle routing problem with time windows using multiobjective genetic algorithms. Brock University; Technical Report # CS-07-04, 91-97.
Potvin, JY. & Rousseau, JM. (1993). A parallel route building algorithm for the vehicle routing and scheduling problem with time windows. European Journal of Operations Research, Vol. 66, 331–340.
Shih, L.& Lin, Y. (1999).Optimal routing for infectious waste collection. J. Environ. Eng. Vol. 125, 479–484.
Teixeira, J., Antunes, AP. & Sousa, JP.(2004). Recyclable waste collection planning—a case study. European Journal of Operational Research, Vol. 158, 543–554.
Tung, DV. &Pinnoi, A. (2000).Vehicle routing-scheduling for waste collection in Hanoi. European Journal of Operational Research, Vol. 125, 449–468.
Weigel, D. & Cao B. (1999).Applying GIS and OR techniques to solve Sears technician-dispatching and home-delivery problems. Interfaces, Vol. 29, Issue 1, 112–130.