
Journal of Mathematics and Statistics
Year: 2009  Volume: 5  Issue: 3  Page No.: 199  205


Ant Colony Optimization for Solving Solid Waste Collection Scheduling Problems

Z. Ismail
and
S.L. Loh

Abstract: Problem statement: Southern Waste Management environment (SWM environment) is a company responsible for the collection and disposal of solid waste for the city of Johor Bahru, a city with over one million populations. The company is implementing an integrated solid waste management system where it involved in the optimization of resources to ensure the effectiveness of its services. Formulating this real life problem into vehicle routing problem with stochastic demand model and using some designed algorithms to minimize operation cost of solid waste management. Approach: The implementation of Ant Colony Optimization (ACO) for solving solid waste collection problem as a VRPSD model was described. A set of data modified from the well known 50 customers problems were used to find the route such that the expected traveling cost was minimized. The total cost was minimized by adopting a preventive restocking policy which was trading off the extra cost of returning to depot after a stockout with the cost of returning depot for restocking before a stockout actually occurs. For comparison purposes, Simulated Annealing (SA) was used to generate the solution under the same condition. Results: For the problem size with 12 customers with vehicle capacity 10 units, both algorithms obtained the same best cost which is 69.4358 units. But the percentage deviations of averages from the associated best cost are 0.1322 and 0.7064 for ACS and SA. The results indicated that for all demand ranges, proposed ACO algorithm showed better performance than SA algorithm. Conclusion: SA was able to obtain good solutions for small ranges especially small size of problem. For ACS, it is always provide good results for all tested ranges and problems sizes of the tested problem. 

• 
Handling household waste, commercial and nontoxic industrial
waste: 
• 
Waste containment to collection 
• 
Transfer station to landfills 
• 
Recycling and waste to energy 
Problem: The solid waste collection problem is formulated into VRPSD model where a street or some nearby streets which had been group together as one unit is represented by the nodes (customers’ locations). The customers’ locations are in form of Cartesian coordinate where each point appears uniquely in a plane through two numbers, called xcoordinate and ycoordinate while demands of customers which are stochastic are recorded in a range form.
This study shows the way of a real life problem being formulated into Vehicle Routing Problem with Stochastic Demand Model and solved by the designed algorithm. Since there is no open source data for VRPSD problem, thus this case study adopted a set of data modified from the well known 50customer problem in Eilon et al.^{[7]} as in Table 1.
The customers’ locations are shown on a plane by designed program as in Fig. 1 to show the positions of all customers graphically.
The problem described above can be modeled as a Vehicle Routing Problem with
Stochastic Demand (VRPSD) as the amount of solid waste is stochastic and may
be presented in a complete graph^{[7]} and Secomandi,^{[9,10]}.
Let the set of nodes be {0, 1,…,n}.

Fig. 1: 
Positions of customers’ locations 
Node 0 denoting the depot node and V = {1,…,n} is a set of customer locations.
Distances between nodes are assumed to be symmetric and it satisfies the triangle
inequality. Customers’ demands are stochastic variables, ξ_{i }=
1, 2,...,n independently distributed with known distribution. It follows a discrete
probability distribution with v possible values, ξ^{1}, ξ^{2},…,ξ^{v}
denoted by p_{i,k} = Prob (ξ_{I} = ξ^{k} ). Actual
demand is only known when the vehicle arrives at the customer location.
Table 1: 
Data of case study 

After the vehicle completed service at customer w, suppose the vehicle has
remaining load q and let f_{w}(q) denotes the expected cost from node
w onward until the n customer and the way back to depot. With this notation,
the expected cost of the a priori tour is f_{0}(Q). The dynamic programming
recursion is shown as follows^{[11]}:
Where:
and
with the boundary condition:
Equation 2 and 3 represents the cost of
proceeding directly to the next customer and the cost of the restocking action
respectively.
Assume that one single vehicle with fixed capacity Q departs from the depot node to delivery goods at different customer locations according to their demands and at the same time, it has to minimize the total expected distance traveled. After all the demands have been served, the vehicle returns to the depot.
The vehicle visits the customers according to the sequence in the given a priori tour. It has to choose depending on the customer’s demand either proceed directly to the next customer or return to depot for restocking. Thus, the goal of this study is find a vehicle route and a routing policy (threshold) at each node in order to minimize the total expected cost^{[1]}.
MATERIALS AND METHODS
The ant colony system algorithm for solving VRPSD: Ant System was efficient
in discovering good or optimal solutions for small problems with nodes up to
30. But for larger problems, it requires unreasonable time to find such a good
result. Thus, Dorigo and Gambardella^{[3,4] }and Bianchi et al.^{[1]}
devised three main changes in Ant System to improve its performance which led
to the existence of ant colony system.

