The Heterogeneous Fixed Fleet Capacitated Arc Routing Problem

Abstract

Abstract: The heterogeneous fixed fleet capacitated arc routing problem (HFFCARP) is a generalization of the CARP, which is with several vehicle types, each type being defined by a capacity, a fixed cost and a cost per distance unit. In order to solve this new NP-hard problem in acceptable time, two-stage heuristics based on route-first, cluster-second were proposed and local search (LS) and enhanced local search (ELS) were proposed to improve the results. The HFFCARP data generated from the CARP benchmark instances were tested and the results show that the heuristics improved by LS and ELS are effective to solve the HFFCARP, and ELS improves the results much more significantly.

Key words: capacitated arc routing problem(CARP), heterogeneous fixed fleet, heuristics, enhanced local search(ELS)

CLC Number:

TP 301

LIU Tian-Tang, JIANG Zhi-Bin, GENG Na, LIU Ran, LIU Shu-Jun. The Heterogeneous Fixed Fleet Capacitated Arc Routing Problem[J]. Journal of Shanghai Jiaotong University, 2012, 46(11): 1759-1763.

References

［1］Golden B L, Wong R T. Capacitated arc routing problems［J］. Networks, 1981, 11(3): 305315.
［2］Golden J, DeArmon J S, Baker E K. Computational experiments with algorithms for a class of routing problems［J］. Computers & Operations Research, 1983, 10(1): 4759.
［3］Ulusoy G. The fleet size and mix problem for capacitated arc routing［J］. European Journal of Operational Research, 1985, 22(3): 329337.
［4］Hertz A, Laporte G, Mittaz M. A tabu search heuristic for the capacitated arc routing problem［J］. Operations Research, 2000, 48(1): 129135.
［5］Brando J, Eglese R. A deterministic tabu search algorithm for the capacitated arc routing problem［J］. Computers & Operations Research, 2008, 35(4): 11121126.
［6］Hertz A, Mittaz M. A variable neighborhood descent algorithm for the undirected capacitated arc routing problem［J］. Transportation Science, 2001, 35(4): 425434.
［7］Beullens P, Muyldermans L, Cattrysse D, et al. A guided local search heuristic for the capacitated arc routing problem［J］. European Journal of Operational Research, 2003, 147(3): 629643.
［8］Lacomme P, Prins C, RamdaneCherif W. Competitive memetic algorithms for arc routing problems［J］. Annals of Operations Research, 2004, 131(1): 159185.
［9］Santos L, CoutinhoRodrigues J, Current J R. An improved ant colony optimization based algorithm for the capacitated arc routing problem［J］. Transportation Research Part B: Methodological, 2010, 44(2): 246266.
［10］Chu F, Labadi N, Prins C. A scatter search for the periodic capacitated arc routing problem［J］. European Journal of Operational Research, 2006, 169(2): 586605.
［11］Lacomme P, Prins C, Sevaux M. A genetic algorithm for a biobjective capacitated arc routing problem［J］. Computers & Operations Research, 2006, 33(12): 34733493.
［12］Belenguer J M, Benavent E, Labadi N, et al. Splitdelivery capacitated arcrouting problem: Lower bound and metaheuristic ［J］. Transportation Science, 2010, 44(2): 206220.
［13］Laporte G, Musmanno R, Vocaturo F. An adaptive large neighbourhood search heuristic for the capacitated arcrouting problem with stochastic demands［J］. Transportation Science, 2010, 44(1): 125135.
［14］Frederickson G. Approximation algorithms for some postman problems［J］. Journal of the ACM (JACM), 1979, 26(3): 538554.