O problema de Sectorização-Rotas nos Arcos (SARP – Sectoring-Arc Routing Problem) consiste na construção de sectores numa dada região e na determinação de viagens em cada sector. Este problema pode ser utilizado na resolução de problemas reais, tais como a recolha de resíduos sólidos urbanos porta-a-porta. O SARP é modelado através de um grafo misto, no qual os arcos e as arestas representam os troços de rua, sendo que apenas um subconjunto destes requer serviço. Cada troço de rua que exija recolha fará parte de um único sector, sendo este servido por um único veículo de capacidade limitada. Desta forma, cada veículo poderá ter de realizar uma ou mais viagens até que o serviço do sector se encontre totalmente executado, mas de tal forma que a sua duração não exceda um determinado valor previamente conhecido. Pretende-se que a duração total das viagens realizadas na região seja mínima. O SARP agrega dois problemas conhecidos num só. Por um lado, o problema de sectorização (ou districting) – de cariz táctico ou estratégico –, que permite particionar uma região grande em subregiões mais pequenas com características que facilitem o serviço que lhes ficará afecto. Por outro lado, ao nível operacional, tem-se o problema de rotas nos arcos com restrições de capacidade (CARP) na sua versão mista (MCARP), onde se optimizam as viagens de serviço. Relativamente a considerar os dois problemas separadamente, o SARP tem a vantagem de evitar a suboptimização. Além disso, e comparativamente ao CARP, o SARP permite, quer evitar a intersecção de viagens de diferentes veículos, quer obter serviços equilibrados. Nesta comunicação, são apresentados os primeiros modelos em programação linear inteira mista que garantem a contiguidade de sectores definidos sobre grafos mistos com procura apenas para algumas das suas ligações. Estes modelos têm ainda a particularidade de serem compactos, ou seja, de considerarem um número não exponencial de variáveis e de restrições. São mostrados e analisados resultados computacionais obtidos para instâncias geradas a partir de outras usadas na literatura para problemas relacionados.

--

modelos; PLI mista; sectorização; rotas