Fig. 2: 
Ant colony system’s algorithm 
Ant Colony System is different from Ant System in three main aspects. Firstly, state transition rule gives a direct way to balance between exploration of new edges and exploitation of a priori and accumulated information about the problem. Secondly, global updating rule is applied only to those edges which belong to the best ant tour and lastly, while ants construct the tour, a local pheromone updating rule is applied.
Basically, Ant Colony System (ACS) works as follows: m ants are initially positioned on n nodes chosen according to some initialization rule such as choosing by randomly, with at most one ant in each customer point. Each ant builds a tour incrementally by applying a state transition rule. While constructing the solution, ants also updating the pheromone on the visited edges by local updating rule. Once the ants complete their tour, the pheromone on edges will be updated again by applying global updating rule^{[2]}.
During construction of tours, ants are guided by both heuristic information and pheromone information. Heuristic information refers to the distances of the edges where ants prefer short edges. An edge with higher amount of pheromone is a desirable choice for ants. The pheromone updating rule is designed so that ants tend to leave more pheromone on the edges which should be visited by ants.
The Ant Colony System algorithm is given as in Fig. 2^{[3,4]}.
There are 3 main components which led to the definition of Ant colony System; they are state transition rule, global updating rule and local updating rule. Each of these components will be shown in detail as follow:
In the ant ACS, an artificial ant k after serves customer r chooses the customer
s to move to from set of J_{k}(r) that remain to be served by ant k
by applying the following state transition rule which is also known as pseudorandomproportionalrule:
Where, 
β 
= 
The control parameter of the relative importance of the visibility 
τ(r,u) 
= 
The pheromone trail on edge (r, u) 
η(r,u) 
= 
A heuristic function which was chosen to be the inverse distance between
customers r and u 
A 
= 
A random number uniformly distributed in [0,1] 

= 
A parameter 
S 
= 
A random variable selected according to the probability distribution which
favors edges which is shorter and higher amount of pheromone 
It is same as in Ant system and also known as randomproportionalrule given
as follow:
where, p_{k}(r,s) is the probability of ant k after serves customer r chooses customer s to move to.
The parameter of a_{0} determines the relative importance of exploitation
versus exploration. When an ant after serves customer r has to choose the customer
s to move to, a random number a (0≤ a ≤1) is generated, if a ≤ a_{0},
the best edge according to Eq. 5 is chosen, otherwise an edge
is chosen according to Eq. 6^{[3]}. While building
a tour, ants visits edges and change their pheromone level by applying local
updating rule as follow:
Where, 
ρ 
= 
A pheromone decay parameter 
Δτ(r,s) 
= 
τ_{0} (initial pheromone level) 
Local updating makes the desirability of edges change dramatically since every time an ant uses an edge will makes its pheromone diminish and makes the edge becomes less desirable due to the loss of some of the pheromone. In other word, local updating drives the ants search not only in a neighborhood of the best previous tour.
Global updating is performed after all the ants have completed their tours.
Among the tours, only the best ant which produced the best tour is allowed to
deposit pheromone. This choice is intended to make the search more directed.
The pheromone level is updated by global updating rule as follow:
Where:
L_{gb} is the length of the global best tour from the beginning of the trial. (globalbest) and a is pheromone decay parameter. Global updating is intended to provide greater amount of pheromone to shorter tours. Eq. 8 dictates that only those edges belong to globally best tour will receive reinforcement.
From the experiments done by previous researchers, the numerical parameters are set as following values:
Where, 
L_{nn} 
= 
The tour length produced by the nearest neighbor heuristic 
n 
= 
The number of customers 
The number of ants used is m = 10. These values were obtained by a preliminary optimization phase in which it is found that the experimental optimal values of the parameters were largely independent of the problem except for τ_{0}^{[4]}.
Case Study: A case study has been carried out and it shows the way of a real life problem being formulated into Vehicle Routing Problem with Stochastic Demand Model and solved by the designed algorithm. Since there is no open source data for VRPSD problem, thus this case study adopted a set of data modified from the well known 50customer problem in Eilon et al.^{[6]} as in Table 1.
For this case study, the stopping criterion for ACS algorithm is in dynamic
form where either number of consecutive nonimproving solutions reaching 50
or number of iteration reaches the maximum level. For SA algorithm, the stopping
criterion used is in static form where the iteration stops after a predetermined
number of maximum iteration is reached. The move that is used in SA algorithm
to obtain the neighboring solution is the swapping of position of any two randomly
chosen customers’ positions. Parameter settings of ACS and SA algorithm for
this case study are shown in Table 2 and 3
respectively.
Table 2: 
Parameter setting of ACS algorithm 

Table 3: 
Parameter setting of SA algorithm 

