Journal of Industrial Engineering and Management Studies

Solving a robust capacitated arc routing problem using a hybrid simulated annealing algorithm: A waste collection application

Document Type : Original Article

Authors

E. Babaee Tirkolaee 1
M. Alinaghian 2
M. Bakhshi Sasi 2
M. M. Seyyed Esfahani 3

1 Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran

2 Department of Industrial Eengineering, Isfahan University of technology, Isfahan, Iran.

3 Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran.

Abstract
The urban waste collection is one of the major municipal activities that involves large expenditures and difficult operational problems. Also, waste collection and disposal have high expenses such as investment cost (i.e. vehicles fleet) and high operational cost (i.e. fuel, maintenance). In fact, making slight improvements in this issue lead to a huge saving in municipal consumption. Some incidents such as altering the pattern of waste collection and abrupt occurrence of events can cause uncertainty in the precise amount of waste easily and consequently, data uncertainty arises.  In this paper, a novel mathematical model is developed for robust capacitated arc routing problem (CARP). The objective function of the proposed model aims to minimize the traversed distance according to the demand uncertainty of the edges. To solve the problem, a hybrid metaheuristic algorithm is developed based on a simulated annealing algorithm and a heuristic algorithm. Moreover, the results obtained from the proposed algorithm are compared with the results of exact method in order to evaluate the algorithm efficiency. The results have shown that the performance of the proposed hybrid metaheuristic is acceptable.

Keywords

Waste collection
Carp
hybrid metaheuristic algorithm
Simulated Annealing Algorithm
robust optimization
Beltrami, Edward J., and Lawrence D. Bodin., 1974. "Networks and vehicle routing for municipal waste collection." Networks 4.1: 65-94.
Bertsimas, Dimitris, and Melvyn Sim., 2003."Robust discrete optimization and network flows." Mathematical programming 98.1-3: 49-71.
Bertsimas, Dimitris, and Melvyn Sim., 2004. "The price of robustness." Operations research 52.1: 35-53.
Chen, Lu, et al., 2014. Optimizing road network daily maintenance operations with stochastic service and travel times." Transportation Research Part E: Logistics and Transportation Review 64: 88-102.
 
Chen, Yuning, Jin-Kao Hao, and Fred Glover., 2016."A hybrid metaheuristic approach for the capacitated arc routing problem." European Journal of Operational Research.
Dror, Moshe, and André Langevin, 2000.Transformations and exact node routing solutions by column generation. Springer US,
Fleury, Gérard, Philippe Lacomme, and Christian Prins, 2004. "Evolutionary algorithms for stochastic arc routing problems." Applications of Evolutionary Computing. Springer Berlin Heidelberg. 501-512.
Fleury, Gérard, et al., 2005."Stochastic capacitated arc routing problems." Document de travail interne. Article en cours de rédaction
Golden, B., Wong, R., 1981." Capacitated arc routing problems." Network, vol.11, pp.305–315.
Golden, Bruce L., Arjang A. Assad, and Edward A. Wasil., 2001. "Routing vehicles in the real world: applications in the solid waste, beverage, food, dairy, and newspaper industries." The vehicle routing problem. Society for Industrial and Applied Mathematics.
 Glover, F.W., Kochenberger, G., 2005. “Handbook of metaheuristics”, Kluwer Academic Publishers, Norwell,
Kirkpatrick, S., & Vecchi, M. P., 1983. Optimization by simmulated annealing. science, 220(4598), 671-680.
 Laporte, Gilbert, Roberto Musmanno, and Francesca Vocaturo., 2010. "An adaptive large neighbourhood search heuristic for the capacitated arc-routing problem with stochastic demands." Transportation Science 44.1: 125-135.
 Santos, Luís, João Coutinho-Rodrigues, and John R. Current., 2010. "An improved ant colony optimization based algorithm for the capacitated arc routing problem." Transportation Research Part B: Methodological 44.2: 246-266.
 Taguchi, Genichi, Subir Chowdhury, and Yuin Wu., 2005. Taguchi's quality engineering handbook. Wiley-Interscience,.
 Vincent, F. Yu, and Shih-Wei Lin., 2015. Iterated greedy heuristic for the time-dependent prize-collecting arc routing problem." Computers & Industrial Engineering 90: 54-66.
 Willemse, Elias J., and Johan W. Joubert, 2016. Constructive heuristics for the Mixed Capacity Arc Routing Problem under Time Restrictions with Intermediate Facilities." Computers & Operations Research 68: 30-62.
Journal of Industrial Engineering and Management Studies
Volume 3, Issue 1
June 2016
Pages 61-76

Home

Guide for Authors

Publication Ethics

Submit Manuscript

Reviewers

Contact Us