Asian Science Citation Index is committed to provide an authoritative, trusted and significant information by the coverage of the most important and influential journals to meet the needs of the global scientific community.  
ASCI Database
308-Lasani Town,
Sargodha Road,
Faisalabad, Pakistan
Fax: +92-41-8815544
Contact Via Web
Suggest a Journal
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 stock-out with the cost of returning depot for restocking before a stock-out 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 non-toxic 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 x-coordinate and y-coordinate 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 50-customer 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 pi,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 fw(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 f0(Q). The dynamic programming recursion is shown as follows[11]:

(1)

Where:

(2)

and

(3)

with the boundary condition:

(4)

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 Jk(r) that remain to be served by ant k by applying the following state transition rule which is also known as pseudo-random-proportional-rule:

(5)

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 random-proportional-rule given as follow:

(6)

where, pk(r,s) is the probability of ant k after serves customer r chooses customer s to move to.

The parameter of a0 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 ≤ a0, 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:

(7)

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:

(8)

Where:

Lgb is the length of the global best tour from the beginning of the trial. (global-best) 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,
Lnn = 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 50-customer 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 non-improving 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 12-48 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 5-20. 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 12-48 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 5-20 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
   
 
 
 
  Related Articles

No Article Found
 
 
 
Copyright   |   Desclaimer   |    Privacy Policy   |   Browsers   |   Accessibility