Real world applications for vehicle collection or delivery along streets usually lead to arc routing problems, with additional and complicating constraints. In this paper we focus on arc routing with an additional constraint to identify vehicle service routes with a limited number of shared nodes, i.e. vehicle service routes with a limited number of intersections. This constraint results in solutions that are better shaped for real application purposes. We propose a new problem, the bounded overlapping MCARP (BCARP), which is denefined as the mixed capacitated arc routing problem (MCARP) with an additional constraint imposing an upper bound on the number of nodes that are common to dierent routes. The best feasible upper bound is obtained from a modifed MCARP in which the minimization criteria is given by the overlapping of the routes. We show how to compute this bound by solving a simpler problem. To obtain feasible solutions for the bigger instances a heuristic for the BCARP is also proposed. Computational results over two sets of well known benchmark instances show that the BCARP model produces better shaped solutions (more compact, and with few intersections of routes) than the MCARP model, with only a small increase in total traveled time.

--

capacitated arc routing problems, district design, integer linear programming, heuristics