A novel heuristic method to solve the capacitated arc routing problem

Abstract: The capacitated arc routing problem is one of the most important routing problems with many applications in real world situations such as snow removing, winter gritting, refuse collection, etc. Since this problem is NP-hard, many of researchers have been developed numerous heuristics and metaheuristics to solve it. In this paper, we propose a new constructive and improvement heuristic in which forming a vehicle’s tour is based on choosing an unserved edge randomly as current partial tour and then extending this partial tour from its both of end nodes base on four effective proposed criteria. When the vehicle load is near its capacity, it should come back to the depot immediately. Finally, the constructed tours are merged into more efficient and cheaper tours. The quality of this new approach was tested on three standard benchmark instances and the results were compared with some known existing heuristics and metaheuristics in the literature. The computational results show an excellent performance of our new method.

How to cite this paper

 Eydi, A & Javazi, L. (2012). A novel heuristic method to solve the capacitated arc routing problem.International Journal of Industrial Engineering Computations , 3(5), 767-776.

Refrences

Arag?o, M.P., Longo, H., & Uchoa, E. (2006). Solving capacitated arc routing problems using a transformation to the CVRP. Computers & Operations Research, 33(6), 1823–1837.

Belenguer, J.M., & Benavent, E. (2003). A cutting plane algorithm for the Capacitated Arc Routing Problem. Computers & Operations Research 30(5), 705-728.

Belenguer, J.M., Benavent, E., Lacomme, P., & Prins, C. (2006). Lower and upper bounds for the mixed capacitated arc routing problem. Computers & Operations Research, 33, 3363–3383.

Benavent, E., Campos, V., Corberan, A., & Mota, E. (1992). The capacitated arc routing problem: Lower bounds. Networks, 22, 669-690.

DeArmon, J.S. (1981). A comparison of heuristics for the capacitated Chinese postman problem. Dissertation, University of Maryland.

Dijkgraaf, E., & Gradus, R. (2007). Fair competition in the refuse collection market. Applied Economic Letters, 14(10), 701–704.

Eglese, R.W. (1994). Routing winter gritting vehicles. Discrete applied mathematics, 48(3), 231-244.

Eglese, R.W., & Li, L.Y.O. (1992). Efficient Routing for Winter Gritting. Journal of Operational Research Society 43(11), 1031–1034.

Golden, B.L., DeArmon, J.S., & Baker, E.K. (1983). Computational experiments with algorithms for a class of routing problems. Computers & Operations Research, 10, 47–59.

Golden, B.L., & Wong, R.T. (1981). Capacitated arc routing problems. Networks, 11, 305–315.
Grandinetti, L., Guerriero, F., Lagana, D., & Pisacane, O. (2012). An optimization-based heuristic for the Multi-objective Undirected Capacitated Arc Routing Problem. Computers & Operations Research, 39(10), 2300-2309.

Han, H.S., Yu, J.J., Park, C.G., & Lee, J.G. (2004). Development of inspection gauge system for gas pipeline. Korean Society Mechanical Engineering International Journal, 18(3), 370–378.

Hertz, A., Laporte, G., & Mittaz, M. (2000). A tabu search heuristic for the capacitated arc routing problem. Operations Research, 48(1), 129–135.

Hertz, A., Laporte, G., & Nanchen-Hugo, P. (1999). Improvement procedures for the undirected rural postman problem. INFORMS Journal on Computing, 11(1), 53–62.

Hirabayashi, H., Saruwatari, Y., & Nishida, N. (1992). Tour construction algorithm for the capacitated arc routing problems. Asia-Pacific Journal of Operations Research, 9, 155–175.

Kirlik, G., & Sipahioglu, A. (2012). Capacitated arc routing problem with deadheading demands. Computers & Operations Research, 39(10), 2380-2394.

Labelle, A., Langevin, A., & Campbell, J.F. (2002). Sector design for snow removal and disposal in urban areas. Socio-Economic Planning Sciences, 36(3), 183–202.

Lacomme, P., Prins, C., & Ramdane-Cherif, W. (2004a). Competitive memetic algorithms for arc routing problems. Annals of Operation Research, 131, 159–185.

Lacomme, P., Prins, C., & Tanguy, A. (2004b). First competitive ant colony scheme for the CARP. Lecture Notes in Computer Science, 3172, 426-427.

Pearn, W.L. (1989). Approximate solutions for the capacitated arc routing problem. Computers & Operations Research, 16, 589-600.

Salazar-Aguilar, M.A., Langevin, A., & Laporte, G. (2012). Synchronized arc routing for snow plowing operations. Computers & Operations Research, 39(7), 1432-1440.

Santos, L., Coutinho-Rodrigues, J.R., & Current, J.R. (2009). An improved heuristic for the capacitated arc routing problem. Computers & Operations Research, 36(9), 2632–2637.

Stern, H.I., & Dror, M. (1979). Routing Electric Meter Readers. Computers & Operations Research 6(4), 209–223.

Tobin, G.A., & Brinkmann, R. (2002). The effectiveness of street sweepers in removing pollutants from road surfaces in Florida. Journal of Environmental Science and Health (Part A) 37(9), 1687–1700.

Ulusoy, G. (1985). The fleet size and mix problem for capacitated arc routing. European Journal of Operational Research, 22, 329–337.

W?hlk, S. (2008). A decade of capacitated arc routing. In: Golden B, Raghavan S, Wasil E, editors. The vehicle routing problem: latest advances and new challenges. New York, USA: Springer, 29–48.

W?hlk, S. (2005). Contributing to arc routing. PhD thesis, University of Southern Denmark.
W?hlk, S. (2006). New lower bound for the capacitated arc routing problem. Computers & Operations Research, 33(12), 3458-3472.