Real world applications for collecting or delivering products along streets usually lead to arc routing problems with additional and complicating requirements. Among them there is the undesirable overlapping of the routes of different vehicles while performing their services. In this work we focus on the mixed capacitated arc routing problem (MCARP) with a limited number of intersections of the routes as a way to avoid the overlapping. Then, we define the bounded overlapping MCARP (BCARP), which results from the MCARP by adding a constraint ensuring an upper bound on the number of nodes shared by different routes. We also introduce a new model to compute the best feasible value for this upper bound. Mixed integer linear programming formulations are presented for the BCARP, and a heuristic is proposed to obtain feasible solutions for the bigger instances. Computational results are reported for well-known benchmark instances. The BCARP seems more suitable for real applications. In fact, the results show that better shaped service routes are obtained (more compact and with fewer intersections), with a small increase in total traveled time, when compared to the MCARP.

--

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