Heuristics fortheruralpostmanproblem

When addressingtheproblemofsnowremovalforsecondaryroads,atoolforsolvingtheruralpostman problem canbeveryuseful.Wepresentsomeideasforheuristicsforthisproblem.Theheuristicsareof the sametypeastheclassicalFredericksonheuristic.Theideasconcerntheorderofthemainstepsin such amethod,namelyconstructingaconnectedgraphwithallverticeshavingevendegree,containing all therequirededges.Wealsoproposetwopostprocessingheuristicsforimprovingthetoursandre- moving unnecessarydetours.Thecomputationaltestsshowthattheideasareinterestingalternativesto the classicalapproach,andthatrunningtimesareacceptable.Westudyproblemcharacteristicsthatmay indicate whichmethodtochoose.