Single Closest Task Assignment: a Heuristic Method for the Sectoring-Arc Routing Problem

Philippe Lacomme (1) , Maria Mourao (2) , Ana Claudia Nunes (2) , Christian Prins (3)

1 LIMOS - Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes
2 ULISBOA - Universidade de Lisboa = University of Lisbon
3 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

The aim of the sectoring-arc routing problem (SARP) is to partition a large region into a given number of smaller sub-regions (sectors) and to build a set of trips in each sector, such that the total duration of the trips is minimized. A graph partition is made to simplify the organization of the activities that must be executed. The SARP arises here in the context of waste collection. A heuristic method is presented, based on the assignment of single tasks to sectors. Sectors are built simultaneously. The heuristic is performed on a set of benchmark problems. Computational results are presented and analysed

Keywords: Routing; Meter reading; Business; Marketing and sales; Costs; Vehicle driving; Cities and towns

Domains: Computer Science [cs]; Operations Research [cs.RO]

Philippe Lacomme, Maria Mourao, Ana Claudia Nunes, Christian Prins. Single Closest Task Assignment: a Heuristic Method for the Sectoring-Arc Routing Problem. 2006 International Conference on Service Systems and Service Management, Oct 2006, Troyes, France. pp.1531-1535, ⟨10.1109/ICSSSM.2006.320763⟩. ⟨hal-02507709⟩