(ARP)
Quando se desenvolvem actividades que est˜ao associadas `as liga¸c˜oes de uma rede e se pretende determinar os respectivos percursos, diz-se que se est´a perante um problema de determina¸c˜ao de rotas nos arcos (ARP – Arc Routing Problem). A recolha de res´ıduos porta-a-porta, a entrega de correspondˆencia ao domic´ılio, a limpeza de neve das ruas ou a leitura de contadores s˜ao exemplos de actividades normalmente associadas aos arcos ou arestas de um grafo. As liga¸c˜oes de uma rede tˆem de ser servidas sempre que se considera que as actividades que se pretendem realizar se desenrolam continuamente em determinados percursos. Nestes casos, os nodos representam intersec¸c˜oes ou pontos de liga¸c˜ao. Em Eiselt et al. (1995a,b) e Assad e Golden (1995) ´e referido um vasto conjunto
de aplica¸c˜oes para os problemas desta fam´ılia e o livro editado por Dror (2000) aborda, para al´em das aplica¸c˜oes, as quest˜oes te´oricas e os m´etodos de resolu¸c˜ao exactos e heur´ısticos. Mais recentemente, em Wøhlk (2008), ´e feita uma revis˜ao da literatura publicada na ´ultima d´ecada para o caso em que existem limita¸c˜oes de capacidade. Mediante determinadas caracter´ısticas, os ARP assumem designa¸c˜oes espec´ıficas. Sem pretender elaborar uma lista exaustiva, referem-se de seguida alguns destes problemas que se consideram mais relevantes para o enquadramento do presente trabalho. Para mais detalhes, sugere-se, por exemplo, o livro Dror (2000).
No problema do carteiro chinˆes (CPP – Chinese Postman Problem) devem percorrer-se todas as liga¸c˜oes (arcos ou arestas) de um grafo. Se tiverem de ser percorridas apenas algumas liga¸c˜oes, designadas com procura, ent˜ao tem-se um problema do carteiro rural (RPP – Rural Postman Problem). O problema da determina¸c˜ao de rotas com procura nos arcos e restri¸c˜oes de capacidade (CARP – Capacitated Arc Routing Problem) refere- -se `as situa¸c˜oes em que os ve´ıculos tˆem capacidade limitada.
O CPP ´e definido num grafo fortemente conexo e a sua resolu¸c˜ao faz-se em tempo polinomial: i) no caso totalmente n˜ao orientado, `a custa da resolu¸c˜ao de um problema de emparelhamento perfeito de custo m´ınimo (minimum cost perfect matching problem); e ii) no caso totalmente orientado, resolvendo um problema de transportes (TP –
Transportation Problem). Para grafos mistos, o CPP ´e NP-dif´ıcil (Papadimitriou, 1976),
mesmo para grafos planares ou quando os custos associados `as liga¸c˜oes s˜ao todos iguais. O RPP ´e NP-dif´ıcil (Lenstra e Rinnooy Kan, 1976), exceptuando os casos totalmente n˜ao orientado ou totalmente orientado, para os quais o subgrafo induzido pelas arestas ou arcos com procura ´e fortemente conexo, que s˜ao resol´uveis em tempo polinomial por redu¸c˜ao a um CPP.
No CARP, tal como foi definido por Golden e Wong (1981), h´a custos de atravessamento e procuras n˜ao negativas associados `as arestas de um grafo e a capacidade dos ve´ıculos ´e conhecida. O CARP consiste em determinar um conjunto de viagens de custo total m´ınimo que, partindo do dep´osito, sirvam todas as arestas com procura e que a procura
total servida por cada viagem n˜ao exceda a capacidade do ve´ıculo. O CARP ´e NP-dif´ıcil, uma vez que inclui o RPP como caso particular. Al´em disso, Golden e Wong (1981) provaram que o problema da determina¸c˜ao de uma solu¸c˜ao para o CARP cujo valor esteja a menos de 1.5 vezes o valor ´optimo ´e tamb´em ele NP-dif´ıcil.
Dada a dificuldade de resolu¸c˜ao do CARP, as abordagens propostas tˆem incidido na obten¸c˜ao de limites inferiores e no desenvolvimento de algoritmos heur´ısticos. A vers˜ao n˜ao orientada do CARP tem sido a mais estudada, para a qual foram desenvolvidas v´arias formula¸c˜oes exactas (Belenguer, 1990; Welz, 1994; Letchford, 1997; Belenguer e Benavent, 1998a) e n˜ao exactas (Letchford, 1997; Belenguer e Benavent, 1998b, 2003), a partir das quais se podem obter limites inferiores.
Em Dror (2000) s˜ao descritos em detalhe os v´arios m´etodos heur´ısticos conhecidos at´e `a sua publica¸c˜ao. Depois dessa data, tˆem surgido na literatura outros m´etodos, muitos deles baseados em t´ecnicas heur´ısticas recentes e mais sofisticadas. Wøhlk (2008) faz uma revis˜ao dos trabalhos publicados na ´ultima d´ecada sobre os v´arios aspectos que envolvem o CARP, incluindo a modela¸c˜ao, limites inferiores e m´etodos de resolu¸c˜ao. De seguida, citam-se alguns trabalhos nesta ´area.
Come¸cando pelas heur´ısticas construtivas, podem referir-se, por exemplo, os algoritmos
construct-strike (Christofides, 1973), path-scanning e augment-merge (Golden et al.,
1983), parallel-insert (Chapleau et al., 1984) e augment-insert (Pearn, 1991).
Foram tamb´em propostos algoritmos construtivos em duas fases do tipo route first-
-cluster second e cluster first-route second. Os m´etodos da categoria route first-cluster second caracterizam-se por, na fase inicial, construir um circuito euleriano gigante
cobrindo todas as liga¸c˜oes com procura, que ´e decomposto, na fase seguinte, em circuitos admiss´ıveis. As heur´ısticas propostas por Ulusoy (1985) e por Hertz et al. (2000) inserem-se nesta categoria. Os m´etodos cluster first-route second operam de forma inversa: primeiro s˜ao formados grupos de liga¸c˜oes com procura (Benavent et al., 1990), cada um deles com procura total inferior `a capacidade dos ve´ıculos, a que se segue a resolu¸c˜ao de um RPP em cada grupo.
Posteriormente, come¸caram a ser desenvolvidos m´etodos melhorativos. Li (1992) propˆos algoritmos de pesquisa tabu e arrefecimento simulado (simulated annealing) para uma aplica¸c˜ao em opera¸c˜oes de espalhar sal nas ruas a fim de provocar o degelo (winter
gritting). Em Eglese (1994) ´e descrito um outro algoritmo de simulated annealing
para uma aplica¸c˜ao idˆentica mas em que se consideram diversas localiza¸c˜oes para os dep´ositos e ruas com diferentes prioridades de servi¸co. Mais tarde, Hertz et al. (2000) propuseram o algoritmo de pesquisa tabu conhecido por CARPET, Beullens et al. (2003) apresentaram um algoritmo de pesquisa local e Lacomme et al. (2004) descreveram um algoritmo mem´etico (memetic algorithm).
Todos os algoritmos referidos atr´as para o CARP foram desenvolvidos especificamente para o caso totalmente n˜ao orientado. O CARP totalmente orientado e o CARP misto (MCARP) tˆem merecido menos aten¸c˜ao, principalmente no que diz respeito a formula¸c˜oes e limites inferiores. Tanto quanto se sabe at´e `a data, Mour˜ao (1997) e Mour˜ao e Almeida (2000) foram os ´unicos a apresentar uma formula¸c˜ao exacta e a desenvolver limites inferiores para o CARP totalmente orientado. Estes dois trabalhos referem ainda m´etodos heur´ısticos de resolu¸c˜ao.
O MCARP foi abordado por Lacomme et al. (2004), Ghiani et al. (2005), Mour˜ao e Amado (2005), Belenguer et al. (2006), Bautista et al. (2008) e, mais recentemente, por Gouveia et al. (2009), embora nem sempre considerem as mesmas caracter´ısticas. Estes autores lidaram de forma diferente com o grafo misto subjacente. Nos trˆes primeiros trabalhos, e tamb´em no ´ultimo, o multigrafo misto ´e transformado num multigrafo totalmente orientado: Mour˜ao e Amado (2005) usam um algoritmo para orientar as arestas e Lacomme et al. (2004), Belenguer et al. (2006) e Gouveia et al. (2009) substituem cada aresta por dois arcos opostos (´e esta a abordagem seguida no presente trabalho), necessitando apenas um deles de ser servido. Ghiani et al. (2005) n˜ao procedem a qualquer transforma¸c˜ao. Uma abordagem diferente foi usada por Bautista et al. (2008), que tamb´em consideram um multigrafo, mas optaram por transformar o problema de rotas nos arcos num problema de rotas nos nodos (NRP). Os trabalhos de Ghiani et al. (2005), Mour˜ao e Amado (2005) e Bautista et al. (2008)
tˆem em comum o facto de tratarem a recolha de res´ıduos. Por outro lado, Lacomme et al. (2004), Belenguer et al. (2006) e Bautista et al. (2008) contemplam a ocorrˆencia de viragens proibidas. Os grafos mistos descritos em Lacomme et al. (2004), Ghiani et al. (2005), Mour˜ao e Amado (2005), Belenguer et al. (2006) e Gouveia et al. (2009) tˆem a particularidade de considerar custos diferentes para as liga¸c˜oes atravessadas em servi¸co ou em vazio (esta caracter´ıstica foi tamb´em seguida no presente trabalho). Pelo contr´ario, Bautista et al. (2008) consideram o mesmo custo para o atravessamento em servi¸co e em vazio.
Em Lacomme et al. (2004) e, posteriormente, com novas vers˜oes em Belenguer et al. (2006), s˜ao apresentados m´etodos construtivos para o MCARP, desenvolvidos a partir de heur´ısticas cl´assicas para o CARP n˜ao orientado: EAM, EPS e EU s˜ao extens˜oes das heur´ısticas augment-merge (Golden e Wong, 1981), path-scanning (Golden et al., 1983) e heur´ıstica de Ulusoy (Ulusoy, 1985), respectivamente. Para al´em das heur´ıs- ticas construtivas adaptadas, nestes dois trabalhos ´e tamb´em descrito um algoritmo mem´etico. Em Lacomme et al. (2004) s˜ao ainda propostos uma formula¸c˜ao n˜ao exacta em programa¸c˜ao linear inteira, desigualdades v´alidas e um algoritmo de planos de corte para a obten¸c˜ao de limites inferiores para o MCARP.
Ghiani et al. (2005) tratam o problema da recolha de res´ıduos no sul de It´alia, modelado atrav´es de um MCARP com janelas temporais, para o qual foi desenvolvida uma heur´ıstica do tipo cluster first-route second. A recolha ´e realizada por ve´ıculos de trˆes dimens˜oes diferentes, sendo que os ve´ıculos de maior dimens˜ao n˜ao podem ser usados em determinadas liga¸c˜oes. ´E tamb´em considerada a existˆencia de recipientes de duas capacidades distintas, tendo de ser observadas certas regras quanto ao ve´ıculo a usar na sua recolha.
Em Mour˜ao e Amado (2005) ´e estudado o caso espec´ıfico da recolha de res´ıduos na cidade de Lisboa, para o qual s˜ao propostas e testadas heur´ısticas, quer com instˆancias geradas aleatoriamente para o efeito, quer com outras instˆancias descritas na literatura por outros autores.
nic´ıpio na zona metropolitana de Barcelona (Espanha). O MCARP considerado ´e transformado num NRP, para o qual prop˜oem uma heur´ıstica baseada em col´onias de formigas (ant colony heuristic).
No trabalho de Gouveia et al. (2009) s˜ao propostas formula¸c˜oes exactas para o MCARP, com a particularidade de conterem um n´umero polinomial de vari´aveis e de restri¸c˜oes, e tamb´em uma relaxa¸c˜ao a partir da qual foi poss´ıvel obter limites inferiores que, por vezes, superam os referidos em Belenguer et al. (2006).
Relativamente ao MCARP, at´e agora s´o se conhecem limites inferiores propostos por Belenguer et al. (2006) e Gouveia et al. (2009).
Os problemas referidos acima tˆem por base situa¸c˜oes em que as actividades est˜ao associadas `as liga¸c˜oes de um grafo. Existem ainda outros casos em que as actividades s˜ao mais adequadamente descritas se representadas nos nodos de um grafo. Isto acontece quando as actividades em causa se desenvolvem de forma discreta numa regi˜ao. A distribui¸c˜ao de bens de consumo ´e um exemplo. Neste tipo de representa¸c˜oes, as liga¸c˜oes estabelecem as rela¸c˜oes de adjacˆencia entre os nodos, que representam os clientes. Quando se pretendem determinar as viagens de custo m´ınimo para ve´ıculos que servem clientes situados nos nodos, diz-se que se pretende resolver um problema de optimiza¸c˜ao de rotas com procura nos nodos (VRP – Vehicle Routing Problem) (Toth e Vigo, 2001).
Um problema mais geral de determina¸c˜ao de percursos ´optimos, com actividades de- senvolvidas quer nas liga¸c˜oes quer nos nodos, assume a designa¸c˜ao de GRP (General
Routing Problem), definido pela primeira vez por Orloff (1974).