For this study, the proposed ACS with local search algorithm and Simulated Annealing (SA) algorithm are tested for problems ranging in size from 1248 customers. Further detail on SA may be found in Kirkpatrick et al.^{[8]}. The program is run for 10 trials for each algorithm under different vehicle capacity values from ten to forty. Best cost refers to the best cost found from the 10 trials for comparison purpose.
RESULTS
Table 4 shows the computational results for algorithm ACS and SA under different problem sizes.
The results indicate that proposed ACS with local search algorithm produces better solutions compared to SA algorithm. For smaller size of problem, deviation between the best cost results from both ACS and SA algorithm is relatively small. For the problem size with 12 customers with vehicle capacity 10 units, both algorithms obtained the same best cost which is 69.4358 units. But the percentage deviations of averages from the associated best cost are 0.1322 and 0.7064 for ACS and SA. This indicates that ACS gives the results in a more consistent manner compared to SA.
The deviation for SA’s solution compared to solutions obtained by ACS is increasing with the problem sizes. For problem size with 12 customers, the best solutions of SA deviated from best solutions of ACS for not more than 0.5%. When it comes to the problem sizes with 48 customers, the best solutions of SA deviated from best solutions of ACS for more than 5%. This indicates that ACS performs much better than SA algorithm in bigger size of problem. However, ACS requires more computational effort or time over SA algorithm.
For each of the problem size, the larger of vehicle capacity gives the lower
total expected cost. The reason behind is, the larger capacity of vehicle is
able to satisfy more customers’ demands in which it reduces the occurring times
for preventive restocking and route failure.
Table 4: 
Comparison of algorithm ACS and SA for different problem sizes 

Table 5: 
Comparison of algorithm ACS and SA for different demand ranges 

In short, ACS showed better performance than SA under all of the problem sizes with various vehicle capacities tested. Next, both algorithms will be tested over demand ranges.
To access the robustness of ACS algorithm, both ACS and SA algorithms are further compared for different demand ranges. The customers’ demands are generated ranged from 520. Again, the program is run for 10 trials for each algorithm under different demand ranges and problem sizes. The capacity of vehicle is set to be 30 units for every trial for this comparison. Table 5 shows the computational results for comparison.
The results indicate that for all demand ranges, proposed ACS algorithm showed better performance than SA algorithm. From Table 5, it can be noted that ACS gives the more consistent solutions compared to SA algorithm. The average total expected cost given by ACS does not deviate too far from its best cost.
With a fixed capacity, the deviation of best costs for SA algorithm from the best cost of ACS is increasing as the demand ranges increases. Further more, for problem size with 12 customers; the best solutions for SA deviated from best solutions of ACS for not more than 0.2%. However, for problem size with 48 customers, the best solutions of SA deviated from best solutions of ACS for more than 4.5%. This shows that ACS algorithm can reach a good solution for larger problem size compare to SA algorithm.
Apparently, SA is able to obtain good solutions for small ranges especially small size of problem. For ACS, it is always provide good results for all tested ranges and problems sizes of the tested problem.
DISCUSSION
Generally, Genetic Algorithm gives a pool of solutions rather than just one. The process of finding superior solutions mimics the evolution process, with solutions being combined or mutated to find out the pool of solutions. Simulated Annealing is a global optimization technique which traverses the search space by generating neighboring solutions of the current solution. A superior neighbor is always accepted and an inferior neighbor is accepted with some probability.
Tabu Search is similar to Simulated Annealing, in that both traverse the solution space by testing mutations of an individual solution. However, simulated annealing generates only one mutated solution but Tabu search generates many mutated solutions and moves to the solution with the lowest fitness of those generated.
Ant Colony System is the extension from Ant System. Both algorithms are categorized as Ant Colony Optimization (ACO) algorithms. In particular, it can be observed that ACS is the most aggressive of the ACO algorithms and it returns the best solution quality for very short computation times^{[5,7]}. ACS has an advantage over Simulated Annealing and Genetic Algorithm approaches when the graph may change dynamically where the Ant Colony algorithm can be run continuously and adapt to changes in real time.
From the results of case study above, it can be known that the ACS algorithm always finds very good solutions for all tested problems in the aspects of various problem sizes and demand ranges. The algorithm finds the good solutions efficiently and consistently compare with other heuristic methods such as Simulated Annealing and it does not exhibit stagnation behavior where the ants continue to search for new possibly better tours. Stagnation behavior is the situation in which all ants make the same tour.
CONCLUSION
The proposed ACS with local search algorithm and Simulated Annealing algorithm are tested for problems ranging in size from 1248 customers. The results indicate that proposed ACS with local search algorithm produces better solutions compare to SA algorithm. Deviation of SA algorithm’s best cost from the best cost results of ACS algorithm is increasing as the problem size increases.
In the second part of comparison, both ACS and SA algorithms are further compared for different demand ranges from 520 units. Again, the results indicate that proposed ACS algorithm showed better performance than SA algorithm. With a fixed capacity, the deviation of best costs for SA algorithm from the best cost of ACS is increasing as the demand ranges increases.
In this study, an efficient heuristic method is presented to solve the VRPSD problem. The ACS exploits the nature phenomenon of ants to solve such stochastic optimization problem. A local search algorithm (descent method) is proposed to be added in the ACS algorithm. The concept of this method is to find the a priori tour that gives the minimum total expected cost. The ACS has been shown the ability in obtaining good solution for VRPSD problem.
ACKNOWLEDGEMENT
This research was supported by the Ministry of Science, Technology and Innovation, Malaysia (MOSTI) under IRPA Grant Vot No. 74285 and the Department of Mathematics, Faculty of Science, University Technology Malaysia. These supports are gratefully acknowledged. The authors would like to thank lecturers and friends for many helpful ideas and discussion.
" target="_blank">View Fulltext

Related
Articles 
Back