A recolha de res´ıduos porta-a-porta tem sido tratada na literatura geralmente associada a aplica¸c˜oes concretas. De seguida s˜ao referidos alguns trabalhos publicados nesta ´area, sendo que a maioria deles aborda a quest˜ao na perspectiva da constru¸c˜ao de viagens. Os trabalhos destacados est˜ao organizados de acordo com o tipo de problema te´orico subjacente, come¸cando por aqueles que podem ser vistos exclusivamente como problemas de determina¸c˜ao de viagens, seguidos dos que s˜ao encarados como problemas de sectoriza¸c˜ao e, por fim, aqueles em que se pretende a determina¸c˜ao simultˆanea de sectores e de viagens.
A elabora¸c˜ao de viagens com vista `a recolha de res´ıduos porta-a-porta ´e abordada na literatura em Mour˜ao (1997), Mour˜ao e Almeida (2000), Mour˜ao e Amado (2005) e Ghiani et al. (2005). Estes trabalhos s˜ao descritos mais detalhadamente na Sec¸c˜ao 2.1. Para al´em destes, s˜ao tamb´em de referir Amponsah e Salhi (2004), Del Pia e Filippi (2006) e Kim et al. (2006).
Amponsah e Salhi (2004) estudam a recolha de res´ıduos em pa´ıses em desenvolvimento, no caso concreto do Gana, onde tˆem de ser tidos em conta, n˜ao s´o factores economi- cistas, como ambientais, devido ao calor que se faz sentir na regi˜ao. Por este motivo, consideram um CARP biobjectivo, para o qual desenvolvem uma heur´ıstica construtiva, aplicando posteriormente melhoramentos.
Em Del Pia e Filippi (2006) ´e considerada a recolha de res´ıduos numa cidade do norte de It´alia, com a particularidade de ter dep´ositos m´oveis. Foi ent˜ao usada uma generaliza¸c˜ao do CARP de modo a contemplar esta caracter´ıstica, para a qual foi desenvolvida uma heur´ıstica de pesquisa local.
A sectoriza¸c˜ao de redes de recolha de res´ıduos, sem a inclus˜ao da determina¸c˜ao de viagens, foi estudada por Silva Gomes (1983), Hanafi et al. (1999) e Lin e Kao (2008). Estes trabalhos s˜ao referidos com mais detalhe na Sec¸c˜ao 2.2.2.
Por ´ultimo, a determina¸c˜ao de sectores incluindo tamb´em a elabora¸c˜ao de viagens para a recolha de res´ıduos ´e tratada em Male e Liebman (1978) e Mour˜ao et al. (2009). Estes trabalhos s˜ao descritos mais pormenorizadamente na Sec¸c˜ao 2.2.2.
Cap´ıtulo
3
Problema de Sectoriza¸c˜ao e Rotas nos Arcos
(SARP)
Neste cap´ıtulo descreve-se o problema de sectoriza¸c˜ao e rotas nos arcos ou SARP (Sectoring-Arc Routing Problem). O SARP ´e ilustrado usando a recolha de res´ıduos urbanos, mas qualquer aplica¸c˜ao envolvendo a parti¸c˜ao das ruas de uma cidade em sectores e a defini¸c˜ao de viagens em cada sector poder´a tamb´em ser modelada de forma semelhante. Ap´os a introdu¸c˜ao, na Sec¸c˜ao 3.1, onde se define o SARP e a sua aplica¸c˜ao `a recolha de res´ıduos, na Sec¸c˜ao 3.2 modela-se o problema e apresenta-se a nota¸c˜ao necess´aria. A Sec¸c˜ao 3.3 ´e dedicada ao estudo da sua complexidade e na Sec¸c˜ao 3.4 s˜ao descritas as instˆancias usadas em testes. Este cap´ıtulo finaliza, na Sec¸c˜ao 3.5, com a apresenta¸c˜ao de um exemplo.
3.1
Introdu¸c˜ao
Come¸ca por caracterizar-se o sistema de recolha de res´ıduos s´olidos urbanos conside- rado. Cada equipa de recolha, doravante designada por tripula¸c˜ao, ´e constitu´ıda por um motorista e, em geral, mais dois tripulantes. A cada tripula¸c˜ao est´a associado um ve´ıculo, representando portanto a mesma entidade. Cada ve´ıculo, e respectiva
tripula¸c˜ao, parte do dep´osito e dirige-se `a zona onde vai efectuar a recolha. Durante o servi¸co, podem ser necess´arias visitas interm´edias `a esta¸c˜ao de despejo – que se sup˜oe localizada no mesmo ponto do dep´osito –, para que n˜ao seja excedida a capacidade do ve´ıculo. Nestes casos, o ve´ıculo ´e descarregado e retomada a recolha. Finalizada a recolha, o ve´ıculo regressa ao dep´osito e descarrega pela ´ultima vez.
Designa-se por viagem o percurso efectuado por um ve´ıculo, desde que este sai do dep´osito at´e l´a voltar para descarregar, incluindo o acto de descarga. O termo servi¸co (de um ve´ıculo) ´e usado para referir o conjunto de todas as viagens realizadas por um mesmo ve´ıculo. Assim, a dura¸c˜ao total do servi¸co de um ve´ıculo ´e contabilizada desde que este sai do dep´osito pela primeira vez at´e que descarrega pela ´ultima vez, incluindo os tempos de descarga.
A defini¸c˜ao de sectores e a determina¸c˜ao de viagens para a recolha urbana de res´ıduos porta-a-porta pode ser modelada por um SARP. Neste contexto, cada sector deve corresponder ao percurso a realizar por um ve´ıculo, que executar´a uma ou mais viagens at´e terminar o servi¸co correspondente. A dura¸c˜ao total do servi¸co em cada sector n˜ao pode exceder um determinado limite conhecido.
Os sectores s˜ao formados com a finalidade de concentrar, numa dada zona da rede, o servi¸co associado a cada ve´ıculo. Esta concentra¸c˜ao, conseguida requerendo que cada sector seja, tanto quanto poss´ıvel, cont´ıguo e compacto, tem vantagens do ponto de vista pr´atico. Se for cont´ıguo, tende a minorar o cruzamento com o servi¸co de outros sectores, permitindo clarificar a atribui¸c˜ao de responsabilidades em rela¸c˜ao ao servi¸co prestado ou a prestar em cada segmento de rua. Por outro lado, sendo compacto, que se caracteriza por ter uma forma mais “arredondada” – em oposi¸c˜ao a ser mais “alongado” –, ´e tamb´em preferido porque favorece a proximidade entre as liga¸c˜oes a servir.
O facto de ter cada sector associado a uma tripula¸c˜ao permite tamb´em diminuir as raz˜oes de conflito entre trabalhadores de tripula¸c˜oes diferentes, na medida em que ´e poss´ıvel tentar equilibr´a-los relativamente ao servi¸co. Optou-se por fazer o equil´ıbrio relativamente `a dura¸c˜ao total do servi¸co, por se ter considerado que as diferen¸cas entre estas dura¸c˜oes s˜ao potencialmente geradoras de mais conflitos do que, por exemplo,
as diferen¸cas relativamente `a quantidade total de res´ıduos recolhidos. A forma¸c˜ao de sectores permite ainda que as estat´ısticas produzidas possam ser agrupadas por sector e que os motoristas tenham de memorizar conjuntos de ruas menos dispersas.
Apesar de, conforme exposto anteriormente, a contiguidade e o equil´ıbrio serem ambos importantes, deu-se mais relevˆancia ao equil´ıbrio. Sendo a contiguidade uma caracte- r´ıstica a ter em considera¸c˜ao, do ponto de vista da recolha de res´ıduos ´e aceit´avel que, ocasionalmente, um ve´ıculo fa¸ca remo¸c˜ao de res´ıduos num local e depois tenha de se deslocar para um outro local n˜ao cont´ıguo para continuar a recolha.
O SARP ´e definido num multigrafo misto, por se considerar que esta representa¸c˜ao ´e a mais adequada para traduzir a estrutura de ruas de uma cidade quando o servi¸co a prestar se distribui ao longo de tro¸cos de rua. A frota ´e constitu´ıda por ve´ıculos idˆenticos que se encontram estacionados no dep´osito, simbolizado por um nodo. A cada liga¸c˜ao (arco ou aresta) est´a associada uma dura¸c˜ao em vazio (deadheading time), que representa o tempo que um ve´ıculo que n˜ao esteja a realizar servi¸co demora a percorrˆe-la. De entre todas as liga¸c˜oes da rede, as que tˆem de ser sujeitas a recolha designam-se por liga¸c˜oes com procura.
No SARP, a quantidade de res´ıduos respeitantes a um sector obriga, em geral, a que o ve´ıculo a ele afecto tenha de efectuar v´arias viagens. Al´em disso, certos tro¸cos de rua s˜ao representados por arcos, mas outros – em que ambos os lados podem ser servidos em simultˆaneo e em qualquer direc¸c˜ao – s˜ao modelados por arestas. Assim, o problema de determina¸c˜ao de rotas nos arcos subjacente em cada sector pode ser modelado por um CARP misto (MCARP).
Em suma, com o SARP pretende fazer-se a parti¸c˜ao das liga¸c˜oes com procura num n´umero conhecido de sectores e resolver, em cada sector, um problema de roteamento, com procura nas liga¸c˜oes, num grafo misto com restri¸c˜oes de capacidade (MCARP), de forma a n˜ao ultrapassar o limite de dura¸c˜ao dentro de cada sector e a minimizar a dura¸c˜ao total das viagens no conjunto de todos os sectores.