In many related arc routing problems the servicing area is required to be partitioned into balanced, connected and compact subareas, frequently named as sectors. For instance, if the collecting or delivering services are to be made in a non daily basis or by a specific vehicle or crew. A practical routing application, the refuse collection problem, is addressed. For a given servicing area, there are several streets in which refuse must be collected by a fleet of K homogeneous vehicles. Due to logistical issues, this servicing area must be partitioned into K sectors that are time bounded and each one serviced by a single vehicle. Moreover, it is required that the sectors are: i) as much balanced as possible so as to minimize the servicing time differences; ii) connected so that each vehicle services a sector without leaving it; and iii) compact shaped so that the services of the different sectors are well apart, not only to be more attractive to the drivers, but also to improve crews’ specialization. These two latter features are not necessarily guaranteed by minimizing traveling distances. We propose an iterative algorithm for designing time effective vehicle trips within subareas that met the three aforementioned characteristics. The algorithm is based on a cluster-first, route-second method. The sectoring phase consists of three steps, which includes initialization, expansion and improvement of sectors. For sectors expansion a new distance measure is suggested, which is based on the number of shared nodes. The sectors improvement is based on a tabu search heuristic. The routing phase comprises a heuristic that tries to improve vehicle trips built during the sectoring phase. Computational experiments on realistic sized randomly generated instances and on real instances are provided to demonstrate the efficiency of the proposed solution methodology.

--